Порядок действий в расширенной форме Бэкуса – Наура

Я создаю формальную спецификацию для очень простого языка правил, очень простого. Я хочу использовать EBNF, так как это стандарт, но я не могу понять, как указать порядок операций. Вот спецификация на данный момент.

rule = statement, { (‘AND’|’OR’), statement};

variable = ‘$’,alphabetic character, {alphabetic character | digit};

statement = variable, [ ‘count’,[white space ],’>’,[white space],number ];

alphabetic character = "A" | "B" | "C" | "D" | "E" | "F" | "G"
                     | "H" | "I" | "J" | "K" | "L" | "M" | "N"
                     | "O" | "P" | "Q" | "R" | "S" | "T" | "U"
                     | "V" | "W" | "X" | "Y" | "Z" ;

number = [ "-" ] , digit , { digit } ;

digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;

white space = ? white space characters ? ;

Вопрос, который у меня есть, заключается в том, как показать, что вещи в скобках должны оцениваться в первую очередь. Итак, что-то вроде этого

$strap AND ($greenSticker count > 5 OR ($greenSticker AND $redSticker))

Это похоже на общую функцию для большинства языков, но мои навыки работы с Google подводят меня, и я не могу найти пример.


language-design rules ebnf grammar operator-precedence
person Dan Walmsley    schedule 29.03.2012    source источник

Ответы (1)


arrow_upward
12
arrow_downward

Учитывая это как упрощенный пример грамматики LL:

expression -> (+|-|ε) term ((+|-) term)*
term -> factor ((*|/) factor)*
factor -> var | number | (expression)

Как видите, операторы с более низким приоритетом (+ и -) подчиняются более общему правилу, чем операторы с более высоким приоритетом (* и /). Все дело в создании правильного дерева синтаксического анализа. Но, как правило, «внешние» или более общие правила имеют меньший приоритет, поэтому операторы сложения и вычитания помещаются рядом с term, потому что term должен быть получен в дальнейшем. Если вы посмотрите на более сложные грамматики, вы увидите, что это доведено до крайности, чтобы иметь надлежащий приоритет.

person Austin Henley    schedule 29.03.2012
comment
Выражая приоритет в правилах грамматики, я не понимаю, почему вы проводите различие между синтаксическим анализом сверху вниз и снизу вверх. Как вы сказали, все дело в создании правильного дерева синтаксического анализа, и вы просто строите его сверху вниз или снизу вверх, чтобы в конечном итоге получить тот же результат. Конечно, это имеет несколько последствий, но мне не очевидно, как вы связываете технику синтаксического анализа с (такого рода) приоритетом. Пожалуйста, объясни. - person Gunther; 30.03.2012
comment
Эта грамматика выражений будет работать и в восходящем синтаксическом анализаторе, и в нисходящем LL-парсере, а не только в парсерах с рекурсивным спуском. Парсер Пратта также является рекурсивным спуском и нисходящим сверху вниз. Ваш второй абзац действительно не имеет для меня никакого смысла. - person user207421; 05.04.2012
comment
Чтобы решить обе ваши проблемы, я только что удалил запутанный абзац. Я надеюсь, что остальная часть моего ответа полезна! - person Austin Henley; 05.04.2012
comment
это имеет смысл, но я все еще немного смущен. когда синтаксический анализатор смотрит на 3 + 4 * 5, откуда он знает, что не нужно сначала оценивать 3 + 4 как выражение, затем оценивать expression как фактор, а затем оценивать factor * 5 как термин последним? Это как-то связано с порядком ваших утверждений? - person chharvey; 17.04.2019
comment
@chharvey Да, это связано с порядком. Правила, расположенные дальше по грамматике (т. е. ближе к терминалам, например number), имеют более высокий приоритет. Таким образом, * и / имеют более высокий приоритет, чем + и -. Возьмите свой пример и попробуйте вручную разобрать его, используя мою грамматику. - person Austin Henley; 17.04.2019
comment
@AustinHenley Я сделал: он все еще работает, хотя и не должен: 3 -> number -> factor -> term[1] ; 4 -> number -> factor -> term[2] ; term[1] + term[2] -> expression -> factor[3] ; 5 -> number -> factor[4] ; factor[3] * factor[4] -> term ; Я что-то упустил? - person chharvey; 17.04.2019