Skip to content
Tutorials Center
My learning

Topics

Lesson 121 of 132 ยท Projects

Project: An Expression Interpreter

Build a calculator language in Rust: a tokenizer, a recursive-descent parser with operator precedence, an AST of enums, an evaluator and error messages that point at the exact column.

When you type 1 + 2 * 3 into a calculator, something has to know that the answer is 7 and not 9. That something is a tiny interpreter, and writing one is the best way to see how programming languages work on the inside. It is also a perfect Rust project: the data you manipulate is a tree, trees are made of enums, and enums plus match are what Rust does best.

We will build a small language with numbers, + - * / % ^, parentheses, unary minus, variables (x = 3 * 4), constants (pi, e) and functions (sqrt(16), max(1, 5, 3)). Every error, from a stray $ to 1 / 0, is reported with the column where it happened, with a caret pointing at it. The work is divided into the three classic phases:

  1. Tokenizer (lexer): turns the text into a list of tokens such as Number(1), Plus, LParen.
  2. Parser: turns tokens into a tree (the abstract syntax tree, or AST) that respects operator precedence.
  3. Evaluator: walks the tree and computes the value.

We build and run each phase on its own, then put them together into a small calculator that reads lines from the Input box.

Stage 1: the tokenizer

A tokenizer groups characters into the smallest meaningful pieces. The characters 1, 2, ., 5 become one token, Number(12.5); the characters s, q, r, t become Ident("sqrt"). Whitespace separates tokens and is then thrown away.

Each token remembers its position (a byte offset into the source). That one extra field is what lets every later phase say "the problem is here". We also create an error type with the same position, and a function that draws the caret.

Rust Stage 1: turning text into tokens

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

How it works:

  • char_indices().peekable() gives (byte_offset, char) pairs plus the ability to look at the next one without consuming it. Peeking is how a lexer decides when a number or a name ends.
  • A number is any run of digits and dots, then handed to str::parse::<f64>(). That is a deliberate simplification: 1.2.3 is read as one lump and rejected by parse, with an error pointing at the start of the number. We do not support the exponent form 1e3; adding it is a good exercise.
  • Positions are byte offsets, which is what slicing needs. For display, render_error converts to a character count, so the caret lines up even after a non-ASCII letter such as the รฏ in naรฏve.
  • The final End token gives the parser a clean way to say "I ran out of input" and a position to report it at.

A real language would produce several tokens for =/==, </<= and so on by peeking at the next character. We have only a single =, the assignment.

Stage 2: the AST and the evaluator

Before parsing, decide what the parser should produce. An expression like 1 + 2 * 3 is not a flat list; it is a tree in which * sits below +:

TEXT
    (+)
   /   \
  1    (*)
       / \
      2   3

Each node is either a leaf (a number, a variable) or an operation with child expressions. In Rust that is a recursive enum. Here is the first obstacle everyone meets:

