Capstone 0/1

Lesson 21 of 21

Build an interpreter

Write a small calculator language: read it, turn it into a tree and work out its value.

Part 1 of 9 What an interpreter is

An interpreter for a calculator

The Python interpreter is the program that reads your code and carries it out. In this last lesson you write an interpreter of your own. It is much smaller than Python's: it understands one kind of line, arithmetic such as 2 * (3 + 4), and prints the line's value. By the end you will have a calculator that reads one line after another, prints each answer, and reports a clear error for a line it cannot work out.

That sounds easy until you look at what the program is given. 2 + 3 * 4 is 14, because * goes before +. Type it at Python's >>> prompt and Python prints 14, even though the + comes first in the line. Yet all Python received was nine characters. Something had to find the numbers and operators among them, work out that 3 * 4 belongs together, and only then do the arithmetic.

Our calculator has to do the same work, and we will build it in three stages, each taking the previous stage's result. Python and C++ run the first two stages on every program you write:

The three stages, on the line 2 * (3 + 4)
StageTakesGivesFor 2 * (3 + 4)
1. Tokenizethe texta list of tokens2 * ( 3 + 4 )
2. Parsethe tokensan expression tree(* 2 (+ 3 4))
3. Evaluatethe treea value14

The calculator language and its rules

Before writing any code, let's fix exactly what a line may contain and what its value is. A line of the calculator is an expression made of whole numbers, the operators +, -, * and /, and parentheses, with spaces allowed anywhere between them. Its value follows these rules:

  • Parentheses are worked out first.
  • * and / have higher precedence than + and -, so they are done first.
  • Operators of the same precedence go from left to right, so 7 - 2 - 1 means (7 - 2) - 1.
  • / drops the fraction, which rounds toward zero, the way C++'s / does: 7 / 2 is 3 and (1 - 8) / 2 is −3.
  • A number has no sign, so −3 is written 0 - 3.

Here are some lines and their values:

Lines of the calculator language and their values
LineValueWhy
2 + 3 * 414* before +: 2 + 12
(2 + 3) * 420parentheses first: 5 × 4
7 - 2 - 14left to right: 5 − 1
7 / 23the fraction of 3.5 is dropped
(1 - 8) / 2−3−3.5 rounds toward zero
8 / (3 - 3)errordivision by zero
(2 + 3errorthe ( is never closed