Recursive descent parser

Recursive descent parsing turns grammar productions into a collection of procedures, usually one procedure per nonterminal. A procedure consumes tokens when they match expected terminals and calls other procedures for nested constructs; the call stack therefore records the current syntactic path.¹ For a grammar such as expr → term (('+' | '-') term)*, an expr function calls term, then repeatedly handles additive operators.

The method is top-down because it begins with the start symbol and predicts productions before seeing the entire input. Its hand-written form can combine parsing with immediate construction of an abstract syntax tree, source-location tracking, and tailored diagnostic messages. The approach is especially attractive for small languages and teaching compilers because the code is direct and easy to inspect, although the grammar and implementation must remain consistent.

Recursive descent works most simply when each grammar decision can be made from the next token or a bounded lookahead sequence. Direct left recursion, such as expr → expr '+' term | term, causes immediate unbounded self-calls and is normally rewritten as an iterative or right-factored form. Common-prefix alternatives likewise require left factoring: statement → identifier '=' expression | identifier '(' arguments ')' can be reorganized so the shared identifier is recognized before the distinction is tested.

These transformations target LL(k) behavior, but they may make a grammar less natural or alter the shape of a directly built tree.² A parser may use one-token lookahead, explicit token predicates, or a small speculative routine. When arbitrary lookahead or ambiguous alternatives are needed, a different parsing strategy or a generated predictive parser may be more suitable.

A typical recursive descent parser maintains a current token and exposes routines such as parseExpression, parseType, and parseStatement. Each routine either returns a node, advances the token position, or reports an error at the earliest point where the expected grammar cannot continue. Synchronization sets—often punctuation such as semicolons, braces, or end-of-file—let the parser skip damaged input and continue reporting later errors.

For deterministic decisions and single-pass token consumption, time is generally linear in input length and stack space follows nesting depth. Naive backtracking changes that guarantee: repeated attempts can become exponential, particularly when alternatives share long prefixes. Memoization can avoid repeated work, while packrat parsing provides linear-time recognition for suitable parsing-expression grammars at the cost of substantial memory usage.

Recursive descent is not limited to parsers written entirely by hand. Parser generators can emit recursive-descent code from predictive grammars, and frameworks such as ANTLR generate adaptive top-down parsers that use lookahead analysis and runtime prediction.³ Hand-written parsers also frequently mix styles: a recursive routine handles declarations while a precedence-climbing or Pratt routine handles expressions.

The technique has practical edge cases. Deeply nested input can exhaust the host language's call stack, so implementations may replace recursion with explicit stacks or loops. Lexer design also affects prediction: treating keywords, identifiers, indentation, or significant whitespace differently can change which alternatives are distinguishable. Modern language implementations may use a parser architecture that retains recursive-descent readability while adding error recovery, incremental reparsing, or semantic predicates; Python's PEG-based parser documentation illustrates how contemporary language grammars can move beyond strict LL(k) restrictions.⁴

Top-down parsing

Parsing that begins with a start symbol and expands toward the input tokens.

LL(k) grammar

A grammar parsed left to right with a leftmost derivation using at most k tokens of lookahead.

Left recursion

A production whose derivation can call the same nonterminal before consuming input.

Left factoring

Rewriting alternatives to remove a shared prefix and make prediction possible.

Packrat parsing

Memoized parsing that can provide linear-time recognition for suitable parsing-expression grammars.