A map of the whole journey a program takes — the analysis/synthesis split, the seven classic phases, the intermediate representations that flow between them, and the wider toolchain of driver, assembler, linker and loader that turns text into a process
This deck frames the whole series. Every later part zooms into one box on the pipeline; here we lay out the map — the phases, the representations between them, and the tools around the compiler proper.
int x = a + b * 2;A compiler is a program that reads a program in one language — the source — and translates it into an equivalent program in another language — the target — reporting any errors it finds along the way. Equivalent means same observable behaviour, not same text.
Grace Hopper's A-0 (1952) compiled — assembled — subroutines from a library. The name stuck even as the job grew into full translation.
The target need not be machine code: a compiler may emit assembly, bytecode, or another high-level language. The defining act is meaning-preserving translation across a language gap.
“Compiler” is one point in a family of language processors. The axes that distinguish them: when translation happens, and what the target is.
| Kind | What it does | When | Example |
|---|---|---|---|
| Compiler (AOT) | Source → machine code, ahead of execution | Build time | GCC, Clang, rustc, Go |
| Interpreter | Executes source / AST directly, no separate target | Run time | CPython (tree-walk-ish), Ruby MRI |
| Transpiler | Source → another high-level language (source-to-source) | Build time | TypeScript→JS, Babel, f2c |
| Bytecode + VM | Source → bytecode, then a VM interprets it | Build + run | javac → JVM, CPython → CPython VM |
| JIT | Compiles hot bytecode to machine code during execution | Run time | HotSpot C2, V8 TurboFan, PyPy |
| Hybrid | AOT to bytecode + JIT/interpret tiers at run time | Both | .NET CLR, modern JVMs, JS engines |
The line is blurry. CPython compiles to .pyc bytecode then interprets it; a JIT interprets first then compiles hot paths. The question is really “how much work happens before the first instruction runs?”
The Dragon Book splits a compiler into an analysis half (the front end) that breaks the source apart and an synthesis half (the back end) that builds the target up. A middle end sits between, working on a language- and target-neutral IR.
A checked AST or IR plus a populated symbol table. It has decided the program is well-formed.
Rewrites the IR into a faster, smaller, equivalent IR. Knows neither syntax nor registers.
Target assembly or object code, tuned to one ISA's registers, addressing modes and pipeline.
Conventionally seven phases. The first three are the front end (analysis); IR generation bridges; the last three are the middle/back end (synthesis). Each consumes the previous phase's output and produces a richer representation.
| Phase | In → Out |
|---|---|
| 1. Lexical analysis | chars → token stream |
| 2. Syntax analysis | tokens → parse tree / AST |
| 3. Semantic analysis | AST → annotated (typed) AST |
| 4. IR generation | AST → intermediate code |
| Phase | In → Out |
|---|---|
| 5. M/I optimisation | IR → better IR |
| 6. Code generation | IR → target asm |
| 7. Target optimisation | asm → tuned asm |
Two services thread through every phase: the symbol table (names → attributes) and the error handler (diagnostics & recovery).
In: raw characters.
Out: a stream of tokens (lexeme + class).
Strips whitespace/comments; groups int, x, = into kinds. Driven by regular expressions → a DFA scanner. (Part 03.)
In: token stream.
Out: a parse tree / AST.
Checks the tokens form a valid sentence of the grammar (CFG). LL/LR parsing builds the tree that captures structure. (Part 04.)
In: AST.
Out: annotated AST + symbol table.
Resolves names, checks types, scopes, declarations. Adds the meaning the grammar alone can't enforce. (Part 05.)
Each phase needs its predecessor's guarantee: you can't parse without tokens, can't type-check without structure, can't generate code without a meaning. The split also localises errors — a lexer error is a stray character, a parser error a malformed phrase, a semantic error a type mismatch.
In: typed AST. Out: intermediate code (e.g. three-address code, SSA).
Lowers tree-shaped meaning into a linear, machine-independent form — explicit temporaries, one operation per instruction. (Part 06.)
In: IR. Out: better IR.
Constant folding, common-subexpression elimination, dead-code elimination, loop-invariant code motion — all on the neutral IR. (Part 07.)
In: optimised IR. Out: target asm / object code.
Instruction selection (tree-tiling/BURS), register allocation (graph-colouring or linear-scan), instruction scheduling. (Part 08.)
In: asm. Out: tuned asm.
Peephole rewrites, addressing-mode tricks, branch alignment, micro-arch scheduling — things that only make sense once the ISA is fixed.
Phases 4–5 belong to the middle end; 6–7 to the back end. The boundary is exactly where target details enter the picture.
What actually moves between phases is a sequence of representations. The symbol table and error handler are cross-cutting — every phase reads and writes them.
int x = a + b * 2;Let's push one statement through the whole machine and watch its representation change at each stage. Assume a, b are int locals already in scope.
Precedence (* binds tighter than +) is captured by the shape of the AST, not the token order.
① Token stream — lexemes tagged with a class:
KW(int) ID(x) OP(=) ID(a) OP(+) ID(b) OP(*) NUM(2) SEMI② / ③ AST (semantic-checked) — precedence in the tree shape; types resolved:
Decl(int, x)
└─ Assign
└─ Add :int
├─ a :int
└─ Mul :int
├─ b :int
└─ 2 :int④ Three-address code — linear, one op each:
t1 = b * 2
t2 = a + t1
x = t2⑤ x86-64 — after instruction selection, allocation & *2→+ strength reduction:
mov eax, DWORD PTR [rbp-8] ; load b
add eax, eax ; b * 2
add eax, DWORD PTR [rbp-4] ; + a
mov DWORD PTR [rbp-12], eax ; store xThree temporaries in IR collapsed to one register (eax); the multiply by 2 became an add. That's the back end and optimiser earning their keep.
The front/middle/back split exists for reuse. With N source languages and M targets, a monolithic design needs N×M compilers. Route everything through one shared IR and you need only N + M halves.
This is the architecture LLVM (Lattner, 2003) made mainstream: a stable IR as a contract so any front end pairs with any back end. The middle-end optimiser, written once, benefits all N×M combinations.
The split is also a contract about knowledge: each part knows exactly enough and no more, which is what lets the pieces be swapped.
Add a new language → write one front end, get every target free. Add a new chip → write one back end, get every language free. Improve the optimiser → everyone benefits. This is why GCC and LLVM are ecosystems, not single programs.
A pass is one complete traversal of the program. Phases are logical; passes are physical. One pass may run several phases; one phase may span several passes.
C's header/forward-declaration culture and the ;-before-use rules are fossils of the single-pass era. Modern languages (Rust, Go) declare freely because their compilers hold the whole module in memory.
“The compiler” in everyday use is really a driver orchestrating several programs. gcc hello.c silently runs a preprocessor, the compiler proper, an assembler and a linker.
The assembler emits relocatable object files (ELF on Linux, Mach-O on macOS, COFF/PE on Windows): machine code plus a symbol table and relocation entries the linker resolves.
gcc -E hello.c # stop after preprocess
gcc -S hello.c # stop after compile → .s
gcc -c hello.c # stop after assemble → .o
gcc hello.c # all the way to a.outThe linker stitches object files and libraries into one image, resolving every cross-reference. The loader (part of the OS) maps that image into a process and starts it.
.a archives).so/.dll/.dylib) is loaded at run timeld.so) resolves symbols, often lazily via the PLT/GOTRead the ELF program headers; mmap the text/data segments; set up the stack, heap, and argv/env; perform relocations and dynamic-symbol binding; transfer control to _start → main. Only now is your program a running process — the destination this whole series is heading toward.
A self-hosting compiler is written in the very language it compiles (GCC in C, rustc in Rust, Go's compiler in Go). The chicken-and-egg of building the first one is bootstrapping.
The classic T-diagram records three languages of a compiler: Source (left), Target (right), Implementation (stem). To self-host, compile your compiler with itself.
Ken Thompson's 1984 Turing lecture, Reflections on Trusting Trust: a compiler binary could inject a backdoor into programs and into future copies of itself — invisibly, even with clean source. You cannot fully trust code you didn't build from a trusted compiler.
A cross-compiler runs on one machine but emits code for another — essential for embedded, mobile and bringing up new hardware. Three machines matter, named by convention.
| Role | Meaning |
|---|---|
| Build | Where the compiler is compiled |
| Host | Where the compiler runs |
| Target | What the compiler emits code for |
A native compiler has build = host = target. A cross-compiler has host ≠ target. A Canadian cross has all three different.
x86_64 - unknown - linux - gnu
│ │ │ │
arch vendor OS ABI/libcOther examples: aarch64-apple-darwin, riscv64gc-unknown-linux-gnu, wasm32-unknown-unknown, thumbv7em-none-eabihf (bare-metal Cortex-M).
rustc --target aarch64-unknown-linux-gnu
clang --target=riscv64-linux-gnu main.cThe triple selects the back end, the ABI, and which sysroot/libc to link against.
Optimisations are not independent: running one can enable or disable another. There is no universally optimal order — this is the phase-ordering problem, a teaser for Part 07.
-O2 schedule)The takeaway for this overview: the pipeline is not a clean conveyor belt in the middle end — it loops, repeats, and is heuristically scheduled. Part 07 dives in.
A compiler that stops at the first error is a poor tool. Good compilers detect many errors per run, locate them precisely, and recover to keep parsing — errors are categorised by the phase that catches them.
Illegal characters, unterminated strings, malformed numbers. Caught by the scanner. @ in C, "abc with no close quote.
Token sequence violates the grammar — a missing ;, unbalanced ). Caught by the parser, which drives most recovery.
Grammatically valid but meaningless: undeclared name, type mismatch, wrong arg count. Caught in semantic analysis.
;, });)Modern compilers (Clang, Rust) set the bar: precise spans with carets, the actual vs expected type, suggested fixes, and avoiding a cascade of bogus follow-on errors. A diagnostic is a UX surface.
Stepping back, a compiler is a sequence of data structures, each closer to the machine than the last. Knowing which representation you're in tells you what's easy and what's hard.
| Representation | Form | Good for | Phase |
|---|---|---|---|
| Character stream | bytes / text | — | input |
| Token stream | flat list of (class, lexeme) | regular structure | after lexing |
| Parse tree / AST | tree | nesting, precedence, scope | after parsing |
| Annotated AST | tree + types/symbols | type rules, name resolution | after sema |
| IR (3-addr / SSA) | linear / CFG of basic blocks | dataflow, optimisation | middle end |
| Asm / object code | instructions + relocations | scheduling, allocation | back end |
| Executable / image | linked segments | loading & running | linker/loader |
Each later part of this series lives in one or two rows of this table. Keep it as your map.
Now you have the map, here's the route. Each remaining deck is one box, plus the runtime that all of this ultimately feeds.
Source text becomes a series of ever-lower representations, each enabling work the previous couldn't — until the loader makes the last one a running process.