10 parts · 10 chapters
Compilers and Interpreters
How source text becomes something a machine runs, stage by stage, using the 471-line compiler from the BYO course as the running example. Its six tests pass, and its own bytecode output shows the first optimisation to write. Measured: the BYO stack VM computed fib(25) in about 150 ms wall time including Node startup; V8's JIT ran the same function in 0.9 ms.
Ten parts: lexing; parsing with recursive descent, Pratt and LR; abstract syntax trees; type checking; intermediate representations and SSA; optimisation passes; code generation; bytecode virtual machines; garbage collectors; and a capstone that extends the BYO compiler with a peephole optimiser, a new type and a mark-sweep heap.
front endCharacters → tokens → tree, with good error messages.
meaningScopes, types and checks before running anything.
middleIR, SSA and the passes that make code faster.
back endBytecode or machine code, registers and calls.
runtimeVMs, dispatch loops, JITs and garbage collection.
practiceExtend a real, tested 471-line compiler.
00
Lexing
Characters in, tokens out
1 ch · ~8 min01Parsing: Recursive Descent, Pratt, LR
The BYO Pratt loop
1 ch · ~8 min02ASTs
Trees as discriminated unions
1 ch · ~8 min03Type Checking
Types computed bottom-up
1 ch · ~8 min04IR and SSA
Three-address code and SSA
1 ch · ~8 min05Optimisation Passes
Folding, and waste in real output
1 ch · ~8 min06Code Generation
From tree to instructions
1 ch · ~8 min07Bytecode VMs
A VM in 55 lines
1 ch · ~8 min08Garbage Collectors
A mark-sweep collector in TypeScript
1 ch · ~8 min09Capstone: Extend the BYO Compiler
Four extensions
1 ch · ~8 minBuilt on Theory of Computation and BYOUses Theory of Computation for automata and grammars and extends the BYO course's compiler (modules/byo/repos/compiler).