Skip to content
Tutorials Center
My learning

Topics

Lesson 51 of 61 ยท Projects

Project: An Expression Calculator Compiler

Build a complete expression compiler in Python: a lexer, a Pratt parser, an AST, a bytecode compiler and a stack VM, with error carets and a differential test.

It is time to put the pieces together. In this project you will build a small but complete compiler for arithmetic expressions such as max(2, 3) * (4 - 1) + -2 ^ 2. It has every stage you met in this track: a lexer, a Pratt parser that builds an AST, a code generator that emits bytecode, and a stack-based virtual machine that runs it. Nothing is hidden: the whole program is a couple of hundred lines of Python.

You will build it in three runnable steps. First the front end (text to tree), then the back end (tree to bytecode to value), and finally the assembled calculator with error messages and an automatic test that compares it against Python's own arithmetic.

What the calculator accepts

The language is deliberately small, so each rule fits in your head:

  • Numbers such as 42 and 3.5.
  • Binary operators + - * / % ^, where ^ means power.
  • Unary minus, parentheses, and four built-in functions: sqrt(x), abs(x), min(a, b) and max(a, b).

Precedence, from loosest to tightest, with the binding powers the parser uses. A pair (left, right) controls grouping: when the right number is larger than the left, an operator is left-associative; when it is smaller, it is right-associative.

Operators Binding power Associativity Example
+ - 1, 2 left 10 - 4 - 3 is (10 - 4) - 3
* / % 3, 4 left 7 % 4 * 2 is (7 % 4) * 2
unary - prefix, 5 n/a -2 * 3 is (-2) * 3
^ 8, 7 right 2 ^ 3 ^ 2 is 2 ^ (3 ^ 2)

The unary minus sits between * and ^ on purpose: -2 ^ 2 is -(2 ^ 2), which is -4, the same convention as mathematics and as Python's -2 ** 2.

The architecture

flowchart LR
    S["Source text"] -->|"characters"| L["Lexer"]
    L -->|"tokens"| P["Pratt parser"]
    P -->|"AST"| C["Bytecode compiler"]
    C -->|"instructions"| V["Stack VM"]
    V --> R["Result or error"]

Each stage consumes the previous stage's output. Errors from any stage carry a column so they can be shown with a caret.

A shared error type, CalcError, carries a message and a column. Every stage that can fail raises it with the position of the guilty character, and one function prints the source line with a caret under that column. Good error messages are not an afterthought; they are part of the design from the first line.

Step 1: lexer, AST and Pratt parser

The lexer is one regular expression with named groups, as in Regular Expressions for Lexers. Each match gives a token kind, its text and its column. Operators and punctuation use their own text as the token kind, which keeps the parser tidy.

The AST needs only four node types: Num, Neg, BinOp and Call. Binary operations and calls remember their column, so a later stage can still point at them.

The parser is a single function, expression(min_bp). It reads a prefix (a number, a unary minus, a parenthesized expression or a function call), then loops: while the next token is an infix operator whose left binding power is at least min_bp, consume it and parse the right-hand side with the operator's right binding power. That one rule produces correct precedence and associativity for everything in the table above.

Run the front end and look at the trees it builds. The sexpr helper prints a tree as a Lisp-style expression, so (+ 1 (* 2 3)) means "1 plus the product of 2 and 3".

Python Step 1: the front end, from text to tree

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 input()), it gets the next line from this box.

Check the trees against the table. 10 - 4 - 3 becomes (- (- 10 4) 3), left-associative. 2 ^ 3 ^ 2 becomes (^ 2 (^ 3 2)), right-associative. -2 ^ 2 becomes (neg (^ 2 2)). The error cases show the caret technique: the column of the offending token is the column of the caret. For the "missing operand" case, the error is at the end of the input, where the next token should have been.

Step 2: the compiler and the virtual machine

The back end has two small jobs. The compiler walks the tree in post-order: operands first, then the operator. That produces stack bytecode: PUSH n, NEG, ADD, SUB, MUL, DIV, MOD, POW and CALL name. Calls compile their arguments left to right, so max(2, 3) is PUSH 2, PUSH 3, CALL max. Binary instructions keep the column of their operator as an operand, which gives the VM what it needs to report a runtime error such as division by zero at the right place.

