Precedence Without a Grammar Table: Building a Pratt Parser Step by Step

pratt-parser/src/main.rs — 201 lines

//! Scene 04: proof. Both parsers live in one binary — `descent.rs`
//! and `pratt.rs` are byte-identical copies of the two crates'
//! `parser.rs` (sha256 them). The table makes precedence visible; the
//! fuzz run turns "the parsers agree" into a number.

mod ast;
mod descent;
mod generate;
mod lexer;
mod pratt;

use anyhow::{Error, Result, ensure};
use clap::{Parser, Subcommand};
use std::time::Instant;

use crate::{
    ast::Expr,
    generate::Generator,
    lexer::{SpanError, render_caret},
};

/// The demo set: the same list feeds the descent crate, the Pratt
/// crate and the proof binary, so the cost columns stay comparable.
const DEMO: &[&str] = &[
    "42",
    "((((((((42))))))))",
    "price * qty > limit && region == \"eu\"",
    "a + b * c",
    "(a + b) * c",
    "2 ** 3 ** 2",
    "-2 ** 2",
    "2 ** -3",
    "!paid || price - fee < 0",
    "primary ?? fallback ?? 0",
    "a < b == c < d",
    "price * (qty - 1) ** 2 / rate",
];

/// Compare the descent and the Pratt parser on identical inputs.
#[derive(Parser)]
struct Args {
    #[command(subcommand)]
    command: Command,
}

#[derive(Subcommand)]
enum Command {
    /// Both parsers over the demo set: s-expressions must be identical
    Table,
    /// Generated expressions: identical ASTs required on every input
    Fuzz {
        /// How many expressions to generate
        #[arg(long, default_value_t = 100_000)]
        count: u64,
        /// Seed for the xorshift stream
        #[arg(long, default_value_t = 0x2A11)]
        seed: u64,
        /// Maximum structural nesting of generated expressions
        #[arg(long, default_value_t = 4)]
        depth: u32,
    },
}

fn main() -> Result<()> {
    match Args::parse().command {
        Command::Table => table(),
        Command::Fuzz { count, seed, depth } => fuzz(count, seed, depth),
    }
}

/// The dozen expressions of the article, through both parsers at once.
fn table() -> Result<()> {
    println!(
        "{:<38}  {:<46} {:>10} {:>8}",
        "expr", "s-expr (identical from both parsers)", "descent", "pratt"
    );
    for src in DEMO {
        let (descent_expr, descent_stats) = descent::parse(src)?;
        let (pratt_expr, pratt_stats) = pratt::parse(src)?;
        let form = descent_expr.to_sexpr();
        ensure!(
            descent_expr == pratt_expr,
            "{src}: descent {form} vs pratt {}",
            pratt_expr.to_sexpr()
        );
        let descent_cost = format!("{}/{}", descent_stats.calls, descent_stats.max_depth);
        let pratt_cost = format!("{}/{}", pratt_stats.calls, pratt_stats.max_depth);
        println!("{src:<38}  {form:<46} {descent_cost:>10} {pratt_cost:>8}");
    }
    println!();
    println!(
        "{} expressions, every AST identical; cost columns are calls/depth",
        DEMO.len()
    );
    Ok(())
}

/// Totals of one parser over a whole corpus.
struct CorpusRun {
    trees: Vec<Expr>,
    calls: u64,
    max_depth: u64,
    elapsed_ms: f64,
}

fn run_corpus(
    name: &str,
    sources: &[String],
    parse: fn(&str) -> Result<(Expr, descent::ParseStats)>,
) -> Result<CorpusRun> {
    let started = Instant::now();
    let mut trees = Vec::with_capacity(sources.len());
    let mut calls = 0;
    let mut max_depth = 0;
    for src in sources {
        let (expr, stats) = match parse(src) {
            Ok(pair) => pair,
            Err(error) => return Err(annotate(name, src, error)),
        };
        calls += stats.calls;
        max_depth = max_depth.max(stats.max_depth);
        trees.push(expr);
    }
    let elapsed_ms = started.elapsed().as_secs_f64() * 1e3;
    Ok(CorpusRun {
        trees,
        calls,
        max_depth,
        elapsed_ms,
    })
}

