Блог

Я мог бы записать группу в скобках, используя что-то вроде:

 expr ::=    "(" <something> ")"
 

Однако иногда полезно использовать несколько уровней вложенности, и поэтому (теоретически) возможно иметь более одного parens, если они совпадают. Например:

 >>> (1) 1
2
>>> (((((-1))))) 2
1
>>> ((2 2) (1 1))
6
>>> (2 2))
SyntaxError: invalid syntax
 

Есть ли способ указать «соответствие» в EBNF или как сопоставление в скобках обрабатывается большинством анализаторов?

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

Для хорошо подобранных круглых скобок правильное производство просто:

 expr ::= "(" expr ")"
 

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

 expr ::= "(" expr ")"
expr ::= NUMBER
expr ::= expr " " expr
expr ::= expr "-" expr
expr ::= expr "*" expr
expr ::= expr "/" expr
 

Или для однозначной грамматики:

 expr        ::= expr " " multExpr
expr        ::= expr "-" multExpr
multExpr    ::= multExpr "*" primaryExpr
multExpr    ::= multExpr "/" primaryExpr
primaryExpr ::= "(" expr ")"
primaryExpr ::= NUMBER
 

Кроме того, как вы обычно «проверяете» правильность — есть ли онлайн-инструмент или что-то, что может проверить синтаксис?

Существует множество генераторов синтаксических анализаторов, которые могут принимать некоторую форму BNF- или EBNF-подобной нотации и генерировать из нее синтаксический анализатор. Вы можете использовать один из них, а затем проверить, анализирует ли сгенерированный анализатор то, что вы хотите. Однако они обычно недоступны в качестве онлайн-инструментов. Также обратите внимание, что генераторам синтаксических анализаторов обычно требуется, чтобы грамматика была однозначной или чтобы вы добавляли объявления приоритета, чтобы устранить неоднозначность.

также не будет бесконечного цикла?

Нет. Конечно, точная механика зависит от используемого алгоритма синтаксического анализа, но если символ в текущей позиции ввода не является открывающей круглой скобкой, то, очевидно, это неправильное производство для использования, и необходимо применить другое (или возникает синтаксическая ошибка, если ни одно из производств не применяется).

Левая рекурсия может вызвать бесконечную рекурсию при использовании алгоритмов синтаксического анализа сверху вниз (хотя в случае генераторов синтаксических анализаторов более вероятно, что грамматика будет либо отклонена, либо в некоторых случаях автоматически переписана, чем вы получите фактическую бесконечную рекурсию или цикл), но не-левая рекурсия не вызывает такого родапроблема с любым алгоритмом.