antlr - 为什么 Antlr 中没有左递归删除语法的选项？

Question

有几次我在 Antlr 中编写语法时遇到了左递归，这就是为什么我问自己为什么没有自动工具可以删除它。在我做了一些研究之后，我发现了两种处理这个问题的方法 - Paull 算法和 Robert C. Moore 的工作中讨论的左角变换Removing Left Recursion from Context-Free Grammars, 2000。我注意到 Paull 的算法是一种非常不切实际的算法，但另一方面，左角变换只会增加语法规则的数量，O(n)但O(n^2)大多数时候比这要低得多，这使得该算法非常有效。所以我的问题是：左递归删除是不是故意将责任留给语法实现者，还是不被视为一种选择？

Answer 1

Two parts to this answer.

1. ANTLR 4 does remove direct left recursion.
2. In general, left-recursion elimination is more complicated for real grammars. ANTLR produces recursive-descent parsers which look very similar to the grammar they are generated from. Left-recursion elimination must consider predicates, embedded actions, arguments, local variables, and (for ANTLR 3) AST operations. The tool wasn't created because it was bound to be somewhere between incomplete (restrictions on the supported constructs), inaccurate (does not produce a parser that behaves properly), and unrealistically complicated.