codeloopback
Guide contents

Lesson 3 of 12

Expression Calculator

We build calc, an interactive calculator. It's small, but it has the same parts as every interpreter and compiler: a tokenizer, a parser, a syntax tree, and an evaluator.

Text
> let rate = 0.2
0.2
> let price = 49.99
49.99
> price * (1 + rate)
59.988
> round(price * 3)
150
> 2 ^ 3 ^ 2
512
> max(1, rate, -3)
1
> 10 / (price - price)
error: division by zero
> 4 + * 2
error: expected a number, variable, or '('
    4 + * 2
        ^

What the project uses:

Part Topics
tokenizer char_indices, Peekable, enums with data, Result
parser recursive functions, Box<Expr>, precedence climbing, pattern matching
evaluator HashMap environment, match on the tree, function pointers
REPL BufRead, Write, IsTerminal, error formatting
Terminal
cargo new calc

The steps are self-contained programs; step 5 is the complete calculator.

Step 1: The tokenizer

The tokenizer turns text into tokens: numbers, names, operators, and punctuation. Each token remembers its byte position, so errors can point at it later. char_indices().peekable() gives each character with its position and lets us look one character ahead, which multi-character tokens like 3.25 and price need.

Rustcargo test
#[derive(Debug, Clone, PartialEq)]
pub enum Token {
    Number(f64),
    Ident(String),
    Op(char), // + - * / ^
    LParen,
    RParen,
    Comma,
    Equals,
}

#[derive(Debug, PartialEq)]
pub struct Spanned {
    pub token: Token,
    pub pos: usize,
}

#[derive(Debug, PartialEq)]
pub enum LexError {
    UnexpectedChar { ch: char, pos: usize },
    BadNumber { text: String, pos: usize },
}

pub fn tokenize(input: &str) -> Result<Vec<Spanned>, LexError> {
    let mut tokens = Vec::new();
    let mut chars = input.char_indices().peekable();
    while let Some(&(pos, ch)) = chars.peek() {
        let token = match ch {
            ' ' | '\t' => {
                chars.next();
                continue;
            }
            '0'..='9' | '.' => {
                let mut text = String::new();
                while let Some(&(_, c)) = chars.peek() {
                    if !(c.is_ascii_digit() || c == '.') {
                        break;
                    }
                    text.push(c);
                    chars.next();
                }
                let value = text.parse().map_err(|_| LexError::BadNumber { text, pos })?;
                tokens.push(Spanned { token: Token::Number(value), pos });
                continue;
            }
            c if c.is_alphabetic() || c == '_' => {
                let mut name = String::new();
                while let Some(&(_, c)) = chars.peek() {
                    if !(c.is_alphanumeric() || c == '_') {
                        break;
                    }
                    name.push(c);
                    chars.next();
                }
                tokens.push(Spanned { token: Token::Ident(name), pos });
                continue;
            }
            '+' | '-' | '*' | '/' | '^' => Token::Op(ch),
            '(' => Token::LParen,
            ')' => Token::RParen,
            ',' => Token::Comma,
            '=' => Token::Equals,
            other => return Err(LexError::UnexpectedChar { ch: other, pos }),
        };
        chars.next();
        tokens.push(Spanned { token, pos });
    }
    Ok(tokens)
}

#[cfg(test)]
mod tests {
    use super::*;

    fn kinds(input: &str) -> Vec<Token> {
        tokenize(input).unwrap().into_iter().map(|s| s.token).collect()
    }

    #[test]
    fn numbers_names_and_operators() {
        assert_eq!(
            kinds("price*1.5 - x_2"),
            vec![
                Token::Ident("price".into()),
                Token::Op('*'),
                Token::Number(1.5),
                Token::Op('-'),
                Token::Ident("x_2".into()),
            ]
        );
    }

    #[test]
    fn positions_are_byte_offsets() {
        let tokens = tokenize("max(a, 10)").unwrap();
        let positions: Vec<usize> = tokens.iter().map(|t| t.pos).collect();
        assert_eq!(positions, vec![0, 3, 4, 5, 7, 9]);
    }

