Expression Parser

A Pratt parser (top-down operator precedence parser) parses expressions with arbitrary precedence levels, prefix unary operators (-x), and both left-associative (+, -, *, /) and right-associative (^ exponentiation) binary operators using a single parameterized recursion parse_bp(min_bp: u8) driven by binding power pairs (left_bp, right_bp).

Binding Power and Associativity Mechanics

Left-Associative Operator (`+`, bp = (3, 4)):
  Input:  a + b + c
  1. At `a`, see `+` with l_bp = 3 >= min_bp(0). Recurse with min_bp = r_bp = 4.
  2. Next `+` has l_bp = 3 < min_bp(4) -> loop breaks!
  Result: ((a + b) + c)

Right-Associative Operator (`^`, bp = (8, 7)):
  Input:  2 ^ 3 ^ 2
  1. At `2`, see `^` with l_bp = 8 >= min_bp(0). Recurse with min_bp = r_bp = 7.
  2. Next `^` has l_bp = 8 >= min_bp(7) -> inner recursion consumes `3 ^ 2` first!
  Result: (2 ^ (3 ^ 2)) = 512

Complete Pratt Expression Parser and Evaluator

#[derive(Debug, Clone, PartialEq)]
pub enum ExprToken {
    Number(f64),
    Ident(String),
    Op(char),
    LParen,
    RParen,
    Comma,
    Eof,
}

pub fn lex_expr(input: &str) -> Result<Vec<ExprToken>, String> {
    let mut chars = input.chars().peekable();
    let mut out = Vec::new();

    while let Some(&c) = chars.peek() {
        if c.is_whitespace() {
            chars.next();
        } else if c.is_ascii_digit() || c == '.' {
            let mut s = String::new();
            while let Some(&d) = chars.peek() {
                if d.is_ascii_digit() || d == '.' {
                    s.push(d);
                    chars.next();
                } else {
                    break;
                }
            }
            let val: f64 = s.parse().map_err(|_| format!("invalid float '{s}'"))?;
            out.push(ExprToken::Number(val));
        } else if c.is_ascii_alphabetic() || c == '_' {
            let mut ident = String::new();
            while let Some(&ch) = chars.peek() {
                if ch.is_ascii_alphanumeric() || ch == '_' {
                    ident.push(ch);
                    chars.next();
                } else {
                    break;
                }
            }
            out.push(ExprToken::Ident(ident));
        } else {
            chars.next();
            match c {
                '+' | '-' | '*' | '/' | '^' => out.push(ExprToken::Op(c)),
                '(' => out.push(ExprToken::LParen),
                ')' => out.push(ExprToken::RParen),
                ',' => out.push(ExprToken::Comma),
                _ => return Err(format!("unknown token '{c}'")),
            }
        }
    }
    out.push(ExprToken::Eof);
    Ok(out)
}

#[derive(Debug, Clone)]
pub enum Ast {
    Num(f64),
    Var(String),
    Unary(char, Box<Ast>),
    Binary(char, Box<Ast>, Box<Ast>),
    Call(String, Vec<Ast>),
}

impl Ast {
    pub fn to_sexpr(&self) -> String {
        match self {
            Ast::Num(n) => format!("{n}"),
            Ast::Var(v) => v.clone(),
            Ast::Unary(op, e) => format!("({op} {})", e.to_sexpr()),
            Ast::Binary(op, l, r) => format!("({op} {} {})", l.to_sexpr(), r.to_sexpr()),
            Ast::Call(name, args) => {
                let rendered: Vec<String> = args.iter().map(|a| a.to_sexpr()).collect();
                format!("({name} {})", rendered.join(" "))
            }
        }
    }

    pub fn eval(&self) -> Result<f64, String> {
        match self {
            Ast::Num(n) => Ok(*n),
            Ast::Var(v) => match v.as_str() {
                "pi" => Ok(std::f64::consts::PI),
                "e" => Ok(std::f64::consts::E),
                _ => Err(format!("unknown constant '{v}'")),
            },
            Ast::Unary('-', inner) => Ok(-inner.eval()?),
            Ast::Unary('+', inner) => inner.eval(),
            Ast::Unary(op, _) => Err(format!("unsupported unary op '{op}'")),
            Ast::Binary(op, l, r) => {
                let a = l.eval()?;
                let b = r.eval()?;
                match op {
                    '+' => Ok(a + b),
                    '-' => Ok(a - b),
                    '*' => Ok(a * b),
                    '/' => Ok(a / b),
                    '^' => Ok(a.powf(b)),
                    _ => Err(format!("unsupported binary op '{op}'")),
                }
            }
            Ast::Call(func, args) => {
                let vals: Result<Vec<f64>, String> = args.iter().map(|a| a.eval()).collect();
                let vals = vals?;
                match (func.as_str(), vals.as_slice()) {
                    ("sqrt", [x]) => Ok(x.sqrt()),
                    ("max", [a, b]) => Ok(a.max(*b)),
                    ("min", [a, b]) => Ok(a.min(*b)),
                    ("abs", [x]) => Ok(x.abs()),
                    _ => Err(format!("unknown function call '{func}' with {} args", vals.len())),
                }
            }
        }
    }
}