/// A parser refusing a generated input is a bug worth a caret.
fn annotate(name: &str, src: &str, error: Error) -> Error {
    let span = error
        .downcast_ref::<SpanError>()
        .map(|span_error| span_error.span);
    match span {
        Some(span) => error.context(format!(
            "{name} refused a generated input:\n{}",
            render_caret(src, span)
        )),
        None => error.context(format!("{name} refused a generated input: {src}")),
    }
}

/// M random expressions; the two parsers must produce M equal trees.
fn fuzz(count: u64, seed: u64, depth: u32) -> Result<()> {
    ensure!(count > 0, "count must be greater than zero");
    let mut generator = Generator::new(seed);
    let sources: Vec<String> = (0..count).map(|_| generator.expr(depth)).collect();
    let bytes: usize = sources.iter().map(String::len).sum();
    println!("seed {seed:#x}, nesting <= {depth}: {count} generated expressions, {bytes} bytes");

    let descent_run = run_corpus("descent", &sources, descent_parse)?;
    println!(
        "descent: {count} parsed, {} parse calls, deepest recursion {}, {:.0} ms",
        descent_run.calls, descent_run.max_depth, descent_run.elapsed_ms
    );
    let pratt_run = run_corpus("pratt", &sources, pratt_parse)?;
    println!(
        "pratt:   {count} parsed, {} parse calls, deepest recursion {}, {:.0} ms",
        pratt_run.calls, pratt_run.max_depth, pratt_run.elapsed_ms
    );

    let mut mismatches = 0;
    for (index, (descent_tree, pratt_tree)) in
        descent_run.trees.iter().zip(&pratt_run.trees).enumerate()
    {
        if descent_tree != pratt_tree {
            mismatches += 1;
            println!("mismatch on {}:", sources[index]);
            println!("  descent: {}", descent_tree.to_sexpr());
            println!("  pratt:   {}", pratt_tree.to_sexpr());
        }
    }
    ensure!(mismatches == 0, "{mismatches} mismatching ASTs");
    println!("verdict: identical ASTs on all {count} inputs, {mismatches} mismatches");
    println!(
        "ladder tax: {:.2}x parse calls for the same trees",
        descent_run.calls as f64 / pratt_run.calls as f64
    );
    Ok(())
}

/// Both parsers export the same shape; these two wrappers only exist
/// because each module declares its own `ParseStats` twin.
fn descent_parse(src: &str) -> Result<(Expr, descent::ParseStats)> {
    descent::parse(src)
}

fn pratt_parse(src: &str) -> Result<(Expr, descent::ParseStats)> {
    let (expr, stats) = pratt::parse(src)?;
    Ok((
        expr,
        descent::ParseStats {
            calls: stats.calls,
            max_depth: stats.max_depth,
        },
    ))
}

pratt-parser/src/lexer.rs — 246 lines

//! Lexer for the expression language: every token carries a byte span.
//!
//! Spans are the running theme of the whole box. The lexer is the only
//! stage that sees source offsets, so it must record them here — no
//! later stage can restore a position the lexer dropped. A token is a
//! kind plus a span; the text itself stays in the source string.

use anyhow::{Error, Result, anyhow, ensure};
use std::fmt::{self, Display, Formatter};
use strum::Display as StrumDisplay;
use thiserror::Error as ThisError;

/// Byte range `start..end` of a token inside the source line.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Span {
    pub start: usize,
    pub end: usize,
}

impl Display for Span {
    fn fmt(&self, formatter: &mut Formatter<'_>) -> fmt::Result {
        // `pad` keeps table columns honest when a width is requested.
        formatter.pad(&format!("{}..{}", self.start, self.end))
    }
}

/// An error that knows which bytes it is about. Both the lexer and the
/// parsers build their errors through this type, so every message in
/// the pipeline can point back at the offending character.
#[derive(Debug, ThisError)]
#[error("{message} at bytes {span}")]
pub struct SpanError {
    pub message: String,
    pub span: Span,
}