    #[test]
    fn rejects_unknown_characters() {
        assert_eq!(tokenize("2 $ 3"), Err(LexError::UnexpectedChar { ch: '$', pos: 2 }));
    }

    #[test]
    fn rejects_malformed_numbers() {
        assert_eq!(tokenize("1.2.3"), Err(LexError::BadNumber { text: "1.2.3".into(), pos: 0 }));
    }
}
Output
running 4 tests
test tests::numbers_names_and_operators ... ok
test tests::positions_are_byte_offsets ... ok
test tests::rejects_malformed_numbers ... ok
test tests::rejects_unknown_characters ... ok

test result: ok. 4 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

Step 2: The syntax tree

The parser's output is a tree. Expr is recursive: a binary expression contains two expressions. A recursive enum needs Box so its size is known. Implementing Display to print the tree fully parenthesized is the easiest way to check that the parser got precedence right.

Rust
use std::fmt;

#[derive(Debug, Clone, PartialEq)]
enum Expr {
    Number(f64),
    Var(String),
    Neg(Box<Expr>),
    Binary { op: char, left: Box<Expr>, right: Box<Expr> },
    Call { name: String, args: Vec<Expr> },
}

impl fmt::Display for Expr {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Expr::Number(n) => write!(f, "{n}"),
            Expr::Var(name) => write!(f, "{name}"),
            Expr::Neg(inner) => write!(f, "(-{inner})"),
            Expr::Binary { op, left, right } => write!(f, "({left} {op} {right})"),
            Expr::Call { name, args } => {
                let args: Vec<String> = args.iter().map(|a| a.to_string()).collect();
                write!(f, "{name}({})", args.join(", "))
            }
        }
    }
}

fn num(n: f64) -> Expr {
    Expr::Number(n)
}

fn bin(op: char, left: Expr, right: Expr) -> Expr {
    Expr::Binary { op, left: Box::new(left), right: Box::new(right) }
}

fn main() {
    // 1 + 2 * 3
    let tree = bin('+', num(1.0), bin('*', num(2.0), num(3.0)));
    println!("{tree}");

    // -price * max(a, 2)
    let tree = bin(
        '*',
        Expr::Neg(Box::new(Expr::Var("price".into()))),
        Expr::Call { name: "max".into(), args: vec![Expr::Var("a".into()), num(2.0)] },
    );
    println!("{tree}");
    println!("{:?}", bin('-', num(1.0), num(2.0)));
}
Output
(1 + (2 * 3))
((-price) * max(a, 2))
Binary { op: '-', left: Number(1.0), right: Number(2.0) }

Step 3: Parsing with precedence climbing

The parser reads tokens left to right and builds the tree. Operator precedence is handled by precedence climbing: parse_expr(min) parses an operand, then keeps absorbing operators whose precedence is at least min. For the right operand it recurses with a higher minimum, so tighter operators bind first.

Operator Precedence Associativity
+ - 1 left: 8 - 3 - 2 is (8 - 3) - 2
* / 2 left
unary - 3
^ 4 right: 2 ^ 3 ^ 2 is 2 ^ (3 ^ 2)
Rust
use std::iter::Peekable;
use std::vec::IntoIter;

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

// A minimal tokenizer (step 1 has the full one, with positions and errors).
fn tokenize(input: &str) -> Vec<Token> {
    let mut tokens = Vec::new();
    let mut chars = input.chars().peekable();
    while let Some(&c) = chars.peek() {
        if c.is_ascii_digit() {
            let mut text = String::new();
            while let Some(&d) = chars.peek().filter(|d| d.is_ascii_digit() || **d == '.') {
                text.push(d);
                chars.next();
            }
            tokens.push(Token::Number(text.parse().unwrap()));
        } else if c.is_alphabetic() {
            let mut name = String::new();
            while let Some(&d) = chars.peek().filter(|d| d.is_alphanumeric()) {
                name.push(d);
                chars.next();
            }
            tokens.push(Token::Ident(name));
        } else {
            chars.next();
            match c {
                '(' => tokens.push(Token::LParen),
                ')' => tokens.push(Token::RParen),
                ',' => tokens.push(Token::Comma),
                ' ' => {}
                op => tokens.push(Token::Op(op)),
            }
        }
    }
    tokens
}

