Why there isn't a option for left-recursion removal of a grammar in Antlr?

Question

Several times I've encountered left recursion while I'm in the process of writing a grammar in Antlr that's why I asked myself why there isn't a automatic tool which removes it. After I did some research I found two methods which deal with this problem - the Paull's algorithm and the left-corner transform discussed in Robert C. Moore's work Removing Left Recursion from Context-Free Grammars, 2000. I noticed that Paull's algorithm is a highly impractical one but left-corner transform on the other hand only increases the number of grammar rule from O(n) to O(n^2) but most of the time is much lower than this which makes that algorithm very efficient. So my question is: Is left-recursion removal not implemented on purpose leaving the responsibility to the grammar implementer or it's just not considered as an option?

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.