5.3 Recursive-Descent Parsing

Recursive descent writes the parser in the host language as mutually recursive functions, usually one function per grammar nonterminal. It is the hand-written form of top-down parsing: the control flow is explicit, AST construction can happen at the recognition point, and diagnostics can use the parser's semantic context instead of exposing a generic table cell.

The method is not “just write some if statements.” A maintainable recursive-descent parser has a small, trustworthy token API, a grammar intentionally shaped for prediction, and a rule that every successful parse function leaves the cursor immediately after the construct it claims to parse.

Build a Tiny Parsing Contract

Most parsers begin with token navigation primitives:

peek()                 // inspect current token; does not consume
previous()             // most recently consumed token
at(kind)               // whether peek().kind is kind
advance()              // consume exactly one token
match(kinds...)        // consume one token if its kind is allowed
expect(kind, message)  // consume kind or report a targeted error

The parser owns a cursor into a token stream that already ends in EOF. expect is the most valuable operation: it centralizes token consumption, source ranges, and “expected X, found Y” diagnostics. A function should not silently return an invented node after failing an expectation unless its recovery policy explicitly says how it will synchronize.

For a statement grammar:

Stmt -> let IDENT = Expr ; | print Expr ;

the dispatcher is a direct predictive choice:

parseStmt(): Stmt {
  if (match(LET)) {
    const name = expect(IDENT, "expected a variable name after 'let'");
    expect(EQUAL, "expected '=' after variable name");
    const value = parseExpr();
    expect(SEMICOLON, "expected ';' after variable declaration");
    return LetStmt(name, value);
  }
  if (match(PRINT)) return PrintStmt(parseExprThenSemicolon());
  throw error(peek(), "expected a statement");
}

The branch is safe because FIRST(let IDENT = Expr ;) and FIRST(print Expr ;) are disjoint. The function does not need to speculate or backtrack.

Encode Associativity With Loops, Not Left Recursion

The natural grammar Expr -> Expr + Term | Term is left-recursive and will cause parseExpr() to call itself before consuming a token. That is infinite recursion, not left associativity. The grammar transformation from Chapter 4 removes the recursion, but source code can express the intended AST even more clearly with a loop:

parseExpr(): Expr {
  let left = parseTerm();
  while (match(PLUS, MINUS)) {
    const operator = previous();
    const right = parseTerm();
    left = Binary(left, operator, right);
  }
  return left;
}

For a - b - c, the first loop iteration produces Binary(a, -, b). The second uses that node as left, producing Binary(Binary(a, -, b), -, c). The code preserves left associativity without retaining left recursion in the grammar. A right-associative operator such as exponentiation normally recurses on its own precedence level instead.

This technique also separates syntax recognition from AST shape. A grammar may use helper nonterminals such as ExprTail, but the AST should rarely preserve them. They exist to make prediction possible, not because a compiler needs ExprTailNode in its semantic model.

Alternatives, Repetition, and Safe Lookahead

The three common shapes map neatly to parser code:

• An alternative with distinct FIRST sets becomes if/switch on peek().kind.

• An optional grammar fragment becomes an if guarded by the FIRST set of that fragment.

• A repetition becomes a while guarded by a token that genuinely starts another iteration.

For argument lists, be precise about delimiters:

Args -> Expr ( , Expr )* | epsilon

parseArgs(): Expr[] {
  const args = [];
  if (at(RPAREN)) return args;
  do {
    args.push(parseExpr());
  } while (match(COMMA));
  return args;
}

An empty list is selected by RPAREN; it is not selected whenever parseExpr fails. That distinction prevents malformed input such as f(,x) from being reinterpreted as an empty argument list and then producing a confusing delayed error.

Avoid blind backtracking in a normal language parser. It can hide grammar ambiguity, duplicate work, and make diagnostics depend on which speculative path happened to fail last. When genuine ambiguity or deep prefix sharing is required, use a deliberate strategy such as Pratt parsing, an LL parser with more lookahead, parser combinators with controlled backtracking, or the LR family in Chapter 6.

State the Cursor Contract Explicitly

Every parseX function should say where it starts, what node it returns, and where the cursor is on success. In parseArgs, entering at ) means an empty list. Entering at , is not an empty list; it is an error. That distinction prevents f(,x) from being silently reinterpreted as f() and blamed on x later.

Use loops for left-associative repetitions, and recurse only when the recursive call consumes input before re-entering. This one rule catches most accidental infinite-recursion bugs.