#[derive(Debug)]
enum Expr {
    Number(f64),
    Var(String),
    Neg(Box<Expr>),
    Binary { op: char, left: Box<Expr>, right: Box<Expr> },
    Call { name: String, args: Vec<Expr> },
}

impl std::fmt::Display for Expr {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Expr::Number(n) => write!(f, "{n}"),
            Expr::Var(name) => write!(f, "{name}"),
            Expr::Neg(inner) => write!(f, "(-{inner})"),
            Expr::Binary { op, left, right } => write!(f, "({left} {op} {right})"),
            Expr::Call { name, args } => {
                let args: Vec<String> = args.iter().map(|a| a.to_string()).collect();
                write!(f, "{name}({})", args.join(", "))
            }
        }
    }
}

fn precedence(op: char) -> Option<(u8, bool)> {
    // (precedence, right-associative?)
    match op {
        '+' | '-' => Some((1, false)),
        '*' | '/' => Some((2, false)),
        '^' => Some((4, true)),
        _ => None,
    }
}

struct Parser {
    tokens: Peekable<IntoIter<Token>>,
}

impl Parser {
    fn parse_expr(&mut self, min: u8) -> Result<Expr, String> {
        let mut left = self.parse_operand()?;
        while let Some(Token::Op(op)) = self.tokens.peek() {
            let op = *op;
            let Some((prec, right_assoc)) = precedence(op) else { break };
            if prec < min {
                break;
            }
            self.tokens.next();
            let right = self.parse_expr(if right_assoc { prec } else { prec + 1 })?;
            left = Expr::Binary { op, left: Box::new(left), right: Box::new(right) };
        }
        Ok(left)
    }

    fn parse_operand(&mut self) -> Result<Expr, String> {
        match self.tokens.next() {
            Some(Token::Number(n)) => Ok(Expr::Number(n)),
            Some(Token::Op('-')) => Ok(Expr::Neg(Box::new(self.parse_expr(3)?))),
            Some(Token::LParen) => {
                let inner = self.parse_expr(1)?;
                self.expect(Token::RParen)?;
                Ok(inner)
            }
            Some(Token::Ident(name)) if self.tokens.peek() == Some(&Token::LParen) => {
                self.tokens.next();
                let mut args = Vec::new();
                if self.tokens.peek() != Some(&Token::RParen) {
                    loop {
                        args.push(self.parse_expr(1)?);
                        if self.tokens.peek() != Some(&Token::Comma) {
                            break;
                        }
                        self.tokens.next();
                    }
                }
                self.expect(Token::RParen)?;
                Ok(Expr::Call { name, args })
            }
            Some(Token::Ident(name)) => Ok(Expr::Var(name)),
            Some(other) => Err(format!("unexpected {other:?}")),
            None => Err(String::from("unexpected end of input")),
        }
    }

    fn expect(&mut self, wanted: Token) -> Result<(), String> {
        match self.tokens.next() {
            Some(token) if token == wanted => Ok(()),
            other => Err(format!("expected {wanted:?}, found {other:?}")),
        }
    }
}

fn parse(input: &str) -> Result<Expr, String> {
    let mut parser = Parser { tokens: tokenize(input).into_iter().peekable() };
    let expr = parser.parse_expr(1)?;
    match parser.tokens.next() {
        None => Ok(expr),
        Some(extra) => Err(format!("unexpected {extra:?} after the expression")),
    }
}

