Paper: Removing Left Recursion From Context-Free Grammars

ACL ID A00-2033
Title Removing Left Recursion From Context-Free Grammars
Venue Annual Conference of the North American Chapter of the Association for Computational Linguistics
Session Main Conference
Year 2000

A long-standing issue regarding algorithms that ma- nipulate context-free grammars (CFGs) in a "top- down" left-to-right fashion is that left recursion can lead to nontermination. An algorithm is known that transforms any CFG into an equivalent non- left-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 algo- rithm, and produces very compact non-left-recursive CFGs in practice.