Recursive Descent Parsing

A recursive descent parser is the most intuitive and widely-used parsing technique. Each grammar rule becomes a function, and the parser calls these functions recursively to build a parse tree.

From Grammar to Code

Consider this grammar for arithmetic expressions:

expression → term ( ("+" | "-") term )*
term       → factor ( ("*" | "/") factor )*
factor     → NUMBER | "(" expression ")"

Each rule maps directly to a function:

function expression():
    left = term()
    while match(PLUS, MINUS):
        op = previous()
        right = term()
        left = Binary(left, op, right)
    return left

The recursion in factor → "(" expression ")" is what gives the technique its name — factor() calls expression(), which calls term(), which calls factor() again.

How It Works

The parser maintains a pointer into the token list (produced by the scanner). Three key operations:

• peek(): look at the current token without consuming it
• advance(): consume the current token and move forward
• match(types...): if the current token matches any of the given types, advance and return true

Why Recursive Descent?

In Crafting Interpreters, Nystrom argues that recursive descent is the "bread and butter" of real-world parsers. GCC, V8, and the Go compiler all use hand-written recursive descent parsers rather than parser generators. The reasons: better error messages, easier debugging, and full control over the parse.

Parser generators like YACC or ANTLR generate parsers from grammar files, but the generated code is often hard to debug. Lua's parser (lparser.c) is hand-written recursive descent, and at about 1,500 lines it parses the entire Lua language.

Error Handling

When the parser encounters an unexpected token, it should:

1. Report the error with the line number and the token
2. Synchronize — skip tokens until it finds a statement boundary (like ;)
3. Continue parsing to find more errors

This is called panic mode recovery and is essential for a useful compiler.

Your Task

Build a recursive descent parser that reads tokens and outputs an AST in S-expression format. Start with arithmetic expressions and build up from there.