Recursive Descent and Pratt Parsing

Two techniques, one parser. Recursive descent handles statements — one function per grammar production, and the Rust call stack mirrors the grammar. Pratt parsing handles expressions — one loop, a binding-power table, and recursion.

Almost every production compiler you have used is built this way: GCC, Clang, rustc, the Go compiler, V8, TypeScript, and Lua all hand-write a recursive-descent parser. This chapter explains why, and how the two halves fit together.

Concept 1: Recursive Descent

1. Concept

For each nonterminal in the grammar, write a function. The function reads tokens, calls the functions for the nonterminals it contains, and returns an AST node. Parsing a program is calling the function for the start symbol.

GRAMMAR                                    PARSER

stat ::= 'while' exp 'do' block 'end'      fn while_stat(&mut self) -> Result<Stmt> {
                                               self.expect(While)?;
                                               let cond = self.expr()?;
                                               self.expect(Do)?;
                                               let body = self.block()?;
                                               self.expect(End)?;
                                               Ok(Stmt::While { cond, body, span })
                                           }

The correspondence is one-to-one. That is the entire appeal.

2. Problem

You need a parser that (a) you can debug, (b) produces good error messages, and (c) can be bent when the grammar has a wart — and every real grammar has warts. Generated parsers are excellent at (a) never, (b) rarely, and (c) never.

3. Mental model

The Rust call stack is the parse tree, being built as you descend. When while_stat calls block, which calls stat, which calls while_stat again, the stack depth is the nesting depth of the program. That is why deeply nested input is a denial-of-service concern, and why the parser needs a depth limit — see production concerns.

4. Implementation

#![allow(unused)]
fn main() {
// src/parser.rs
pub struct Parser {
    tokens: Vec<Token>,
    pos: usize,
    depth: usize,                       // recursion guard; see §8
}

impl Parser {
    fn peek(&self) -> &TokenKind { &self.tokens[self.pos].kind }
    fn at(&self, k: &TokenKind) -> bool { self.peek() == k }
    fn advance(&mut self) -> Token { let t = self.tokens[self.pos].clone(); self.pos += 1; t }

    /// Consume a token of the expected kind, or produce an error pointing at
    /// what we actually found. The message names BOTH, because "unexpected
    /// token" without the expectation is useless to the person reading it.
    fn expect(&mut self, k: TokenKind) -> Result<Token> {
        if self.at(&k) { Ok(self.advance()) }
        else {
            Err(self.err_here(format!("expected {}, found {}",
                                      describe(&k), describe(self.peek()))))
        }
    }

    fn statement(&mut self) -> Result<Stmt> {
        // ONE token of lookahead selects the production. That property is
        // called LL(1) and it is why this parser needs no backtracking.
        match self.peek() {
            TokenKind::Local    => self.local_stat(),
            TokenKind::If       => self.if_stat(),
            TokenKind::While    => self.while_stat(),
            TokenKind::For      => self.for_stat(),
            TokenKind::Do       => self.do_stat(),
            TokenKind::Function => self.function_stat(),
            TokenKind::Break    => { let t = self.advance(); Ok(Stmt::Break { span: t.span }) }
            TokenKind::Return   => self.return_stat(),
            TokenKind::Semi     => { let t = self.advance(); Ok(Stmt::Empty { span: t.span }) }
            // Everything else is either an assignment or a call, and we cannot
            // tell which with one token. Parse an expression, THEN decide.
            _ => self.expr_stat(),
        }
    }
}
}

The parts that carry meaning:

