Recursive Descent Parsing

A context-free grammar (CFG) consists of nonterminals, terminals, a start symbol, and productions of the form `A → α`, where `α` is a string of terminals and nonterminals. A top-down parser builds a parse tree starting from the start symbol and repeatedly expanding nonterminals, trying to match the resulting frontier of terminals against the input stream left to right. Recursive descent is the most direct realization of this idea: for every nonterminal `A` in the grammar, write a procedure `parseA()` whose job is to recognize a string derivable from `A`, consuming exactly that many tokens from the input and returning (typically) a parse-tree or AST node. The central mechanism that makes this work without backtracking is predictive parsing: when a nonterminal has several productions, the parser decides which one to use by examining a small, bounded window of upcoming tokens — classically just the next token, i.e. one token of lookahead. This is safe exactly when the grammar is LL(1): for every nonterminal, the sets of tokens that can begin each alternative production (their FIRST sets, extended by FOLLOW sets when an alternative can derive the empty string) are pairwise disjoint. Under this condition, the choice of production is a deterministic function of the current lookahead token, so no backtracking or trial-and-error is ever needed. Two well-known grammar transformations are usually required before a CFG can be parsed by naive recursive descent. Left recursion elimination rewrites rules like `A → A α | β` (which would cause `parseA` to call itself before consuming any input, looping forever) into an equivalent right-recursive or iterative form. Left factoring rewrites rules whose alternatives share a common prefix, such as `A → α β | α γ`, into a form where the parser can defer the choice until after consuming the shared prefix, restoring disjoint FIRST sets. Both transformations preserve the language generated by the grammar while making it LL(1)-friendly.

