1 The Problem
The grand finale: a compiler. Unlike the interpreter (which evaluated directly), a compiler translates source into instructions — here, simple stack-based bytecode — which a tiny virtual machine then executes. It ties together everything: tokenizing, parsing, code generation, and a VM. This is how Python, Java, and most languages actually work.
Where this shows up: Python (compiles to bytecode for its VM), Java (bytecode for the JVM), every compiled language, query planners, even regex engines that compile patterns. Separating “compile once” from “run many times” is a foundational idea — and the capstone of this entire canon.
2 How to Think About It
Think about translate-then-execute, before any code:
The plan — in plain English
1. Tokenize + parse the source (as in the interpreter). → 2. Generate bytecode: instead of computing, emit instructions like PUSH 2, PUSH 3, ADD. → 3. The VM runs the instructions using a stack: push numbers, and operators pop two and push the result. → The compiler produces instructions once; the VM can run them any time.
3 The Build — explained part by part
Here is a complete compiler and VM. It is the longest project — but every part builds on what you already know. Read each explanation.
Pythoncompiler.py
import re
# ---- FRONT END: tokenize + parse, emitting bytecode ----
def tokenize(text):
tokens = []
for part in re.findall(r"\d+|[+\-*/()]", text):
tokens.append(("NUM", int(part)) if part.isdigit() else (part, part))
return tokens
class Compiler:
def __init__(self, tokens):
self.tokens = tokens
self.pos = 0
self.code = [] # the bytecode we emit
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):
self.term()
while self.peek()[0] in ("+", "-"):
op = self.eat()[0]
self.term()
self.code.append("ADD" if op == "+" else "SUB")
def term(self):
self.factor()
while self.peek()[0] in ("*", "/"):
op = self.eat()[0]
self.factor()
self.code.append("MUL" if op == "*" else "DIV")
def factor(self):
tok_type, tok_value = self.eat()
if tok_type == "NUM":
self.code.append(("PUSH", tok_value)) # emit a push
elif tok_type == "(":
self.expr()
self.eat() # consume ")"
def compile_source(text):
c = Compiler(tokenize(text))
c.expr()
return c.code
# ---- BACK END: a stack-based virtual machine ----
def run(bytecode):
stack = []
for instruction in bytecode:
if isinstance(instruction, tuple): # ("PUSH", n)
stack.append(instruction[1])
else:
b = stack.pop(); a = stack.pop() # operators pop two
if instruction == "ADD": stack.append(a + b)
elif instruction == "SUB": stack.append(a - b)
elif instruction == "MUL": stack.append(a * b)
elif instruction == "DIV": stack.append(a / b)
return stack[0]
if __name__ == "__main__":
code = compile_source("2 + 3 * 4")
print("Bytecode:", code)
print("Result:", run(code)) # 14
What each part does — in plain words
the parser methods now emit instead of compute — compare to the interpreter: there, factor returned a number; here it appends ("PUSH", value) to the bytecode. The structure is identical; only the action differs — that is the leap from interpreting to compiling.self.code.append("ADD") — after parsing both sides of a
+, we emit an ADD instruction. The operands were already emitted as pushes, so ADD just says “combine the top two”.order matters — we emit both operands before the operator. So
2 + 3 becomes PUSH 2, PUSH 3, ADD. This is “postfix” order, exactly what a stack machine wants.the VM’s stack —
run walks the instructions: a PUSH puts a number on the stack; an operator pops two, computes, and pushes the result. After all instructions, the answer is the single value left on the stack.a = stack.pop(); b = stack.pop() order — we pop
b first (it was pushed last), then a, so a - b subtracts in the right direction.compile once, run anytime — the bytecode is a portable artifact. This separation — a compiler front end and a VM back end — is precisely how Python and Java work.
Common mistakes — and how to avoid them
✗ Emitting the operator before its operands — the stack machine then has nothing to operate on.
✓ Emit both operands first, then the operator (postfix order).
✗ Popping operands in the wrong order —
SUB and DIV come out backwards.✓ Pop
b (top) first, then a, and compute a op b.✗ Mixing evaluation into the compiler — that makes it an interpreter, not a compiler.
✓ The compiler should only emit instructions; the VM executes them.
4 Test & Prove Each Part
We test both halves: that compilation emits correct bytecode, and that the VM executes it to the right answer.
Compiling emits push/operator bytecode
The VM executes bytecode correctly
Precedence is preserved through to the result
The full pipeline matches direct calculation
Pythontest_compiler.py
import re
def tokenize(text):
tokens = []
for part in re.findall(r"\d+|[+\-*/()]", text):
tokens.append(("NUM", int(part)) if part.isdigit() else (part, part))
return tokens
class Compiler:
def __init__(self, tokens):
self.tokens = tokens
self.pos = 0
self.code = []
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):
self.term()
while self.peek()[0] in ("+", "-"):
op = self.eat()[0]
self.term()
self.code.append("ADD" if op == "+" else "SUB")
def term(self):
self.factor()
while self.peek()[0] in ("*", "/"):
op = self.eat()[0]
self.factor()
self.code.append("MUL" if op == "*" else "DIV")
def factor(self):
tok_type, tok_value = self.eat()
if tok_type == "NUM":
self.code.append(("PUSH", tok_value))
elif tok_type == "(":
self.expr()
self.eat()
def compile_source(text):
c = Compiler(tokenize(text))
c.expr()
return c.code
def run(bytecode):
stack = []
for ins in bytecode:
if isinstance(ins, tuple):
stack.append(ins[1])
else:
b = stack.pop(); a = stack.pop()
if ins == "ADD": stack.append(a + b)
elif ins == "SUB": stack.append(a - b)
elif ins == "MUL": stack.append(a * b)
elif ins == "DIV": stack.append(a / b)
return stack[0]
def test_emits_bytecode():
"""2 + 3 compiles to push, push, add."""
assert compile_source("2 + 3") == [("PUSH", 2), ("PUSH", 3), "ADD"]
def test_vm_runs():
"""The VM executes simple bytecode."""
assert run([("PUSH", 2), ("PUSH", 3), "ADD"]) == 5
def test_precedence_preserved():
"""2 + 3 * 4 compiles and runs to 14."""
assert run(compile_source("2 + 3 * 4")) == 14
def test_full_pipeline():
"""The pipeline matches direct calculation."""
assert run(compile_source("(2 + 3) * 4")) == 20
Run with pytest -v. The test_emits_bytecode test shows the compiler’s output explicitly — you can read the instructions. The pipeline tests prove compile-then-run gives the same answers as the interpreter, the two approaches meeting at the same result.
5 The Interface
compilecompile_source(text)source to bytecode
Output
[("PUSH", 2), ("PUSH", 3), ("PUSH", 4), "MUL", "ADD"]runrun(bytecode)VM executes it
Result
146 Run It & Automate It
Run it locally
python3 compiler.pySee the bytecode your source compiles to, then watch the VM run it. You have built a real compiler.
Jenkins runs the tests automatically — each line explained below.
What you should see when it works
Terminala real run
Bytecode: [('PUSH', 2), ('PUSH', 3), ('PUSH', 4), 'MUL', 'ADD']
Result: 14If it breaks — how to fix it
🚨 Subtraction/division give wrong signs.
Check pop order:
b = pop(); a = pop() then a - b.🚨
IndexError in the VM.The stack underflowed — your bytecode order is wrong. Operands must be pushed before operators.
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. Add
STORE/LOADinstructions and a variable slot. (Teaches: memory in a VM.) - Disassemble. Pretty-print bytecode like Python's
dismodule. (Teaches: tooling.) - Compile to a file. Save bytecode and load it to run later. (Teaches: the real compile-once benefit.)
What you learned
You built a compiler and virtual machine — the capstone. You tokenize, parse, generate stack-based bytecode, and execute it on a VM. This is how Python and Java actually run: compile to bytecode once, execute on a VM. You have completed the journey from print("hello") to building a language. Related: re, Object-Oriented Python.