• match self.peek() is predictive parsing: one token decides the production, so there is no backtracking and no exponential blowup. A grammar with this property is LL(1), and Ember's is, with exactly one exception.
• That exception is expr_stat. x = 1 and f(1) both start with an identifier, and no fixed amount of lookahead distinguishes a.b.c[d].e = 1 from a.b.c[d].e(). The fix is the standard one: parse a prefixexp, then look at the next token — = means it was an assignment target, ( means it was a call. Parse first, classify second. Lua's lparser.c does exactly this in exprstat.
• expect names both the expectation and the reality. This is a two-minute decision in Lab 2 that determines the quality of every syntax error your language will ever produce.

5. Alternatives

6. Decision

We hand-write a recursive-descent parser (option A).

Three reasons, in order of weight:

1. Error messages. Every production compiler that people praise for diagnostics hand-writes its parser, and this is not a coincidence — a generator does not know that a missing end should be reported at the if that opened it rather than at EOF.
2. The exceptions. Real grammars need special cases (expr_stat above; Lua's a = f \n (g).x ambiguity). In a hand-written parser a special case is an if. In a generator it is a conflict report and a lexer hack.
3. It is the technique in the industry. Reading rustc's or V8's parser after this section is a short step. Reading a bison grammar teaches you bison.

7. Tradeoffs

8. Production concerns

Deeply nested input is a denial-of-service vector, and this is the single most important production fact in the chapter.

python3 -c "print('return ' + '('*100000 + '1' + ')'*100000)" > bomb.ember
ember ast bomb.ember

With no guard, that overflows the Rust stack and aborts the process — not an error, not a panic that can be caught, an abort. A host embedding your runtime cannot defend against it. It is found by the fuzzer in Section 6 within seconds, and it is found by users on day one.

#![allow(unused)]
fn main() {
const MAX_PARSE_DEPTH: usize = 200;

fn enter(&mut self) -> Result<DepthGuard<'_>> {
    self.depth += 1;
    if self.depth > MAX_PARSE_DEPTH {
        return Err(self.err_here("expression nests too deeply"));
    }
    Ok(DepthGuard { p: self })          // Drop decrements — no early-return leak
}
}

Call enter() at the top of every recursive entry point: expr_bp, block, primary. The DepthGuard exists because a hand-decremented counter is wrong on every ? in the function, and ? is on every line.

Warning: A depth limit is not optional and it is not a Section 5 concern. It belongs in Lab 2, because the alternative is a crash the host cannot catch. This is also the first place in the curriculum where a safety property and a correctness property are the same thing.

Other production concerns:

• Error recovery. Ember's Lab 2 parser stops at the first syntax error. Lab 24 adds panic-mode recovery: on an error, skip tokens until a synchronizing token (end, ;, local, function, EOF), then resume. The synchronizing set is chosen so recovery lands at a statement boundary.
• Cloning tokens. advance() above clones. For Ident(String) that is an allocation per identifier use. It is fine, it is measured in Section 7, and the fix (std::mem::take on the token, since it is consumed exactly once) is a two-line change you should not make until the benchmark says so.

9. References

rg -n 'static void statement|exprstat|restassign' lparser.c
rg -n 'enterlevel|LUAI_MAXCCALLS' lparser.c lstate.h   # Lua's own depth guard

• Lua's lparser.c — under 2,000 lines for the whole parser and code generator. Note enterlevel/leavelevel and LUAI_MAXCCALLS: Lua hit the nesting problem too, and its answer is the same shape as ours.
• rust-lang/rust, compiler/rustc_parse/src/parser/ — a hand-written recursive-descent parser at industrial scale, with recovery machinery worth studying after you have written the naive one.
• Crafting Interpreters, chapter 6 ("Parsing Expressions") and chapter 17 — the same two techniques, in Java and C.

Concept 2: Pratt Parsing

1. Concept

A Pratt parser (also "precedence climbing", also "top-down operator precedence") parses expressions with one function that takes a minimum binding power. It parses a prefix, then loops: while the next operator binds at least as tightly as the minimum, consume it and recurse for its right operand.

2. Problem

The stratified-grammar approach needs one function per precedence level. Ember has nine levels, so that is nine nearly identical functions, and adding an operator means editing two and writing one. Pratt collapses all nine into one function and one table.

3. Mental model

expr_bp(min_bp) means: "parse the largest expression you can, but stop the moment you meet an operator that binds looser than min_bp — that one belongs to my caller."

The recursion passes the current operator's right binding power down. The loop compares the next operator's left binding power against the minimum. Two numbers, one comparison, all of precedence and associativity.

4. Implementation

#![allow(unused)]
fn main() {
impl Parser {
    pub fn expr(&mut self) -> Result<Expr> { self.expr_bp(0) }

    fn expr_bp(&mut self, min_bp: u8) -> Result<Expr> {
        let _guard = self.enter()?;                     // depth limit, see above

        // ── 1. The prefix position: something that can START an expression ──
        let mut lhs = match self.peek() {
            k if prefix_bp(k).is_some() => {            // unary  -  not  #
                let op_tok = self.advance();
                let bp = prefix_bp(&op_tok.kind).unwrap();
                let rhs = self.expr_bp(bp)?;            // NOT bp+1: prefix ops are
                                                        // right-nested by nature
                let span = op_tok.span.merge(rhs.span());
                Expr::Unary { op: unop(&op_tok.kind), operand: Box::new(rhs), span }
            }
            _ => self.primary()?,                       // literal, name, (exp), {…}
        };

        // ── 2. The infix loop ───────────────────────────────────────────────
        loop {
            let Some((l_bp, r_bp)) = infix_bp(self.peek()) else { break };
            if l_bp < min_bp { break; }                 // ← belongs to the caller

            let op_tok = self.advance();
            let rhs = self.expr_bp(r_bp)?;              // ← associativity lives here
            let span = lhs.span().merge(rhs.span());
            lhs = Expr::Binary { op: binop(&op_tok.kind), lhs: Box::new(lhs),
                                 rhs: Box::new(rhs), span };
        }
        Ok(lhs)
    }
}
}

That is the entire expression parser. Nine precedence levels, both associativities, unary operators, and parenthesization, in about twenty-five lines.

The three lines that matter:

• if l_bp < min_bp { break; } — the operator to the left of us pulled harder, so we stop and let it have our lhs.
• self.expr_bp(r_bp) — passing the right binding power is what makes (17, 16) right-associative and (10, 11) left-associative. There is no if for associativity.
• lhs.span().merge(rhs.span()) — the binary node's span covers its whole subtree, so error: attempt to multiply nil by number can underline article.boost * 2 rather than just *.

The Trace: 1 + 2 * 3

Follow the recursion. Indentation is call depth; ▸ is a call, ◂ is a return.

▸ expr_bp(0)
    prefix: primary() → Int(1)                     lhs = 1
    loop:  peek '+' → (10, 11); 10 >= 0 → take it
  ▸ expr_bp(11)                                    ← r_bp of '+'
        prefix: primary() → Int(2)                 lhs = 2
        loop: peek '*' → (12, 13); 12 >= 11 → take it
      ▸ expr_bp(13)                                ← r_bp of '*'
            prefix: primary() → Int(3)             lhs = 3
            loop: peek Eof → no infix_bp → break
      ◂ returns Int(3)
        lhs = Mul(2, 3)
        loop: peek Eof → break
  ◂ returns Mul(2, 3)
    lhs = Add(1, Mul(2, 3))
    loop: peek Eof → break
◂ returns Add(1, Mul(2, 3))

Now the same trace for 1 * 2 + 3, where the comparison goes the other way:

▸ expr_bp(0)
    lhs = 1;  peek '*' → (12, 13); 12 >= 0 → take
  ▸ expr_bp(13)
        lhs = 2;  peek '+' → (10, 11);  10 < 13  →  BREAK
  ◂ returns Int(2)                       ← '+' was NOT consumed; it is the caller's
    lhs = Mul(1, 2)
    loop: peek '+' → (10, 11); 10 >= 0 → take
  ▸ expr_bp(11) → Int(3)
    lhs = Add(Mul(1, 2), 3)
◂ Add(Mul(1,2), 3)

10 < 13 → BREAK is the whole algorithm. Read those two traces until the comparison feels obvious; that is the twenty minutes that makes week 3 of the weekly plan take one sitting instead of three.

Verify it on your own implementation:

ember ast -e 'return 1 + 2 * 3'
ember ast -e 'return 1 * 2 + 3'
ember ast -e 'return 2 ^ 3 ^ 2'      # right-assoc: the RIGHT child is the nested one
ember ast -e 'return 1 - 2 - 3'      # left-assoc:  the LEFT  child is the nested one

5. Alternatives

6. Decision

We use Pratt (option A), after writing the stratified version (option B) in Lab 2 and deleting it.

Writing B first is not busywork: it takes twenty minutes, it makes the six-function stack concrete, and then the diff to A is the lesson. Skipping it means Pratt looks like a magic trick instead of a refactor. Keep the diff in docs/learning/02-parser.md.

7. Tradeoffs

8. Production concerns

• The depth guard applies here too, and expr_bp is the most likely place to blow the stack: 1+1+1+… a hundred thousand times recurses once per operator in a right-associative chain.
• Postfix and mixfix operators. Calls f(x), indexing t[k], and field access t.k are postfix operators at the highest precedence. They can live in the same loop (give them a left binding power of 18 and consume the argument list instead of recursing) or in primary's suffix loop. Ember puts them in a suffixed_expr loop inside primary, because their right-hand sides are not expressions parsed by binding power — t.name takes a name, not an expression. Note that decision in Lab 13 when you get there.
• Ternary and assignment-as-expression are the two constructs that make people abandon Pratt. Ember has neither: assignment is a statement, which is a Lua decision and a good one — it makes if x = 1 then a syntax error rather than a bug.

9. References

rg -n 'priority\[\]|UNARY_PRIORITY|static BinOpr subexpr' lparser.c

Read that. Lua's subexpr(ls, v, limit) is expr_bp(min_bp) under a different name, and its priority[] array holds exactly the (left, right) pairs from the previous chapter. Ember's design is not like Lua's; within a rename, it is Lua's.

• Vaughan Pratt, Top Down Operator Precedence, POPL 1973 — the original paper.
• Aleksey Kladov, Simple but Powerful Pratt Parsing (2020) — the source of the (l_bp, r_bp) formulation used here.
• Andy Chu's Pratt Parsing Index and Updates — a survey connecting Pratt, precedence climbing, and shunting yard as the same algorithm in three dialects.

Things to Notice

• Two techniques, chosen per problem. Statements are keyword-directed, so recursive descent is a perfect fit. Expressions are operator-directed, so Pratt is. Using one technique for both is a self-imposed constraint, not a virtue.
• The call stack is the parse tree. That is why the parser is easy to debug and why it is a DoS target. Both facts come from the same property.
• parse first, classify second is the general answer to "I need more lookahead". It shows up again in Section 3, when the compiler must decide whether an expression is an assignment target.
• Lua's parser emits bytecode directly — lparser.c calls into lcode.c as it parses, with no AST at all. That is a legitimate design (fast, one pass, less memory) and Ember rejects it deliberately: an AST is what makes the tree-walking reference interpreter possible, and the reference interpreter is what makes differential testing possible. One design decision, made in Lab 2, buys a testing strategy in Lab 12.

Validation / Self-check

1. What is the correspondence between a grammar production and a recursive-descent function?
2. What does LL(1) mean, and where exactly does Ember's grammar fail it? How is that handled?
3. Trace expr_bp on 1 * 2 + 3, writing the min_bp at each call and the comparison at each loop test.
4. Which single line of expr_bp implements associativity, and what would you change to make ^ left-associative?
5. Why must expect name both the expected and the found token?
6. Give the input that overflows the parser's stack, explain why a Result cannot catch it without a guard, and write the guard.
7. Why is DepthGuard a Drop type rather than a decrement at the end of the function?
8. Lua's parser produces bytecode with no AST. Name one advantage of that and the specific capability Ember gives up if it copies it.

Next: The AST.