Recursive-Descent Parsing

You have an LL(1) parsing table — a neat grid that, given the nonterminal on top of the stack and the next input token, tells you which production to apply. A table-driven parser reads that grid at runtime with an explicit stack. But there is a second way to spend the same information, and it is the one that ships in real compilers: bake the grammar directly into code. Write one function per nonterminal, let the function call itself and its neighbours to match the right-hand sides, and the call stack of the language becomes the parser's stack. That is recursive-descent parsing — the most direct, readable, hand-hackable way to turn a grammar into a program.

It is called descent because it starts at the grammar's start symbol and works downward toward the leaves, and recursive because a nonterminal that appears inside its own definition becomes a function that (directly or indirectly) calls itself. The structure of the parser mirrors the structure of the grammar so faithfully that you can practically read one off the other.

One function per nonterminal

Take a fragment of grammar for arithmetic expressions, written to encode precedence (a \text{term} binds tighter than an \text{expr}) and left-to-right structure:

\begin{aligned} \textit{expr} &\;\to\; \textit{term}\ \big(\,(\texttt{+}\mid\texttt{-})\ \textit{term}\,\big)^{*}\\ \textit{term} &\;\to\; \textit{factor}\ \big(\,(\texttt{*}\mid\texttt{/})\ \textit{factor}\,\big)^{*}\\ \textit{factor} &\;\to\; \texttt{num}\ \mid\ \texttt{id}\ \mid\ \texttt{(}\ \textit{expr}\ \texttt{)} \end{aligned}

Each nonterminal on the left becomes a parsing function. Each alternative on the right becomes a branch chosen by peeking at the current token (the lookahead); each terminal becomes a match; each nonterminal reference becomes a function call. The Kleene stars ((\ldots)^{*}) become while loops. Nothing else is needed — the grammar is the control flow.

// A sketch of the shape (see the full runnable version below). function parseExpr() { let node = parseTerm(); while (peek() === "+" || peek() === "-") { const op = next(); node = { op, left: node, right: parseTerm() }; } return node; }

Predictive vs. backtracking descent

There are two flavours of recursive descent, and the difference is everything.

Predictive (the good kind)Backtracking (the slow kind)
How it chooses a production peeks at a fixed number of tokens (usually 1) and commits — no take-backs tries an alternative, and if it fails, rewinds the input and tries the next
Requires an LL(1) grammar (disjoint FIRST sets; no left recursion) works on more grammars, even ambiguous ones
Speed linear, O(n) can be exponential in the worst case

Predictive parsing is what you almost always want: with disjoint FIRST sets the lookahead token uniquely selects the production, so the parser never guesses wrong and never backtracks. Backtracking descent (the ancestor of modern PEG and packrat parsers) is more powerful but pays for it: without memoisation it can blow up, and its "first match wins" ordering silently hides ambiguity. This page is about the predictive kind.

The engine room: peek, next, and expect

Every recursive-descent parser rests on three tiny helpers over the token stream. Keep them boring and correct and the rest writes itself:

Notice that expect is the only place errors are detected in a predictive parser: the parser predicts what must come next, and a mismatch between prediction and reality is a syntax error. The quality of that error message is entirely in your hands here — a theme the error-recovery page picks up.

Building an AST as you descend

A recogniser answers only "is this valid?". A real parser returns something — an abstract syntax tree — and recursive descent builds it beautifully: each function returns the node for the sub-phrase it parsed, and the caller stitches those returns together. Because parseExpr's loop puts the previous node on the left of each new \texttt{+} node, the tree comes out left-associative for free — a - b - c parses as (a-b)-c, exactly as arithmetic demands. Here is the whole thing: a complete parser and evaluator for arithmetic, with numbers, identifiers, the four operators, and parentheses.

