Loading…
The pipeline that turns source text into an executable, phase by phase - and what each phase can and cannot catch.
int x = "hello"; is grammatically perfectly well-formed.| 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.
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.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 | ε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.
break appears inside a loop, every path returns a value.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 |
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.10 questions on Compiler Design · misses join your review queue, on this device only