Pratt parsing

Deep dive

How it works

In: token stream (one token of lookahead) and a binding-power table · Out: expression tree (here an S-expression string) · State: cursor into the tokens, recursion depth · Cost: O(n) time, stack O(nesting)

1. expr(min_bp) reads one token and applies its nud (null denotation, "starts an expression"): literal, ( expr ), or a prefix operator that calls expr(r) with its right power r.
2. Loop: peek at the next token. If it has no led (), :, end), stop.
3. Postfix operator (!, also call (...) and index [...]): if its left power l >= min_bp, wrap the left side and continue.
4. Infix operator with powers (l, r): if l < min_bp, stop and let the caller take it; otherwise consume it, parse the right side with expr(r), wrap, continue. This test is the whole precedence rule.
5. Associativity: with l < r (+ is (3, 4)) a second + on the right fails 3 >= 4, so the loop in the outer frame takes it: left-associative. With l > r (^ is (8, 7)) the inner frame takes it: right-associative.
6. Ternary a ? b : c: ? is an infix token whose led parses the middle with expr(0) (inside the pair nothing binds it), expects :, then parses the last part with the right power. : is not an operator, so it ends the middle on its own.
7. Call and index are postfix operators with a high left power whose led parses a comma list up to the closing token, the same way as the ternary middle.

Start with expr(0). The usual pairing keeps the ladder ?: < + - < * / < prefix - < ^ < !, so -x^2 is -(x^2) and 2^3! is 2^(3!).

Code

#[derive(Clone, Copy, PartialEq, Debug)]
pub enum Tok { Num(i64), Op(char), Eof }

const MAX_DEPTH: u32 = 256; // bounds native stack use on hostile input

/// Binding power of a prefix operator: its right power only.
fn prefix_bp(op: char) -> Option<u8> {
    match op { '-' => Some(7), _ => None } // above * /, below ^ and !: -x^2 = -(x^2)
}
/// Postfix: left power only.
fn postfix_bp(op: char) -> Option<u8> {
    match op { '!' => Some(9), _ => None }
}
/// Infix: (left, right). right < left = right-associative.
fn infix_bp(op: char) -> Option<(u8, u8)> {
    match op {
        '?' => Some((2, 1)), // a ? b : c, right-associative
        '+' | '-' => Some((3, 4)),
        '*' | '/' => Some((5, 6)),
        '^' => Some((8, 7)),
        _ => None,
    }
}

pub struct Parser<'a> { toks: &'a [Tok], pos: usize, depth: u32 }

impl<'a> Parser<'a> {
    pub fn parse(toks: &'a [Tok]) -> Result<String, String> {
        let mut p = Parser { toks, pos: 0, depth: 0 };
        let e = p.expr(0)?;
        match p.peek() { Tok::Eof => Ok(e), t => Err(format!("unexpected {:?} at {}", t, p.pos)) }
    }
    fn peek(&self) -> Tok { self.toks.get(self.pos).copied().unwrap_or(Tok::Eof) }
    fn next(&mut self) -> Tok { let t = self.peek(); self.pos += 1; t }

    /// Parse an expression whose operators all bind tighter than `min_bp`.
    fn expr(&mut self, min_bp: u8) -> Result<String, String> {
        self.depth += 1;
        if self.depth > MAX_DEPTH { return Err("nesting too deep".into()); }
        // nud: how a token starts an expression
        let mut lhs = match self.next() {
            Tok::Num(n) => n.to_string(),
            Tok::Op('(') => {
                let e = self.expr(0)?;
                if self.next() != Tok::Op(')') { return Err("expected ')'".into()); }
                e
            }
            Tok::Op(op) => match prefix_bp(op) {
                Some(r) => format!("({} {})", op, self.expr(r)?),
                None => return Err(format!("unexpected '{}' at {}", op, self.pos - 1)),
            },
            Tok::Eof => return Err("unexpected end".into()),
        };
        // led: how a token continues an expression to its left
        loop {
            let op = match self.peek() { Tok::Op(c) => c, _ => break };
            if let Some(l) = postfix_bp(op) {
                if l < min_bp { break; }
                self.pos += 1;
                lhs = format!("({} {})", op, lhs);
                continue;
            }
            let Some((l, r)) = infix_bp(op) else { break }; // ')' and ':' end here
            if l < min_bp { break; }
            self.pos += 1;
            if op == '?' {
                let mid = self.expr(0)?; // between ? and : anything goes
                if self.next() != Tok::Op(':') { return Err("expected ':'".into()); }
                let rhs = self.expr(r)?;
                lhs = format!("(? {} {} {})", lhs, mid, rhs);
            } else {
                let rhs = self.expr(r)?;
                lhs = format!("({} {} {})", op, lhs, rhs);
            }
        }
        self.depth -= 1;
        Ok(lhs)
    }
}

fn lex(s: &str) -> Vec<Tok> { // test helper: one char per token, digits are numbers
    s.chars().filter(|c| !c.is_whitespace())
        .map(|c| c.to_digit(10).map_or(Tok::Op(c), |d| Tok::Num(d as i64))).collect()
}

