Lab 2: The Pratt Parser (Milestone 1)

Background

You will build src/ast.rs and src/parser.rs, and ember ast will print the tree for any expression. You will write the stratified recursive-descent expression parser first, run it, then replace it with a Pratt parser and keep the diff — because the diff is the lesson.

By the end of this lab, precedence and associativity are correct, spans cover every subtree, and a 100,000-deep nesting bomb returns an error instead of aborting the process.

Why This Lab Matters

Precedence bugs are silent. A wrong binding power produces a program that runs and computes the wrong answer. Nothing downstream can detect it. The tests you write here are the only defense you will ever have.
The depth guard you add in Step 6 is a security control, not a nicety. Without it, a hostile or merely careless script aborts the host process in a way no Result can catch.
The AST shape you choose here is consumed by two backends for the next fourteen weeks. This is the last cheap moment to change it.

Prerequisites

Grammars and Precedence and Recursive Descent and Pratt Parsing read. Re-read the two traces before Step 4.
The AST read.
Lab 1 complete: ember tokens works and its tests pass.

Predict First

1 + 2 * 3 — is Add or Mul at the root?
2 ^ 3 ^ 2 — which child of the outer ^ is the nested one?
-2 ^ 2 — is the root Unary(Neg) or Binary(Pow)?
1 - 2 - 3 — same question, mirrored.
((((...1...)))) nested 100,000 deep — what happens with no depth guard? Be specific about which stack and what the process does.
After you add a depth guard at parse time, is the drop of a legal 199-deep tree safe? Why?

Step 1: The AST

Concept. The contract between the front end and everything else.

Goal. Expr, Stmt, Block, and the operator enums, with a span() accessor.

Write src/ast.rs as given in The AST. Add:

#![allow(unused)]
fn main() {
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub enum BinOp { Add, Sub, Mul, Div, IDiv, Mod, Pow, Concat,
                 Eq, Ne, Lt, Le, Gt, Ge, And, Or }
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub enum UnOp { Neg, Not, Len }

impl Expr {
    /// Every node knows its extent. Used by `merge`, by diagnostics, and by
    /// the compiler's line table in §3.
    pub fn span(&self) -> Span {
        use Expr::*;
        match self {
            Nil { span } | Bool { span, .. } | Int { span, .. } | Float { span, .. }
            | Str { span, .. } | Vararg { span } | Name { span, .. }
            | Index { span, .. } | Call { span, .. } | Method { span, .. }
            | Unary { span, .. } | Binary { span, .. } | Function { span, .. }
            | Table { span, .. } => *span,
        }
    }
}
}

The part that matters. That match has no _ arm. When Lab 13 adds Expr::Table, the compiler will refuse to build until this arm is updated — which is exactly what you want. Never write _ => Span::EMPTY in a span() accessor; you would be trading a compile error for a diagnostic that silently points at byte 0.

Checkpoint question. Why does Binary's span cover the whole subtree instead of just the operator token?

Step 2: The Parser Skeleton

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

impl Parser {
    pub fn new(tokens: Vec<Token>) -> Self { Parser { tokens, pos: 0, depth: 0 } }

    fn peek(&self) -> &TokenKind { &self.tokens[self.pos].kind }
    fn peek_span(&self) -> Span { self.tokens[self.pos].span }
    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 }

    fn expect(&mut self, k: TokenKind) -> Result<Token> {
        if self.at(&k) { return Ok(self.advance()); }
        Err(self.err_here(format!("expected {}, found {}",
                                  describe(&k), describe(self.peek()))))
    }

    fn err_here(&self, msg: impl Into<String>) -> EmberError {
        EmberError { kind: ErrorKind::Parse, message: msg.into(),
                     span: Some(self.peek_span()), traceback: Vec::new() }
    }
}
}

self.tokens[self.pos] never panics because tokenize always ends with Eof and no rule advances past it. Write that invariant as a comment — it is the only thing standing between this parser and an index-out-of-bounds on malformed input.

Step 3: The Naive Stratified Parser (Write It, Then Delete It)

Concept. Precedence as grammar nesting.

Goal. Feel the six-function stack, so that Step 4 reads as a simplification rather than a trick. Budget twenty minutes. Handle only + - * / ^ and unary minus.

