删除左递归

Question

下面的语法有左递归，

E= E+T|T
T= T*F|F
F= a|b|c

如何去掉呢？有没有一般程序？

Answer 1

是的，有一个一般过程，请参见wikipedia。

E = TE'
E'= (e) | +TE'
T = FT'
T'= (e) | *FT'
F = a | b | c

// (e) is "epsilon" which is defined as the empty string

应该提到的是，这会从左到右改变 + 和 * 的关联性。也就是说，之前 a + b + c 被解析为 (a + b) + c，现在被解析为 a + (b + c)。

这不是加法和乘法的问题，但是例如减法和除法的问题。

维基百科文章有更多关于左递归删除过程及其复杂性的详细信息。

Answer 2

例如，一般过程可以在 Wikipedia 中找到。我将演示 E = E+T|T：

E 是左递归非终结符。
+T 是非空序列 (alpha)。
T 是不以 E 开头的序列（测试版）。

我们为“其余”创建一个新的非终结符，即。非空序列。这处理递归。

E' = epsilon|+TE'

我们修改原始规则以使用新的非终结符来处理递归。

E = TE'

Answer 3

正如其他人指出的那样，有一个用右递归替换左递归的通用过程。其他答案很好地展示了如何使用通用过程来删除给定语法中的左递归。

这是一个以特定于该语法的方式重构给定语法的解决方案。

E= T+E|T
T= F*T|F
F= a|b|c

Answer 4

产生式

E = E+T
  | T
T = T*F
  | F
F = a|b|c

转到

E= T ('+' T)*
T= F ('*' F)*
F= a|b|c

​​“保持与使用 A(E,T) 处理第一个 E 析取项相同的处理”。新版本使用：

ret = T1;
while(set.more()) ret = A(ret, set.pop_front().T);