fn main() {
    for input in ["1 + 2 * 3", "(1 + 2) * 3", "8 - 3 - 2", "2 ^ 3 ^ 2", "-2 ^ 2", "-x * 3", "max(a, b + 1, 2)", "(1 + 2", "1 2"] {
        match parse(input) {
            Ok(tree) => println!("{input:<18} => {tree}"),
            Err(error) => println!("{input:<18} => error: {error}"),
        }
    }
}
Output
1 + 2 * 3          => (1 + (2 * 3))
(1 + 2) * 3        => ((1 + 2) * 3)
8 - 3 - 2          => ((8 - 3) - 2)
2 ^ 3 ^ 2          => (2 ^ (3 ^ 2))
-2 ^ 2             => (-(2 ^ 2))
-x * 3             => ((-x) * 3)
max(a, b + 1, 2)   => max(a, (b + 1), 2)
(1 + 2             => error: expected RParen, found None
1 2                => error: unexpected Number(2.0) after the expression

-2 ^ 2 is -(2 ^ 2) = -4, as in mathematics (and Python), because ^ binds tighter than unary minus.

Step 4: Evaluating the tree

Evaluation is one match over the tree, calling itself for sub-expressions. Variables live in a HashMap. Built-in functions are a table of plain function pointers that take a slice of arguments, which handles fixed and variable argument counts alike.

Rust
use std::collections::HashMap;

enum Expr {
    Number(f64),
    Var(String),
    Neg(Box<Expr>),
    Binary { op: char, left: Box<Expr>, right: Box<Expr> },
    Call { name: String, args: Vec<Expr> },
}

#[derive(Debug, PartialEq)]
enum EvalError {
    UnknownVariable(String),
    UnknownFunction(String),
    WrongArgCount { name: String, expected: &'static str, found: usize },
    DivisionByZero,
}

type Builtin = fn(&[f64]) -> Option<f64>; // None = wrong number of arguments

fn one(args: &[f64], f: fn(f64) -> f64) -> Option<f64> {
    match args {
        [x] => Some(f(*x)),
        _ => None,
    }
}

fn sqrt(a: &[f64]) -> Option<f64> {
    one(a, f64::sqrt)
}

fn abs(a: &[f64]) -> Option<f64> {
    one(a, f64::abs)
}

fn round(a: &[f64]) -> Option<f64> {
    one(a, f64::round)
}

fn max(a: &[f64]) -> Option<f64> {
    a.iter().copied().reduce(f64::max)
}

fn min(a: &[f64]) -> Option<f64> {
    a.iter().copied().reduce(f64::min)
}

fn builtins() -> HashMap<&'static str, (Builtin, &'static str)> {
    // The array's type makes each function item coerce to the `Builtin` pointer type.
    let table: [(&'static str, Builtin, &'static str); 5] =
        [("sqrt", sqrt, "1"), ("abs", abs, "1"), ("round", round, "1"), ("max", max, "at least 1"), ("min", min, "at least 1")];
    table.into_iter().map(|(name, function, arity)| (name, (function, arity))).collect()
}

struct Env {
    vars: HashMap<String, f64>,
    functions: HashMap<&'static str, (Builtin, &'static str)>,
}

impl Env {
    fn eval(&self, expr: &Expr) -> Result<f64, EvalError> {
        match expr {
            Expr::Number(n) => Ok(*n),
            Expr::Var(name) => self.vars.get(name).copied().ok_or_else(|| EvalError::UnknownVariable(name.clone())),
            Expr::Neg(inner) => Ok(-self.eval(inner)?),
            Expr::Binary { op, left, right } => {
                let (l, r) = (self.eval(left)?, self.eval(right)?);
                match op {
                    '+' => Ok(l + r),
                    '-' => Ok(l - r),
                    '*' => Ok(l * r),
                    '/' if r == 0.0 => Err(EvalError::DivisionByZero),
                    '/' => Ok(l / r),
                    '^' => Ok(l.powf(r)),
                    _ => unreachable!("the parser only produces + - * / ^"),
                }
            }
            Expr::Call { name, args } => {
                let (function, expected) =
                    self.functions.get(name.as_str()).ok_or_else(|| EvalError::UnknownFunction(name.clone()))?;
                let values = args.iter().map(|a| self.eval(a)).collect::<Result<Vec<f64>, _>>()?;
                function(&values).ok_or(EvalError::WrongArgCount { name: name.clone(), expected, found: values.len() })
            }
        }
    }
}

