0

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

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

其中 1 是“真”，0 是“假”，+ 是“或”，* 是“和”，~ 是“非”，“c”只是一些变量名（它可以是任何单个字母）。我计划使用括号而不是实现某种操作顺序。

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

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

但我不确定我将如何在此之上实现 + 和 *。从我所读到的明显实现中，我相当确定

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

会导致无限循环，因为它是“左递归”的。我不确定如何更改它以消除这种无限递归。

4

2 回答 2

1

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

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

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

Expression ::= 1
             | 0
             | Character
             | ParExpr

ParExpr ::= ( Expression ParOp  Expression )

ParOp ::= +
        | *
于 2016-04-13T19:39:11.747 回答
0

让我为您搜索... https://en.wikipedia.org/wiki/Recursive_descent_parser

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

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

登录 ::= + | *

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

一元运算 ::= ~

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

于 2016-04-13T19:43:58.497 回答