Removing left recursion from context-free grammars
Robert C. Moore · 2000
context-free grammars (CFGs) in a "topdown " left-to-right fashion is that left recursion can lead to nontermination. An algorithm is known that transforms any CFG into an equivalent nonleft -recursive CFG, but the resulting grammars are often too large for practical use. We present a new method for removing left recursion from CFGs that is both theoretically superior to the standard algorithm, and produces very compact non-left-recursive CFGs in practice.