The virtual machine loops over the instruction list with an operand stack. Binary instructions pop the right operand first. Before it divides or raises to a power, it checks for situations that cannot be evaluated and raises a CalcError with the stored column.

The program below builds the tree for max(2, 3) * (4 - 1) + -2 ^ 2 by hand (the parser from step 1 would normally do this), compiles it, and runs it with a trace so you can watch the stack.

Python Step 2: the back end, from tree to value

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 input()), it gets the next line from this box.

Read the trace. max(2, 3) leaves 3. (4 - 1) leaves 3 as well, so the multiplication gives 9. Then 2 ^ 2 gives 4, NEG makes it -4, and the final ADD leaves 5. The stack never holds more than three values, a number the compiler could compute ahead of time and store with the bytecode, as CPython does.

Step 3: the whole calculator

Now join the stages. The function calculate(text) runs lexer, parser, compiler and VM, and turns any CalcError into the familiar message with a caret. It also converts Python's OverflowError (for results like 9 ^ 9 ^ 9) into a calculator error, so no raw Python exception escapes.

The last part of the program is a differential test, a technique from Testing and Debugging a Compiler. It generates hundreds of random expressions, evaluates each with the calculator and with Python's eval (after turning ^ into **), and asserts that the answers agree. Python's evaluator acts as the reference implementation. The random seed is fixed, so the test is repeatable.

Python Step 3: the finished calculator and its test

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 input()), it gets the next line from this box.

All results in the first block are correct, including the awkward ones: 2 ^ 3 ^ 2 is 512, not 64, and -2 ^ 2 is -4. The second block shows each stage reporting its own kind of mistake with a caret: the lexer ($), the parser (missing operand, missing parenthesis, stray token), the parser's checks on calls (unknown function, wrong argument count) and the VM (division by zero, negative square root, overflow). The final line is the proof of correctness that matters most: 398 random expressions agree with Python, and the two that divide by zero are reported as errors instead of crashing.

Where to go from here

You now have a working compiler. Each of these extensions teaches one more idea from the track:

  • Constant folding. Before compiling, replace any BinOp whose children are both Num with a single Num, as in Local Optimizations.
  • Variables. Add a name = expression form, a symbol table and LOAD/STORE instructions.
  • A postfix operator. Add ! for factorial, which shows how Pratt parsing handles postfix operators.
  • Better errors. Show a range of columns with ^^^^ instead of one caret, and suggest the closest function name when someone types sqt(9).
  • A disassembler with line numbers, or an option to report the stack depth a program needs.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the table of binding powers, why does ^ have the pair (8, 7) while + has (1, 2)?

    After the right-hand side is started with the operator's right power, the same operator can continue the chain only if its left power is at least that value. For + (1, 2) it cannot, so grouping is to the left. For ^ (8, 7) it can, so the chain groups to the right.
  2. 2. What does the compiler emit for max(2, 3)?

    Arguments are compiled left to right, so they sit on the stack in order, and the CALL instruction pops them as a group.
  3. 3. Why do BinOp nodes and binary instructions store a column?

    By the time the VM divides by zero, the source text is long gone as far as the instruction stream is concerned. Carrying the column along lets the error message still show a caret.
  4. 4. What is the purpose of the differential test at the end?

    A differential test runs the same input through two implementations and flags any disagreement. It finds bugs in precedence, associativity and arithmetic that hand-picked examples miss.

Summary

  • The calculator compiler has five stages: lexer, Pratt parser, bytecode compiler, stack VM and an error reporter that shows a caret.
  • Binding powers encode both precedence and associativity: a right power above the left makes an operator left-associative, and the reverse makes it right-associative.
  • A post-order walk of the AST produces correct stack code; arguments and operands end up on the stack in the order the instructions expect.
  • Carrying source columns through the AST and bytecode lets even run-time errors point at the source.
  • A differential test against Python's own arithmetic gives strong evidence that the compiler is correct.

Next: Project: A Complete Toy Language