Crafting a parser, part 4: Pratt parsing and precedence

Expressions are where naive recursive descent gets ugly. 1 + 2 * 3 must parse as 1 + (2 * 3), and a forest of add_expr / mul_expr / unary_expr functions encodes precedence by accident of nesting. Pratt parsing (a.k.a. precedence climbing) replaces that whole forest with one loop and a table.

This is part four of Crafting a parser in Rust.

Binding power

Give every operator a numeric binding power. Higher binds tighter. * binds tighter than +; left-associativity falls out of making the right-hand power one notch higher than the left.

Picking the numbers

Don't agonize over exact values — only their order matters. Space them out (10, 20, 30) so you can slot a new operator between two existing ones later without renumbering.

Left versus right associativity

Associativity is encoded as the gap between an operator's left and right power. Equal-ish with the right one higher means left-associative; the reverse means right-associative.

pratt.rs

1fn expr_bp(&mut self, min_bp: u8) -> Expr {2    let mut lhs = self.prefix();             // literal, unary, or ( group )3    loop {4        let op = self.peek_infix_op();5        let (l_bp, r_bp) = infix_binding_power(op);6        if l_bp < min_bp { break; }          // operator binds too loosely: stop7        self.bump();8        let rhs = self.expr_bp(r_bp);        // recurse with the right power9        lhs = Expr::binary(lhs, op, rhs);10    }11    lhs12}

Reading the loop

expr_bp(0) parses a full expression. Each iteration grabs an infix operator only if it binds at least as tightly as min_bp; otherwise it returns and lets an outer call take it. That single comparison is the entire precedence mechanism:

display

Associativity in one line

Left-assoc +: binding power (1, 2) — the right side demands a higher power, so a second + at the same level stops and nests left. Right-assoc =: (2, 1), and assignment chains to the right. No grammar rewrite, just two numbers.

Prefix and postfix fit the same frame

Unary minus is a prefix op with its own binding power. Postfix !, call (), and index [] slot into the same loop. Pratt handles prefix, infix, and postfix uniformly — the reason it scales to real languages.

prefix()

owns: atoms + unary

literals, identifiers`-x`, `!x`, `( expr )`

Returns the left operand the loop starts from.

infix loop

owns: precedence

table lookup per operatorthe `min_bp` gate

Where associativity and precedence actually live.

🦀

Ferris' hot tip

Keep the binding-power table next to the operator enum, not scattered through the parser. When you add a new operator later, you touch exactly one function.

Takeaways

One loop + a binding-power table replaces N precedence levels.
Associativity is the asymmetry between left and right binding power.
Prefix, infix, and postfix all ride the same loop.

Next: error recovery and diagnostics.