Parsingimplementation

Recursive Descent

One function per grammar rule, the call stack as the parse stack. It is the technique most production compilers actually use — and the one that loops forever if you hand it a left-recursive grammar.

The question

How do I write a parser by hand, and why does my expression rule recurse forever?

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

What the program is here

The grammar itself, transliterated into code: one function per nonterminal, a call where the production names a nonterminal, a token match where it names a terminal. The parser's state is a position in the token array plus the runtime call stack, and that stack *is* the partially-built derivation — the chain of active frames at any moment is the path from the start symbol down to the token being consumed. Its output is the AST, built on the way back up.

What this phase may assume or do

A grammar can be parsed this way only if the parser can choose the correct alternative for a nonterminal by looking at a bounded number of upcoming tokens, and only if no production can reach itself as its own leftmost symbol without consuming input. The first condition is what makes the grammar LL(k) — see [[ll-parsing]]. The second is the real trap: violate it and the parser does not produce a wrong tree, it never produces anything, because it recurses on the same token forever.

Key points

One function per nonterminal; a nonterminal on the right-hand side becomes a call, a terminal becomes a token match.
The runtime call stack is the parse stack, and the chain of active frames is the derivation path currently being explored.
A left-recursive production transliterates into a function that calls itself having consumed nothing, so it recurses until the stack is exhausted — on valid input.
The standard fix rewrites recursion to iteration; the loop must fold into the *left* operand or associativity silently inverts.
Costs: one stack frame per precedence level, no tool checking the code against the grammar, and a hand-written message for every failure.
Buys: real code, real stack traces, arbitrary diagnostics, per-construct recovery, and ad-hoc context sensitivity — which is why production compilers choose it.

The grammar becomes the code

Recursive descent is the least clever parsing technique and the most widely deployed. There is no table, no automaton and no generator. You write down the grammar, then you write one function per rule, and the transliteration is nearly mechanical: a nonterminal on the right-hand side becomes a call, a terminal becomes a "consume this token or report an error", an alternation becomes a branch on the lookahead, and a repetition becomes a loop.

The grammar has to be written in a form that suits it. Notice that the productions below use EBNF repetition — term (( '+' | '-' ) term)* — rather than the left-recursive expr -> expr '+' term from [[what-parsing-does]]. The two describe exactly the same language. Only one of them can be transliterated directly, and the section after next explains why.

The grammar in a form recursive descent can consume directly

expression	::=	term (('+' \| '-') term)*	Repetition, not left recursion. The loop is what will produce left associativity.
term	::=	factor (('' \| '/') factor)	One level deeper, so it binds tighter.
factor	::=	NUMBER \| '-' factor \| '(' expression ')'	Unary minus recurses on itself to the right, which is fine — it consumes the `-` first.

Three functions, and the recursion that matters

Here is the whole parser. Read parseExpression first: it parses one term, then loops for as long as the next token is + or -, folding each new operand into the left-hand side. That loop is the entire mechanism of left associativity — after 1 - 2 - 3 the accumulated left is (1 - 2) before 3 is ever read.

