1 The Problem
We want to build an interpreter — a program that reads code and runs it. Ours handles arithmetic with proper precedence: 2 + 3 * 4 gives 14, not 20. It works in three classic stages: tokenize (split into symbols), parse (build a tree that captures precedence), and evaluate (walk the tree). This is exactly how Python itself runs your code.
Where this shows up: every programming language, every calculator, SQL engines, template languages, config parsers, spreadsheet formulas. The tokenize–parse–evaluate pipeline is one of the most fundamental and reusable ideas in all of computer science.
2 How to Think About It
Think about the three stages, before any code:
The plan — in plain English
1. Tokenize: turn the text "2 + 3" into a list of symbols: number 2, plus, number 3. → 2. Parse: build a tree that captures precedence — multiplication binds tighter than addition, so it sits lower in the tree. → 3. Evaluate: walk the tree bottom-up, computing each node. The tree structure is what makes precedence work automatically.
3 The Build — explained part by part
Here is a complete interpreter with a recursive-descent parser. It is longer than usual — read each part’s explanation below.
Pythoninterpreter.py
import re
# ---- 1. TOKENIZE: text -> list of tokens ----
def tokenize(text):
tokens = []
for part in re.findall(r"\d+|[+\-*/()]", text):
if part.isdigit():
tokens.append(("NUM", int(part)))
else:
tokens.append((part, part))
return tokens
# ---- 2 & 3. PARSE + EVALUATE (recursive descent) ----
class Parser:
def __init__(self, tokens):
self.tokens = tokens
self.pos = 0
def peek(self):
return self.tokens[self.pos] if self.pos < len(self.tokens) else (None, None)
def eat(self):
tok = self.tokens[self.pos]
self.pos += 1
return tok
def expr(self):
# expr handles + and - (lowest precedence).
value = self.term()
while self.peek()[0] in ("+", "-"):
op = self.eat()[0]
right = self.term()
value = value + right if op == "+" else value - right
return value
def term(self):
# term handles * and / (higher precedence).
value = self.factor()
while self.peek()[0] in ("*", "/"):
op = self.eat()[0]
right = self.factor()
value = value * right if op == "*" else value / right
return value
def factor(self):
# factor handles numbers and parentheses (highest).
tok_type, tok_value = self.eat()
if tok_type == "NUM":
return tok_value
if tok_type == "(":
value = self.expr()
self.eat() # consume ")"
return value
def evaluate(text):
return Parser(tokenize(text)).expr()
if __name__ == "__main__":
print(evaluate("2 + 3 * 4")) # 14, not 20
print(evaluate("(2 + 3) * 4")) # 20
What each part does — in plain words
tokenize(text) — the regex \d+|[+\-*/()] finds either a run of digits or a single operator/paren. Each becomes a token: numbers as ("NUM", 5), operators as themselves. Text becomes a clean list of symbols.the three methods expr / term / factor — this is recursive descent, and the structure is the precedence.
expr handles +/−, but first calls term for each side; term handles *//, but first calls factor. Because term runs “inside” expr, multiplication always groups tighter — precedence falls out of the call structure.factor() — the base case: a number returns its value; a
( recursively parses a whole sub-expression and consumes the closing ). Parentheses override precedence by starting fresh at the top.peek / eat —
peek looks at the current token without consuming it (to decide what to do); eat consumes and returns it (to move forward). This look-then-take rhythm drives all parsing.why a tree of calls? — we evaluate as we parse here, but the call structure mirrors the tree
2 + (3 * 4). Walking that structure computes the answer with correct precedence, automatically.
Common mistakes — and how to avoid them
✗ Trying to handle precedence with if-statements about operators — a tangle that never quite works.
✓ Let the grammar do it: expr calls term calls factor. Structure encodes precedence.
✗ Forgetting to consume the closing
) — the parser loses its place.✓ After parsing a parenthesised expr,
eat() the closing paren.✗ Mixing peek and eat up — consuming a token you only meant to look at.
✓ Use peek to decide, eat to advance. Keep them distinct.
4 Test & Prove Each Part
We test that arithmetic evaluates with correct precedence and parentheses — the whole point.
Addition works: 2 + 3 is 5
Precedence holds: 2 + 3 * 4 is 14, not 20
Parentheses override: (2 + 3) * 4 is 20
Nested expressions evaluate correctly
Pythontest_interpreter.py
import re
def tokenize(text):
tokens = []
for part in re.findall(r"\d+|[+\-*/()]", text):
if part.isdigit():
tokens.append(("NUM", int(part)))
else:
tokens.append((part, part))
return tokens
class Parser:
def __init__(self, tokens):
self.tokens = tokens
self.pos = 0
def peek(self):
return self.tokens[self.pos] if self.pos < len(self.tokens) else (None, None)
def eat(self):
tok = self.tokens[self.pos]
self.pos += 1
return tok
def expr(self):
value = self.term()
while self.peek()[0] in ("+", "-"):
op = self.eat()[0]
right = self.term()
value = value + right if op == "+" else value - right
return value
def term(self):
value = self.factor()
while self.peek()[0] in ("*", "/"):
op = self.eat()[0]
right = self.factor()
value = value * right if op == "*" else value / right
return value
def factor(self):
tok_type, tok_value = self.eat()
if tok_type == "NUM":
return tok_value
if tok_type == "(":
value = self.expr()
self.eat()
return value
def evaluate(text):
return Parser(tokenize(text)).expr()
def test_addition():
"""2 + 3 is 5."""
assert evaluate("2 + 3") == 5
def test_precedence():
"""Multiplication binds tighter than addition."""
assert evaluate("2 + 3 * 4") == 14
def test_parentheses():
"""Parentheses override precedence."""
assert evaluate("(2 + 3) * 4") == 20
def test_nested():
"""Nested expressions evaluate correctly."""
assert evaluate("2 * (3 + 4) * 2") == 28
Run with pytest -v. The precedence test is the heart of it: if 2 + 3 * 4 gives 14, your parser correctly captured that multiplication binds tighter — without any special-case code, just from the structure of expr calling term.
5 The Interface
INPUTan expression stringarithmetic to evaluate
Input
evaluate("2 + 3 * 4")OUTPUTthe resultcomputed with precedence
Output
14 # not 20 — multiplication first6 Run It & Automate It
Run it locally
python3 interpreter.pySee precedence and parentheses work. Try your own expressions in the
evaluate(...) call.Jenkins runs the tests automatically — each line explained below.
What you should see when it works
Terminala real run
14
20If it breaks — how to fix it
🚨
2 + 3 * 4 gives 20.Your precedence is wrong — ensure term (*//) is called inside expr (+/-), not the other way around.
🚨
IndexError.You ran past the end of the tokens. Check peek guards against
pos >= len.GroovyJenkinsfile
// Jenkinsfile — automated tests on every change.
pipeline {
agent any
stages {
stage('Get the code') { steps { checkout scm } } // download the code
stage('Install') { steps { sh 'python3 -m venv venv && . venv/bin/activate && pip install pytest' } } // test tool
stage('Test') { steps { sh '. venv/bin/activate && pytest -v' } } // run every test
}
post {
success { echo 'All tests passed.' }
failure { echo 'A test failed — look above.' }
}
}
🎯 Try this next — make it yours
- Variables. Support
x = 5thenx + 2. (Teaches: an environment.) - An AST. Build an explicit tree of node objects, then evaluate it separately. (Teaches: true ASTs.)
- Functions. Add
sqrt(16). (Teaches: calls and arguments — toward a real language.)
What you learned
You built an interpreter: tokenize, parse with recursive descent, and evaluate — with operator precedence emerging naturally from the parser’s structure. This pipeline is how every programming language runs. You now understand what Python does with your code. Related: re, Functions & Scope.