通过递归下降解析布尔表达式中的 + 和 *

Question

我正在为布尔表达式编写递归下降解析器，例如：

(1 * 0) 
(0 + ~1)
(0 * (1 + c)

其中1是'True'，0是'False'，+是'or'，*是'and'，~是'not'和'c' 只是一些变量名（它可以是任何单个字母）。我计划使用括号而不是实现某种操作顺序。

我当前的解析器可以识别以下形式的表达式

Expression ::= 1
             | 0 
             | Character
             | ~ Expression

但我不确定如何在此基础上实现 + 和 *。从我所读到的

的明显实现中，我相当确定

Expression ::= 1
             | 0
             | Character
             | ( Expression + Expression )
             | ( Expression * Expression )

会导致无限循环，因为它是 'left-recursive'。我不确定如何更改它以消除这种无限递归。

Answer 1

有了括号，你所拥有的就不是递归的了。左递归是指产生式可以（直接或间接）到达自身而中间不消耗任何令牌。这样的语法确实会在递归下降解析器中导致无限递归，但你的语法不会发生这种情况。

您确实遇到了语法不明确的问题：在括号后，直到整个左边才知道是 + 还是 * 形式被解析-hand 表达式已被解析。

解决该问题的一种方法是提取共享 prefix/suffix 作品中的公共部分：

Expression ::= 1
             | 0
             | Character
             | ParExpr

ParExpr ::= ( Expression ParOp  Expression )

ParOp ::= +
        | *

Answer 2

我帮你搜一下... https://en.wikipedia.org/wiki/Recursive_descent_parser

领先的 LPAREN 防止它被左递归。如果您想概括表达式并具有一些运算符优先级，请遵循维基百科文章中 BNF 的表达式部分。

但是，您所选择的语法存在语法歧义。当你有相同优先级的运算符时，将它们组合成一个非终结符，例如

LogOp ::= + | *

标记相似的操作数以允许扩展：

UnaryOp ::= ~

现在你可以......没关系，@500 刚刚发布了一个很好的答案，涵盖了我的最后一点。

通过递归下降解析布尔表达式中的 + 和 *

Parsing + and * in boolean expressions by recursive descent

parsing

recursion

recursive-descent

left-recursion