Grammarspec

Left Recursion

The rule that makes `-` group correctly is the same rule that makes a recursive-descent parser call itself forever. LR parsers prefer it, top-down parsers cannot survive it, and the standard fix trades a grammar rewrite for a loop that folds left by hand.

The question

Why does expr → expr "+" term hang a recursive-descent parser but not an LR parser, and how do I get rid of it?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

A production whose right-hand side begins with the nonterminal it defines. That single structural property is what a top-down parser must decide on *before* consuming any input, which is why it is fatal there and harmless in a bottom-up parser that decides after the input is on the stack. The grammar is the same either way; what differs is which algorithm can reconstruct a derivation from it.

What this phase may assume or do

Eliminating left recursion is legal only if the rewritten grammar generates exactly the same set of sentences. It is *not* required to preserve parse trees, and the standard transformation does not: the resulting rule is right-recursive or iterative, so the left-associative grouping the original encoded must be re-established when the AST is built. A transformation that changes the trees without re-establishing it changes what programs mean.

Key points

Left recursion means a nonterminal can derive a form beginning with itself, directly or through other rules.
A recursive-descent parser recurses without consuming input and dies with a stack overflow on the first expression.
An LR parser handles it natively and prefers it, because left recursion keeps the parser stack at constant depth on long lists.
The standard elimination A → A α | β ⇒ A → β A', A' → α A' | ε preserves the language and changes every parse tree.
The associativity the left recursion encoded must be re-established explicitly, normally by folding a loop's result into the left operand.
Indirect left recursion is eliminable by Paull's algorithm and usually not worth it — switch to a bottom-up or Pratt parser instead.
CPython's PEG parser and ANTLR 4 both support direct left recursion natively, so "PEGs cannot do left recursion" is out of date.

The rule that eats itself

Left recursion is the property that a nonterminal can derive a sentential form beginning with itself. Direct left recursion is the visible case — expression → expression "+" term. Indirect left recursion hides behind one or more other rules: A → B "x" together with B → A "y" is left-recursive even though neither production mentions itself.

A recursive-descent parser implements each nonterminal as a function that inspects the upcoming tokens and picks an alternative. For expression → expression "+" term, the first thing the chosen alternative does is call parseExpression — with the input pointer unmoved. That call inspects the same tokens, picks the same alternative, and calls itself again. Nothing consumes anything, and the process terminates only when the call stack does.

The symptom is characteristic and worth recognising: a stack overflow or a segmentation fault on the very first expression the parser sees, with no error message and no partial output. It is not a subtle bug and it is not a bug in the input; it is the grammar and the algorithm being incompatible.

The transliteration that does not terminate

1function parseExpression() {
2  // alternative 1: expression "+" term
3  const left = parseExpression()   // <- input pointer has not moved
4  expect(PLUS)
5  const right = parseTerm()
6  return Binary('+', left, right)
7}

The recursive call happens before any token is consumed, so the recursion has no base case in terms of input. Adding lookahead does not help: whatever token is next, the same alternative is still the one that can start with it.

Why LR does not care

implementationThe PEG row is the default behaviour, not a law. Warth, Douglass and Millstein published a memoisation technique in 2008 that supports left recursion in packrat parsers, and CPython's PEG parser — introduced in 3.9 by PEP 617 and used for the language since — implements direct left recursion on that basis. ANTLR 4 goes further and rewrites direct left recursion automatically before generating code. Neither handles all indirect left recursion.

A bottom-up parser never has to guess which production it is in. It shifts tokens onto a stack and reduces only when a complete right-hand side is sitting on top. For expression → expression "+" term it will have already reduced something to expression, shifted +, reduced something to term, and only then does it apply the rule. The nonterminal on the left of the right-hand side is not a prediction; it is a thing already built.

That is why the Bison manual actively *recommends* left recursion for lists. A right-recursive rule forces the parser to shift every element of the list before it can reduce anything, so the parser stack grows in proportion to the list length; a left-recursive rule reduces as it goes and keeps the stack at constant depth. On generated source files with tens of thousands of array initialisers, that is the difference between parsing and overflowing.

