我如何能实现这一个消除？
A := AB |
AC |
D |
E ;
Answer 1:
这就是所谓的立即左递归的例子，而像这样的删除：
A := DA' |
EA' ;
A' := ε |
BA' |
CA' ;
其基本思路是，首先需要注意的是解析当A你必然有一个开始D或E 。 后D或E你要么结束（尾ε）或继续（如果我们在AB或AC建设）。
实际的算法是这样的：
对于任何左递归生产这样的： A -> A a1 | ... | A ak | b1 | b2 | ... | bm A -> A a1 | ... | A ak | b1 | b2 | ... | bm A -> A a1 | ... | A ak | b1 | b2 | ... | bm与更换生产A -> b1 A' | b2 A' | ... | bm A' A -> b1 A' | b2 A' | ... | bm A' A -> b1 A' | b2 A' | ... | bm A'并添加生产A' -> ε | a1 A' | ... | ak A' A' -> ε | a1 A' | ... | ak A' A' -> ε | a1 A' | ... | ak A' 。
参见维基百科：左递归对消除算法（包括消除间接左递归的）的更多信息。
Answer 2:
可用的另一种形式是：
A := (D | E) (B | C)*
这样做的机制是差不多的，但是有些解析器会处理这种形式更好。 还考虑什么，将采取Munge时间与语法自身沿着行为规则; 其他形式要求保理工具生成的一种新型A'规则回到那里，因为这形式没有。
文章来源: How to implement a left recursion eliminator?
