Left recursion

Left recursion occurs when a nonterminal A has a production A → Aα (immediate left recursion) or when A derives a string starting with A through a sequence of productions (indirect left recursion).¹ Immediate left recursion is straightforward: the leftmost symbol in the right-hand side is the same nonterminal. Indirect left recursion requires a chain, e.g., A → Bβ, B → Aγ. Both forms are problematic for top-down parsing algorithms that attempt to match the leftmost symbol first.²

Top-down parsers, including recursive descent and LL parsers, expand nonterminals starting from the leftmost symbol of the current sentential form. With left recursion, the parser would repeatedly expand the same nonterminal without consuming any input, leading to infinite recursion or stack overflow.¹ Practical parser generators often require left recursion to be eliminated before grammar submission. However, some techniques, such as left-corner parsing or using a lookahead, can handle certain forms of left recursion without modification.³

Left recursion can be algorithmically removed by rewriting the grammar. For immediate left recursion, the standard method introduces a new nonterminal and transforms the productions into right-recursive form.¹ For example, A → Aα | β becomes A → βA′, A′ → αA′ | ε. Indirect left recursion requires first ordering the nonterminals and then eliminating recursion in a cycle. The resulting grammar is equivalent in language but no longer left-recursive, making it suitable for top-down parsing.⁴ This transformation may increase grammar size and introduce left factoring needs.

While left recursion is typically avoided in top-down parsing, it is natural in left-associative operator expressions (e.g., E → E + T). Some parser generators, like ANTLR4, can handle left recursion directly using adaptive parsing techniques.⁵ In parsing expression grammars (PEGs), left recursion is generally disallowed because the ordered-choice semantics cause infinite loops, though recent research has proposed limited support.⁶ Another niche: natural language grammars, such as for English, often contain left recursion in noun phrases, requiring special handling in computational linguistics.

Nonterminal

A symbol in a formal grammar that can be replaced by a sequence of terminals and nonterminals.

Production

A rule of the form A → γ, where A is a nonterminal and γ is a string of grammar symbols.

Top-down parsing

A parsing strategy that constructs a parse tree starting from the start symbol and expanding nonterminals leftmost first.

Leftmost derivation

A derivation in which the leftmost nonterminal is always replaced first.