/// Shorthand: an `anyhow` error carrying a span, downcastable later.
pub fn spanned(message: impl Into<String>, span: Span) -> Error {
    anyhow!(SpanError {
        message: message.into(),
        span
    })
}

/// Two lines for a terminal: the source and a caret run under the span.
pub fn render_caret(src: &str, span: Span) -> String {
    let width = span.end.saturating_sub(span.start).max(1);
    let pad = " ".repeat(span.start);
    let carets = "^".repeat(width);
    format!("  {src}\n  {pad}{carets} bytes {span}")
}

/// Everything the language can spell. `Display` prints the surface form.
#[derive(Debug, Clone, Copy, PartialEq, Eq, StrumDisplay)]
pub enum TokenKind {
    #[strum(serialize = "number")]
    Number,
    #[strum(serialize = "string")]
    Str,
    #[strum(serialize = "ident")]
    Ident,
    #[strum(serialize = "||")]
    OrOr,
    #[strum(serialize = "&&")]
    AndAnd,
    #[strum(serialize = "??")]
    QuestionQuestion,
    #[strum(serialize = "==")]
    EqEq,
    #[strum(serialize = "!=")]
    BangEq,
    #[strum(serialize = "<")]
    Lt,
    #[strum(serialize = "<=")]
    LtEq,
    #[strum(serialize = ">")]
    Gt,
    #[strum(serialize = ">=")]
    GtEq,
    #[strum(serialize = "+")]
    Plus,
    #[strum(serialize = "-")]
    Minus,
    #[strum(serialize = "*")]
    Star,
    #[strum(serialize = "/")]
    Slash,
    #[strum(serialize = "%")]
    Percent,
    #[strum(serialize = "**")]
    StarStar,
    #[strum(serialize = "!")]
    Bang,
    #[strum(serialize = "(")]
    LParen,
    #[strum(serialize = ")")]
    RParen,
}

/// A token: what it is and where it sits. Nothing else — the text is a
/// slice of the source, recoverable from the span at any time.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Token {
    pub kind: TokenKind,
    pub span: Span,
}

/// Tokenize one source line. ASCII only, so byte offsets are also
/// column numbers — one less thing between a span and a caret.
pub fn lex(src: &str) -> Result<Vec<Token>> {
    ensure!(src.is_ascii(), "only ascii input is supported in this demo");
    let bytes = src.as_bytes();
    let mut tokens = Vec::new();
    let mut pos = 0;
    while pos < bytes.len() {
        let start = pos;
        let byte = bytes[pos];
        let kind = match byte {
            b' ' | b'\t' => {
                pos += 1;
                continue;
            }
            b'0'..=b'9' => {
                pos = scan_number(bytes, pos);
                TokenKind::Number
            }
            b'a'..=b'z' | b'A'..=b'Z' | b'_' => {
                pos = scan_ident(bytes, pos);
                TokenKind::Ident
            }
            b'"' => {
                pos = scan_string(bytes, pos)?;
                TokenKind::Str
            }
            // These four operators only exist doubled: || && ?? ==
            b'|' | b'&' | b'?' | b'=' => {
                if bytes.get(pos + 1) != Some(&byte) {
                    let span = Span {
                        start,
                        end: start + 1,
                    };
                    let symbol = byte as char;
                    return Err(spanned(format!("unexpected character '{symbol}'"), span));
                }
                pos += 2;
                match byte {
                    b'|' => TokenKind::OrOr,
                    b'&' => TokenKind::AndAnd,
                    b'?' => TokenKind::QuestionQuestion,
                    _ => TokenKind::EqEq,
                }
            }
            b'!' => two_or_one(bytes, &mut pos, b'=', TokenKind::BangEq, TokenKind::Bang),
            b'<' => two_or_one(bytes, &mut pos, b'=', TokenKind::LtEq, TokenKind::Lt),
            b'>' => two_or_one(bytes, &mut pos, b'=', TokenKind::GtEq, TokenKind::Gt),
            b'*' => two_or_one(bytes, &mut pos, b'*', TokenKind::StarStar, TokenKind::Star),
            b'+' => single(&mut pos, TokenKind::Plus),
            b'-' => single(&mut pos, TokenKind::Minus),
            b'/' => single(&mut pos, TokenKind::Slash),
            b'%' => single(&mut pos, TokenKind::Percent),
            b'(' => single(&mut pos, TokenKind::LParen),
            b')' => single(&mut pos, TokenKind::RParen),
            other => {
                let span = Span {
                    start,
                    end: start + 1,
                };
                let symbol = other as char;
                return Err(spanned(format!("unexpected character '{symbol}'"), span));
            }
        };
        tokens.push(Token {
            kind,
            span: Span { start, end: pos },
        });
    }
    Ok(tokens)
}

