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

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 )

将导致无限循环，因为它是"左递归"。我不确定如何更改它来消除这种无限递归。

Answer 1

有了括号，就不会留下递归了。左递归是指生产可以（直接或间接）到达自身，其间不消耗任何令牌。这样的语法确实会在递归下降语法分析器中导致无限递归，但这在您的语法分析器中是不可能的。

您确实存在语法不明确的问题：在括号之后，直到解析完整个左侧表达式，才知道是+还是*形式。

解决这个问题的一种方法是在共享前缀/后缀生产中提取公共部分：

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刚刚发布了一个很好的答案，涵盖了我的最后一点。