BNF 中的父项，EBNF

Question

我可以使用类似以下的方法捕获括号内的组：

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

但是，有时使用多层嵌套很有用，因此（理论上）可以有多个括号，只要它们匹配。例如：

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

有没有办法在 EBNF 中指定“匹配性”，或者大多数解析器如何处理括号匹配？

Answer 1

为了能够匹配任意数量的任何东西（无论是括号、运算符、列表项等），您需要递归（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

Also, how do you usually go about 'testing' that it is correct -- is there an online tool or something that can validate a syntax?

有许多解析器生成器可以接受某种形式的 BNF 或类似 EBNF 的表示法并从中生成解析器。您可以使用其中之一，然后测试生成的解析器是否解析了您想要的内容。不过，它们通常不能作为在线工具使用。另请注意，解析器生成器通常需要语法明确，或者您添加优先级声明来消除歧义。

also wouldn't infinite loop?

没有。确切的机制当然取决于使用的解析算法，但如果当前输入位置的字符不是左括号，那么显然这不是正确的产生式，需要应用另一个（或语法错误）如果 none 的作品适用，则提出。

当使用自上而下的解析算法时，左递归会导致无限递归（尽管在解析器生成器的情况下，语法更有可能被拒绝，或者在某些情况下自动重写，而不是你得到一个实际的无限递归或循环），但非左递归不会导致任何算法出现此类问题。

BNF 中的父项，EBNF

Parens in BNF, EBNF

parsing

grammar

lex

bnf

ebnf