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?
Two parts to this answer.