#![allow(unused)]
fn main() {
// TEMPORARY. Deleted at the end of Step 4. Keep the diff in docs/learning/02-parser.md.
fn expr_naive(&mut self)   -> Result<Expr> { self.additive() }

fn additive(&mut self) -> Result<Expr> {
    let mut lhs = self.multiplicative()?;
    while matches!(self.peek(), TokenKind::Plus | TokenKind::Minus) {
        let op = self.advance();
        let rhs = self.multiplicative()?;        // ← LEFT-assoc: loop, don't recurse
        let span = lhs.span().merge(rhs.span());
        lhs = Expr::Binary { op: binop(&op.kind), lhs: Box::new(lhs),
                             rhs: Box::new(rhs), span };
    }
    Ok(lhs)
}

fn multiplicative(&mut self) -> Result<Expr> {
    let mut lhs = self.unary()?;
    while matches!(self.peek(), TokenKind::Star | TokenKind::Slash) { /* same shape */ }
    Ok(lhs)
}

fn unary(&mut self) -> Result<Expr> {
    if matches!(self.peek(), TokenKind::Minus) {
        let op = self.advance();
        let operand = self.unary()?;             // ← right-nested by recursion
        let span = op.span.merge(operand.span());
        return Ok(Expr::Unary { op: UnOp::Neg, operand: Box::new(operand), span });
    }
    self.power()
}

fn power(&mut self) -> Result<Expr> {
    let base = self.primary()?;
    if matches!(self.peek(), TokenKind::Caret) {
        self.advance();
        let exp = self.unary()?;                 // ← RIGHT-assoc: recurse at the SAME level,
                                                 //   and via unary() so 2^-3 works
        let span = base.span().merge(exp.span());
        return Ok(Expr::Binary { op: BinOp::Pow, lhs: Box::new(base),
                                 rhs: Box::new(exp), span });
    }
    Ok(base)
}
}

Run it and look at what you have. Five functions for five precedence levels. Ember has nine levels plus postfix operators. Note in your journal: what would adding .. at level 4 cost here? (Answer: a new function, plus edits to the two functions on either side, plus getting its right-associativity right by recursing into itself.)

Checkpoint question. In additive the loop gives left-associativity; in power the recursion gives right-associativity. Explain both in one sentence about which side the nesting happens on.

Step 4: The Pratt Parser

Concept. Precedence as data.

Goal. Replace all five functions with one, plus two tables.

Write infix_bp and prefix_bp from Grammars and Precedence, and expr_bp from Recursive Descent and Pratt.

Then delete expr_naive and its five helpers, and record the diff:

git add -A && git commit -m "lab-02: naive stratified expression parser"
# ... write the Pratt version, delete the naive one ...
git diff HEAD --stat
git diff HEAD > docs/learning/02-parser-pratt.diff

That diff — five functions and ~70 lines becoming one function and ~25 — is the artifact. Reference it in docs/learning/02-parser.md.

Checkpoint question. In expr_bp, the prefix arm calls self.expr_bp(bp) with the prefix operator's binding power, not bp + 1. Why does -2 ^ 2 still parse as -(2 ^ 2)?

Step 5: Primary Expressions and Statements

#![allow(unused)]
fn main() {
fn primary(&mut self) -> Result<Expr> {
    let t = self.advance();
    Ok(match t.kind {
        TokenKind::Nil          => Expr::Nil { span: t.span },
        TokenKind::True         => Expr::Bool { value: true,  span: t.span },
        TokenKind::False        => Expr::Bool { value: false, span: t.span },
        TokenKind::Int(v)       => Expr::Int { value: v, span: t.span },
        TokenKind::Float(v)     => Expr::Float { value: v, span: t.span },
        TokenKind::Str(s)       => Expr::Str { value: s, span: t.span },
        TokenKind::Ident(n)     => Expr::Name { name: n, span: t.span },
        TokenKind::LParen => {
            let inner = self.expr_bp(0)?;
            let close = self.expect(TokenKind::RParen)?;
            // The parenthesis span is DISCARDED and the inner node returned
            // unchanged: this is what "abstract" syntax tree means. Lab 17 adds
            // a Paren node for the ONE case where it carries meaning.
            let _ = (t.span, close.span);
            inner
        }
        k => return Err(EmberError {
            kind: ErrorKind::Parse,
            message: format!("expected an expression, found {}", describe(&k)),
            span: Some(t.span), traceback: Vec::new() }),
    })
}
}