fn single(pos: &mut usize, kind: TokenKind) -> TokenKind {
    *pos += 1;
    kind
}

/// `<=`-style pairs: consume two bytes when the second matches.
fn two_or_one(
    bytes: &[u8],
    pos: &mut usize,
    second: u8,
    pair: TokenKind,
    one: TokenKind,
) -> TokenKind {
    if bytes.get(*pos + 1) == Some(&second) {
        *pos += 2;
        return pair;
    }
    *pos += 1;
    one
}

fn scan_digits(bytes: &[u8], mut pos: usize) -> usize {
    while pos < bytes.len() && bytes[pos].is_ascii_digit() {
        pos += 1;
    }
    pos
}

/// Digits, then optionally `.` followed by at least one digit.
fn scan_number(bytes: &[u8], pos: usize) -> usize {
    let mut pos = scan_digits(bytes, pos);
    let dot = bytes.get(pos) == Some(&b'.');
    if dot && bytes.get(pos + 1).is_some_and(|byte| byte.is_ascii_digit()) {
        pos = scan_digits(bytes, pos + 2);
    }
    pos
}

fn scan_ident(bytes: &[u8], mut pos: usize) -> usize {
    while pos < bytes.len() {
        let byte = bytes[pos];
        let tail = byte.is_ascii_alphanumeric() || byte == b'_';
        if !tail {
            break;
        }
        pos += 1;
    }
    pos
}

/// From the opening quote to just past the closing one. No escapes in
/// this language; an unterminated literal is an error with a span that
/// covers everything the string swallowed.
fn scan_string(bytes: &[u8], start: usize) -> Result<usize> {
    let mut pos = start + 1;
    while pos < bytes.len() {
        if bytes[pos] == b'"' {
            return Ok(pos + 1);
        }
        pos += 1;
    }
    let span = Span {
        start,
        end: bytes.len(),
    };
    Err(spanned("unterminated string literal", span))
}

pratt-parser/src/ast.rs — 102 lines

//! The AST and its parenthesized (s-expression) form.
//!
//! `to_sexpr` is the proof format of this demo: every precedence and
//! associativity decision becomes a visible parenthesis. Two parsers
//! agree exactly when their s-expressions match byte for byte.

use strum::Display;

/// Prefix operators.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Display)]
pub enum UnaryOp {
    #[strum(serialize = "-")]
    Neg,
    #[strum(serialize = "!")]
    Not,
}

/// Infix operators, printed exactly as written in the source.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Display)]
pub enum BinaryOp {
    #[strum(serialize = "??")]
    Coalesce,
    #[strum(serialize = "||")]
    Or,
    #[strum(serialize = "&&")]
    And,
    #[strum(serialize = "==")]
    Eq,
    #[strum(serialize = "!=")]
    Ne,
    #[strum(serialize = "<")]
    Lt,
    #[strum(serialize = "<=")]
    Le,
    #[strum(serialize = ">")]
    Gt,
    #[strum(serialize = ">=")]
    Ge,
    #[strum(serialize = "+")]
    Add,
    #[strum(serialize = "-")]
    Sub,
    #[strum(serialize = "*")]
    Mul,
    #[strum(serialize = "/")]
    Div,
    #[strum(serialize = "%")]
    Rem,
    #[strum(serialize = "**")]
    Pow,
}

