Reference topics: Stanford CS143 Β· independent study notes, not affiliated

Compilers

Lexical analysis, parsing, semantic analysis, type checking, code generation, and optimization.

5Lectures
1Assignments
1Exams
42hDuration
1

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...

⏱ 50 min read

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:

  1. Lexical analysis: turn characters into tokens
  2. Syntax analysis (parsing): turn tokens into a syntax tree
  3. Semantic analysis: check types, resolve names
  4. Intermediate representation (IR): lower to a simple language
  5. Optimization: improve the IR
  6. Code generation: produce assembly
  7. 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:

  1. Reserve them: the lexer has separate rules for keywords before identifier rule.
  2. 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 logos crate 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
2

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 ...

⏱ 50 min read

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 - c is (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
3

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?...

⏱ 50 min read

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
4

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 ...

⏱ 50 min read

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
5

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:...

⏱ 50 min read

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: reorder for pipeline efficiency
  3. Register allocation: virtual β†’ physical registers
  4. Peephole optimization: local cleanups
  5. 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.