Then read parseFactor. Its ( case calls parseExpression again, and that call is the descent that gives the technique its name. Parenthesised subexpressions restart the precedence ladder from the top, which is exactly what parentheses mean, and it costs one line.

A complete recursive-descent expression parser

1interface Token { kind: string; text: string; span: Span }
2 
3class Parser {
4  private i = 0
5  constructor(private readonly tokens: Token[]) {}
6 
7  private peek(): Token { return this.tokens[this.i] }
8  private atEnd(): boolean { return this.peek().kind === 'EOF' }
9 
10  /** Consume and return the next token if it is one of `kinds`; otherwise null. */
11  private match(...kinds: string[]): Token | null {
12    if (kinds.includes(this.peek().kind)) return this.tokens[this.i++]
13    return null
14  }
15 
16  /** Consume the next token, or raise a diagnostic naming what was expected. */
17  private expect(kind: string, why: string): Token {
18    const tok = this.match(kind)
19    if (tok) return tok
20    throw new ParseError(
21      `Expected ${kind} ${why}. Found '${this.peek().text}' instead.`,
22      this.peek().span,
23    )
24  }
25 
26  // expression -> term (('+' | '-') term)*
27  parseExpression(): Ast {
28    let left = this.parseTerm()
29    for (;;) {
30      const op = this.match('PLUS', 'MINUS')
31      if (!op) return left
32      const right = this.parseTerm()
33      left = { kind: 'Binary', op: op.text, opSpan: op.span, left, right,
34               span: join(left.span, right.span) }
35    }
36  }
37 
38  // term -> factor (('*' | '/') factor)*
39  parseTerm(): Ast {
40    let left = this.parseFactor()
41    for (;;) {
42      const op = this.match('STAR', 'SLASH')
43      if (!op) return left
44      const right = this.parseFactor()
45      left = { kind: 'Binary', op: op.text, opSpan: op.span, left, right,
46               span: join(left.span, right.span) }
47    }
48  }
49 
50  // factor -> NUMBER | '-' factor | '(' expression ')'
51  parseFactor(): Ast {
52    const num = this.match('NUMBER')
53    if (num) return { kind: 'Number', value: Number(num.text), span: num.span }
54 
55    const neg = this.match('MINUS')
56    if (neg) {
57      const operand = this.parseFactor()   // right recursion: the '-' is already consumed
58      return { kind: 'Unary', op: '-', operand, span: join(neg.span, operand.span) }
59    }
60 
61    const open = this.expect('LPAREN', 'to start a grouped expression')
62    const inner = this.parseExpression()   // ← the descent
63    const close = this.expect('RPAREN', 'after the grouped expression')
64    return { ...inner, span: join(open.span, close.span) }
65  }
66}

Two details do disproportionate work. expect takes a why string, so the diagnostic reads "Expected RPAREN after the grouped expression" instead of "syntax error" — the message quality of a hand-written parser comes from having somewhere to put that string, and a generated parser has nowhere. And parseFactor returns the inner node with a widened span for the parenthesised case, so (1 + 2) reports positions including the parentheses without keeping a parenthesis node.

Why left recursion loops forever here

Now transliterate the *other* grammar — the left-recursive expr -> expr '+' term | term — with the same mechanical rule. A nonterminal on the right becomes a call, so the first thing parseExpression does is call parseExpression.

No token has been consumed at that point. The parser is in exactly the state it was in one frame ago: same token index, same function, same alternative selected. So it does it again, and again, until the runtime call stack is exhausted. The observable symptom is a stack overflow on the first expression in the file, or a hang, and — importantly — the failure has nothing to do with the input being wrong. It happens on 1.

This is not a defect of recursive descent so much as the defining constraint of top-down parsing: a top-down parser must commit to a production before it has seen what the production produces, so a production that begins with itself gives it nothing to commit on. Bottom-up parsers do not have this problem at all, which is one of the genuine advantages of [[lr-parsing]] — LR grammars *prefer* left recursion, because it keeps the parse stack shallow.

The fix is standard and mechanical: rewrite the rule to iteration, which is what the working parser above does, or apply the general left-recursion elimination transform that introduces a tail nonterminal. Both are covered in [[left-recursion]]. What is worth noticing is that the iterative version is not a workaround grudgingly accepted — it produces *better* code than the recursive form would, because a loop over operands is O(1) in stack depth where the recursion would have been O(n).

Left recursion eliminated — the rewrite every hand-written parser applies

Before

expr -> expr '+' term
     |  expr '-' term
     |  term

After

expr -> term (('+' | '-') term)*

// in code:
//   let left = parseTerm()
//   while (match('+','-')) left = Binary(op, left, parseTerm())

Legal only when

The rewrite preserves the language and the tree shape only if the loop folds operands into the *left* operand of the new node, as the code above does. Under that condition a - b - c still builds as (a - b) - c, which is what the left-recursive grammar specified, and the two grammars accept exactly the same strings.

Illegal when

If the loop instead builds Binary(op, parseTerm(), left) or recurses on the right — expr -> term ('-' expr)? — the grammar still accepts the same strings but produces right-associated trees, so 8 - 3 - 2 evaluates to 7 instead of 3. No error is reported at any stage. This is the single most common bug in a first hand-written parser, and it is invisible to any test that only uses + and *.

What it costs, and why compilers pay it anyway

implementationRecursion-depth limits are real and specific: Clang has -fbracket-depth (default 256 for nested parentheses/brackets/braces) and CPython enforces a compiler-level nesting limit that raises MemoryError or a syntax error on sufficiently nested literals. The specific limits differ by compiler and version and some are configurable; what generalises is that every production recursive-descent parser has one, because without it a hostile input is a crash rather than an error message.

The technique has real limits. Each precedence level is a function and a stack frame, so C's fifteen levels mean roughly fifteen calls to reach a bare identifier; a deeply nested expression in a generated source file can genuinely overflow the stack, and production frontends carry explicit recursion-depth limits to turn that crash into a diagnostic. Adding a precedence level means editing several functions. And there is no tool checking that the code still matches the grammar in the specification — the two drift, silently.

Against that: the parser is ordinary code. It can be stepped in a debugger, the stack trace names the construct being parsed, error messages can say anything you can write in a string, recovery can be tailored per construct, and any context sensitivity the language demands is a normal if. Those are exactly the properties an IDE-grade frontend needs, which is why the list of compilers that hand-write it is the list of compilers you have heard of — see [[ll-vs-lr]].

One further note on scale: the version above is a toy in that it handles three precedence levels with three near-identical functions. Real hand-written parsers usually keep recursive descent for statements and declarations, where the constructs are genuinely different from one another, and switch to [[pratt-parsing]] for expressions, where they are not. That hybrid is the actual state of the art, and it is what Clang, rustc and Go all do.

Recursive descent, honestlytypical

Property	What you get	What it costs
Implementation	Ordinary functions; no build step, no generated code	You maintain the correspondence to the grammar by hand, and it drifts
Diagnostics	Any message you can write, at the exact point of failure	Every one has to be written; there is no default that is any good
Debugging	A stack trace that names the construct being parsed	Deep grammars make deep stacks and noisy traces
Grammar power	LL(k) with unbounded ad-hoc lookahead where you need it	Left recursion is fatal; ambiguity has to be resolved by hand
Stack usage	Proportional to nesting depth, which is usually small	Adversarial or generated input overflows it unless you cap depth
Adding a precedence level	Mechanical	Touches several functions; Pratt parsing reduces this to a table entry

How it works

The steps, in the order the compiler takes them.

Write the grammar in a form with no left recursion, using repetition where the original used left recursion.
Create one function per nonterminal, returning the AST node for that construct.
Choose among a rule's alternatives by branching on the lookahead token — the FIRST set of each alternative decides which branch is taken.
For a terminal in the production, consume the token if it matches and raise a diagnostic naming the expected kind if it does not.
For a repetition, loop while the lookahead is in the repeated part's FIRST set, folding each iteration into the accumulated left operand.
Build the node on the way back up, computing its span as the union of the spans of everything consumed.
On a mismatch, report and then synchronize to a token that an enclosing construct can resume from rather than unwinding to the top — see [[parser-synchronization]].

How it breaks

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

The parser hangs or dies with a stack overflow on the very first expression in the file, including on input as simple as 1, because a rule was left-recursive.
8 - 3 - 2 compiles fine and evaluates to 7. There is no diagnostic anywhere, and the bug survives until someone writes a test with a non-associative operator.
A deeply nested generated file — a machine-produced array literal, say — crashes the compiler with a segfault rather than an error, because no recursion-depth cap was installed.
The parser reports "unexpected token" pointing at the token *after* the real problem, because the failing expect used the current lookahead's span rather than the span where the construct began.
The grammar in the language specification and the parser in the repository disagree, and a program that the spec accepts is rejected by the implementation with no obvious owner for the bug.
One construct's parse function consumes tokens on a failed alternative before backtracking, and the parser silently skips input, producing a tree that is missing a statement nobody notices.

When it helps

Any language whose grammar you control, or which was designed to be LL — which is most languages designed after 1990, precisely so that this technique works.
Frontends that must serve an IDE: error tolerance, incremental reparse and per-construct recovery are all much easier when the parser is code rather than a table.
Small parsers of any kind — config formats, query languages, template syntaxes — where a generator's build step and dependency would cost more than the parser.

When it hurts

A grammar you do not control that is genuinely not LL, such as one written for an LR generator with heavy left recursion and ambiguity resolved by precedence declarations. Transforming it by hand is error-prone and the transform is not always obvious.
A grammar that changes frequently and is itself the specification — a standards document under active revision, or a SQL dialect tracking a vendor. Regenerating from a declarative grammar is cheaper than re-deriving the hand-written code every revision.

What it costs

Every one of these is paid by something.

Hand-writing buys arbitrary diagnostics, per-construct error recovery and ordinary debuggability, and pays with a parser that no tool can check against the language grammar — the two drift, and nothing tells you.
The call stack as parse stack buys clarity and costs stack depth proportional to nesting, which turns adversarial input into a crash unless an explicit depth limit is added and tested.
One function per precedence level buys a readable, direct correspondence to the grammar, and pays a call per level on every leaf expression plus a multi-function edit every time the precedence table changes.
Rewriting left recursion as iteration buys termination and shallow stacks, and costs a grammar that no longer matches the specification's text — so a reviewer comparing the two has to know the transform to see that they agree.

What else you could do

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

[[pratt-parsing]] replaces the tower of precedence functions with one loop and a binding-power table. For expressions it is strictly better, and the standard modern design uses recursive descent for statements and Pratt for expressions.
A table-driven LL(1) parser encodes the same decisions as an explicit stack and a table, removing the call-stack depth limit at the cost of every diagnostic becoming table-derived — see [[ll-parsing]].
[[lr-parsing]] handles left recursion natively and a strictly larger class of grammars, which is exactly why generators target it — see [[ll-vs-lr]].
Parser combinators build the same top-down parser out of composable higher-order functions. Very fast to write and to change, and they inherit every left-recursion problem plus, in most libraries, unpredictable error messages and backtracking costs.
PEG with packrat memoisation gives unlimited lookahead and linear time via a memo table, at the cost of memory proportional to input times rules, and ordered choice that silently hides ambiguity rather than reporting it.

See it for yourself

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

Read one: Clang's clang/lib/Parse/ParseExpr.cpp and rustc's compiler/rustc_parse/src/parser/expr.rs are both hand-written recursive descent and both readable. Go's is cmd/compile/internal/syntax/parser.go.
Prove the left-recursion failure to yourself: write the left-recursive version of parseExpression in any language, call it on a single number, and watch the stack trace. It is the same function repeated to the frame limit.
Find the recursion cap in a compiler you use: clang -fbracket-depth=N, and in CPython try eval("(" * 200 + "1" + ")" * 200) to see the nesting limit reported as an error rather than a crash.
Instrument your own parser by printing the function name and token index on entry; the resulting trace is the derivation, and comparing it against a hand-derivation of the grammar is how you find a rule you transliterated wrongly.
Our stepper at /compilers/parsing shows the active call chain and the token position side by side for each step.

Plausible wrong readings

Stated the way a confident engineer states them.

"Left recursion produces a wrong tree." It produces no tree. The parser never consumes a token, so it recurses until the stack is exhausted — on input that is completely valid.
"Recursive descent can only parse simple languages." C, C++, Rust, Go, Java and JavaScript are all parsed this way in their primary implementations. The limitation is on grammar *form*, not on language complexity.
"Because it is hand-written, it must be slower than a generated table-driven parser." Hand-written recursive descent is usually faster in practice: no table indirection, excellent branch prediction, and the compiler can inline across the rule functions.
"The recursion in parseFactor calling parseExpression is the dangerous kind." It is not — a ( has already been consumed, so the parser has made progress. Recursion is only fatal when it can reach itself with the token position unchanged.

Misconceptions

The claim, and what is actually true.

You need a parser generator for a real language.

Most production compilers for the languages you use are hand-written recursive descent. Generators are chosen for grammar churn and formal conformance, not for capability.

Left recursion is a theoretical concern.

It is the first bug almost every hand-written parser hits, and its symptom — a stack overflow on trivially valid input — looks nothing like a grammar problem, which is what makes it cost an afternoon.

The fix for left recursion changes what the language accepts.

The rewrite accepts exactly the same strings. What it can change, if done carelessly, is the tree shape and therefore associativity — which is a semantic change with no diagnostic.

Go deeper

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

overview

Write one function for each rule in the grammar. Inside it, call the function for each sub-rule and consume the tokens the rule mentions. The call stack does the bookkeeping, and the tree gets built as the calls return. The one rule you must obey: a function must never call itself before consuming at least one token, because then it can never stop.

practical

Start from an EBNF grammar with no left recursion. Write peek, match and expect first; expect should take a reason string so every diagnostic can say what it was expecting and why. Use a loop, not recursion, for chains of the same operator, and fold into the left operand. Add a recursion-depth counter early — it costs four lines and turns a crash on hostile input into an error message. Test associativity explicitly with - and /, because + and * will pass either way.

advanced

The interesting engineering is what happens after the first error, not before it. A parser that throws is unusable in an IDE, which must have a tree for a file that is mid-keystroke and syntactically broken. That pushes the design toward functions that return error nodes rather than raising, a sync-set parameter threaded down the call chain so each function knows which tokens an ancestor can resume from, and a delimiter stack so recovery never skips past a brace it owes. At that point the call stack is no longer just convenient — it is carrying recovery context that a table-driven parser has to reconstruct explicitly, and that asymmetry is most of why IDE-grade frontends are hand-written.

How much this depends on

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

implementationThat Clang, rustc, Go's gc, Roslyn and V8 all use hand-written recursive descent is true of their current primary frontends. It has not always been: GCC's C++ frontend was Bison-generated until GCC 3.4 (2004) and its C frontend until GCC 4.1, and Go's parser was yacc-generated before Go 1.6. The migrations went in one direction, but the fact is historical, not a law.

typicalThe claim that hand-written descent is faster than generated table-driven parsers reflects common measurements on mainstream compilers, where locality and branch prediction favour code over tables. It is not guaranteed: a highly tuned generated parser with a compact table can win on a grammar with many alternatives per rule, and neither result transfers without measuring.

simplifiedThe parser shown throws on the first error. A production parser never does: it reports, inserts an error node, synchronizes, and continues, so that one file yields all its errors at once. That machinery is roughly as much code again as the parser itself — see the Diagnostics module.

If you were asked this in an interview

Write the three functions for an expression grammar with + and *, then tell me what happens if I change expression to be left-recursive.
Your parser builds 8 - 3 - 2 as 8 - (3 - 2). Where exactly is the bug, and why did no test catch it?
How would you stop a hostile input file from crashing this parser?

Connections

DSArecursion stack n-ary-tree

OS & Networkingstack-frames stack-overflow

Domains that do not exist yet

Testing & Reliability Engineering — Adversarial and generated input as a test class
Recursion depth limits exist because of inputs no human writes. Generating them systematically is fuzzing, which is owned there; [[compiler-fuzzing]] is the compiler-specific application.