/// Expression tree. Grouping parens do not survive parsing: structure
/// is the only thing the tree remembers, which is the whole point.
#[derive(Debug, Clone, PartialEq)]
pub enum Expr {
    /// Numeric literal kept as source text: `2.50` stays `2.50`.
    Number(String),
    /// String literal without its quotes.
    Str(String),
    /// A name to be resolved against a context at evaluation time.
    Ident(String),
    Unary {
        op: UnaryOp,
        expr: Box<Expr>,
    },
    Binary {
        op: BinaryOp,
        left: Box<Expr>,
        right: Box<Expr>,
    },
}

pub fn unary(op: UnaryOp, expr: Expr) -> Expr {
    Expr::Unary {
        op,
        expr: Box::new(expr),
    }
}

pub fn binary(op: BinaryOp, left: Expr, right: Expr) -> Expr {
    Expr::Binary {
        op,
        left: Box::new(left),
        right: Box::new(right),
    }
}

impl Expr {
    /// Lisp-style prefix form: `(&& (> (* price qty) limit) ...)`.
    pub fn to_sexpr(&self) -> String {
        match self {
            Expr::Number(text) => text.clone(),
            Expr::Str(text) => format!("\"{text}\""),
            Expr::Ident(name) => name.clone(),
            Expr::Unary { op, expr } => format!("({op} {})", expr.to_sexpr()),
            Expr::Binary { op, left, right } => {
                format!("({op} {} {})", left.to_sexpr(), right.to_sexpr())
            }
        }
    }
}

pratt-parser/src/descent.rs — 277 lines

//! Recursive descent: the grammar table spelled as a ladder of functions.
//!
//! One function per precedence level. Each level first parses the
//! next-tighter level, then loops on its own operators. The entry point
//! is the loosest level, so every atom — even a bare `42` — pays a full
//! trip down all the rungs. The counters below make that cost a number.

use crate::{
    ast::{BinaryOp, Expr, UnaryOp, binary, unary},
    lexer::{Span, Token, TokenKind, lex, spanned},
};
use anyhow::{Error, Result};

/// Counters filled while parsing: how much work the *shape* of the
/// parser causes, separately from the size of the input.
#[derive(Debug, Clone, Copy)]
pub struct ParseStats {
    /// Parse-function invocations.
    pub calls: u64,
    /// Deepest recursion reached (the entry function is depth 1).
    pub max_depth: u64,
}

/// Parse one source line into an expression tree.
pub fn parse(src: &str) -> Result<(Expr, ParseStats)> {
    let tokens = lex(src)?;
    let mut parser = Parser {
        src,
        tokens: &tokens,
        pos: 0,
        calls: 0,
        max_depth: 0,
    };
    let expr = parser.parse_coalesce(1)?;
    parser.expect_end()?;
    let stats = ParseStats {
        calls: parser.calls,
        max_depth: parser.max_depth,
    };
    Ok((expr, stats))
}

struct Parser<'a> {
    src: &'a str,
    tokens: &'a [Token],
    pos: usize,
    calls: u64,
    max_depth: u64,
}