Statements arrive across Labs 5–7; for now ember ast parses a single expression, and a file is Block { stmts: [ExprStat] }.

Note: The error message is "expected an expression, found X", not "unexpected token". Every error message in this parser names what the parser wanted. This is a five-second decision per message and it is most of the difference between a language that is pleasant to use and one that is not.

Step 6: The Depth Guard

Concept. A recursive parser is a stack-consuming loop over untrusted input.

Goal. A 100,000-deep nesting produces an Err, and the process survives.

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

struct DepthGuard<'p> { depth: &'p std::cell::Cell<usize> }
impl Drop for DepthGuard<'_> {
    fn drop(&mut self) { self.depth.set(self.depth.get() - 1); }
}

impl Parser {
    fn enter(&self) -> Result<DepthGuard<'_>> {
        self.depth.set(self.depth.get() + 1);
        if self.depth.get() > MAX_PARSE_DEPTH {
            self.depth.set(self.depth.get() - 1);
            return Err(self.err_here("expression nests too deeply"));
        }
        Ok(DepthGuard { depth: &self.depth })
    }
}
}

Call let _guard = self.enter()?; at the top of expr_bp, primary, and block.

The parts that matter.

depth is a Cell<usize> rather than a plain field so enter(&self) can take a shared borrow. The alternative — enter(&mut self) returning a guard borrowing &mut self — would hold a mutable borrow of the parser for the whole function body, and nothing else could run. This is the first real borrow-checker design decision in the curriculum; the alternative is to increment/decrement by hand, which is wrong at every ?.
The guard decrements on Drop, so an early ? return cannot leak depth. Test that: parse a failing-but-shallow input a thousand times in a loop and assert the parser still accepts a 199-deep input afterwards.
200 is a policy number, not a fact. It is the same order as Lua's LUAI_MAXCCALLS (200) and it should be configurable from Engine in Section 5. Leave a TODO(§5) next to it.

Warning: This guard also bounds the depth of the tree, which bounds the depth of its recursive Drop — see The AST. One guard, two hazards. If you later raise the limit to 10,000, re-test the drop path, because it will abort long before the parser does on some platforms.

Step 7: `ember ast`

#![allow(unused)]
fn main() {
fn print_expr(e: &Expr, indent: usize, out: &mut String) {
    let pad = "    ".repeat(indent);
    match e {
        Expr::Int { value, span }   => out.push_str(&format!("{pad}Int({value}){}\n", loc(*span))),
        Expr::Binary { op, lhs, rhs, span } => {
            out.push_str(&format!("{pad}Binary({op:?}){}\n", loc(*span)));
            print_expr(lhs, indent + 1, out);
            print_expr(rhs, indent + 1, out);
        }
        // ... one arm per variant, no `_`
    }
}
fn loc(s: Span) -> String { format!("    @{}..{}", s.start, s.end) }
}

The Trace

$ ember tokens -e '10 + 20 * 3'
   #  span     kind          text
   0  0..2     Int(10)       "10"
   1  3..4     Plus          "+"
   2  5..7     Int(20)       "20"
   3  8..9     Star          "*"
   4  10..11   Int(3)        "3"
   5  11..11   Eof           ""

$ ember ast -e '10 + 20 * 3'
Binary(Add)                  @0..11
    Int(10)                  @0..2
    Binary(Mul)              @5..11
        Int(20)              @5..7
        Int(3)               @10..11

$ ember ast -e '(10 + 20) * 3'
Binary(Mul)                  @0..13
    Binary(Add)              @1..8          ← the parens are GONE; only the shape remains
        Int(10)              @1..3
        Int(20)              @6..8
    Int(3)                   @12..13

$ ember ast -e '2 ^ 3 ^ 2'
Binary(Pow)                  @0..9
    Int(2)                   @0..1
    Binary(Pow)              @4..9          ← RIGHT child nested: right-associative
        Int(3)               @4..5
        Int(2)               @8..9

