Recursive descent parsing

Recursive descent parsing is a top-down parsing technique in which each non-terminal in a context-free grammar is implemented as a function that recognizes the corresponding syntactic construct. The parser begins with the start symbol and recursively calls functions to match the right-hand sides of grammar productions, consuming tokens from the input stream as it goes. It is the most intuitively natural parsing technique — the structure of the parser mirrors the structure of the grammar — and it is the dominant approach in modern programming language implementation.

Recursive descent parsers are typically LL(k) parsers: they read the input Left-to-right and produce a Leftmost derivation, using k tokens of lookahead to decide which production to apply. A recursive descent parser can handle any LL(k) grammar, but it cannot handle left recursion — a production of the form A → A α — because the corresponding function would call itself infinitely without consuming input. Left recursion must be eliminated through grammar transformation before recursive descent can be applied.

The resurgence of recursive descent in contemporary language design — evident in the parsers for Rust, Go, Swift, and virtually every language created since 2010 — marks a significant departure from the table-driven LR paradigm that dominated the twentieth century. Recursive descent parsers are easier to write by hand, produce better error messages, and can integrate semantic analysis and syntax-directed translation directly into the parsing functions. They sacrifice some theoretical power — they cannot handle all context-free grammars — but gain engineering flexibility.

Recursive descent parsing is not a step backward from LR parsing; it is an admission that parsing is a user interface problem, not just a formal language problem. The parser's error messages are the language's first teaching moment, and recursive descent parsers are better teachers than table-driven automata. The theoretical purists who insist on maximal grammar coverage are optimizing for a metric that compiler writers stopped caring about decades ago.