impl Parser<'_> {
    // --- the ladder: one function per precedence level ---------------

    /// Level 1: `??` — right-associative through self-recursion.
    fn parse_coalesce(&mut self, depth: u64) -> Result<Expr> {
        self.note(depth);
        let left = self.parse_or(depth + 1)?;
        if self.eat(TokenKind::QuestionQuestion) {
            let right = self.parse_coalesce(depth + 1)?;
            return Ok(binary(BinaryOp::Coalesce, left, right));
        }
        Ok(left)
    }

    /// Level 2: `||`.
    fn parse_or(&mut self, depth: u64) -> Result<Expr> {
        self.note(depth);
        let mut left = self.parse_and(depth + 1)?;
        while self.eat(TokenKind::OrOr) {
            let right = self.parse_and(depth + 1)?;
            left = binary(BinaryOp::Or, left, right);
        }
        Ok(left)
    }

    /// Level 3: `&&`.
    fn parse_and(&mut self, depth: u64) -> Result<Expr> {
        self.note(depth);
        let mut left = self.parse_equality(depth + 1)?;
        while self.eat(TokenKind::AndAnd) {
            let right = self.parse_equality(depth + 1)?;
            left = binary(BinaryOp::And, left, right);
        }
        Ok(left)
    }

    /// Level 4: `==` and `!=`.
    fn parse_equality(&mut self, depth: u64) -> Result<Expr> {
        self.note(depth);
        let mut left = self.parse_comparison(depth + 1)?;
        loop {
            let op = if self.eat(TokenKind::EqEq) {
                BinaryOp::Eq
            } else if self.eat(TokenKind::BangEq) {
                BinaryOp::Ne
            } else {
                return Ok(left);
            };
            let right = self.parse_comparison(depth + 1)?;
            left = binary(op, left, right);
        }
    }

    /// Level 5: `<`, `<=`, `>`, `>=`.
    fn parse_comparison(&mut self, depth: u64) -> Result<Expr> {
        self.note(depth);
        let mut left = self.parse_additive(depth + 1)?;
        loop {
            let op = if self.eat(TokenKind::Lt) {
                BinaryOp::Lt
            } else if self.eat(TokenKind::LtEq) {
                BinaryOp::Le
            } else if self.eat(TokenKind::Gt) {
                BinaryOp::Gt
            } else if self.eat(TokenKind::GtEq) {
                BinaryOp::Ge
            } else {
                return Ok(left);
            };
            let right = self.parse_additive(depth + 1)?;
            left = binary(op, left, right);
        }
    }

    /// Level 6: `+` and `-`.
    fn parse_additive(&mut self, depth: u64) -> Result<Expr> {
        self.note(depth);
        let mut left = self.parse_multiplicative(depth + 1)?;
        loop {
            let op = if self.eat(TokenKind::Plus) {
                BinaryOp::Add
            } else if self.eat(TokenKind::Minus) {
                BinaryOp::Sub
            } else {
                return Ok(left);
            };
            let right = self.parse_multiplicative(depth + 1)?;
            left = binary(op, left, right);
        }
    }

    /// Level 7: `*`, `/`, `%`.
    fn parse_multiplicative(&mut self, depth: u64) -> Result<Expr> {
        self.note(depth);
        let mut left = self.parse_unary(depth + 1)?;
        loop {
            let op = if self.eat(TokenKind::Star) {
                BinaryOp::Mul
            } else if self.eat(TokenKind::Slash) {
                BinaryOp::Div
            } else if self.eat(TokenKind::Percent) {
                BinaryOp::Rem
            } else {
                return Ok(left);
            };
            let right = self.parse_unary(depth + 1)?;
            left = binary(op, left, right);
        }
    }

    /// Level 8: prefix `-` and `!`; stacked prefixes recurse here.
    fn parse_unary(&mut self, depth: u64) -> Result<Expr> {
        self.note(depth);
        let op = if self.eat(TokenKind::Minus) {
            Some(UnaryOp::Neg)
        } else if self.eat(TokenKind::Bang) {
            Some(UnaryOp::Not)
        } else {
            None
        };
        match op {
            Some(op) => Ok(unary(op, self.parse_unary(depth + 1)?)),
            None => self.parse_power(depth + 1),
        }
    }

    /// Level 9: `**` — right-associative, and its right side may carry
    /// a fresh sign, so `-2 ** 2` is `-(2 ** 2)` and `2 ** -3` works.
    fn parse_power(&mut self, depth: u64) -> Result<Expr> {
        self.note(depth);
        let left = self.parse_primary(depth + 1)?;
        if self.eat(TokenKind::StarStar) {
            let right = self.parse_unary(depth + 1)?;
            return Ok(binary(BinaryOp::Pow, left, right));
        }
        Ok(left)
    }

    /// Level 10: atoms, plus grouping parens that restart the ladder.
    fn parse_primary(&mut self, depth: u64) -> Result<Expr> {
        self.note(depth);
        let token = self.advance()?;
        match token.kind {
            TokenKind::Number => Ok(Expr::Number(self.slice(token.span).to_string())),
            TokenKind::Str => Ok(Expr::Str(self.inner_str(token.span))),
            TokenKind::Ident => Ok(Expr::Ident(self.slice(token.span).to_string())),
            TokenKind::LParen => {
                let expr = self.parse_coalesce(depth + 1)?;
                self.expect(TokenKind::RParen)?;
                Ok(expr)
            }
            kind => Err(spanned(
                format!("expected an expression, found '{kind}'"),
                token.span,
            )),
        }
    }

    // --- shared plumbing ----------------------------------------------

    fn note(&mut self, depth: u64) {
        self.calls += 1;
        self.max_depth = self.max_depth.max(depth);
    }

    fn peek(&self) -> Option<Token> {
        self.tokens.get(self.pos).copied()
    }

    fn advance(&mut self) -> Result<Token> {
        let token = self.peek().ok_or_else(|| self.end_of_input())?;
        self.pos += 1;
        Ok(token)
    }

    fn eat(&mut self, kind: TokenKind) -> bool {
        if self.peek().is_some_and(|token| token.kind == kind) {
            self.pos += 1;
            return true;
        }
        false
    }

    fn expect(&mut self, kind: TokenKind) -> Result<()> {
        match self.peek() {
            Some(token) if token.kind == kind => {
                self.pos += 1;
                Ok(())
            }
            Some(token) => Err(spanned(
                format!("expected '{kind}', found '{}'", self.slice(token.span)),
                token.span,
            )),
            None => Err(self.end_of_input()),
        }
    }

    fn expect_end(&mut self) -> Result<()> {
        match self.peek() {
            None => Ok(()),
            Some(token) => Err(spanned(
                format!(
                    "unexpected trailing input starting with '{}'",
                    self.slice(token.span)
                ),
                token.span,
            )),
        }
    }

    fn end_of_input(&self) -> Error {
        let end = Span {
            start: self.src.len(),
            end: self.src.len(),
        };
        spanned("unexpected end of input", end)
    }

    fn slice(&self, span: Span) -> &str {
        &self.src[span.start..span.end]
    }

    /// String literal text without the surrounding quotes.
    fn inner_str(&self, span: Span) -> String {
        self.src[span.start + 1..span.end - 1].to_string()
    }
}