So the same grammar property is a hard error in one parser family and a performance recommendation in the other. This is the clearest example in the domain that "is this grammar good" is not a question you can answer without naming the algorithm — which is the bridge into [[ll-vs-lr]].

One grammar property, four parser families

Parser family	Left recursion	Right recursion	Why
Recursive descent / LL	Non-terminating	Fine	Must choose the production before consuming input
LR / LALRtypical	Preferred	Works, stack grows with list length	Chooses after the right-hand side is on the stack
PEG / packratimplementation	Non-terminating by default	Fine	Ordered choice is still a top-down prediction
Pratt / precedence climbing	Not applicable	Not applicable	Never predicts a nonterminal; loops on binding power instead

Eliminating it, and paying the bill

The textbook transformation for direct left recursion is mechanical. A rule of the form A → A α | β becomes A → β A' with A' → α A' | ε. The new nonterminal absorbs the repetition, and the recursion has moved to the right where a top-down parser can handle it: A' is only entered after α has been consumed.

The transformation preserves the language exactly. It does *not* preserve the parse tree, and this is the part that gets skipped. The original left-recursive rule encoded left associativity structurally; the rewritten rule is right-recursive and encodes nothing. A parser that builds nodes straight from the rewritten grammar will produce a - (b - c). The associativity has to be put back deliberately, and the standard way to do that is to skip the grammar rewrite entirely and write the loop.

The loop form is what essentially every hand-written parser actually contains, and it is worth recognising as the same transformation arrived at from the other end: parse one operand, then repeatedly consume an operator and another operand, folding the accumulated node into the left position each time. It is the EBNF star from [[bnf-and-ebnf]], implemented, with the fold direction written down.

Left recursion into iteration, with the associativity restored by hand

Before

expression ::= expression "-" term
            |  term

After

expression ::= term ("-" term)*

// and in the parser, folding left:
//   let node = parseTerm()
//   while (match("-")) node = Binary("-", node, parseTerm())
//   return node

Legal only when

The grammar rewrite is legal because both forms generate exactly term ("-" term)^n for every n ≥ 0 — the accepted language is unchanged. The *implementation* is legal only with the fold shown: assigning the accumulated node to the left operand inside the loop reproduces the left-leaning tree the original left-recursive rule produced.

Illegal when

Applying only the grammar half — rewriting to expression ::= term "-" expression | term and building nodes directly from it — is a language-preserving, meaning-changing transformation. 8 - 4 - 2 then parses as 8 - (4 - 2) and evaluates to 6 instead of 2. Every acceptance test still passes, because the set of accepted inputs did not change.

Indirect left recursion, and when to stop

Indirect left recursion — A → B x, B → C y, C → A z — is eliminated by Paull's algorithm: order the nonterminals, substitute earlier ones into the right-hand sides of later ones until all left recursion is direct, then apply the direct transformation. It works, and it produces a grammar that no longer resembles the one anybody wrote, with generated nonterminal names and rules that make diagnostics meaningless.

In practice that is the point at which most implementations stop transforming and change tools. If the grammar is genuinely mutually recursive on its left edge, either use a bottom-up parser that does not care, or use a Pratt parser for the expression part where the problem almost always lives. Expression grammars are where left recursion is unavoidable and also where Pratt parsing is strongest, so the two answers coincide.

The historical footnote is worth carrying: this is a large part of why hand-written recursive-descent parsers in production compilers are almost always recursive descent *for statements* and Pratt or precedence-climbing *for expressions*. Clang, rustc and several JavaScript engines are all built that way. The hybrid is not a compromise — it is each technique used where its weakness does not apply.

How it works

The steps, in the order the compiler takes them.

