Left recursion

Left recursion is a property of context-free grammars in which a non-terminal symbol can derive a sentential form that begins with the same non-terminal — formally, \(A \Rightarrow^+ A\alpha\). Left recursion poses a fundamental challenge for recursive descent parsers and other top-down parsing strategies, because a naive parser would enter infinite recursion attempting to expand a symbol that immediately reintroduces itself. The standard resolution, left recursion elimination, transforms left-recursive productions into right-recursive equivalents through algebraic manipulation of the grammar. Yet left recursion is not merely a parsing inconvenience. In programming language design, left-recursive grammars often reflect the natural associativity of operations: arithmetic expressions like \(E \to E + T | T\) are left-recursive because addition associates to the left. The necessity of eliminating left recursion for some parsers while preserving it for semantic correctness reveals a tension between the formal structure of a language and the computational model used to recognize it — a tension that appears whenever abstract specification meets concrete implementation.