fn main() {
    let p = |s: &str| Parser::parse(&lex(s));
    assert_eq!(p("1+2*3").unwrap(), "(+ 1 (* 2 3))");
    assert_eq!(p("1-2-3").unwrap(), "(- (- 1 2) 3)");        // left-assoc
    assert_eq!(p("2^3^2").unwrap(), "(^ 2 (^ 3 2))");        // right-assoc
    assert_eq!(p("-2^2").unwrap(), "(- (^ 2 2))");           // prefix below ^
    assert_eq!(p("-2*3").unwrap(), "(* (- 2) 3)");           // prefix above *
    assert_eq!(p("2^3!").unwrap(), "(^ 2 (! 3))");           // postfix above ^
    assert_eq!(p("(1+2)*3").unwrap(), "(* (+ 1 2) 3)");
    assert_eq!(p("1?2:3?4:5").unwrap(), "(? 1 2 (? 3 4 5))"); // right-assoc ternary
    assert_eq!(p("1+2?3:4+5").unwrap(), "(? (+ 1 2) 3 (+ 4 5))");
    assert!(p("1+").is_err() && p("(1").is_err() && p("1?2").is_err() && p("1 2").is_err());
    let deep = "(".repeat(100_000) + "1" + &")".repeat(100_000);
    assert_eq!(p(&deep).unwrap_err(), "nesting too deep");
}

Asserts cover precedence, both associativities, prefix vs ^, postfix vs ^, parentheses, right-associative ternary, malformed input and 100 000-deep parentheses (rejected by the depth limit).

Complexity and constants

• Time O(n): each token is peeked a bounded number of times and consumed once; each operator causes one recursive call.
• Measured on one Apple-silicon Mac, release build, this code on a 24-token expression parsed 200 000 times: about 42 ns per token. That includes one String allocation per node because the output is text; a node arena (as in recursive-descent parsing) removes most of it.
• Cost drivers: one allocation per node, one call per prefix operator or right-hand side. No syscalls, no I/O.
• Stack: one frame per pending right-hand side. Left-associative chains (1+2+3+...) are a loop and do not grow it; ^ chains, prefix chains and parentheses do. The format!-based output here is quadratic on one very long left chain (each wrap copies the left text); real parsers build nodes, not strings.

Efficiency

• Cost: order of tens of ns per token measured above, dominated by node construction; the dispatch itself is a match and an integer compare per operator. Bound: allocation, not memory bandwidth.
• Levers:
  • Arena nodes with u32 child indices instead of Box or String per node — removes most of the measured per-token time (own measurement above, not isolated) — whenever the tree is built once and dropped whole.
  • One loop instead of a function per precedence level — one frame per atom instead of one per level (Norvell; own reasoning, not measured) — grammars with 10+ levels such as Rust or C expressions.
  • Depth counter — turns a stack overflow (process abort) into an error — any input from outside.
• Naive → standard → state of the art:
  • One function per level, ~10 calls per atom · O(levels) per atom
  • Pratt / precedence climbing, one loop · O(1) calls per atom, O(operators) recursion
  • Same loop over a pre-lexed token array or lexing on demand, arena nodes, compact u8 table · O(n) with the allocator mostly out of the way

Implementation notes

• Return (l, r) from one table function: both numbers live together, so they cannot drift apart. Keep a gap (use odd/even or step by 2) when you add levels later.
• Prefix - sits between * / and ^, not at the top: that is the decision that makes -x^2 mean -(x^2) and -a*b mean (-a)*b. Write the test for it.
• Non-associative operators (a < b < c rejected): give equal l and r, then error if the next operator has the same left power as the one just consumed.
• Pick l < min_bp or <= once; mixing them between table and loop gives off-by-one precedence.

Pitfalls

• Equal powers with a wrong inequality make 1-2-3 right-associative. Test a-b-c and a^b^c first.
• Missing end tokens: ), :, ] and , must have no infix entry, or the loop swallows them; the caller checks them.
• Forgetting the final Eof check accepts 1 2 as 1.
• Prefix power too high turns -2^2 into (-2)^2.
• No depth limit: ((((... or -----... overflows the native stack.

Variants and alternatives

In production

• rust-analyzer parses Rust expressions with expr_bp in crates/parser/src/grammar/expressions.rs, whose own comment links matklad's Pratt article; current_op returns (binding power, kind, associativity) and right-associative operators recurse with op_bp, left-associative with op_bp + 1 (read from source, 2026-10-20).
• SQL parsers — sqlparser (sqlparser-rs, the parser of Apache DataFusion) parses expressions with parse_subexpr(precedence) and get_next_precedence, the same loop with a numeric precedence per operator (its README calls the expression parser a Pratt design).
• Clang parses binary expressions in ParseRHSOfBinaryExpression with prec:: levels (read from source, 2026-10-20).
• Lua lparser.c: subexpr(ls, v, limit) with a priority[] table of left/right pairs; ^ is {14, 13} and UNARY_PRIORITY is 12 (read from source). Same left/right-power scheme under another name.

Implementations

Sources

• Vaughan R. Pratt, Top Down Operator Precedence, POPL 1973. doi
• Alex Kladov (matklad), Simple but Powerful Pratt Parsing, 2020. read · code
• Bob Nystrom, Pratt Parsers: Expression Parsing Made Easy, 2011. read
• Douglas Crockford, Top Down Operator Precedence. read
• Theodore Norvell, Parsing Expressions by Recursive Descent. read