View source for 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 parser]]s''' 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 grammar|formal structure]]''' of a language and the '''[[computational model]]''' used to recognize it — a tension that appears whenever abstract specification meets concrete implementation.

[[Category:Computer Science]]
[[Category:Mathematics]]
[[Category:Language]]