BNF 中的父项,EBNF

Parens in BNF, EBNF

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

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

但是,有时使用多层嵌套很有用,因此(理论上)可以有多个括号,只要它们匹配。例如:

>>> (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

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 的作品适用,则提出。

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