fn num(n: f64) -> Expr {
    Expr::Number(n)
}

fn var(name: &str) -> Expr {
    Expr::Var(name.to_string())
}

fn bin(op: char, left: Expr, right: Expr) -> Expr {
    Expr::Binary { op, left: Box::new(left), right: Box::new(right) }
}

fn call(name: &str, args: Vec<Expr>) -> Expr {
    Expr::Call { name: name.to_string(), args }
}

fn main() {
    let env = Env { vars: HashMap::from([(String::from("price"), 49.99), (String::from("rate"), 0.2)]), functions: builtins() };

    let cases = [
        ("price * (1 + rate)", bin('*', var("price"), bin('+', num(1.0), var("rate")))),
        ("round(price * 3)", call("round", vec![bin('*', var("price"), num(3.0))])),
        ("max(1, rate, -3)", call("max", vec![num(1.0), var("rate"), Expr::Neg(Box::new(num(3.0)))])),
        ("sqrt(2, 3)", call("sqrt", vec![num(2.0), num(3.0)])),
        ("10 / (rate - rate)", bin('/', num(10.0), bin('-', var("rate"), var("rate")))),
        ("tax * 2", bin('*', var("tax"), num(2.0))),
        ("median(1)", call("median", vec![num(1.0)])),
    ];
    for (source, expr) in &cases {
        println!("{source:<20} => {:?}", env.eval(expr));
    }
}
Output
price * (1 + rate)   => Ok(59.988)
round(price * 3)     => Ok(150.0)
max(1, rate, -3)     => Ok(1.0)
sqrt(2, 3)           => Err(WrongArgCount { name: "sqrt", expected: "1", found: 2 })
10 / (rate - rate)   => Err(DivisionByZero)
tax * 2              => Err(UnknownVariable("tax"))
median(1)            => Err(UnknownFunction("median"))

Each built-in is an ordinary function with the same signature, stored as a function pointer (fn(&[f64]) -> Option<f64>). A closure that captures nothing would coerce to the same type. collect::<Result<Vec<_>, _>>() evaluates the arguments and stops at the first error, as in Iterator Adapters.

Step 5: The complete calculator

The final program joins the pieces and adds statements (let name = expr and name = expr), one error type with positions, and a REPL. Errors that have a position are printed with a caret under the offending token. When standard input is a terminal, calc shows a prompt; otherwise (a pipe or no input at all) it runs a short demo script, which is what you see below.

Rust
use std::collections::HashMap;
use std::fmt;
use std::io::{self, BufRead, IsTerminal, Read, Write};
use std::iter::Peekable;
use std::vec::IntoIter;

// ---------- tokens ----------

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

#[derive(Debug, Clone)]
struct Spanned {
    token: Token,
    pos: usize,
}

// ---------- errors ----------

#[derive(Debug)]
enum CalcError {
    Syntax { message: String, pos: usize },
    UnknownVariable(String),
    UnknownFunction(String),
    WrongArgCount { name: String, expected: &'static str, found: usize },
    DivisionByZero,
}

impl fmt::Display for CalcError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            CalcError::Syntax { message, .. } => write!(f, "{message}"),
            CalcError::UnknownVariable(name) => write!(f, "unknown variable `{name}`"),
            CalcError::UnknownFunction(name) => write!(f, "unknown function `{name}`"),
            CalcError::WrongArgCount { name, expected, found } => {
                write!(f, "`{name}` takes {expected} argument(s), got {found}")
            }
            CalcError::DivisionByZero => write!(f, "division by zero"),
        }
    }
}

fn syntax(message: impl Into<String>, pos: usize) -> CalcError {
    CalcError::Syntax { message: message.into(), pos }
}

// ---------- tokenizer ----------