Rust A recursive enum without Box (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The compiler says error[E0072]: recursive type Expr has infinite size. An Expr would contain two Exprs, each containing two more, without end, so the compiler cannot compute its size. The fix, which the help note suggests, is indirection: a Box<Expr> is a pointer of a known size to a value on the heap.

Now the real AST. Nodes that can fail at run time remember their source position, so evaluation errors can point at the culprit too. The evaluator is a single recursive function with a match that has one arm per variant. We build trees by hand here and let the parser do it in the next stage.

Rust Stage 2: a hand-built AST and its evaluator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Things to learn from this stage:

  • One enum, one match. Adding an operation means adding a variant, and the compiler then points to every match that needs a new arm. This is the "expression problem" solved the Rust way: closed set of variants, open set of functions.
  • Box<Expr> appears only where an Expr contains another Expr directly. Vec<Expr> (the call arguments) needs no box: a Vec is already a pointer to heap memory.
  • match (name, args) on a tuple of a &str and a slice with patterns like ("min", [first, rest @ ..]) gives a built-in function table that checks the argument count at the same time. Guards (if *x < 0.0) refine a pattern.
  • The match arm BinOp::Div | BinOp::Rem if b == 0.0 catches both divisions before the ordinary ones. The order of arms matters.
  • collect::<Result<Vec<_>, _>>() turns an iterator of results into one result: the first error stops the collection and is returned. This is how ?-like behavior works inside an iterator chain.
  • pi * r ^ 2 gives a floating-point number; we print it with {:.4} to avoid depending on the last digits.

Stage 3: the parser

Now the interesting part: turning tokens into that tree with correct precedence and associativity. We use a technique called precedence climbing, a compact cousin of recursive descent. The grammar, from loosest to tightest binding, is:

Level Operators Associativity
1 + - left: 1 - 2 - 3 is (1 - 2) - 3
2 * / % left
3 unary - prefix
4 ^ right: 2 ^ 3 ^ 2 is 2 ^ (3 ^ 2)

Unary minus binds looser than ^, which is the convention in mathematics: -2 ^ 2 is -(2 ^ 2) = -4. And 2 ^ -1 still works, because the right operand of ^ may start with a unary minus.

The algorithm in words: parse_expr(min_prec) parses a unary/primary expression as the left side, then keeps looking at the next operator. If its precedence is at least min_prec, it consumes the operator and parses the right side with a higher minimum (for left-associative operators) or the same minimum (for right-associative ones), and combines both sides into a node. When it sees an operator that binds too loosely, it stops and lets the caller deal with it.

We also add a depth limit. A hostile input such as ((((โ€ฆ a hundred thousand times deep would overflow the stack of a naive recursive parser, which would crash the whole program. A counter turns that into an ordinary error.

The program below includes the tokenizer from stage 1 (shortened to the essentials) and prints each tree in a fully parenthesized form, which shows the precedence decisions.

Rust Stage 3: precedence climbing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Look at the top rows of the output until the precedence rules become obvious:

  • 1 + 2 * 3 becomes (1 + (2 * 3)): the * binds tighter, so it ends up deeper in the tree.
  • 10 - 4 - 3 becomes ((10 - 4) - 3): for equal precedence, the left one groups first. That is the prec + 1 in the recursive call: the right side must be strictly tighter.
  • 2 ^ 3 ^ 2 becomes (2 ^ (3 ^ 2)): ^ passes prec itself, so the right side may contain another ^.
  • -2 ^ 2 becomes (-(2 ^ 2)): the unary minus parses its operand with UNARY_PREC, and ^ (4) is at least that tight.

Details worth studying:

  • Error messages say what the parser expected and what it found. expected an expression, found the end of the input points at the end of the line for 2 +. All of that comes from the Display impl for TokenKind and one helper, expected.
  • advance never moves past End. That means a parser bug cannot make peek index out of bounds; the worst outcome is an error.
  • parse_primary is a match on token.kind by value. The clone made in peek makes this possible without borrow conflicts with self.advance(). Cloning a small token is cheap; in a performance-sensitive parser you would index into the vector instead.
  • The depth counter is decremented after the call (self.depth -= 1). When an error returns early with ? inside parse_binary, we still pass through that line, because parse_expr stores the result first and only then decrements.

Print the tree in a fully parenthesized form while you build a parser. It shows at once whether precedence and associativity are right, and it makes a perfect assertion for tests: assert_eq!(parse("1 + 2 * 3").unwrap().to_string(), "(1 + (2 * 3))").

Stage 4: the complete interpreter

Time to assemble the three phases into a program with a read-eval-print loop (a REPL). Each input line is tokenized, parsed and evaluated against an environment that persists between lines, so variables work. A line that starts with :ast prints the tree instead of evaluating it.

Two more safety checks go into run_line: a maximum source length (so a huge input cannot build an AST so deep that evaluating or dropping it recurses too far) and the depth limit from stage 3. Before the REPL starts, the program runs a short table of self-checks, the same idea as a test suite.

Rust Stage 4: the complete calculator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Read the output from the top and match every answer to the input line that caused it. A few things to check yourself: -2 ^ 2 gives -4 (the minus applies after the power), 2 ^ 3 ^ 2 gives 512 (right associativity), and each failing line draws a caret under the exact column of the problem. For 1 / (x - 2.5) the caret sits under the /, the operator whose node produced the error.

Some design remarks:

  • Phase boundaries are Result boundaries. run_line is three function calls joined by ?. Because all phases share the Error { kind, pos } type, one rendering function serves all of them.
  • Errors keep position by construction. The nodes that can fail at run time (Var, Binary, Call) store a pos. Nodes that cannot fail (Number, Neg) do not, which keeps the tree small.
  • Error { pos: error.pos + by, ..error } is struct update syntax: copy the other fields (here, kind) from error, replacing pos. The old error is partly moved, which is fine because we no longer use it.
  • Floating point is visible. Try 0.1 + 0.2 and you will see 0.30000000000000004. A calculator for money would use integers or decimals; this one is honest about what f64 does.
  • value.to_string() for an f64 prints 7 for 7.0 and 3.5 for 3.5, which is why the output looks like a calculator and not like 7.0.

Testing an interpreter

An interpreter is almost a pure function, which makes testing easy and valuable. In a Cargo project you would write these in #[cfg(test)] mod tests (read-only here, since the editor does not run the test harness; the self-test in stage 4 does the same job in the editor):

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

    fn eval_str(source: &str) -> Result<f64, ErrorKind> {
        let tree = parse(source).map_err(|e| e.kind)?;
        eval(&tree, &mut Env::new()).map_err(|e| e.kind)
    }

    #[test]
    fn precedence_and_associativity() {
        assert_eq!(parse("1 + 2 * 3").unwrap().to_string(), "(1 + (2 * 3))");
        assert_eq!(parse("2 ^ 3 ^ 2").unwrap().to_string(), "(2 ^ (3 ^ 2))");
        assert_eq!(eval_str("10 - 4 - 3"), Ok(3.0));
    }

    #[test]
    fn errors_have_positions() {
        let error = parse("1 + $").unwrap_err();
        assert_eq!(error, Error { kind: ErrorKind::UnexpectedChar('$'), pos: 4 });
    }

    #[test]
    fn division_by_zero_is_an_error_not_infinity() {
        assert_eq!(eval_str("1 / 0"), Err(ErrorKind::DivisionByZero));
    }
}

Good extra tests: random expressions compared with Rust's own arithmetic; the printed tree of an expression, parsed again, should give the same tree (a round trip); and a fuzz-style test that feeds random bytes to parse and checks that it never panics. The last one is the most valuable for any parser that handles outside input.

Where to go from here

  1. Add comparison operators and booleans (<, ==, and) and an if(cond, a, b) function.
  2. Add user-defined functions: f(x) = x * x + 1. You need a new Expr variant, a function table in Env, and scoped variables for parameters.
  3. Make the evaluator return a Value enum (Number, Bool, Str) instead of f64, and report type errors.
  4. Compile to a stack machine: an Instr enum (Push(f64), Add, Mul) and a loop with a Vec<f64> stack. It is faster than walking the tree, and a first taste of how real VMs work.
  5. Replace recursion in eval with an explicit stack, so even a very deep tree cannot exhaust the thread stack.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does enum Expr { Number(f64), Add(Expr, Expr) } fail to compile (E0072)?

    The compiler must know the size of Expr. A Box<Expr> is a pointer of fixed size, which breaks the infinite regress.
  2. 2. With the rule 'right associative operators recurse with the same precedence', how is 2 ^ 3 ^ 2 parsed?

    Passing prec instead of prec + 1 lets the right-hand side contain another ^, so the exponents group from the right.
  3. 3. Why does the parser bound the nesting depth (MAX_DEPTH) and the input length?

    Each nesting level uses stack space. A limit turns a potential crash into an ordinary error message.
  4. 4. Where does the caret in 1 / (x - 2.5) point for the division-by-zero error, and why?

    When the parser builds a Binary node, it stores the position of the operator token. The evaluator reports that position when apply fails.
  5. 5. What is collect::<Result<Vec<f64>, Error>>() doing when evaluating call arguments?

    Collecting an iterator of Results into a Result of a collection stops at the first Err and returns it, otherwise it returns Ok with all the values.

Summary

  • An interpreter has three phases: tokenize (text to tokens), parse (tokens to an AST) and evaluate (walk the tree).
  • Model the tree as a recursive enum; boxing children (Box<Expr>) gives it a finite size. Add a match arm per variant in each function that walks the tree.
  • Precedence climbing: parse_expr(min_prec) loops over operators, recursing with prec + 1 for left-associative and prec for right-associative operators.
  • Store source positions in tokens and in the nodes that can fail, and use one Error { kind, pos } type to draw a caret under the exact column.
  • Defend recursive code against hostile input with depth and length limits.
  • Tests for parsers are cheap: print the tree in parenthesized form, compare results, round-trip, and fuzz for panics.

Next: Project: A Concurrent Job Pipeline