pratt-parser/src/pratt.rs — 180 lines

//! Pratt parsing: one function and a table of binding powers.
//!
//! `parse_expr(min_bp)` replaces the whole ladder. The loop keeps
//! consuming operators while they bind at least as tightly as the
//! caller allows; recursing with the operator's right power decides
//! associativity. Precedence lives in one table, not in call structure.

use crate::{
    ast::{BinaryOp, Expr, UnaryOp, binary, unary},
    lexer::{Span, Token, TokenKind, lex, spanned},
};
use anyhow::{Error, Result};

/// Counters filled while parsing: same meaning as in the descent
/// crate, so the two parsers can be compared number to number.
#[derive(Debug, Clone, Copy)]
pub struct ParseStats {
    /// Parse-function invocations.
    pub calls: u64,
    /// Deepest recursion reached (the entry function is depth 1).
    pub max_depth: u64,
}

/// Prefix `-` and `!` bind tighter than `*` but looser than the left
/// side of `**`, so `-2 ** 2` reads as `-(2 ** 2)` — same as descent.
const PREFIX_BP: u8 = 15;

/// The whole grammar table: an operator, how hard it holds its left
/// operand and how hard it holds its right one. Left < right makes the
/// operator left-associative; `??` and `**` flip the pair and become
/// right-associative. Adding an operator is adding one row.
fn binding_power(kind: TokenKind) -> Option<(BinaryOp, u8, u8)> {
    let row = match kind {
        TokenKind::QuestionQuestion => (BinaryOp::Coalesce, 2, 1),
        TokenKind::OrOr => (BinaryOp::Or, 3, 4),
        TokenKind::AndAnd => (BinaryOp::And, 5, 6),
        TokenKind::EqEq => (BinaryOp::Eq, 7, 8),
        TokenKind::BangEq => (BinaryOp::Ne, 7, 8),
        TokenKind::Lt => (BinaryOp::Lt, 9, 10),
        TokenKind::LtEq => (BinaryOp::Le, 9, 10),
        TokenKind::Gt => (BinaryOp::Gt, 9, 10),
        TokenKind::GtEq => (BinaryOp::Ge, 9, 10),
        TokenKind::Plus => (BinaryOp::Add, 11, 12),
        TokenKind::Minus => (BinaryOp::Sub, 11, 12),
        TokenKind::Star => (BinaryOp::Mul, 13, 14),
        TokenKind::Slash => (BinaryOp::Div, 13, 14),
        TokenKind::Percent => (BinaryOp::Rem, 13, 14),
        TokenKind::StarStar => (BinaryOp::Pow, 16, 15),
        _ => return None,
    };
    Some(row)
}