fn tokenize(input: &str) -> Result<Vec<Spanned>, CalcError> {
    let mut tokens = Vec::new();
    let mut chars = input.char_indices().peekable();
    while let Some(&(pos, ch)) = chars.peek() {
        let token = match ch {
            c if c.is_whitespace() => {
                chars.next();
                continue;
            }
            '0'..='9' | '.' => {
                let mut text = String::new();
                while let Some(&(_, c)) = chars.peek().filter(|(_, c)| c.is_ascii_digit() || *c == '.') {
                    text.push(c);
                    chars.next();
                }
                let value = text.parse().map_err(|_| syntax(format!("invalid number `{text}`"), pos))?;
                tokens.push(Spanned { token: Token::Number(value), pos });
                continue;
            }
            c if c.is_alphabetic() || c == '_' => {
                let mut name = String::new();
                while let Some(&(_, c)) = chars.peek().filter(|(_, c)| c.is_alphanumeric() || *c == '_') {
                    name.push(c);
                    chars.next();
                }
                tokens.push(Spanned { token: Token::Ident(name), pos });
                continue;
            }
            '+' | '-' | '*' | '/' | '^' => Token::Op(ch),
            '(' => Token::LParen,
            ')' => Token::RParen,
            ',' => Token::Comma,
            '=' => Token::Equals,
            other => return Err(syntax(format!("unexpected character `{other}`"), pos)),
        };
        chars.next();
        tokens.push(Spanned { token, pos });
    }
    Ok(tokens)
}

// ---------- syntax tree and parser ----------

enum Expr {
    Number(f64),
    Var(String),
    Neg(Box<Expr>),
    Binary { op: char, left: Box<Expr>, right: Box<Expr> },
    Call { name: String, args: Vec<Expr> },
}

enum Statement {
    Let { name: String, value: Expr },
    Expr(Expr),
}

fn precedence(op: char) -> Option<(u8, bool)> {
    match op {
        '+' | '-' => Some((1, false)),
        '*' | '/' => Some((2, false)),
        '^' => Some((4, true)),
        _ => None,
    }
}

struct Parser {
    tokens: Peekable<IntoIter<Spanned>>,
    end: usize, // position just past the input, for "unexpected end" errors
}

impl Parser {
    fn peek(&mut self) -> Option<&Token> {
        self.tokens.peek().map(|s| &s.token)
    }

    fn next_pos(&mut self) -> usize {
        self.tokens.peek().map_or(self.end, |s| s.pos)
    }

    fn statement(&mut self) -> Result<Statement, CalcError> {
        // `let x = ...` or `x = ...`
        let mut lookahead = self.tokens.clone();
        let is_let = matches!(lookahead.peek(), Some(Spanned { token: Token::Ident(word), .. }) if word == "let");
        if is_let {
            lookahead.next();
        }
        let assigns = matches!(
            (lookahead.next().map(|s| s.token), lookahead.next().map(|s| s.token)),
            (Some(Token::Ident(_)), Some(Token::Equals))
        );
        if is_let || assigns {
            if is_let {
                self.tokens.next();
            }
            let pos = self.next_pos();
            let Some(Token::Ident(name)) = self.tokens.next().map(|s| s.token) else {
                return Err(syntax("expected a variable name after `let`", pos));
            };
            let pos = self.next_pos();
            if self.tokens.next().map(|s| s.token) != Some(Token::Equals) {
                return Err(syntax("expected `=`", pos));
            }
            return Ok(Statement::Let { name, value: self.expr(1)? });
        }
        Ok(Statement::Expr(self.expr(1)?))
    }

    fn expr(&mut self, min: u8) -> Result<Expr, CalcError> {
        let mut left = self.operand()?;
        while let Some(&Token::Op(op)) = self.peek() {
            let Some((prec, right_assoc)) = precedence(op) else { break };
            if prec < min {
                break;
            }
            self.tokens.next();
            let right = self.expr(if right_assoc { prec } else { prec + 1 })?;
            left = Expr::Binary { op, left: Box::new(left), right: Box::new(right) };
        }
        Ok(left)
    }

