The whole series in one sitting. We design a tiny language — MiniLang — and build a complete compiler for it in ~400 lines of Python: a hand-written lexer, a recursive-descent + Pratt parser, a type checker, a three-address SSA-ish IR, two optimisations, a bytecode emitter and a stack VM. One running example — an iterative factorial — threads through every slide so you watch the same program transform, stage by stage, until it prints 120.
A capstone, not a lecture. Every slide carries the same program forward one phase. By the end you have seen a real compiler — small, but complete and internally consistent — from source text to a printed result.
Seven passes, each a small function over the previous pass's output. Nothing here is toy in shape — this is exactly the skeleton of a real compiler, just scaled down. Same example all the way through.
Each pass is something you already met: lexing (03), parsing (04), type checking (05), IR (06), optimisation (07), codegen (08), and a runtime (09). Here they fit together on one desk.
We implement in Python throughout — readable, no build step, and the dataclasses map cleanly onto AST/IR nodes. The compiled language is MiniLang; the host language is Python.
Every feature we add is a feature we must lex, parse, check, lower, optimise and codegen. So we keep MiniLang deliberately tiny — just enough to be Turing-complete and recognisably a real language.
int and boollet; assignment+ - * /; comparison < > == !=if/else and whilefn with returnprint as a built-in statementfact.mlfn fact(n) {
let acc = 1;
while (n > 1) {
acc = acc * n;
n = n - 1;
}
return acc;
}
print(fact(5));It exercises nearly every feature in one screen: a function, a let, a while loop with a comparison, mutation of two variables, a call, and a print. Its result — 120 — is easy to check by hand. We will see this exact program at every stage.
A compact grammar drives the parser's structure. Statements are LL(1) — one token of lookahead picks the rule. Expressions use a precedence-driven sub-grammar (the Pratt parser, slide 08) rather than the layered rules shown here.
program = { decl } ;
decl = fnDecl | statement ;
fnDecl = "fn" IDENT "(" params? ")" block ;
params = IDENT { "," IDENT } ;
block = "{" { statement } "}" ;
statement = letStmt | assign | ifStmt
| whileStmt | returnStmt
| printStmt | exprStmt ;
letStmt = "let" IDENT "=" expr ";" ;
assign = IDENT "=" expr ";" ;
ifStmt = "if" "(" expr ")" block
[ "else" block ] ;
whileStmt = "while" "(" expr ")" block ;
returnStmt = "return" expr ";" ;
printStmt = "print" "(" expr ")" ";" ;
exprStmt = expr ";" ;(* expression grammar — by precedence,
lowest to highest *)
expr = equality ;
equality = compare { ("==" | "!=") compare } ;
compare = term { ("<" | ">" ) term } ;
term = factor { ("+" | "-" ) factor } ;
factor = unary { ("*" | "/" ) unary } ;
unary = [ "-" | "!" ] unary | call ;
call = primary { "(" args? ")" } ;
args = expr { "," expr } ;
primary = NUMBER | "true" | "false"
| IDENT | "(" expr ")" ;{ x } — zero or more (left-associative loop)[ x ] — optionalfactor (*) before term (+)UPPERCASE = terminal token classes from the lexerThe lexer turns the character stream into a token stream, tracking line/column for error messages. It is a single pass with a few if-ladders — no regex engine, no table generator. (Deck 03 covered the theory; this is the practice.)
KEYWORDS = {"fn","let","if","else","while",
"return","print","true","false"}
class Tok:
def __init__(s, kind, val, line, col):
s.kind, s.val = kind, val
s.line, s.col = line, col
def __repr__(s):
return f"{s.kind}:{s.val!r}@{s.line}:{s.col}"
def lex(src):
toks, i, line, col = [], 0, 1, 1
def adv(n=1):
nonlocal i, col
i += n; col += n
while i < len(src):
c = src[i]
if c in " \t": adv()
elif c == "\n": i+=1; line+=1; col=1 elif c.isdigit():
j = i
while i<len(src) and src[i].isdigit(): adv()
toks.append(Tok("NUM", int(src[j:i]), line, col))
elif c.isalpha() or c=="_":
j = i
while i<len(src) and (src[i].isalnum() or src[i]=="_"):
adv()
w = src[j:i]
kind = w if w in KEYWORDS else "IDENT"
toks.append(Tok(kind, w, line, col))
else:
two = src[i:i+2]
if two in ("==","!=","<=",">="):
toks.append(Tok(two, two, line, col)); adv(2)
elif c in "+-*/()<>{},;=!":
toks.append(Tok(c, c, line, col)); adv()
else:
raise LexError(line, col, f"bad char {c!r}")
toks.append(Tok("EOF", None, line, col))
return toksTwo-character operators (==, !=) are matched before single characters — maximal munch. Keywords are just identifiers looked up in a set, so adding one is a one-line change.
fact.mlRunning lex(open("fact.ml").read()) on our example yields this stream (whitespace and newlines dropped, line:col elided for brevity). This is the only thing the parser ever sees — the source text is gone.
fn IDENT:fact ( IDENT:n ) {
let IDENT:acc = NUM:1 ;
while ( IDENT:n > NUM:1 ) {
IDENT:acc = IDENT:acc * IDENT:n ;
IDENT:n = IDENT:n - NUM:1 ;
}
return IDENT:acc ;
}
print ( IDENT:fact ( NUM:5 ) ) ;
EOFfact, n, acc → IDENT (not keywords)fn, let, while, return, print → keyword kinds1 and 5 → NUM with an integer value, already parsed>, *, -, = → single-char operator tokensEOF token terminates the stream=The lexer emits a single = token in both let acc = 1 and acc = acc * n. Disambiguating declaration from assignment is the parser's job, not the lexer's — lexing is context-free.
The 9-line program becomes 43 tokens. Each carries a source position, so any later phase can point back at the exact character that caused a problem.
Before parsing, define the tree. Python @dataclasses give us cheap, typed, comparable nodes — ideal for golden tests. Statements and expressions are two small families.
from dataclasses import dataclass, field
# ─── expressions ───
@dataclass
class Num: value: int
@dataclass
class Bool: value: bool
@dataclass
class Var: name: str
@dataclass
class Unary: op: str; operand: object
@dataclass
class Bin: op: str; lhs: object; rhs: object
@dataclass
class Call: fn: str; args: list# ─── statements ───
@dataclass
class Let: name: str; init: object
@dataclass
class Assign: name: str; value: object
@dataclass
class If: cond: object; then: list; els: list
@dataclass
class While: cond: object; body: list
@dataclass
class Return: value: object
@dataclass
class Print: value: object
@dataclass
class ExprStmt: expr: object
@dataclass
class Fn: name: str; params: list; body: list
@dataclass
class Program: decls: listEach node also carries a line field (omitted above for space) copied from its first token — the thread that lets a type error on slide 10 say "line 4, column 9". Nodes are pure data: no methods, no behaviour. Passes are functions over nodes.
Statements use recursive descent — one method per grammar rule. Expressions use a Pratt (precedence-climbing) parser: one loop driven by a binding-power table, far terser than the layered EBNF rules.
class Parser:
def __init__(s, toks): s.toks, s.i = toks, 0
def peek(s): return s.toks[s.i]
def next(s): t = s.toks[s.i]; s.i += 1; return t
def eat(s, k):
t = s.next()
if t.kind != k:
raise ParseError(t, f"expected {k}, got {t.kind}")
return t
def statement(s):
k = s.peek().kind
if k == "let": return s.let_stmt()
if k == "if": return s.if_stmt()
if k == "while": return s.while_stmt()
if k == "return": return s.return_stmt()
if k == "print": return s.print_stmt()
return s.assign_or_expr() # Pratt: left binding powers per operator
LBP = {"==":1,"!=":1,"<":2,">":2,
"+":3,"-":3,"*":4,"/":4}
def expr(s, min_bp=0):
left = s.unary() # nud
while s.peek().kind in s.LBP and \
s.LBP[s.peek().kind] > min_bp:
op = s.next().kind # led
right = s.expr(s.LBP[op]) # climb
left = Bin(op, left, right)
return left
def unary(s):
if s.peek().kind in ("-","!"):
op = s.next().kind
return Unary(op, s.unary())
return s.call() # then primaryBecause * has a higher binding power (4) than + (3), acc * n binds before any surrounding + automatically — precedence falls out of the min_bp comparison, no grammar layering needed.
fact.mlParsing the token stream produces this tree. The Fn node roots the function; the body is a list of statements; the while's condition and the multiply nest as Bin nodes. Top level holds the Fn and the print(fact(5)).
One walk of the AST builds a scoped symbol table and checks types. MiniLang has just two types, int and bool, so the checker is a small recursive function that returns a type or raises with a source span.
class Scope:
def __init__(s, parent=None):
s.vars, s.parent = {}, parent
def define(s, name, ty): s.vars[name] = ty
def lookup(s, name):
sc = s
while sc:
if name in sc.vars: return sc.vars[name]
sc = sc.parent
return None
INT, BOOL = "int", "bool"
ARITH = {"+","-","*","/"}
CMP = {"<",">","==","!="}def check_expr(e, scope):
if isinstance(e, Num): return INT
if isinstance(e, Bool): return BOOL
if isinstance(e, Var):
ty = scope.lookup(e.name)
if ty is None:
err(e.line, f"undefined variable {e.name!r}")
return ty
if isinstance(e, Bin):
lt, rt = check_expr(e.lhs, scope), check_expr(e.rhs, scope)
if lt != INT or rt != INT:
err(e.line, f"operator {e.op!r} needs int operands")
return INT if e.op in ARITH else BOOL # cmp → boolStatements thread the scope: Let calls scope.define(name, check_expr(init)); entering a block pushes a child Scope; if/while require their condition to be bool. Shadowing is resolved by the lookup chain — innermost scope wins.
Our fact.ml passes cleanly. To see the checker bite, break it: use a bool where an int is required. The checker reports the exact line, caught before any code is generated.
fn fact(n) {
let acc = 1;
while (n > 1) {
acc = acc * (n > 0); // ← bool * int
n = n - 1;
}
return acc;
}lookup returns None)bool condition in if/whilereturn outside a function bodyerror: operator '*' needs int operands
--> fact.ml:4:11
|
4 | acc = acc * (n > 0);
| ^^^^^^^^^^^^^ rhs has type bool
|
note: comparison '>' yields bool, not intThe IR and VM assume well-typed input — the multiply opcode just pops two ints. Catching type errors in the front end keeps every later phase simple: by the time we lower, "it type-checks" is an invariant we can rely on.
We lower the typed AST to a linear three-address IR over basic blocks. Every instruction has at most one operator and writes one temporary. Control flow becomes explicit br / cbr between blocks — the while loop unfolds into a header, body and exit block.
@dataclass
class Instr: op: str; args: tuple; dst: str = None
@dataclass
class Block: label: str; instrs: list; term: object
class Lower:
def __init__(s): s.n = 0; s.blocks = []
def temp(s): s.n += 1; return f"t{s.n}"
def expr(s, e, blk):
if isinstance(e, Num):
t = s.temp(); blk.append(Instr("const",(e.value,),t)); return t
if isinstance(e, Var): return e.name
if isinstance(e, Bin):
a = s.expr(e.lhs, blk); b = s.expr(e.rhs, blk)
t = s.temp(); blk.append(Instr(e.op,(a,b),t)); return t def while_(s, node):
head, body, end = s.new_blocks(3)
s.emit_br(head)
# header: test, then conditional branch
c = s.expr(node.cond, head.instrs)
head.term = Cbr(c, body.label, end.label)
# body: statements, then back-edge to header
for st in node.body: s.stmt(st, body.instrs)
body.term = Br(head.label)
s.cur = end # fall through to exit blockEach temporary t1, t2, … is assigned once — the defining property of SSA. Named locals (acc, n) are still reassigned here; a full SSA pass (deck 06) would rename them and insert φ-nodes at the loop header.
Here is fact lowered to four basic blocks. The φ-nodes at the loop header pick the value from the entry edge or the back-edge — this is the SSA form (deck 06) the optimiser actually rewrites.
fn fact(n):
entry:
acc.0 = const 1
br header
header: ; loop test
n.1 = phi [n.0, entry], [n.2, body]
acc.1 = phi [acc.0, entry], [acc.2, body]
t1 = gt n.1, 1
cbr t1, body, exit
body:
acc.2 = mul acc.1, n.1
n.2 = sub n.1, 1
br header
exit:
ret acc.1The dashed back-edge body→header is what makes this a loop. The φ at the header is the only place two definitions of n / acc meet.
SSA makes peephole optimisations almost trivial. We add two passes (deck 07): constant folding evaluates compile-time-constant instructions, and dead-code elimination deletes instructions whose result is never used.
# Constant folding: fold ops on literal args
FOLD = {"add":lambda a,b:a+b, "sub":lambda a,b:a-b,
"mul":lambda a,b:a*b, "gt":lambda a,b:int(a>b)}
def fold(blocks, consts):
for blk in blocks:
for ins in blk.instrs:
a = [consts.get(x, x) for x in ins.args]
if ins.op in FOLD and all(isinstance(x,int) for x in a):
v = FOLD[ins.op](*a) # evaluate now
ins.op, ins.args = "const", (v,)
consts[ins.dst] = v # propagate
def dce(blocks):
used = {x for b in blocks for i in b.instrs
for x in i.args} | live_in_terms(blocks)
for b in blocks:
b.instrs = [i for i in b.instrs
if i.dst in used or i.op=="call"] t1 = const 2
t2 = const 3
t3 = mul t1, t2 ; 2 * 3
r = add t3, n ; r = 6 + n
u = const 99 ; let unused = 99
ret r t3 = const 6 ; 2*3 folded
r = add t3, n
ret r ; 'u' deleted — never usedFold first (it creates new constants and may make values dead), then DCE sweeps them up. Real compilers iterate the two to a fixpoint.
The back end targets a stack machine (like JVM / CPython bytecode, deck 09). Values live on an operand stack; locals live in numbered slots per call frame. Fourteen opcodes are enough for all of MiniLang.
| Opcode | Stack effect | Meaning |
|---|---|---|
CONST k | → k | push literal k |
LOAD s | → locals[s] | push local slot s |
STORE s | v → | pop into slot s |
ADD/SUB/MUL/DIV | a b → r | integer arithmetic |
LT / GT / EQ | a b → 0|1 | comparison |
JMP t | — | jump to offset t |
JZ t | v → | jump if popped == 0 |
CALL f n | args → r | call f with n args |
RET | v → | return top of stack |
PRINT | v → | pop & print |
HALT | — | stop the VM |
Each three-address instruction expands to a short opcode sequence: t = mul a, b becomes LOAD a; LOAD b; MUL; STORE t. A cbr becomes the condition followed by JZ exit. Block labels resolve to integer offsets in a second pass (back-patching).
define i64 @fact(i64 %n) {
; our three-address IR maps almost
; 1:1 onto LLVM's SSA form —
; mul → mul i64, cbr → br i1,
; phi → phi. Then llc does regalloc
; & instruction selection for you.
}factHere is the emitted bytecode for the fact function after labels are back-patched to offsets. Locals: slot 0 = n (the argument), slot 1 = acc. Compare it instruction-by-instruction with the IR on slide 13.
fn fact/1: ; arity 1
0 CONST 1 ; acc = 1
1 STORE 1
; --- header (offset 2) ---
2 LOAD 0 ; n
3 CONST 1
4 GT ; n > 1
5 JZ 15 ; if !cond → exit
6 LOAD 1 ; acc
7 LOAD 0 ; n
8 MUL ; acc * n
9 STORE 1 ; acc = ...
10 LOAD 0 ; n
11 CONST 1
12 SUB ; n - 1
13 STORE 0 ; n = ...
14 JMP 2 ; back to header
15 LOAD 1 ; exit: acc
16 RETacc = 1)JZ 15 is the cbr — exit when n > 1 is falseJMP 2 is the loop back-edgeLOAD/CONST pushes, each binary op pops two and pushes one 0 CONST 5
1 CALL fact 1 ; fact(5) → 120
2 PRINT
3 HALTThe whole function is 17 bytecodes. No registers to allocate — the stack is the calling convention. That simplicity is why bytecode VMs are easy to write and port.
A stack VM is a while loop with a dispatch on the opcode. Each frame holds an instruction pointer, a local array and shares the operand stack. This loop executes the bytecode above and prints the result.
class Frame:
def __init__(s, code, locals_):
s.code, s.ip, s.locals = code, 0, locals_
def run(program, entry):
stack, frames = [], [Frame(entry, [])]
while frames:
f = frames[-1]
op, *a = f.code[f.ip]; f.ip += 1
if op == "CONST": stack.append(a[0])
elif op == "LOAD": stack.append(f.locals[a[0]])
elif op == "STORE":
v = stack.pop()
while len(f.locals) <= a[0]: f.locals.append(0)
f.locals[a[0]] = v
elif op == "ADD": b=stack.pop(); stack.append(stack.pop()+b)
elif op == "SUB": b=stack.pop(); stack.append(stack.pop()-b)
elif op == "MUL": b=stack.pop(); stack.append(stack.pop()*b) elif op == "GT":
b=stack.pop(); stack.append(int(stack.pop() > b))
elif op == "JMP": f.ip = a[0]
elif op == "JZ":
if stack.pop() == 0: f.ip = a[0]
elif op == "CALL":
fn, n = program[a[0]], a[1]
args = [stack.pop() for _ in range(n)][::-1]
frames.append(Frame(fn.code, args))
elif op == "RET":
frames.pop() # back to caller
elif op == "PRINT": print(stack.pop())
elif op == "HALT": return
# RET leaves the return value on the shared stackNo registers, no addressing modes, no calling-convention bookkeeping. The operand stack carries arguments and results; RET just pops the frame and leaves the value behind for the caller. ~25 lines runs the language.
The driver wires every pass together. From source file to printed answer is six function calls — and out comes 120, matching 5! = 5×4×3×2×1.
def compile_and_run(path):
src = open(path).read()
toks = lex(src) # 03 — lexer
ast = Parser(toks).program() # 04 — parser
check(ast) # 05 — semantics
ir = Lower().run(ast) # 06 — lowering
fold(ir.blocks, {}); dce(ir.blocks) # 07 — optimise
program = emit(ir) # 08 — codegen
run(program, program["__main__"]) # 09 — VM
if __name__ == "__main__":
compile_and_run("fact.ml")$ python minilang.py fact.ml
120| iter | n | acc | n>1? |
|---|---|---|---|
| start | 5 | 1 | true |
| 1 | 4 | 5 | true |
| 2 | 3 | 20 | true |
| 3 | 2 | 60 | true |
| 4 | 1 | 120 | false |
| exit | 1 | 120 | — |
The same program produced the tokens (06), AST (09), IR (13), bytecode (16), and now the answer — every artefact in this deck describes this one execution. That consistency is the whole point of the capstone.
A compiler is a function; test it like one. Each stage takes a value and returns a value, so each is testable in isolation — and the whole pipeline is testable with golden files.
repr(ast) equality — dataclasses compare structurallyKeep tests/*.ml beside *.expected. Run each through the full pipeline and diff stdout. A failing diff is a regression — cheap, high-coverage, and they double as documentation.
import subprocess, glob
def test_golden():
for ml in glob.glob("tests/*.ml"):
expected = open(ml.replace(".ml",".expected")).read()
out = subprocess.run(
["python","minilang.py",ml],
capture_output=True, text=True).stdout
assert out == expected, ml
# tests/fact.ml + tests/fact.expected ("120\n")
# tests/fib.ml + tests/fib.expected ("55\n")Every token carries line/col; every AST and IR node copies it. So a message can always point at the offending source — fact.ml:4:11 — with a caret and a note. Carry positions everywhere; never throw them away.
MiniLang is a skeleton. Every shortcut we took is a door to a deeper topic. Here is the path from this toy to a real front end — and the canonical books and projects to take you there.
float, then strings & a heap (now you need a GC — deck 09)llc finishTry parsing a non-trivial subset of C or Python; wire your IR into LLVM via its C API or llvmlite; or target WebAssembly and run in a browser.
Ten decks, one journey: from the history of the idea to a working compiler you built yourself. Each phase we coded today was a deck of its own — here they are, in order, threaded by the same arrow you saw on slide 1.
fact(5) → 43 tokens → an AST → 4 basic blocks of SSA-ish IR → folded IR → 17 bytecodes → 120. Same program, every slide.
From Grace Hopper's A-0 (deck 01) to your own working VM (deck 10) — you've now seen, and built, the whole arc from source text to running code.