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
About Compiler Design
A compiler is a long pipeline of small, well-understood transformations, and the reason the subject is worth studying is that almost every stage is a reusable idea. Lexing, parsing, building a symbol table, walking an intermediate representation, allocating registers — these turn up in linters, formatters, query engines, template systems and configuration languages.
The pipeline shape also means each phase can be understood on its own. Parsing turns a flat string into a tree using a grammar. Semantic analysis decorates the tree with meaning. Optimisation rewrites the intermediate form into something cheaper but equivalent, and the word equivalent is doing a lot of work. Code generation finally commits to a machine.
Register allocation and optimisation are where the animations matter most: both are algorithms whose intermediate states are the entire point, and both are ordinarily taught with before-and-after snapshots that skip the interesting middle.
What to know first
- Fluency in at least one language, and curiosity about what happens to the source
- Theory of Computation helps, particularly automata and grammars
Where it gets used
- Writing a parser for a config or query language without inventing the theory
- Reading compiler output and knowing which optimisation produced it
- Understanding why some code is intrinsically hard for a compiler to speed up