// ---- Tokens: numbers, identifiers, operators, parens ---- type Tok = { kind: string; text: string; value?: number }; function lex(src: string): Tok[] { const toks: Tok[] = []; let i = 0; while (i < src.length) { const c = src[i]; if (c === " ") { i++; continue; } if (c >= "0" && c <= "9") { let j = i; while (j < src.length && src[j] >= "0" && src[j] <= "9") j++; toks.push({ kind: "num", text: src.slice(i, j), value: Number(src.slice(i, j)) }); i = j; continue; } if (c >= "a" && c <= "z") { toks.push({ kind: "id", text: c }); i++; continue; } if ("+-*/()".includes(c)) { toks.push({ kind: c, text: c }); i++; continue; } throw new Error(`bad char '${c}'`); } toks.push({ kind: "eof", text: "<eof>" }); return toks; } // ---- Recursive-descent parser + evaluator ---- class Parser { private toks: Tok[]; private pos = 0; private env: Record<string, number>; constructor(toks: Tok[], env: Record<string, number>) { this.toks = toks; this.env = env; } private peek(): Tok { return this.toks[this.pos]; } private next(): Tok { return this.toks[this.pos++]; } private expect(kind: string): Tok { if (this.peek().kind !== kind) throw new Error(`expected '${kind}' but found '${this.peek().text}'`); return this.next(); } parse(): number { const v = this.expr(); this.expect("eof"); // nothing may trail a complete expression return v; } // expr -> term (('+' | '-') term)* private expr(): number { let v = this.term(); while (this.peek().kind === "+" || this.peek().kind === "-") { const op = this.next().kind; const rhs = this.term(); v = op === "+" ? v + rhs : v - rhs; // left-associative fold } return v; } // term -> factor (('*' | '/') factor)* private term(): number { let v = this.factor(); while (this.peek().kind === "*" || this.peek().kind === "/") { const op = this.next().kind; const rhs = this.factor(); v = op === "*" ? v * rhs : v / rhs; } return v; } // factor -> num | id | '(' expr ')' private factor(): number { const t = this.peek(); if (t.kind === "num") { this.next(); return t.value!; } if (t.kind === "id") { this.next(); return this.env[t.text] ?? 0; } if (t.kind === "(") { this.next(); const v = this.expr(); this.expect(")"); return v; } throw new Error(`unexpected token '${t.text}'`); } } const env = { x: 10, y: 3 }; for (const src of ["2 + 3 * 4", "(2 + 3) * 4", "x - y - 1", "20 / (2 + 2)"]) { console.log(`${src.padEnd(14)} = ${new Parser(lex(src), env).parse()}`); }

Run it. 2 + 3 * 4 gives 14, not 20, because term greedily grabs the 3\times 4 before expr ever sees the \texttt{+} — precedence is enforced purely by which function calls which. Swap the evaluation for node construction ({ op, left, right }) and the very same skeleton yields an AST instead of a number.

Every industrial C, C++, C# and Rust front end you can name uses a hand-written recursive-descent parser, not a generated table. GCC switched away from a Bison grammar to hand-written descent; Clang, the Microsoft/Roslyn C# compiler, the Rust compiler and V8's JavaScript parser were recursive descent from the start. Why abandon the elegant machinery? Three reasons. Error messages: a human wrote the code, so a human can write "did you forget a semicolon after this expression?" exactly where it belongs — generated parsers famously say "syntax error". Context: real languages have grammar quirks (C's "is this a type or a variable?" ambiguity, C++'s most-vexing-parse) that are trivial to resolve with an if in hand-written code and agonising in a pure grammar. Control: you can hook in semantic actions, error recovery, and incremental re-parsing wherever you like. The tidy table wins the textbook; the messy function wins the shipping compiler.

Expressions the slick way: Pratt / precedence climbing

Writing one function per precedence level (expr, term, factor, …) is clear but tedious — a language with ten precedence levels wants ten near-identical functions. The Pratt parser (a.k.a. precedence climbing, or top-down operator precedence) collapses them into a single recursive function parameterised by a "minimum binding power". Each operator carries a numeric precedence; the loop keeps folding while the next operator binds at least as tightly as the current threshold, and recurses with a higher threshold to climb into tighter sub-expressions.

// One function replaces expr/term/factor. bp = binding powers per operator. const bp: Record<string, number> = { "+": 1, "-": 1, "*": 2, "/": 2 }; function parseExpr(minBp: number): Node { let left = parseFactor(); // a num, id, or ( expr ) while (bp[peek()] !== undefined && bp[peek()] >= minBp) { const op = next(); const right = parseExpr(bp[op] + 1); // climb: tighter ops bind first left = { op, left, right }; } return left; }

This is how many production parsers (including parts of Clang and rustc) handle expression grammars: the statement-level constructs stay as readable hand-written functions, and the fiddly operator-precedence part is delegated to one compact Pratt loop. It is the same top-down idea — just data-driven on precedence instead of hard-coded into the call graph.

The single fatal mistake in recursive descent is a left-recursive production. Suppose you write the grammar the "natural" mathematical way: \textit{expr} \to \textit{expr}\ \texttt{+}\ \textit{term}. Translate it literally and parseExpr's very first action is to call parseExpr — with the cursor not moved one bit. No token is consumed, so the recursion never bottoms out: instant stack overflow, before a single character is read. A predictive parser cannot have left recursion.

The cure is standard. Eliminate the left recursion by rewriting A \to A\alpha \mid \beta as A \to \beta\,A', A' \to \alpha\,A' \mid \varepsilon — which is exactly the \textit{term}\ (\ldots)^{*} loop form we used above. In practice you skip the formal rewrite and reach straight for the while loop: the loop is the de-left-recursed grammar, and as a bonus it gives you the correct left-associative tree, which a naive right-recursive rewrite would not. Rule of thumb: whenever a nonterminal would recurse on itself with no token consumed first, turn that self-reference into a loop.