Compilers
Lexical analysis, parsing, semantic analysis, type checking, code generation, and optimization.
Introduction to Compilers and Lexical Analysis
What is a Compiler? A compiler translates a program written in a source language (C, Rust, Java) into an equivalent program in a target language (assembly, bytecode, another high-level language). The...
What is a Compiler?
A compiler translates a program written in a source language (C, Rust, Java) into an equivalent program in a target language (assembly, bytecode, another high-level language).
The compiler must preserve the meaning of the program while producing efficient output. This is a subtle balance: correctness first, then performance.
Why Study Compilers?
Compilers teach you:
- How your code actually runs on the machine
- Why certain coding patterns are faster than others
- How to write programs that optimize well
- How to build any kind of language processor (interpreters, DSLs, transpilers)
Every serious programmer should build at least one compiler.
The Compilation Pipeline
Modern compilers have many stages:
- Lexical analysis: turn characters into tokens
- Syntax analysis (parsing): turn tokens into a syntax tree
- Semantic analysis: check types, resolve names
- Intermediate representation (IR): lower to a simple language
- Optimization: improve the IR
- Code generation: produce assembly
- Assembly and linking: produce an executable
Each stage has a clear input and output. This modularity makes compilers manageable.
Lexical Analysis
The lexer reads the source character by character and produces a stream of tokens: identifiers, numbers, keywords, operators, punctuation.
Example: int x = 42;
Becomes: [KEYWORD int] [IDENT x] [ASSIGN =] [NUMBER 42] [SEMICOLON ;]
Lexers also handle whitespace and comments (usually discarded), and track line numbers for error messages.
Regular Expressions
Lexical patterns are described with regular expressions:
- Identifier:
[a-zA-Z_][a-zA-Z0-9_]* - Integer:
[0-9]+ - Float:
[0-9]+\.[0-9]+ - Whitespace:
[ \t\n]+
Each regex matches a family of strings. The lexer picks the longest match (maximal munch).
Finite Automata
A regex can be converted to a finite automaton (DFA or NFA). The DFA reads the input one character at a time and transitions between states.
- NFA: has epsilon transitions, can be in multiple states
- DFA: deterministic, exactly one state at a time
Subset construction converts NFA to DFA. The DFA runs in O(n) time for n input characters.
Building a Lexer
Tools like lex, flex, or re2c generate lexers from regex specifications. Or hand-write a lexer with a big switch statement for simple languages.
Example with flex:
%%
[a-zA-Z_][a-zA-Z0-9_]* { return IDENTIFIER; }
[0-9]+ { return INTEGER; }
[ \t\n]+ { /* skip */ }
"=" { return ASSIGN; }
";" { return SEMICOLON; }
%%
Each rule matches a pattern and returns a token type.
Handling Keywords
Keywords (if, while, return) look like identifiers but have special meaning. Two strategies:
- Reserve them: the lexer has separate rules for keywords before identifier rule.
- Post-process: match as identifier, then check against a keyword table.
The second is simpler and often faster.
Error Handling
Lexers must handle:
- Illegal characters (
@in C) - Unterminated strings
- Unterminated comments
- Invalid numeric literals (e.g.,
12abc)
Good error messages point to the exact line and column. "Unexpected character '@' at line 5, column 12" beats "syntax error."
Real-World Lexers
- C: flex-generated or hand-written (GCC uses a hand-written lexer)
- Python: hand-written in CPython (tokenizer)
- JavaScript: hand-written in V8
- Rust: hand-written in rustc (using
logoscrate sometimes)
Hand-written lexers are often faster and more controllable than generated ones.
Key Takeaways
- Compiler = source language to target language translation
- Pipeline: lex β parse β semantic β IR β optimize β codegen
- Lexer: characters to tokens via regex + DFA
- Keywords: reserve or post-process
- Error handling: precise line/column reporting
- Modern compilers often hand-write the lexer for speed
Parsing and Grammar
What is Parsing? The parser takes the token stream from the lexer and builds a syntax tree (or parse tree) that captures the grammatical structure of the program. int x = 42; β Declaration ...
What is Parsing?
The parser takes the token stream from the lexer and builds a syntax tree (or parse tree) that captures the grammatical structure of the program.
int x = 42; β Declaration
βββ Type: int
βββ Name: x
βββ Value: 42
The tree is what the semantic analyzer and code generator work with.
Context-Free Grammars
Grammar rules describe valid programs:
expression β expression + term
| expression - term
| term
term β term * factor
| term / factor
| factor
factor β ( expression )
| number
Non-terminals: expression, term, factor.
Terminals: +, -, *, /, (, ), number.
Derivation and Parse Trees
Starting from a start symbol (e.g., program), apply production rules until you get terminals.
A derivation is a sequence of rule applications. A parse tree shows the structure of a derivation.
Ambiguity
A grammar is ambiguous if some string has multiple parse trees.
Classic example: a + b * c β do we add or multiply first?
Standard fix: encode precedence in the grammar (as above with expression/term/factor).
Another example: if a then if b then c else d β does else bind to the first or second if? Grammar must specify.
Top-Down Parsing
Start from the start symbol, try to derive the input.
Recursive descent: one function per non-terminal. Each function tries the rules in order.
parseExpression() {
parseTerm();
while (peek() == '+' || peek() == '-') {
consume();
parseTerm();
}
}
Simple, easy to understand, hand-written. Used in many production compilers.
LL(1): predicts which rule to use by looking at 1 token. Requires the grammar to be LL(1).
Bottom-Up Parsing
Start from the input, reduce to the start symbol.
LR parsing: shifts tokens onto a stack and reduces when the top matches a rule's right-hand side.
LR parsers are more powerful than LL: can handle more grammars, including left-recursive ones.
Variants: SLR(1), LALR(1), LR(1). Most parser generators use LALR(1).
Tools
- yacc/bison: LALR(1) parser generator
- ANTLR: LL(*) parser generator
- PEG.js: Parsing Expression Grammars
- Tree-sitter: incremental parser (used in editors)
Generating parsers from grammars is convenient but often yields slower parsers than hand-written recursive descent.
Operator Precedence and Associativity
Real grammars need:
- Precedence:
*binds tighter than+ - Associativity:
a - b - cis(a - b) - c
Encode with grammar layers (expression β term β factor) or use Pratt parsing (precedence climbing).
Pratt parsing is elegant and fast β used in many production compilers.
Abstract Syntax Tree (AST)
The parse tree has too much detail (parentheses, intermediate non-terminals). The AST collapses to just the meaningful nodes.
For 1 + 2 * 3:
Parse tree: AST:
+ +
/ \ / \
1 * 1 *
/ \ / \
2 3 2 3
The AST is what the rest of the compiler works with.
Error Recovery
Real parsers must handle errors gracefully:
- Panic mode: skip tokens until a sync point (semicolon, closing brace)
- Error productions: add rules for common mistakes
- Automatic repair: try to fix missing tokens
Good error messages are a competitive advantage. Modern compilers (Rust, Swift) invest heavily in this.
Key Takeaways
- Parser: tokens β syntax tree
- Context-free grammars define syntax
- Ambiguity: fix with precedence layers
- Top-down (LL, recursive descent) vs bottom-up (LR)
- Tools: yacc, bison, ANTLR, tree-sitter
- AST collapses parse tree to meaningful nodes
- Error recovery is essential for usability
Semantic Analysis and Type Checking
What is Semantic Analysis? The parser checks syntax. The semantic analyzer checks meaning: Are all variables declared before use? Are types compatible? Are functions called with the right arguments?...
What is Semantic Analysis?
The parser checks syntax. The semantic analyzer checks meaning:
- Are all variables declared before use?
- Are types compatible?
- Are functions called with the right arguments?
- Are break/continue inside loops?
- Are classes used correctly?
Semantic errors are valid syntax but invalid meaning.
int x = "hello"; // syntax OK, type error
Symbol Tables
Track what names are in scope and their attributes (type, storage, etc.).
A symbol table is a mapping from identifier to a symbol record.
Symbols are organized in nested scopes:
- Global scope
- Function scope
- Block scope
- Class scope
When leaving a scope, its symbols are removed.
Scope Rules
Lexical (static) scoping: a name resolves to the nearest enclosing scope. This is what C, Java, Python, Rust use.
int x = 1;
void f() {
int x = 2;
print(x); // prints 2
}
Dynamic scoping: a name resolves to the most recent declaration on the call stack. Rare; Lisp has an option.
Type Systems
Types classify values and constrain operations:
- Int + Int = Int
- Float + Int = Float
- String + Int = error (in statically typed languages)
Types catch bugs early, document intent, and enable optimization.
Static vs Dynamic Typing
Static: types checked at compile time. C, C++, Java, Rust, Haskell.
Pros: errors caught early, faster runtime, better optimization.
Cons: more verbose, requires explicit annotations (or inference).
Dynamic: types checked at runtime. Python, JavaScript, Ruby.
Pros: flexible, concise.
Cons: errors at runtime, slower.
Gradual: allow both. TypeScript, Python with type hints.
Type Inference
Infer types without annotations:
let x = 42; // x is Int
let y = x + 1; // y is Int
let f = |n| n * 2; // f: (Int) β Int
Hindley-Milner type inference is the classic algorithm. Used in Haskell, ML, Rust (partially).
Type Checking Rules
For each operation, define rules:
β’ e1 : Int β’ e2 : Int
βββββββββββββββββββββββββ
β’ e1 + e2 : Int
This says: if e1 and e2 are both Int, then e1 + e2 is Int.
The β’ symbol means "in context, has type." Rules are read bottom-up (to check the conclusion, check the premises).
Subtyping
Some types are subtypes of others:
Dog <: Animal
Then anywhere an Animal is expected, a Dog can be used.
Used in OOP languages: a Cat and Dog are both Animals, a pointer to Animal can hold either.
Covariance: List<Dog> <: List<Animal>? (No, usually β because you could add a Cat to List<Animal>.)
Contravariance: Function(Animal) <: Function(Dog)? (Yes β a function that handles any Animal can handle a Dog.)
Variance rules are subtle and cause real bugs.
Type Systems in Practice
- Java: nominative (types declared, no structural matching)
- TypeScript: structural (shape matters, not name)
- Go: mostly nominal, some structural (interfaces)
- Rust: nominal + traits (like interfaces)
- Haskell: powerful inference, type classes
Each has trade-offs in expressiveness and complexity.
Attribute Grammars
Semantic analysis can be formalized as attribute grammars:
- Synthesized attributes: computed from children
- Inherited attributes: passed down from parents
Type information often flows both ways.
Key Takeaways
- Semantic analysis checks meaning beyond syntax
- Symbol tables track declarations and scopes
- Lexical (static) vs dynamic scoping
- Type systems catch errors early or late
- Static typing: fast, safe. Dynamic: flexible
- Type inference reduces annotation burden
- Subtyping and variance rules are subtle
- Attribute grammars formalize semantic checks
Intermediate Representation and Optimization
Why an Intermediate Representation? A compiler could go directly from AST to assembly. So why insert an IR? Portability: N frontends Γ M backends β N + M (instead of N Γ M) Optimization: optimize ...
Why an Intermediate Representation?
A compiler could go directly from AST to assembly. So why insert an IR?
- Portability: N frontends Γ M backends β N + M (instead of N Γ M)
- Optimization: optimize the IR once, benefit all languages and targets
- Simplicity: the IR has few constructs; algorithms are simpler
LLVM IR, GCC's GIMPLE, and Java bytecode are famous IRs.
Three-Address Code
The most common IR form:
t1 = a + b
t2 = t1 * c
t3 = t2 - d
Each instruction has at most one operator. Results are stored in temporaries.
This makes data flow explicit, which enables optimization.
Control Flow Graph (CFG)
Basic blocks (straight-line code) connected by edges (branches).
BB1: entry
β
BB2: condition
βββ BB3: then
βββ BB4: else
β
BB5: exit
Optimizations operate on the CFG: remove unreachable blocks, merge blocks, simplify branches.
Static Single Assignment (SSA)
A variant of IR where each variable is assigned exactly once.
Original:
x = 1
x = x + 1
y = x * 2
SSA:
x1 = 1
x2 = x1 + 1
y1 = x2 * 2
When control flow merges, a phi function picks the right version:
if (cond) x1 = 1; else x2 = 2;
x3 = phi(x1, x2)
SSA makes many optimizations trivial. Used in LLVM, GCC (partially), Go, Swift.
Optimization Categories
Local: within a basic block.
- Constant folding:
2 + 3β5 - Algebraic simplification:
x * 1βx - Strength reduction:
x * 2βx << 1
Global: across blocks.
- Common subexpression elimination (CSE)
- Copy propagation
- Dead code elimination
- Loop-invariant code motion
Interprocedural: across functions.
- Inlining
- Whole-program analysis
- Devirtualization
Constant Folding and Propagation
Compute constant expressions at compile time.
x = 3 + 4 β x = 7
y = x * 2 β y = 14
Propagate constants through variables, then fold.
Dead Code Elimination
Remove code whose results are never used:
x = compute() // x never used
y = 42 // y never used
return z
Remove the first two lines. Improves both size and speed (no wasted computation).
Common Subexpression Elimination
If the same expression is computed twice, compute once:
a = b + c
d = b + c β d = a
With SSA, this is automatic: two occurrences with the same operands are the same value.
Loop Optimization
Loops dominate runtime. Optimizations target them:
Loop-invariant code motion:
for (i = 0; i < n; i++) {
x = a * b; // invariant
arr[i] = x + i;
}
Hoist x = a * b outside the loop.
Loop unrolling: execute multiple iterations in one loop body, reducing loop overhead.
Loop fusion: merge adjacent loops over the same range.
Loop interchange: reorder nested loops for cache locality.
Inlining
Replace a function call with the function body. Eliminates call overhead and enables further optimizations.
Trade-off: code size growth. Compilers use heuristics (function size, call frequency).
Vectorization
Use SIMD instructions (SSE, AVX, NEON) to process multiple values at once.
for (i = 0; i < n; i++) c[i] = a[i] + b[i]; // scalar
// becomes 4 or 8 adds in one instruction (SIMD)
Auto-vectorization by the compiler is hard. Explicit SIMD via intrinsics is common.
Register Allocation
Map infinite virtual registers (SSA values) to finite physical registers (16 on x86-64, 31 on RISC-V).
Approach: graph coloring. Two values interfere if they're live at the same time β can't share a register.
NP-hard in general; heuristics used in practice (Chaitin-Briggs).
Spilling: if not enough registers, spill to stack. Adds loads/stores.
Optimization Levels
- -O0: no optimization, fast compile, easy debug
- -O1: basic optimizations
- -O2: more aggressive, standard for release
- -O3: most aggressive, including vectorization
- -Os: optimize for size
- -Ofast: -O3 + fast math (breaks IEEE compliance)
Key Takeaways
- IR decouples frontend and backend
- Three-address code: one operation per instruction
- CFG organizes control flow
- SSA simplifies analysis
- Optimizations: local, global, interprocedural
- Common: folding, DCE, CSE, inlining, vectorization
- Register allocation via graph coloring
- Choose optimization level based on need
Code Generation and Runtime Systems
From IR to Machine Code The code generator translates the optimized IR into target machine code. Tasks: 1. Instruction selection: which instructions implement each IR op? 2. Instruction scheduling:...
From IR to Machine Code
The code generator translates the optimized IR into target machine code. Tasks:
- Instruction selection: which instructions implement each IR op?
- Instruction scheduling: reorder for pipeline efficiency
- Register allocation: virtual β physical registers
- Peephole optimization: local cleanups
- Assembly emission: write the .s file
Instruction Selection
IR: a = b + c
For x86-64, use add:
mov rax, [b]
add rax, [c]
mov [a], rax
For ARM, use ADD:
ldr r0, [b]
ldr r1, [c]
add r0, r0, r1
str r0, [a]
Selection uses pattern matching or tree rewriting. Modern compilers use a universal pattern (LLVM uses SelectionDAG, then MachineInstr).
Instruction Scheduling
Reorder instructions to hide latencies:
load r1, [mem]
add r2, r1, r3 // stalls waiting for load
Better:
load r1, [mem]
add r4, r5, r6 // independent
add r2, r1, r3
Modern CPUs are out-of-order, so scheduling matters less. But it still helps in-order cores (ARM Cortex-M).
Peephole Optimization
Look at small windows of instructions and replace with better ones.
mov rax, 0 β xor rax, rax ; smaller, faster
add rsp, 0 β (removed)
Simple, local, and effective.
Calling Conventions
Every function call follows a standard:
x86-64 System V (Linux, macOS):
- Args 1-6 in RDI, RSI, RDX, RCX, R8, R9
- Args 7+ on the stack
- Return value in RAX
- Callee-saves RBX, RBP, R12-R15
- Caller-saves RAX, RCX, RDX, RSI, RDI, R8-R11
ARM64:
- Args 1-8 in X0-X7
- Return in X0
- Callee-saves X19-X29
The compiler must follow the convention or else C interop fails.
Stack Frames
Each function call creates a stack frame:
βββββββββββββββββββ β higher addresses
β caller's frame β
βββββββββββββββββββ€
β return address β
βββββββββββββββββββ€ β RBP (frame pointer)
β saved RBP β
βββββββββββββββββββ€
β local variablesβ
β spilled regs β
βββββββββββββββββββ€ β RSP (stack pointer)
β outgoing args β
βββββββββββββββββββ β lower addresses
Prologue: push RBP; mov RBP, RSP; sub RSP, N.
Epilogue: leave (mov RSP, RBP; pop RBP); ret.
Frame pointers are optional (-fomit-frame-pointer), freeing RBP as a general register.
Object Files and Linking
Compilation produces an object file (.o) with:
- Code (text section)
- Data (initialized, uninitialized)
- Symbols (defined and undefined)
- Relocations (fix up addresses at load time)
The linker combines .o files and libraries into an executable, resolving symbols and applying relocations.
Static linking: all code copied into executable. Large but self-contained.
Dynamic linking: shared libraries (.so) loaded at runtime. Smaller, shareable, but version-dependent.
Runtime Systems
The compiler emits calls to a runtime library for:
- Memory allocation (malloc, free)
- Garbage collection (in GC languages)
- Exception handling
- Thread management
- Dynamic dispatch (vtable lookups)
Some compilers emit code that relies on libc; others (Go, Rust) ship their own runtime.
Garbage Collection
For GC languages, the runtime manages memory. Techniques:
Mark-and-sweep: start from roots, mark reachable, sweep unreachable.
Copying: copy live objects to a new space, discard the rest. Fast but needs 2x memory.
Generational: most objects die young. Collect young objects frequently, old rarely. Java, C#, JavaScript use this.
Reference counting: count references; free when zero. Python uses it. Cycles need extra handling.
Tracing: various algorithms (Go, Java G1, ZGC).
JIT Compilation
Just-In-Time: compile at runtime, optimizing for the actual use case.
- V8 (JavaScript): compiles hot functions to machine code
- PyPy (Python): JIT for Python
- .NET CLR: compiles IL to native on first call
JITs can beat static compilers on long-running programs (profile-guided), but startup is slower.
AOT vs JIT
- AOT (Ahead-Of-Time): compile before running. Fast startup, slower peak performance.
- JIT: compile at runtime. Slower startup, faster peak performance for hot code.
Modern systems mix: Android ART uses AOT for common functions + JIT for others.
Key Takeaways
- Codegen: IR β machine code
- Instruction selection, scheduling, register allocation
- Peephole optimization: local cleanups
- Calling conventions ensure interop
- Stack frames: locals, spill, return
- Linker combines objects into executables
- Runtime systems for memory, exceptions, threads
- GC: mark-sweep, copying, generational
- JIT for dynamic languages, AOT for ahead-of-time
π Problem Set 1: Lexing, Parsing, Type Checking
Q1. Write a regular expression for an identifier that starts with a letter and contains letters, digits, and underscores.
Show Solution
[a-zA-Z_][a-zA-Z0-9_]*
Q2. Given the grammar E β E+T | T, T β T*F | F, F β id, parse 'a+b*c'. Show the parse tree.
Show Solution
E β E+T β T+T β F+T β a+T β a+T*F β a+F*F β a+b*F β a+b*c. Parse tree: + at root, a on left, * on right; * has b and c as children.
Q3. Explain how type inference works for `let f = |x| x + 1` in a Hindley-Milner system.
Show Solution
x is used with +, so x must be numeric (Int or Float). + is Int β Int β Int in default. So x : Int, and f : Int β Int. Unification algorithm: assign fresh type vars, unify constraints as you traverse the AST.
π― Midterm 1: Lex, Parse, Types, Optimization
Q1. Explain why the grammar S β if E then S | if E then S else S is ambiguous. Rewrite to fix.
Show Solution
String 'if a then if b then c else d' β does else bind to inner or outer if? Ambiguous. Standard fix: S β M | U, M β if E then M else M | other, U β if E then S | if E then M else U. Forces else to bind to nearest unmatched if.
Q2. Apply constant folding and dead code elimination to: x = 3 + 4; y = x * 2; return z;
Show Solution
Constant folding: x = 7. Then y = 14. Dead code: x and y never used. Remove both lines. Result: return z;
Q3. Sketch the pipeline for compiling 'a = b + c * d' through lexing, parsing, IR, optimization, and codegen.
Show Solution
Lex: [id a] [=] [id b] [+] [id c] [*] [id d]. Parse: Assign(a, Add(b, Mul(c, d))). IR: t1 = c*d; t2 = b+t1; a = t2. Optimize: possible CSE if reused. Codegen (x86-64): imul rcx, rdx; add rbx, rcx; mov [a], rbx.