$ ember ast -e '1 - 2 - 3'
Binary(Sub)                  @0..9
    Binary(Sub)              @0..5          ← LEFT child nested: left-associative
        Int(1)               @0..1
        Int(2)               @4..5
    Int(3)                   @8..9

$ ember ast -e '-2 ^ 2'
Unary(Neg)                   @0..6
    Binary(Pow)              @1..6          ← ^ took the 2 before unary minus could
        Int(2)               @1..2
        Int(2)               @5..6

Read the last three carefully. Right-associativity is "the nested node is the right child." Left-associativity is "the nested node is the left child." -2 ^ 2 has Unary at the root with Pow beneath it, which is why it evaluates to -4. If any of those three trees is a different shape on your machine, your binding-power table is wrong — and no other test in this curriculum will tell you.

Expected Output

$ ember ast -e '1 + * 2'
<argv>:1:5: error: expected an expression, found '*'

   1 │ 1 + * 2
     │     ^

$ ember ast -e '(1 + 2'
<argv>:1:7: error: expected ')', found end of file

   1 │ (1 + 2
     │       ^

$ python3 -c "print('('*100000 + '1' + ')'*100000)" | ember ast /dev/stdin
<stdin>:1:201: error: expression nests too deeply
$ echo $?
1

That last one exiting 1 rather than being killed by a signal is the deliverable.

Debugging Steps

`2 ^ 3 ^ 2` has the nesting on the left

Your ^ entry is (16, 17) instead of (17, 16). Right-associative means right bp < left bp.

`-2 ^ 2` parses as `(-2) ^ 2`

Unary's binding power is ≥ ^'s left bp. It must be lower: unary 14, ^ left 17.

Every expression is a single `Int` and the rest is ignored

expr() calls expr_bp with a min_bp that is too high, or the infix loop's break condition is inverted (l_bp <= min_bp instead of <).

Spans are correct on leaves and wrong on interior nodes

You are using the operator token's span for Binary instead of lhs.span().merge(rhs.span()).

The nesting bomb still aborts

enter() is called in expr_bp but not in primary, and ( recursion goes through primary. Every function that can recurse needs the guard.

`cargo test` hangs on the depth test

enter() returns Err but you decrement after the early return, so depth never comes back down and the parser rejects everything afterwards. Look at the explicit decrement before the return Err in Step 6 — that one is easy to miss because the Drop guard was never constructed on that path.

Experiment

CLAIM. Precedence errors are undetectable without an external reference.

METHOD. Deliberately swap two rows in your infix_bp table — make + bind tighter than *. Run the whole test suite you have written so far. Then run the differential shell loop from the section index.

PREDICTION. Before running: how many of your existing tests fail? How many of the differential comparisons fail?

RESULT. Record both numbers. The gap between them is the argument for the entire differential testing strategy that Section 3 formalizes — and it is why the lua comparison loop should grow every time you add an operator.

Test

#![allow(unused)]
fn main() {
fn parse_expr(src: &str) -> Expr { /* tokenize + Parser::new + expr() */ }

#[test]
fn precedence_and_associativity() {
    // Each case names the RULE it is testing. The shapes were verified against
    // Lua 5.4 with: lua -e 'print(EXPR)'
    use BinOp::*;
    // `*` binds tighter than `+`  →  Add at the root, Mul on the right
    assert!(matches!(parse_expr("1 + 2 * 3"),
        Expr::Binary { op: Add, ref rhs, .. } if matches!(**rhs, Expr::Binary { op: Mul, .. })));
    // `-` is LEFT-associative      →  the nested Sub is the LEFT child
    assert!(matches!(parse_expr("1 - 2 - 3"),
        Expr::Binary { op: Sub, ref lhs, .. } if matches!(**lhs, Expr::Binary { op: Sub, .. })));
    // `^` is RIGHT-associative     →  the nested Pow is the RIGHT child (Lua 5.4 §3.4.8)
    assert!(matches!(parse_expr("2 ^ 3 ^ 2"),
        Expr::Binary { op: Pow, ref rhs, .. } if matches!(**rhs, Expr::Binary { op: Pow, .. })));
    // `..` is RIGHT-associative    (Lua 5.4 §3.4.8)
    assert!(matches!(parse_expr("'a'..'b'..'c'"),
        Expr::Binary { op: Concat, ref rhs, .. } if matches!(**rhs, Expr::Binary { op: Concat, .. })));
    // `^` binds tighter than unary minus on its LEFT: -2^2 == -(2^2) == -4
    assert!(matches!(parse_expr("-2 ^ 2"),
        Expr::Unary { op: UnOp::Neg, ref operand, .. }
            if matches!(**operand, Expr::Binary { op: Pow, .. })));
    // ...but unary minus is allowed as ^'s RIGHT operand: 2^-3
    assert!(matches!(parse_expr("2 ^ -3"),
        Expr::Binary { op: Pow, ref rhs, .. } if matches!(**rhs, Expr::Unary { .. })));
}

#[test]
fn every_node_has_a_real_span_covering_its_children() {
    fn check(e: &Expr, parent: Span) {
        assert_ne!(e.span(), Span::EMPTY, "node with empty span: {e:?}");
        assert!(e.span().start >= parent.start && e.span().end <= parent.end,
                "child span {:?} escapes parent {:?}", e.span(), parent);
        for c in children(e) { check(c, e.span()); }
    }
    let e = parse_expr("1 + 2 * (3 - -4) ^ 5");
    check(&e, e.span());
}

#[test]
fn deeply_nested_input_errors_and_does_not_abort() {
    let src = format!("{}1{}", "(".repeat(100_000), ")".repeat(100_000));
    let err = tokenize(&src).and_then(|t| Parser::new(t).expr()).unwrap_err();
    assert_eq!(err.kind, ErrorKind::Parse);
    // The important assertion is IMPLICIT: this test finishing at all proves
    // the process did not abort. Keep a shallow parse after it to prove the
    // depth counter recovered.
    assert!(Parser::new(tokenize("1 + 1").unwrap()).expr().is_ok());
}
}

cargo test --lib parser

Challenge Extensions

Error recovery. On a parse error, skip tokens until a synchronizing token (end, ;, local, function, return, EOF), then continue. Report every error in one run. Measure: on a file with five deliberate syntax errors, how many does each version report, and how many of the recovered ones are real versus cascade noise?
Round-trip property test. Add a proptest generator for Expr, a pretty-printer that emits fully-parenthesized source, and assert parse(print(e)) == e. This catches precedence bugs automatically and is the strongest test in this lab.
Postfix operators in the Pratt loop. Move t.k, t[k], and f(x) into expr_bp as left-binding-power-18 postfix operators instead of a suffix loop in primary. Which reads better? Write the ADR.
A second ^ associativity. Change ^ to left-associative, run the lua comparison loop, and count how many expressions change meaning. Then change it back. This takes two minutes and makes the stakes concrete.
Arena AST. Replace Box<Expr> with ExprId(u32) into a Vec<Expr>. Measure parse time and peak memory on a 1 MB source. Note what happened to the deep-Drop hazard.

Deliverables

src/ast.rs complete, with span() accessors that have no _ arm.
src/parser.rs with expr_bp, infix_bp, prefix_bp, primary, and expect.
The naive stratified parser written, run, deleted, and its diff saved to docs/learning/02-parser-pratt.diff.
ember ast reproduces all six trees in The Trace.
The precedence/associativity test passes, with each case naming its rule.
The span-containment test passes over a nested expression.
The 100,000-deep nesting test passes, and the process exits 1 rather than aborting.
Every parse error message names what was expected.
docs/learning/02-parser.md and 03-ast.md written.

Validation / Self-check

Trace expr_bp on 1 * 2 + 3, writing min_bp at each call and the comparison at each loop test.
Which single line implements associativity? What would you change to make ^ left-associative?
Why is depth a Cell<usize> rather than a plain field?
Why does DepthGuard decrement on Drop instead of at the end of the function?
The depth guard prevents two distinct crashes. Name both and explain why one guard covers them.
Why is there no Paren node, and what is the single future case that will require one?
Why does primary's error say "expected an expression" rather than "unexpected token"?
You swap two rows in infix_bp. Which of your tests catch it, and which do not? What does that tell you about test design in a compiler?

Next: Lab 3 — The First Evaluator.

Open-Source Engineer & Contributor