pub struct PrattParser {
    tokens: Vec<ExprToken>,
    pos: usize,
}

impl PrattParser {
    pub fn new(tokens: Vec<ExprToken>) -> Self {
        Self { tokens, pos: 0 }
    }

    fn peek(&self) -> &ExprToken {
        &self.tokens[self.pos]
    }

    fn next(&mut self) -> ExprToken {
        let tok = self.tokens[self.pos].clone();
        if self.pos + 1 < self.tokens.len() {
            self.pos += 1;
        }
        tok
    }

    fn prefix_binding_power(op: char) -> u8 {
        match op {
            '+' | '-' => 7,
            _ => panic!("not a prefix operator: {op}"),
        }
    }

    fn infix_binding_power(op: char) -> Option<(u8, u8)> {
        match op {
            '+' | '-' => Some((3, 4)),
            '*' | '/' => Some((5, 6)),
            '^' => Some((8, 7)), // Right-associative: l_bp (8) > r_bp (7)
            _ => None,
        }
    }

    pub fn parse_expr(&mut self, min_bp: u8) -> Result<Ast, String> {
        let mut lhs = match self.next() {
            ExprToken::Number(n) => Ast::Num(n),
            ExprToken::Ident(name) => {
                if *self.peek() == ExprToken::LParen {
                    self.next(); // consume '('
                    let mut args = Vec::new();
                    if *self.peek() != ExprToken::RParen {
                        loop {
                            args.push(self.parse_expr(0)?);
                            if *self.peek() == ExprToken::Comma {
                                self.next();
                            } else {
                                break;
                            }
                        }
                    }
                    if self.next() != ExprToken::RParen {
                        return Err("expected ')' after function arguments".into());
                    }
                    Ast::Call(name, args)
                } else {
                    Ast::Var(name)
                }
            }
            ExprToken::LParen => {
                let inner = self.parse_expr(0)?;
                if self.next() != ExprToken::RParen {
                    return Err("expected closing ')'".into());
                }
                inner
            }
            ExprToken::Op(op @ ('+' | '-')) => {
                let r_bp = Self::prefix_binding_power(op);
                let rhs = self.parse_expr(r_bp)?;
                Ast::Unary(op, Box::new(rhs))
            }
            other => return Err(format!("unexpected token in prefix position: {other:?}")),
        };

        while let ExprToken::Op(op) = *self.peek() {
            let Some((l_bp, r_bp)) = Self::infix_binding_power(op) else {
                break;
            };
            if l_bp < min_bp {
                break;
            }
            self.next(); // consume operator
            let rhs = self.parse_expr(r_bp)?;
            lhs = Ast::Binary(op, Box::new(lhs), Box::new(rhs));
        }

        Ok(lhs)
    }
}

fn main() {
    let expressions = [
        "1 + 2 * 3 - 4",
        "2 ^ 3 ^ 2",
        "-2 ^ 2 + max(10, sqrt(144) * 2)",
    ];

    for src in expressions {
        let tokens = lex_expr(src).unwrap();
        let mut parser = PrattParser::new(tokens);
        let ast = parser.parse_expr(0).unwrap();
        println!("Input : {}", src);
        println!("S-Expr: {}", ast.to_sexpr());
        println!("Value : {}\n", ast.eval().unwrap());
    }
}

Input : 1 + 2 * 3 - 4
S-Expr: (- (+ 1 (* 2 3)) 4)
Value : 3

Input : 2 ^ 3 ^ 2
S-Expr: (^ 2 (^ 3 2))
Value : 512

Input : -2 ^ 2 + max(10, sqrt(144) * 2)
S-Expr: (+ (- (^ 2 2)) (max 10 (* (sqrt 144) 2)))
Value : 20