当我在Antlr中编写语法时，我多次遇到左递归，这就是为什么我问自己为什么没有一个自动工具来删除它。在我做了一些研究后，我发现了两种处理这个问题的方法-Paull算法和Robert C.Moore的作品Removing Left Recursion from Context-Free Grammars, 2000中讨论的左角变换。我注意到Paull的算法是一个非常不切实际的算法，但左角变换只会将语法规则的数量从O(n)增加到O(n^2)，但大多数时间都比这低得多，这使得该算法非常有效。所以我的问题是：左递归移除不是故意实现的，而是将责任留给语法实现者，或者它只是不被视为一种选择？
这个答案的两部分。
- ANTLR 4删除了直接左递归
- 一般来说，左递归消去对于真正的语法来说更为复杂。ANTLR生成递归下降语法分析器，它们看起来与生成语法的语法非常相似。左递归消除必须考虑谓词、嵌入操作、自变量、局部变量和（对于ANTLR3）AST操作。没有创建该工具，因为它必然介于不完整（对支持的结构的限制）、不准确（不能生成行为正常的解析器）和不切实际的复杂之间