Detect direct left recursion by checking whether any production for A starts with A.
Detect indirect left recursion by computing, for each nonterminal, the set of nonterminals that can begin a derivation from it, and looking for a cycle.
For direct left recursion A → A α₁ | … | A αₙ | β₁ | … | βₘ, write A → β₁ A' | … | βₘ A' and A' → α₁ A' | … | αₙ A' | ε.
In an implementation, prefer the equivalent iterative form: parse one β, then loop consuming αs, folding the accumulated node into the left operand each time.
For indirect left recursion, order the nonterminals and substitute earlier definitions into later right-hand sides until every remaining left recursion is direct, then apply the direct rule.
Verify the language is unchanged with acceptance tests, and verify the trees are unchanged with an evaluation test on a non-commutative operator.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

The compiler segfaults or reports a stack overflow on the first source file it is given, before emitting any diagnostic — the parser recursed without consuming a token.
A grammar is rewritten to be right-recursive and every acceptance test passes, but 8 - 4 - 2 now evaluates to 6 and a / b / c is wrong everywhere in the codebase.
A right-recursive list rule fed to an LR parser overflows the parser stack on a machine-generated source file with fifty thousand initialisers, while every hand-written file in the test suite parses fine.
Paull's algorithm is applied to a whole grammar and the parser now reports errors naming generated nonterminals such as expr_tail_3, which no user can act on.
A PEG grammar copied from a specification with left-recursive rules silently fails to match the recursive alternative, so a legal construct is reported as a syntax error rather than looping — the ordered-choice failure mode.

When it helps

Reading a grammar and predicting which parsing technique it was written for: heavy left recursion means it was written for yacc or Bison.
Diagnosing a parser that dies immediately with no message — left recursion is the first hypothesis and takes seconds to confirm.
Deciding a parser architecture: knowing that expressions are where left recursion is unavoidable is the argument for the recursive-descent-plus-Pratt hybrid.

When it hurts

Eliminating left recursion in a grammar that will be fed to an LR generator is pure loss: it costs a rewrite, costs tree fidelity and makes the parser stack grow with list length.
Mechanically eliminating indirect left recursion produces a grammar whose nonterminal names are meaningless, which destroys the diagnostics that were the reason to hand-write the parser in the first place.

What it costs

Every one of these is paid by something.

Eliminating left recursion buys compatibility with top-down parsing and costs the structural encoding of associativity, which must then be restored in code and can no longer be checked from the grammar.
Keeping left recursion and using an LR generator buys grammar fidelity and constant parser-stack depth, and costs the diagnostics and error recovery that hand-written descent parsers are chosen for.
The recursive-descent-plus-Pratt hybrid buys both — readable statement parsing and left-recursion-free expressions — and costs a second parsing mechanism in the codebase that every contributor has to learn.

What else you could do

What a different compiler or language does instead, and when that is better.

Use an LR or LALR generator and leave the grammar alone. This is what Bison exists for, and its manual explicitly recommends left recursion; the price is generated tables and state-numbered errors — see [[lr-parsing]].
Use a Pratt or precedence-climbing parser for expressions, which never predicts a nonterminal and so has no left-recursion problem at all. The price is that precedence lives in a table rather than in the grammar — see [[pratt-parsing]].
Use a PEG tool that supports left recursion natively — CPython's parser generator, or ANTLR 4's automatic rewriting of direct left recursion. The price is a dependency on a specific tool's extension, since neither is part of the PEG formalism.
Use GLR, which forks at the undecidable points and prunes the branches that fail. It accepts everything context-free including left recursion, and pays in time and downstream machinery — see [[parser-generators]].

See it for yourself

The flag, dump or tool that shows you this directly.

bison -v grammar.y and read grammar.output: a left-recursive rule shows a state that reduces immediately, while a right-recursive one shows a state that shifts repeatedly — the stack-depth argument, visible.
ANTLR 4 rewrites direct left recursion automatically; antlr4 -Xlog MyGrammar.g4 shows the rewritten rules it generated, which is the textbook transformation performed for you.
CPython's grammar at Grammar/python.gram contains left-recursive rules directly — search for sum: and note that sum '+' term appears with the recursion on the left, which the PEG generator handles.
For a suspected left-recursion hang in your own parser, run it under a debugger and look at the stack: a repeating cycle of the same two or three frames with an unchanged input position is diagnostic.

Plausible wrong readings