    fn operand(&mut self) -> Result<Expr, CalcError> {
        let pos = self.next_pos();
        match self.tokens.next().map(|s| s.token) {
            Some(Token::Number(n)) => Ok(Expr::Number(n)),
            Some(Token::Op('-')) => Ok(Expr::Neg(Box::new(self.expr(3)?))),
            Some(Token::LParen) => {
                let inner = self.expr(1)?;
                self.expect(Token::RParen, "`)`")?;
                Ok(inner)
            }
            Some(Token::Ident(name)) if self.peek() == Some(&Token::LParen) => {
                self.tokens.next();
                let mut args = Vec::new();
                if self.peek() != Some(&Token::RParen) {
                    loop {
                        args.push(self.expr(1)?);
                        if self.peek() != Some(&Token::Comma) {
                            break;
                        }
                        self.tokens.next();
                    }
                }
                self.expect(Token::RParen, "`)` or `,`")?;
                Ok(Expr::Call { name, args })
            }
            Some(Token::Ident(name)) => Ok(Expr::Var(name)),
            _ => Err(syntax("expected a number, variable, or '('", pos)),
        }
    }

    fn expect(&mut self, wanted: Token, description: &str) -> Result<(), CalcError> {
        let pos = self.next_pos();
        match self.tokens.next() {
            Some(s) if s.token == wanted => Ok(()),
            _ => Err(syntax(format!("expected {description}"), pos)),
        }
    }
}

fn parse(input: &str) -> Result<Statement, CalcError> {
    let tokens = tokenize(input)?;
    let mut parser = Parser { tokens: tokens.into_iter().peekable(), end: input.len() };
    let statement = parser.statement()?;
    match parser.tokens.next() {
        None => Ok(statement),
        Some(extra) => Err(syntax("unexpected input after the expression", extra.pos)),
    }
}

// ---------- evaluator ----------

type Builtin = fn(&[f64]) -> Option<f64>;

fn one(args: &[f64], f: fn(f64) -> f64) -> Option<f64> {
    match args {
        [x] => Some(f(*x)),
        _ => None,
    }
}

fn sqrt(a: &[f64]) -> Option<f64> {
    one(a, f64::sqrt)
}

fn abs(a: &[f64]) -> Option<f64> {
    one(a, f64::abs)
}

fn round(a: &[f64]) -> Option<f64> {
    one(a, f64::round)
}

fn max(a: &[f64]) -> Option<f64> {
    a.iter().copied().reduce(f64::max)
}

fn min(a: &[f64]) -> Option<f64> {
    a.iter().copied().reduce(f64::min)
}

fn builtins() -> HashMap<&'static str, (Builtin, &'static str)> {
    // The array's type makes each function item coerce to the `Builtin` pointer type.
    let table: [(&'static str, Builtin, &'static str); 5] =
        [("sqrt", sqrt, "1"), ("abs", abs, "1"), ("round", round, "1"), ("max", max, "at least 1"), ("min", min, "at least 1")];
    table.into_iter().map(|(name, function, arity)| (name, (function, arity))).collect()
}

struct Calculator {
    vars: HashMap<String, f64>,
    functions: HashMap<&'static str, (Builtin, &'static str)>,
}

impl Calculator {
    fn new() -> Calculator {
        let functions = builtins();
        let vars = HashMap::from([(String::from("pi"), std::f64::consts::PI)]);
        Calculator { vars, functions }
    }

    fn run_line(&mut self, line: &str) -> Result<f64, CalcError> {
        match parse(line)? {
            Statement::Let { name, value } => {
                let value = self.eval(&value)?;
                self.vars.insert(name, value);
                Ok(value)
            }
            Statement::Expr(expr) => self.eval(&expr),
        }
    }