Building a recursive descent parser by hand follows a fixed recipe once the grammar is LL(1): 1. For each nonterminal `A`, write a function `parseA()`. 2. Inside `parseA`, inspect the current lookahead token to decide which production of `A` applies (predictive dispatch using FIRST/FOLLOW sets). 3. For each symbol on the right-hand side of the chosen production: if it is a terminal, match it (check it equals the lookahead, then advance); if it is a nonterminal `B`, call `parseB()` recursively. 4. If no production's FIRST set contains the lookahead (and the nonterminal cannot derive empty, or the lookahead isn't in FOLLOW), report a syntax error. 5. The start symbol's procedure is invoked once, and after it returns, the parser checks that all input has been consumed (end-of-file reached). Take a classic expression grammar, already left-recursion-eliminated so it is LL(1): ``` Expr → Term ExprRest ExprRest → '+' Term ExprRest | '-' Term ExprRest | ε Term → Factor TermRest TermRest → '' Factor TermRest | '/' Factor TermRest | ε Factor → '(' Expr ')' | NUMBER ``` This directly compiles into mutually recursive procedures: ``` function parseExpr(): node = parseTerm() return parseExprRest(node) function parseExprRest(left): if lookahead == '+': match('+') right = parseTerm() left = makeNode('+', left, right) return parseExprRest(left) else if lookahead == '-': match('-') right = parseTerm() left = makeNode('-', left, right) return parseExprRest(left) else: return left # ε-production: FOLLOW(ExprRest) contains ')' and EOF function parseTerm(): node = parseFactor() return parseTermRest(node) function parseTermRest(left): if lookahead == '': match('') right = parseFactor() left = makeNode('', left, right) return parseTermRest(left) else if lookahead == '/': match('/') right = parseFactor() left = makeNode('/', left, right) return parseTermRest(left) else: return left function parseFactor(): if lookahead == '(': match('(') node = parseExpr() match(')') return node else if lookahead == NUMBER: value = lookahead.value match(NUMBER) return makeLeaf(value) else: error("expected '(' or NUMBER, got " + lookahead) function match(expectedToken): if lookahead == expectedToken: lookahead = nextToken() # advance the token stream else: error("expected " + expectedToken + ", got " + lookahead) function parseProgram(): lookahead = nextToken() root = parseExpr() if lookahead != EOF: error("unexpected trailing input: " + lookahead) return root ``` Notice that the ε-productions in `ExprRest` and `TermRest` are what turn left recursion into an iterative loop expressed via tail recursion: instead of `Expr → Expr + Term`, we get `Expr → Term ExprRest` with `ExprRest` looping on `+`/`-` and terminating on anything in `FOLLOW(ExprRest)`. The rewriting from `+` chains into `ExprRest` tail calls is exactly the standard left-recursion-elimination transformation applied to arithmetic grammars.

Time complexity. For an LL(1) grammar with no ε-loops, each call to a `parseA` procedure either (a) matches at least one terminal before returning, or (b) is an ε-production that returns immediately without recursing further on the same input position. Because `match` strictly advances the token position and the grammar is finite and acyclic in its non-consuming derivations, the total number of procedure invocations is bounded by a constant factor times the number of tokens, `n`. Each invocation does O(1) work choosing a production (a table lookup or a chain of `if`/`else` over a bounded alphabet) plus the recursive calls it makes, so the total running time is O(n), linear in the length of the input — the same asymptotic bound as the table-driven LL(1) automaton, since recursive descent is an LL(1) automaton with the parsing stack implemented implicitly as the call stack.

Space complexity. The maximum depth of the call stack equals the maximum nesting depth of the derivation tree, which is O(n) in the worst case (e.g., `((((1))))` nests parentheses n/2 deep). So space is O(n) worst case, O(d) where d is nesting depth in typical inputs — this mirrors the explicit stack a table-driven LL(1) parser would need, so recursive descent trades an explicit stack for the runtime's call stack without changing the asymptotic bound.

Correctness. The argument is by structural induction on the grammar, showing an invariant: if the lookahead correctly reflects the next unconsumed token, then a call to `parseA()` terminates having consumed exactly a prefix of the input derivable from `A`, if and only if such a prefix exists starting at the current position, and otherwise reports an error.

• Base case: `A` derives only terminal strings (e.g., `Factor → NUMBER`). `match` directly checks token equality against the single required terminal, so the invariant holds trivially.
• Inductive step: Suppose `A → X₁ X₂ … Xₖ` is chosen. By the LL(1) condition, this production is selected only when the lookahead lies in FIRST(`A`'s chosen alternative) — guaranteeing it is the unique correct choice, because FIRST sets of alternatives are disjoint by construction (after left-factoring) and ε-alternatives are only taken when the lookahead is outside every other alternative's FIRST set but inside FOLLOW(A). By the induction hypothesis, each recursive call `parseXᵢ()` correctly consumes the maximal valid prefix derivable from `Xᵢ`, leaving the lookahead correctly positioned for `Xᵢ₊₁`. Chaining these calls in order therefore consumes exactly the prefix derivable from the whole right-hand side.
• Termination: Each recursive call either strictly decreases the remaining input (via `match`) or is one of finitely many ε-alternatives that do not recurse further without consuming input, since the grammar has no left recursion. So no infinite regress occurs.

This shows the parser accepts precisely the language generated by the grammar (soundness and completeness relative to the CFG) and does so deterministically — no backtracking, no exponential blowup — provided the LL(1) condition genuinely holds. If it does not (ambiguous grammar, unresolved left recursion, or overlapping FIRST sets), naive recursive descent may loop forever, silently pick the wrong production, or require unbounded lookahead/backtracking, which is the central honest tradeoff of the technique: it is fast and simple exactly when the grammar is well-behaved, and it is the programmer's responsibility to make the grammar LL(1) by transformation.

Parse the token stream `3 + 4 * 2` `EOF` against the grammar above, tracing calls, lookahead, and the AST built.

The resulting AST is `add(3, mul(4, 2))` — multiplication correctly binds tighter than addition, even though the input listed `+` before ``, because `Term` (built from ``/`/`) is nested inside `ExprRest`'s handling of `+`, matching the grammar's designed precedence hierarchy. This is precisely why the grammar was structured with `Expr` built from `Term`s and `Term` built from `Factor`s: grammar layering encodes operator precedence, and recursive descent's call nesting directly executes that layering. A second, trickier trace: parsing `( 1 + 2 ) 3`. Here `parseFactor()` sees lookahead `(`, matches it, calls `parseExpr()` recursively (not `parseFactor()`!), which fully parses `1 + 2` down to `add(1,2)`, then `parseFactor()` matches the closing `)`, returning the subtree. Back in `parseTermRest`, the lookahead is now ``, so it matches `*`, parses `3`, and produces `mul(add(1,2), 3)`. This demonstrates the mutual-recursion property in its name: `parseExpr` calls (indirectly) `parseFactor`, which calls back into `parseExpr` — the call stack correctly models arbitrarily deep nested parenthesization, bounded only by available stack space.

Recursive descent's intellectual roots lie in the formalization of context-free grammars and the theory of top-down derivation that made predictive, table-free parsing possible to reason about rigorously.

Recursive descent parsers are the backbone of many production language front ends precisely because hand-written control flow permits context-sensitive error recovery and messages that generated LL/LR tables struggle to express — Clang is famous for pinpoint-accurate diagnostics rooted in its recursive descent C/C++/Objective-C parser. Microsoft's Roslyn compiler for C# and Visual Basic, Google's Go compiler toolchain (`go/parser`), and the Rust compiler `rustc` all use hand-written recursive descent parsers rather than parser generators. Beyond full language compilers, recursive descent is the standard technique for parsing configuration languages, expression evaluators embedded in applications (spreadsheet formulas, calculator apps, query languages), JSON/XML-adjacent formats, and command interpreters, anywhere a small, fast, easily debugged parser beats the machinery of a generated table. It is also the natural teaching bridge between the abstract theory of Top-Down Parsing and the more automated machinery of LL Parsing and Parse Tables, and its output — the parse tree built alongside the recursive calls — is typically simplified immediately into the more compact Abstract Syntax Trees used by later compiler phases such as semantic analysis and code generation.

Ask the tutor: Can you show me how to transform a specific left-recursive grammar rule step by step into the right-recursive form used for recursive descent?