Left Recursion

Left recursion is a grammar production in which a non-terminal symbol appears as the leftmost symbol on the right-hand side of its own production rule: A → A α. It is the bane of recursive descent parsing because a naive implementation calls itself forever, consuming no input and growing the call stack without bound. The standard elimination technique — converting A → A α | β to A → β A' ; A' → α A' | ε — preserves the language but distorts the parse tree, requiring post-processing to recover the original left-associative structure.

Left recursion is not merely a parsing inconvenience. It is a structural property that signals left-associativity in the underlying language: expressions like a - b - c are naturally left-recursive because they group as (a - b) - c. The fact that recursive descent cannot handle left recursion directly is not a flaw in the grammar but a mismatch between the grammar's natural structure and the parser's execution model. This mismatch reveals a deeper tension in language design: the syntax that is easiest for humans to specify is not always the syntax that is easiest for machines to parse.