    fn eval(&self, expr: &Expr) -> Result<f64, CalcError> {
        match expr {
            Expr::Number(n) => Ok(*n),
            Expr::Var(name) => self.vars.get(name).copied().ok_or_else(|| CalcError::UnknownVariable(name.clone())),
            Expr::Neg(inner) => Ok(-self.eval(inner)?),
            Expr::Binary { op, left, right } => {
                let (l, r) = (self.eval(left)?, self.eval(right)?);
                match op {
                    '+' => Ok(l + r),
                    '-' => Ok(l - r),
                    '*' => Ok(l * r),
                    '/' if r == 0.0 => Err(CalcError::DivisionByZero),
                    '/' => Ok(l / r),
                    '^' => Ok(l.powf(r)),
                    _ => unreachable!("the parser only produces + - * / ^"),
                }
            }
            Expr::Call { name, args } => {
                let (function, expected) =
                    self.functions.get(name.as_str()).ok_or_else(|| CalcError::UnknownFunction(name.clone()))?;
                let values = args.iter().map(|a| self.eval(a)).collect::<Result<Vec<f64>, _>>()?;
                function(&values).ok_or(CalcError::WrongArgCount { name: name.clone(), expected, found: values.len() })
            }
        }
    }
}

// ---------- REPL ----------

fn repl(input: impl BufRead, mut out: impl Write, echo: bool, prompt: bool) -> io::Result<()> {
    let mut calc = Calculator::new();
    if prompt {
        write!(out, "> ")?;
        out.flush()?;
    }
    for line in input.lines() {
        let line = line?;
        if echo {
            writeln!(out, "> {line}")?;
        }
        if !line.trim().is_empty() {
            match calc.run_line(&line) {
                Ok(value) => writeln!(out, "{value}")?,
                Err(error) => {
                    writeln!(out, "error: {error}")?;
                    if let CalcError::Syntax { pos, .. } = error {
                        writeln!(out, "    {line}")?;
                        writeln!(out, "    {}^", " ".repeat(line[..pos].chars().count()))?;
                    }
                }
            }
        }
        if prompt {
            write!(out, "> ")?;
            out.flush()?;
        }
    }
    Ok(())
}

const DEMO: &str = "\
let rate = 0.2
let price = 49.99
price * (1 + rate)
round(price * 3)
2 ^ 3 ^ 2
max(1, rate, -3)
total = price * 2
sqrt(total, 2)
10 / (price - price)
4 + * 2
max(1, 2
2 $ 3
";

fn main() -> io::Result<()> {
    let stdin = io::stdin();
    if stdin.is_terminal() {
        return repl(stdin.lock(), io::stdout(), false, true);
    }
    // Piped input, e.g. `echo "2 ^ 10" | calc`: no prompts. No input at all: the demo.
    let mut piped = String::new();
    stdin.lock().read_to_string(&mut piped)?;
    if piped.trim().is_empty() {
        repl(DEMO.as_bytes(), io::stdout(), true, false)
    } else {
        repl(piped.as_bytes(), io::stdout(), false, false)
    }
}
Output
> let rate = 0.2
0.2
> let price = 49.99
49.99
> price * (1 + rate)
59.988
> round(price * 3)
150
> 2 ^ 3 ^ 2
512
> max(1, rate, -3)
1
> total = price * 2
99.98
> sqrt(total, 2)
error: `sqrt` takes 1 argument(s), got 2
> 10 / (price - price)
error: division by zero
> 4 + * 2
error: expected a number, variable, or '('
    4 + * 2
        ^
> max(1, 2
error: expected `)` or `,`
    max(1, 2
            ^
> 2 $ 3
error: unexpected character `$`
    2 $ 3
      ^

Ideas for extending it

  • Add comparison operators (<, ==) and an if(cond, a, b) function; comparisons need a lower precedence than +.
  • Let users define functions: let area(r) = pi * r ^ 2 stores an Expr and parameter names in the environment.
  • Use rustyline for line editing and history in interactive mode.
  • Evaluate with exact decimals using the rust_decimal crate, so 0.1 + 0.2 prints 0.3.

Summary

  • An interpreter has three stages: characters become tokens, tokens become a tree, and the tree is evaluated. Keeping them separate makes each one testable.
  • Recursive data needs indirection: Box<Expr> inside enum Expr.
  • Precedence climbing handles any number of precedence levels and both associativities with one small recursive function.
  • Tokens carry positions so errors can point at the input, and one error enum covers both syntax and evaluation errors.
  • IsTerminal lets the same program act as an interactive REPL or a filter in a pipeline.

Next: Markdown to HTML Converter.