/// Parse one source line into an expression tree.
pub fn parse(src: &str) -> Result<(Expr, ParseStats)> {
    let tokens = lex(src)?;
    let mut parser = Parser {
        src,
        tokens: &tokens,
        pos: 0,
        calls: 0,
        max_depth: 0,
    };
    let expr = parser.parse_expr(0, 1)?;
    parser.expect_end()?;
    let stats = ParseStats {
        calls: parser.calls,
        max_depth: parser.max_depth,
    };
    Ok((expr, stats))
}

struct Parser<'a> {
    src: &'a str,
    tokens: &'a [Token],
    pos: usize,
    calls: u64,
    max_depth: u64,
}

impl Parser<'_> {
    /// The single parse function: a prefix position, then a loop that
    /// takes every operator binding at least as hard as `min_bp`.
    fn parse_expr(&mut self, min_bp: u8, depth: u64) -> Result<Expr> {
        self.note(depth);
        let token = self.advance()?;
        let mut left = match token.kind {
            TokenKind::Number => Expr::Number(self.slice(token.span).to_string()),
            TokenKind::Str => Expr::Str(self.inner_str(token.span)),
            TokenKind::Ident => Expr::Ident(self.slice(token.span).to_string()),
            TokenKind::Minus => unary(UnaryOp::Neg, self.parse_expr(PREFIX_BP, depth + 1)?),
            TokenKind::Bang => unary(UnaryOp::Not, self.parse_expr(PREFIX_BP, depth + 1)?),
            TokenKind::LParen => {
                let inner = self.parse_expr(0, depth + 1)?;
                self.expect(TokenKind::RParen)?;
                inner
            }
            kind => {
                return Err(spanned(
                    format!("expected an expression, found '{kind}'"),
                    token.span,
                ));
            }
        };
        loop {
            let Some(next) = self.peek() else { break };
            let Some((op, left_bp, right_bp)) = binding_power(next.kind) else {
                break;
            };
            if left_bp < min_bp {
                break;
            }
            self.pos += 1;
            let right = self.parse_expr(right_bp, depth + 1)?;
            left = binary(op, left, right);
        }
        Ok(left)
    }

    // --- shared plumbing ----------------------------------------------

    fn note(&mut self, depth: u64) {
        self.calls += 1;
        self.max_depth = self.max_depth.max(depth);
    }

    fn peek(&self) -> Option<Token> {
        self.tokens.get(self.pos).copied()
    }

    fn advance(&mut self) -> Result<Token> {
        let token = self.peek().ok_or_else(|| self.end_of_input())?;
        self.pos += 1;
        Ok(token)
    }

    fn expect(&mut self, kind: TokenKind) -> Result<()> {
        match self.peek() {
            Some(token) if token.kind == kind => {
                self.pos += 1;
                Ok(())
            }
            Some(token) => Err(spanned(
                format!("expected '{kind}', found '{}'", self.slice(token.span)),
                token.span,
            )),
            None => Err(self.end_of_input()),
        }
    }

    fn expect_end(&mut self) -> Result<()> {
        match self.peek() {
            None => Ok(()),
            Some(token) => Err(spanned(
                format!(
                    "unexpected trailing input starting with '{}'",
                    self.slice(token.span)
                ),
                token.span,
            )),
        }
    }

    fn end_of_input(&self) -> Error {
        let end = Span {
            start: self.src.len(),
            end: self.src.len(),
        };
        spanned("unexpected end of input", end)
    }

    fn slice(&self, span: Span) -> &str {
        &self.src[span.start..span.end]
    }

    /// String literal text without the surrounding quotes.
    fn inner_str(&self, span: Span) -> String {
        self.src[span.start + 1..span.end - 1].to_string()
    }
}