How a tiny interpreter works

2 + 3 * 4

Fourteen, please. I can do the sum myself, but the program needs to recognise the pieces, arrange the operations and carry them out. I'm working on a much larger Go interpreter and plenty of it is still unfamiliar. This is a small bit I can hold in my head because one expression needs the main stages without dragging all of Go along with it.

The lexer reads characters and produces tokens:

NUMBER(2)  PLUS  NUMBER(3)  STAR  NUMBER(4)

Spaces can separate tokens but they aren't what defines them, and 2+3*4 should give the same sequence of number and operator tokens in this little language. Each digit sequence becomes a number, and each operator becomes its own token. At this stage we haven't decided which arithmetic happens first. The lexer sees * as one more operator, with no idea it's meant to go before the plus.

With the tokens ready, why not do each operation as it arrives? Add two and three, then multiply by four:

2 + 3 → 5
5 * 4 → 20

Twenty.

The numbers are right, and both operations work, but I've given them the wrong order. Recognising a multiplication token hasn't told the program to do that multiplication first.

The parser can make that decision by arranging the sequence into a tree:

The multiplication sits below the addition, so to calculate the value of the whole expression we first need the value of the addition's right child. That child happens to require multiplying three and four. This tree is an abstract syntax tree, or AST. It keeps the relationships that matter to evaluation. Spaces don't need their own nodes.

Once the tree exists, the evaluator doesn't need to remember the precedence rules. Following the children gives me the order. I like being able to look at the drawing and see that decision. No running program needed yet.

One way to build it is recursive descent. Use a function for each level of the grammar:

expression → addition and subtraction
term       → multiplication and division
atom       → a number, or a parenthesised expression

I'd let the expression reader ask the term reader for an operand, and let that reader consume a complete multiplication or division before returning its result. So the outer reader gets 3 * 4 as one piece while arranging the addition. Right, that's the part I'd watch in a trace if the tree put the wrong operator on top.

When the atom reader finds an opening parenthesis it calls the expression reader again, then requires the closing parenthesis before returning the resulting subtree. Change the input to (2 + 3) * 4 and multiplication goes on top, with addition underneath it. Twenty again. This time that's the answer we want. The parentheses have changed the structure.

Walk the tree

Now we can evaluate it. A number node returns its value. A binary operation evaluates its two children and applies its operator to their results. Here's a small JavaScript evaluator:

function evaluate(node) {
  if (node.kind === "number") return node.value;
  const left = evaluate(node.left);
  const right = evaluate(node.right);
  switch (node.op) {
    case "+": return left + right;
    case "-": return left - right;
    case "*": return left * right;
    case "/": return left / right;
    default: throw new Error("Unknown operator");
  }
}

For the first tree the number nodes provide two, three and four. Multiplication returns twelve, and the addition receives that result along with two from its other child, so it returns fourteen. I quite like how little the evaluator needs to know now, it follows the children and does the sums, and if it searches for an asterisk or decides which operation happens first, I have more parser work to do. The decision belongs in the tree.

Source	Grouping	Result
`2 + 3 * 4`	`2 + (3 * 4)`	14
`(2 + 3) * 4`	`(2 + 3) * 4`	20
`8 / 2 / 2`	`(8 / 2) / 2`	2

Figure 1 - From text to a result. The grouping determines which operation happens first.

The last row groups division from the left and computes 8 / 2 before dividing by two again. Division here uses JavaScript numbers, so 3 / 2 would give 1.5.

A missing closing parenthesis is the parser's problem because the structure is incomplete. An unrecognised character belongs with the lexer. Those failures have different explanations because the stages have different jobs.

Variables would need an environment, which maps names to values. A variable node would look up its name during evaluation. Then functions would need calls and assignments would change that environment, and if I carry on to control flow.... No, this tiny example can stop growing for now.

Fourteen.

A lot of naming and arranging to do a sum, but now I can point at where each part happens. I'm leaving variables and functions for another day.