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

，你通常如何“测试”它是正确的--是否有一个在线工具或什么东西可以验证一个语法？

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

也不会无限循环吗？

不是的。确切的机制当然取决于所使用的解析算法，但是如果当前输入位置上的字符不是一个括号，那么显然这不是应该使用的结果，需要应用另一个结果(如果不应用任何结果，则会引发语法错误)。

在使用自顶向下的解析算法时，左递归可以导致无限递归(尽管在解析器生成器的情况下，语法可能被拒绝，或者在某些情况下会自动重写，而不是得到一个实际的无限递归或循环)，但是非左递归不会对任何算法造成这样的问题。