删除左递归

Question

以下语法已经离开了递归

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

如何删除它？它有什么一般程序吗？

Answer 1

是的,有一般程序,例如维基百科.

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

应该提到这改变的关联性+,并*从左至右.也就是说,在a + b + c解析之前(a + b) + c,它现在被解析为a + (b + c).

这对于加法和乘法来说不是问题,但例如,对于减法和除法来说这将是一个问题.

维基百科文章详细介绍了左递归删除过程及其复杂性.