A Pratt parser for expressions
The grammar article put every birch operator on a precedence ladder; the
scanner article produced the flat token list. This step joins the two: by
the end, birch reads expressions and groups them correctly — 1 + 2 * 3
comes back as (1 + (2 * 3)) — and it happens without the pile of
near-identical functions that a straight recursive-descent parser needs for
this grammar. The parse result is still text; Representing a program as a
tree replaces the strings with real nodes one step from now.
Where the reader starts
Section titled “Where the reader starts”The previous step is published and tagged, so start from its end state:
git checkout interpreter-ch02cargo run -qThat prints the token table from last time. Everything this article adds
goes into the same single file, src/main.rs: the scanner stays as it is,
the parser joins it, and main changes. The scanner has exactly one line
changed — TokenKind also derives PartialEq, because the parser compares
token kinds constantly — and that is the only edit to code you have already
seen. At the end of the article, the same two commands at the
interpreter-ch03 tag print grouped expressions instead.
The ladder the grammar wants to become
Section titled “The ladder the grammar wants to become”Written as recursive descent, the expression half of the grammar turns into one function per row:
expression → assignmentassignment → IDENT "=" assignment | logicOrlogicOr → logicAnd ( "or" logicAnd )*logicAnd → equality ( "and" equality )*equality → comparison ( ( "!=" | "==" ) comparison )*comparison → term ( ( ">" | ">=" | "<" | "<=" ) term )*term → factor ( ( "+" | "-" ) factor )*factor → unary ( ( "*" | "/" | "%" ) unary )*unary → ( "!" | "-" ) unary | postfixpostfix → primary ( "(" arguments? ")" | "[" expression "]" )*Each of those functions has the same skeleton:
fn term(&mut self) -> Result<Expr, ParseError> { let mut lhs = self.factor()?; while the next token is "+" or "-" { advance; let rhs = self.factor()?; lhs = combine(lhs, op, rhs); } Ok(lhs)}factor is byte-for-byte the same shape with *, / and %.
comparison is the same shape again with four operators instead of two.
Six of the nine rows are this one function with a different operator list,
and every new operator means editing two places: the function that accepts
it and the row above that calls it. The only genuinely distinct row is
assignment, which is right-associative and only accepts a variable on its
left — the rest is scaffolding around the same loop.
A Pratt parser’s move is to notice that the differences between those functions are data: which tokens count as operators, how tightly each binds, and which side it associates towards. Write that down as a table and one loop reads it.
Binding powers
Section titled “Binding powers”The table maps a token kind to a pair of numbers, (left, right), called
binding powers. The left number answers “should I take this operator at my
current level?”, the right number answers “how tightly does its right side
bind?” — and associativity falls out of the gap between them:
Assign => (1, 0) // right-associativeOr => (2, 3)And => (3, 4)EqualEqual | BangEqual => (4, 5)Less | LessEqual | Greater | GreaterEqual => (5, 6)Plus | Minus => (6, 7)Star | Slash | Percent => (7, 8)anything else => None // not an infix operator hereFor every row except assignment, the right power is left + 1. Parsing the
right side with that higher minimum means it stops before meeting another
operator of the same row — so 10 - 4 - 3 groups as (10 - 4) - 3, which
is what subtraction means. Assignment is the one right-associative row: its
right power sits below its left, so the right side is allowed to meet
another = and keep going, and a = b = c groups as a = (b = c).
Operators missing from the table — (, [, ,, ;, a closing anything —
get None, which is how the loop knows the expression is over. The closing
parenthesis of a grouping does not end the expression by being consumed; it
ends it by not being in the table, so the recursive call unwinds and the
caller that opened the paren consumes its match.
The loop
Section titled “The loop”expression is the whole algorithm. It parses one prefix form, then loops:
look the next token up in the table, and while its left power clears the
current minimum, consume it, parse the right side, and wrap what came
before. The minimum starts at 0 — anything in the table is welcome — and
rises with every descent:
fn expression(&mut self, min_prec: u8) -> ... { let mut lhs = self.prefix()?; loop { let Some((left, right)) = binding_power(next token) else { break }; if left < min_prec { break; } advance; let rhs = self.expression(right)?; lhs = combine(lhs, op, rhs); } Ok(lhs)}Trace 1 + 2 * 3 through it: prefix gives 1; + has powers (6, 7), so
the right side is parsed at minimum 7; inside that, prefix gives 2 and
* has powers (7, 8), so 7 clears the minimum and the multiplication
is taken; the multiplication’s right side runs at minimum 8, finds 3 and
then nothing in the table. The additions and multiplications nest exactly
as the numbers dictate, and no function ever mentioned * by name.
Two forms do not go through the table at all. Calls and indexes are
postfix — they bind tighter than anything, so the loop checks for ( and
[ before consulting the table, whatever the minimum is, and keeps
checking: makeCounter(10)() is a call on a call. Grouping parentheses,
meanwhile, live in the prefix parser, and they are the cheapest case there
is: parse an expression inside, expect ), and return the inner text
unchanged — the source already supplied the grouping, and the binary reprints
supply their own.
Prefix forms and the output shape
Section titled “Prefix forms and the output shape”The prefix parser handles everything an expression can start with: the
literals, a variable, (, [, and the two unary operators. Unary is the
one place with a hand-picked number: the operand parses at a minimum above
every binding power in the table, so -n * 2 groups as ((- n) * 2) — the
minus hugs n, not the whole product.
What comes out is the expression printed back with every grouping the
parser chose made explicit. That is a deliberate stand-in, not the finish
line: the real tree is the next step’s subject. But the parser already
needs one structural fact — = is only allowed a bare variable on its
left — and a string cannot carry structure, so expression returns a bool
alongside the text, threaded through every level: true only for a prefix
variable, cleared by every operator that wraps. 1 = 2 and
tick() = 3 fail with invalid assignment target, pointed at the =.
That bool is the small, honest awkwardness that proves the point: the
parser is already dragging information about the tree through every level,
and strings are the wrong vehicle for it.
Errors: one, loud, located
Section titled “Errors: one, loud, located”The scanner collected every mistake in one pass; the parser stops at the first one. A parse error carries the line and column of the token that broke the grammar, and the message says what was expected and what was found:
1 + parse error: 1:4 expected an expression, found the end of inputOne error per run is not the long-term plan — recovering and syncing to the next statement is how a real parser survives a typo-ridden file — but recovery belongs to the statement half of the grammar, which arrives with the tree. The expression parser’s job here is to be correct first.
The whole parser
Section titled “The whole parser”This is the complete src/main.rs for this step. The scanner is unchanged
apart from the PartialEq derive; the parser and the new main are all
new:
//! birch, step 3: the expression parser.//!//! A Pratt parser: precedence is one table, not one function per level//! of the grammar. Each snippet prints back with every grouping the//! parser chose made explicit, so the parse decisions are visible.
#[derive(Debug, Clone, PartialEq)]enum TokenKind { // keywords Var, Fun, If, While, Return, True, False, Nil, And, Or, // literals Ident, Number, Str, // punctuation LeftParen, RightParen, LeftBrace, RightBrace, LeftBracket, RightBracket, Comma, Semicolon, // operators Assign, Bang, BangEqual, EqualEqual, Greater, GreaterEqual, Less, LessEqual, Plus, Minus, Star, Slash, Percent, // end of input Eof,}
#[derive(Clone)]struct Token { kind: TokenKind, lexeme: String, line: usize, col: usize,}
struct ScanError { line: usize, col: usize, message: String,}
struct Scanner { chars: Vec<char>, start: usize, // first char of the token being scanned current: usize, line: usize, col: usize, tokens: Vec<Token>, errors: Vec<ScanError>,}
impl Scanner { fn new(source: &str) -> Self { Scanner { chars: source.chars().collect(), start: 0, current: 0, line: 1, col: 1, tokens: Vec::new(), errors: Vec::new(), } }
fn scan_tokens(mut self) -> (Vec<Token>, Vec<ScanError>) { while !self.at_end() { self.start = self.current; self.scan_token(); } self.tokens.push(Token { kind: TokenKind::Eof, lexeme: String::new(), line: self.line, col: self.col, }); (self.tokens, self.errors) }
fn scan_token(&mut self) { let line = self.line; let col = self.col; let c = self.advance(); match c { '(' => self.add(TokenKind::LeftParen, line, col), ')' => self.add(TokenKind::RightParen, line, col), '{' => self.add(TokenKind::LeftBrace, line, col), '}' => self.add(TokenKind::RightBrace, line, col), '[' => self.add(TokenKind::LeftBracket, line, col), ']' => self.add(TokenKind::RightBracket, line, col), ',' => self.add(TokenKind::Comma, line, col), ';' => self.add(TokenKind::Semicolon, line, col), '+' => self.add(TokenKind::Plus, line, col), '-' => self.add(TokenKind::Minus, line, col), '*' => self.add(TokenKind::Star, line, col), '%' => self.add(TokenKind::Percent, line, col), '/' => { if self.match_next('/') { // a comment runs to the end of the line while self.peek() != Some('\n') && self.peek().is_some() { self.advance(); } } else { self.add(TokenKind::Slash, line, col); } } '=' => { let kind = if self.match_next('=') { TokenKind::EqualEqual } else { TokenKind::Assign }; self.add(kind, line, col); } '!' => { let kind = if self.match_next('=') { TokenKind::BangEqual } else { TokenKind::Bang }; self.add(kind, line, col); } '<' => { let kind = if self.match_next('=') { TokenKind::LessEqual } else { TokenKind::Less }; self.add(kind, line, col); } '>' => { let kind = if self.match_next('=') { TokenKind::GreaterEqual } else { TokenKind::Greater }; self.add(kind, line, col); } '"' => self.string(line, col), c if c.is_ascii_digit() => self.number(line, col), c if c.is_ascii_alphabetic() || c == '_' => self.identifier(line, col), c if c.is_whitespace() => { if c == '\n' { self.line += 1; self.col = 1; } } other => self.errors.push(ScanError { line, col, message: format!("unexpected character `{other}`"), }), } }
fn string(&mut self, line: usize, col: usize) { loop { match self.peek() { Some('"') => { self.advance(); self.add(TokenKind::Str, line, col); return; } Some('\n') | None => { self.errors.push(ScanError { line, col, message: String::from("unterminated string"), }); return; } Some(_) => { self.advance(); } } } }
fn number(&mut self, line: usize, col: usize) { while self.peek().is_some_and(|c| c.is_ascii_digit()) { self.advance(); } // a fraction, but only when the dot is followed by a digit: // `1.5` is one number, `1..3` is `1`, `.`, `.3` if self.peek() == Some('.') && self.peek2().is_some_and(|c| c.is_ascii_digit()) { self.advance(); // the dot while self.peek().is_some_and(|c| c.is_ascii_digit()) { self.advance(); } } self.add(TokenKind::Number, line, col); }
fn identifier(&mut self, line: usize, col: usize) { while self .peek() .is_some_and(|c| c.is_ascii_alphanumeric() || c == '_') { self.advance(); } let word: String = self.chars[self.start..self.current].iter().collect(); self.add(keyword(&word), line, col); }
// -- cursor helpers -------------------------------------------------
fn at_end(&self) -> bool { self.current >= self.chars.len() }
fn advance(&mut self) -> char { let c = self.chars[self.current]; self.current += 1; self.col += 1; c }
fn peek(&self) -> Option<char> { self.chars.get(self.current).copied() }
fn peek2(&self) -> Option<char> { self.chars.get(self.current + 1).copied() }
fn match_next(&mut self, expected: char) -> bool { if self.peek() == Some(expected) { self.advance(); true } else { false } }
fn add(&mut self, kind: TokenKind, line: usize, col: usize) { let lexeme: String = self.chars[self.start..self.current].iter().collect(); self.tokens.push(Token { kind, lexeme, line, col, }); }}
fn keyword(word: &str) -> TokenKind { match word { "var" => TokenKind::Var, "fun" => TokenKind::Fun, "if" => TokenKind::If, "while" => TokenKind::While, "return" => TokenKind::Return, "true" => TokenKind::True, "false" => TokenKind::False, "nil" => TokenKind::Nil, "and" => TokenKind::And, "or" => TokenKind::Or, _ => TokenKind::Ident, }}
// ------------------------------------------------------------ the parser
struct ParseError { line: usize, col: usize, message: String,}
struct Parser { tokens: Vec<Token>, pos: usize,}
// binds tighter than every infix operator, so `-n * 2` groups as `(-n) * 2`const UNARY: u8 = 9;
impl Parser { fn new(tokens: Vec<Token>) -> Self { Parser { tokens, pos: 0 } }
fn parse(&mut self) -> Result<String, ParseError> { let (tree, _) = self.expression(0)?; let trailing = self.advance(); if trailing.kind != TokenKind::Eof { return Err(ParseError { line: trailing.line, col: trailing.col, message: format!("unexpected `{}` after the expression", trailing.lexeme), }); } Ok(tree) }
// Returns the expression printed back with every grouping explicit, // plus whether it is a bare variable — the one thing `=` cares about. fn expression(&mut self, min_prec: u8) -> Result<(String, bool), ParseError> { let (mut lhs, mut is_var) = self.prefix()?; loop { // calls and indexes bind tighter than anything in the table: // they hug whatever is on their left, whatever the minimum match self.peek().kind { TokenKind::LeftParen => { self.pos += 1; let mut args = Vec::new(); if self.peek().kind != TokenKind::RightParen { loop { args.push(self.expression(0)?.0); if !self.match_kind(TokenKind::Comma) { break; } } } self.expect(TokenKind::RightParen, "`)`")?; lhs = format!("({lhs}({}))", args.join(", ")); is_var = false; continue; } TokenKind::LeftBracket => { self.pos += 1; let index = self.expression(0)?.0; self.expect(TokenKind::RightBracket, "`]`")?; lhs = format!("({lhs}[{index}])"); is_var = false; continue; } _ => {} } let Some((left, right)) = self.infix_binding_power() else { break; }; if left < min_prec { break; } let op = self.advance(); if op.kind == TokenKind::Assign && !is_var { return Err(ParseError { line: op.line, col: op.col, message: String::from("invalid assignment target"), }); } let rhs = self.expression(right)?.0; lhs = format!("({lhs} {} {rhs})", op.lexeme); is_var = false; } Ok((lhs, is_var)) }
// Infix binding powers, lowest row first. A pair is (left, right): // parsing the right side with `right` as its minimum is what makes // associativity work. `left + 1` stops the right side before another // operator of the same row — left-associative. `=` is the one // right-associative operator, so its right power sits below its left. fn infix_binding_power(&self) -> Option<(u8, u8)> { Some(match self.peek().kind { TokenKind::Assign => (1, 0), TokenKind::Or => (2, 3), TokenKind::And => (3, 4), TokenKind::EqualEqual | TokenKind::BangEqual => (4, 5), TokenKind::Less | TokenKind::LessEqual | TokenKind::Greater | TokenKind::GreaterEqual => (5, 6), TokenKind::Plus | TokenKind::Minus => (6, 7), TokenKind::Star | TokenKind::Slash | TokenKind::Percent => (7, 8), _ => return None, }) }
fn prefix(&mut self) -> Result<(String, bool), ParseError> { let token = self.advance(); match token.kind { TokenKind::Ident => Ok((token.lexeme, true)), TokenKind::Number | TokenKind::Str | TokenKind::True | TokenKind::False | TokenKind::Nil => Ok((token.lexeme, false)), TokenKind::Minus | TokenKind::Bang => { let operand = self.expression(UNARY)?.0; Ok((format!("({} {operand})", token.lexeme), false)) } TokenKind::LeftParen => { let inner = self.expression(0)?.0; self.expect(TokenKind::RightParen, "`)`")?; Ok((inner, false)) } TokenKind::LeftBracket => { let mut items = Vec::new(); if self.peek().kind != TokenKind::RightBracket { loop { items.push(self.expression(0)?.0); if !self.match_kind(TokenKind::Comma) { break; } } } self.expect(TokenKind::RightBracket, "`]`")?; Ok((format!("([{}])", items.join(", ")), false)) } _ => Err(ParseError { line: token.line, col: token.col, message: if token.kind == TokenKind::Eof { String::from("expected an expression, found the end of input") } else { format!("expected an expression, found `{}`", token.lexeme) }, }), } }
fn peek(&self) -> &Token { &self.tokens[self.pos] }
fn advance(&mut self) -> Token { let token = self.tokens[self.pos].clone(); if token.kind != TokenKind::Eof { self.pos += 1; } token }
fn match_kind(&mut self, kind: TokenKind) -> bool { if self.peek().kind == kind { self.pos += 1; true } else { false } }
fn expect(&mut self, kind: TokenKind, what: &str) -> Result<(), ParseError> { let token = self.advance(); if token.kind == kind { return Ok(()); } let message = if token.kind == TokenKind::Eof { format!("expected {what}, found the end of input") } else { format!("expected {what}, found `{}`", token.lexeme) }; Err(ParseError { line: token.line, col: token.col, message, }) }}
fn main() { let snippets = [ "1 + 2 * 3", "(1 + 2) * 3", "10 - 4 - 3", "-n * 2", "!done and count < 10", "n = n + 1", "names[i + 1]", "makeCounter(10)()", "1 +", "1 = 2", ];
for source in snippets { println!("{source}"); let (tokens, errors) = Scanner::new(source).scan_tokens(); if !errors.is_empty() { for e in &errors { println!(" scan error: {}:{} {}", e.line, e.col, e.message); } continue; } match Parser::new(tokens).parse() { Ok(tree) => println!(" = {tree}"), Err(e) => println!(" parse error: {}:{} {}", e.line, e.col, e.message), } }}Running it
Section titled “Running it”Each snippet prints the expression back with every grouping explicit, or a located error:
cargo run -q1 + 2 * 3 = (1 + (2 * 3))(1 + 2) * 3 = ((1 + 2) * 3)10 - 4 - 3 = ((10 - 4) - 3)-n * 2 = ((- n) * 2)!done and count < 10 = ((! done) and (count < 10))n = n + 1 = (n = (n + 1))names[i + 1] = (names[(i + 1)])makeCounter(10)() = ((makeCounter(10))())1 + parse error: 1:4 expected an expression, found the end of input1 = 2 parse error: 1:3 invalid assignment targetCheck the ones that look boring. 10 - 4 - 3 groups left, because the
right side parsed at left + 1 refused the second -. (1 + 2) * 3
needed no new parentheses around the group — the source provided them, and
the loop’s reprint wrapped the rest. And -n * 2 put the minus inside the
product, purely because the unary operand parsed above every binding power
in the table.
Where this leaves the track
Section titled “Where this leaves the track”The tree at interpreter-ch03 contains a cargo project that scans and
parses expressions — correctly, with positions on every error — and proves
the grouping by printing it. The strings are scaffolding, and the next
step, Representing a program as a tree, tears them out: one enum per
node, Box exactly where the grammar recurses, and the statement half of
the grammar arriving as more variants. Until then, the
track overview has the full itinerary.