Compiler Design
A compiler is a pipeline of transformations, and each one has a shape you can draw. These topics take a single expression and carry it through every phase.
Start from the beginning →13 topics you can watch now, 11 still to come.
Foundations
What a compiler is, what it is not, and everything else that runs before your program does.
- What is a Compiler?Start here. One program translated ahead of time, one interpreted line by line, and why Java does both.
- The Language Processing SystemPreprocessor, compiler, assembler, linker, loader — five tools, and the file each one hands to the next.
- Bootstrapping and cross-compilers
The pipeline
The whole journey first, so every later phase has somewhere to sit.
- Front end vs back end in depth
- Passes and pass structure
Lexical analysis
Turning a stream of characters into a stream of words.
- Tokens and LexemesSixteen characters become six tokens — longest match, discarded whitespace, and a symbol table.
- Symbol Tables and ScopePush a scope on entry, pop it on exit, and search inward-out. That is all lexical scoping is.
- Regex to DFA for scanning
Parsing
Discovering the structure that the grammar says must be there.
- FIRST and FOLLOW SetsThe two set computations that fill an LL(1) table — and the ε-productions that make FOLLOW necessary.
- LL(1) Predictive ParsingA stack of what is still expected, one lookahead token, and no backtracking anywhere.
- Shift-Reduce ParsingWatch a stack and a parse tree build each other — and see exactly where operator precedence is decided.
- LR(0) item sets
- SLR, LALR and CLR
Semantic analysis
Checking the things a grammar cannot express, like types.
- Syntax-directed translation
- Attribute grammars
Intermediate code
A representation simple enough to optimise and easy to emit from.
- Three-Address CodeWalk the syntax tree bottom-up; every operator emits exactly one instruction.
- Basic Blocks and Flow GraphsThree rules find the leaders, the leaders make the blocks, and a cycle in the graph is a loop.
- DAG representation of a block
Optimisation and generation
Making it smaller and faster, then making it real instructions.
- Peephole OptimisationA three-instruction window and a handful of patterns turn seven instructions into four.
- Register Allocation by Graph ColouringVariables live at the same time interfere; colouring the graph assigns registers, and running out means a spill.
- Loop optimisation
- Instruction selection