Compiler Design
Lexers, parsers, syntax trees, type checking, intermediate code, optimization and code generation: every phase of a compiler built and run in Python.
- Level
- Advanced
- Time
- About 24 hours
- Modules
- 5
- Lessons
- 15
- Exercises
- 45
A compiler turns text that people write into instructions a machine can run. This course builds one phase at a time: a lexer that splits text into tokens, parsers that check the grammar and build a syntax tree, symbol tables and a type checker that find mistakes, three-address code and the optimizations that improve it, and finally stack-machine code and register allocation.
Every phase is real code you run in your browser. You write recursive-descent, LL(1) and shift-reduce parsers, compute FIRST and FOLLOW sets, check scopes and types, lower loops to jumps, fold constants and remove dead code, build control-flow graphs and liveness, and compile a small language all the way to a virtual machine. By the end you can read the output of real compilers and explain what each part of it is for.
What you will learn
- Write lexers with regular expressions and by hand
- Write recursive-descent, LL(1) and shift-reduce parsers, and compute FIRST and FOLLOW sets
- Build syntax trees, resolve names in nested scopes and type-check programs
- Lower programs to three-address code and optimize it
- Build control-flow graphs, compute liveness and allocate registers
- Generate stack-machine code with backpatched jumps and run it on a virtual machine
Skills you will gain
- Lexical analysis
- Parsing and grammar analysis
- Syntax trees, scopes and type checking
- Intermediate code and optimization
- Dataflow analysis and code generation
Before you start
- Python: functions, classes, dictionaries, sets and recursion (the Python course)
- Stacks, trees and graphs (the Data Structures course)
- Regular expressions and grammars help (the Theory of Computation course)
Where it is used
- Interpreters and compilers for programming and query languages
- Linters, formatters and editor tooling built on syntax trees
- Configuration and domain-specific languages
- Reading compiler output to make code faster
Modules
Module 1: From source to tokens
What a compiler is made of, and its first phase: turning characters into tokens, with regular expressions and with a hand-written scanner.
- 1
How a compiler works Intermediate
A compiler turns source code into something a machine can run, in phases: lexing, parsing, checking, intermediate code, optimisation and code generation. Build a whole tiny compiler for arithmetic in 60 lines of Python.
- 2
Lexical analysis with regular expressions Intermediate
A lexer turns characters into tokens: numbers, names, keywords and operators, with their positions. Build one from a table of regular expressions combined into a single pattern, the way many real lexers are generated.
- 3
A hand-written lexer Intermediate
Write a lexer the way production compilers often do: one character at a time, with peek and advance, longest match, and lookahead for two-character operators and decimal numbers.
Module 2: Parsing
Turning tokens into structure: recursive descent, the FIRST and FOLLOW sets behind predictive parsing, table-driven LL(1) parsing and bottom-up shift-reduce parsing.
- 1
Recursive-descent parsing Intermediate
Turn a grammar into a parser by writing one function per rule. Handle precedence with levels, associativity with loops or recursion, remove left recursion, and report syntax errors clearly.
- 2
FIRST and FOLLOW sets Advanced
Predictive parsers decide which rule to use by looking at the next token. Compute nullable symbols, FIRST sets and FOLLOW sets by repeating simple rules until nothing changes.
- 3
LL(1) parsing with a table Advanced
Build a parse table from FIRST and FOLLOW sets, then parse with an explicit stack instead of recursion. Detect grammars that need more than one token of lookahead.
- 4
Bottom-up parsing: shift and reduce Advanced
Bottom-up parsers read tokens onto a stack and reduce them to grammar rules when a rule's body is on top. See shift-reduce parsing step by step, resolve conflicts with precedence, and learn why LR parsers accept left-recursive grammars.
Module 3: Trees, scopes and types
The program as a tree: abstract syntax trees and tree walks, symbol tables with nested scopes, and type checking with type rules.
- 1
Abstract syntax trees Intermediate
Represent a program as a tree of nodes that keeps its meaning and drops the punctuation. Build the tree in the parser, then walk it with recursive functions to print, evaluate or check it.
- 2
Symbol tables and scopes Intermediate
A compiler must know what each name refers to. Keep a symbol table as a stack of scopes, declare names in the innermost scope, look them up from the inside out, and report undeclared and duplicate names.
- 3
Type checking Advanced
Give every expression a type and reject programs that combine types wrongly, before they run. Write type rules, check a tree bottom-up with an environment of declared types, and report clear type errors.
Module 4: Intermediate code and optimization
Lowering to three-address code, local optimizations such as constant folding and dead code elimination, and control-flow graphs with liveness analysis.
- 1
Three-address code Advanced
Lower the syntax tree to an intermediate representation: simple instructions with at most one operator each, temporaries for partial results, and labels with jumps for loops and conditions.
- 2
Optimizing intermediate code Advanced
Make code faster without changing what it does. Fold constants, propagate known values and copies, simplify with algebra, reuse common subexpressions and delete dead code, all on three-address code.
- 3
Basic blocks, control-flow graphs and liveness Advanced
Split code into basic blocks, connect them into a control-flow graph, find loops and unreachable code, and compute which variables are live with a dataflow analysis repeated until nothing changes.
Module 5: Generating code
The back end: compiling to a stack machine with backpatched jumps, running it on a virtual machine, and assigning registers with linear scan.
- 1
Generating code for a stack machine Advanced
Compile variables, loops and conditions to stack-machine instructions, fill in jump addresses with backpatching, and run the result on a small virtual machine, the way the JVM, CPython and WebAssembly work.
- 2
Register allocation Advanced
Decide which values live in the processor's few registers. Compute live ranges, measure register pressure, and assign registers with linear scan, spilling to memory when there are not enough.
Projects
- A compiler for a small language Build a compiler for a small language with variables, arithmetic, comparisons, if/else, while and print, that compiles to stack-machine code and runs it on your own virtual machine.
- An optimizing back end Build a back end that takes three-address code, optimizes it, analyses its control flow and assigns registers, and show how much each step improves the code.
What to learn next
- Theory of Computation Finite automata, regular expressions, grammars, pushdown automata, Turing machines, the halting problem and P vs NP, every machine built and run in Python.
- Algorithms Searching, sorting, recursion, greedy choices, dynamic programming and graph algorithms, with the cost of each one counted.