Compiler Design
The pipeline that turns source text into an executable, phase by phase — and what each phase can and cannot catch.
If you remember nothing else
- Six phases: lexical, syntax, semantic, intermediate code generation, optimisation, code generation — with the symbol table and error handler spanning all of them.
- Lexical analysis uses regular expressions and finite automata; syntax analysis uses context-free grammars and pushdown automata. The Chomsky hierarchy is why.
- A type error is caught in semantic analysis, not syntax analysis —
int x = "hello";is grammatically perfectly well-formed. - LL parsers are top-down and build a leftmost derivation; LR parsers are bottom-up, build a rightmost derivation in reverse, and handle strictly more grammars.
- Left recursion breaks recursive-descent parsing and must be eliminated; left factoring removes the need to look ahead further.
- Compilation proper is only one stage: preprocessing, compiling, assembling and linking are four distinct programs.
The phases of a compiler
| Phase | Input | Output | Catches |
|---|---|---|---|
| 1. Lexical analysis | Character stream | Token stream | Illegal characters, malformed literals |
| 2. Syntax analysis | Token stream | Parse tree / AST | Missing semicolons, unbalanced brackets |
| 3. Semantic analysis | Parse tree | Annotated AST | Type errors, undeclared variables, wrong argument counts |
| 4. Intermediate code gen | Annotated AST | Three-address code / IR | — |
| 5. Optimisation | IR | Better IR | — |
| 6. Code generation | IR | Target assembly or machine code | — |
The symbol table and the error handler interact with every phase, which is why they are drawn alongside rather than within the pipeline.
Lexical analysis
The scanner reads characters and groups them into tokens, discarding whitespace and comments. It is specified with regular expressions and implemented as a finite automaton — which is exactly why regular languages sit at the bottom of the Chomsky hierarchy and are enough for this job.
| Term | Meaning | Example |
|---|---|---|
| Token | A category name plus optional attribute | <id, ptr-to-symtab> |
| Pattern | The rule describing what the token looks like | letter(letter|digit)* |
| Lexeme | The actual character sequence matched | count, 42, while |
Source: position = initial + rate * 60;
Tokens: <id, "position"> <assign_op> <id, "initial"> <plus_op>
<id, "rate"> <mult_op> <num, 60> <semicolon>
Whitespace and comments are discarded and never reach the parser.Syntax analysis
The parser checks that the token stream conforms to the language's context-free grammar and builds a parse tree. Regular expressions are insufficient here — nested constructs such as balanced parentheses and block structure require a stack, hence a pushdown automaton.
| Top-down (LL) | Bottom-up (LR) | |
|---|---|---|
| Builds the tree | From the root down | From the leaves up |
| Derivation | Leftmost | Rightmost, in reverse |
| Core actions | Predict and match | Shift and reduce |
| Cannot handle | Left recursion; needs left factoring | Handles both |
| Grammar coverage | Smaller class | Strictly larger class |
| Implementation | Recursive descent — easy to hand-write | Table-driven; usually generated |
| Tools | ANTLR, hand-written parsers | yacc, bison |
LEFT RECURSION - a recursive-descent parser for this loops forever,
because parsing E immediately calls E again with no input consumed:
E -> E + T | T
Eliminate by introducing a new non-terminal:
E -> T E'
E' -> + T E' | ε
LEFT FACTORING - the parser cannot choose between these two with one
token of lookahead, since both start with "if":
S -> if E then S else S | if E then S
Factor the common prefix out:
S -> if E then S S'
S' -> else S | εSemantic analysis and the symbol table
Syntax analysis proves the program is well-formed; semantic analysis proves it is well-meaning. These are the checks a context-free grammar cannot express.
- Type checking — operands are compatible; implicit conversions are inserted where the language permits.
- Declaration checking — every identifier is declared before use, and not declared twice in one scope.
- Scope resolution — each use is bound to the correct declaration under the language's scoping rules.
- Function signature checking — argument count and types match the declaration; the return type matches what is returned.
- Flow checks —
breakappears inside a loop, every path returns a value.
Intermediate code and optimisation
An intermediate representation is machine-independent but simpler than the source, which is what lets one optimiser serve every front end and every back end. Three-address code is the standard teaching form: at most one operator per instruction, with explicit temporaries.
Source: a = b * c + b * c * 2
Three-address code (naive):
t1 = b * c
t2 = b * c
t3 = t2 * 2
t4 = t1 + t3
a = t4
After COMMON SUBEXPRESSION ELIMINATION (b*c computed once):
t1 = b * c
t3 = t1 * 2
t4 = t1 + t3
a = t4
Other representations you should be able to name:
Postfix: a b c * b c * 2 * + =
Syntax tree / DAG: shares the repeated b*c subtree
Quadruples: (op, arg1, arg2, result)
Triples: (op, arg1, arg2) - referenced by position| Optimisation | Does | Example |
|---|---|---|
| Constant folding | Evaluates constant expressions at compile time | x = 3 * 4 → x = 12 |
| Constant propagation | Replaces a variable with its known constant value | x=5; y=x+2 → y=7 |
| Common subexpression elimination | Computes a repeated expression once | As above |
| Dead code elimination | Removes code whose result is never used | An assignment to a variable never read again |
| Strength reduction | Replaces an expensive operation with a cheaper one | x*2 → x<<1; multiplication in a loop → addition |
| Loop-invariant code motion | Hoists a computation that does not change out of the loop | for(...) { y = a*b; ... } |
| Copy propagation | Replaces a copied variable with its source | y=x; z=y+1 → z=x+1 |
| Inlining | Replaces a call with the function body | Removes call overhead, enables further optimisation |
Code generation and the toolchain
The code generator maps IR to target instructions, and must solve three problems: instruction selection (which machine instructions implement this IR operation), register allocation (which values live in the limited register set), and instruction ordering (which schedule best fits the pipeline).
gcc hello.c -o hello # four separate programs run in sequence
# 1. PREPROCESSOR (cpp) - expands #include, #define, strips comments
gcc -E hello.c -o hello.i
# 2. COMPILER (cc1) - the six phases; produces assembly
gcc -S hello.i -o hello.s
# 3. ASSEMBLER (as) - assembly to relocatable object code
gcc -c hello.s -o hello.o
# 4. LINKER (ld) - resolves symbols across object files and libraries,
# assigns final addresses, produces the executable
gcc hello.o -o hello
# "undefined reference to printf" is a LINKER error, not a compiler one:
# the compiler was satisfied by the declaration in stdio.h; only the
# linker discovers that no definition was supplied.Self-check
10 questions on Compiler Design · nothing is stored