Stated the way a confident engineer states them.

"Left recursion is a bug in the grammar." It is a bug only relative to a top-down algorithm. Bison's manual recommends it, and the trees it produces are the ones you want.
"Eliminating left recursion is a purely mechanical, safe rewrite." It is mechanical and it changes every parse tree. Safety requires restoring the fold direction in the AST construction.
"PEG parsers cannot handle left recursion." Not since 2008 in theory and not since Python 3.9 in practice. Plain packrat cannot; several real tools can.
"If the parser does not hang, there is no left recursion." A memoising or rewriting tool may have handled it silently. Whether it also preserved the associativity you wanted is a separate question worth checking.

Misconceptions

The claim, and what is actually true.

Adding more lookahead fixes left recursion.

It does not. However many tokens the parser peeks at, the left-recursive alternative can still begin with the same tokens, so the same alternative is chosen and no input is consumed.

Left and right recursion are interchangeable because they accept the same strings.

They build mirrored trees. For every non-commutative operator that is a semantic change no acceptance test can see.

Hand-written parsers avoid left recursion because it is hard.

They avoid it because top-down prediction cannot terminate on it. The loop they write instead *is* the elimination, applied by hand and with the fold direction chosen deliberately.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

A rule like expr → expr "+" term starts by mentioning itself. A top-down parser implements that as a function that calls itself before reading anything, so it never terminates. A bottom-up parser builds the left expr first and then applies the rule, so it has no problem at all. The usual fix is to write a loop instead of a recursion.

practical

If your parser dies instantly with a stack overflow, look for a rule that starts with its own name. Replace it with the loop form — parse one operand, then while (match(op)) node = Binary(op, node, parseOperand()) — and check the fold. The loop as written folds left, which is what - and / need. If the operator is right-associative, recurse on the right instead, and say so in a comment because the grammar no longer does.

advanced

The reason this is the bridge between the grammar module and the parsing module is that it is the first place where the grammar and the algorithm stop being separable. Everything earlier in this module was a property of the grammar alone; left recursion is a property of the pair. That pairing is what the LL and LR hierarchies formalise — LL(k) and LR(k) are classes of *grammars*, defined by whether a particular decision procedure works on them, not classes of languages. A language can have an LR(1) grammar and no LL(k) grammar for any k, and that asymmetry is exactly the left-recursion problem generalised. It is also why "is my grammar good" is unanswerable and "is my grammar LALR(1)" is answerable by a tool in milliseconds.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

specThat direct left recursion is non-terminating for a naive top-down parser, and that the A → βA' transformation preserves the generated language, are results about the algorithms and grammars themselves. They hold regardless of tooling. What varies is whether a given tool has added an extension that works around the limitation.

implementationCPython has used a PEG parser supporting direct left recursion since 3.9 (PEP 617); before that it used an LL(1) parser and its grammar was written to avoid left recursion entirely. ANTLR 4 rewrites direct left recursion automatically while ANTLR 3 did not. Neither supports arbitrary indirect left recursion, so a grammar that relies on one tool's extension is not portable to the other.

typicalThe recommendation to prefer left recursion in Bison grammars is in the Bison manual and is about parser-stack depth on long lists. It is a strong default rather than an absolute: for a rule where the natural semantic action builds a right-leaning structure, such as a right-associative operator, right recursion is the correct choice and the stack cost is accepted.

If you were asked this in an interview

Why does expr → expr "+" term hang a recursive-descent parser, and why does an LR parser not care?
Eliminate the left recursion from that rule, then tell me what you have to do to keep a - b - c meaning (a - b) - c.
Bison's manual recommends left recursion for lists. What is the argument, and when would you ignore it?

Connections

DSArecursion stack

Databasesql-parser-internals

Domains that do not exist yet

Programming Languages & Runtime Internals — Why an unbounded recursion becomes a stack overflow rather than an allocation failure
The observable symptom of left recursion is a blown call stack, and what that actually costs — guard pages, the default thread stack size, whether the runtime can catch it — is the runtime's half of the story rather than the compiler's.