Compiler Design Cheatsheet

Compilation Pipeline

Phase	In → Out	Tool
Lexer	chars → tokens	lex / flex
Parser	tokens → AST	yacc / bison / ANTLR
Semantic	AST → typed AST	hand-written
IR gen	AST → TAC / SSA	LLVM IR
Optimiser	IR → IR	opt passes
Codegen	IR → asm	llc / backend

Lexing

Regex → Scanner

regex --Thompson--> NFA --subset construction--> DFA --minimise--> scanner

IDENT   ::= [a-zA-Z_][a-zA-Z0-9_]*
NUMBER  ::= [0-9]+ (\.[0-9]+)?
Maximal munch: always take the LONGEST matching lexeme
  ">="  -> one token, not ">" then "="

Token stream

let x = 42;
[KEYWORD let] [IDENT x] [ASSIGN =] [NUMBER 42] [SEMI ;]

Parsing

Parser Comparison

Type	Strategy	Left rec.	Power
LL(1)	Top-down, leftmost	No	Weakest
SLR(1)	Bottom-up	Yes	Medium
LALR(1)	Bottom-up (yacc)	Yes	High
LR(1)	Bottom-up	Yes	Highest

Recursive Descent

function parseExpr() {          // expr -> term (("+"|"-") term)*
  let n = parseTerm();
  while (peek()==="+" || peek()==="-") {
    const op = next();
    n = { op, left: n, right: parseTerm() };
  }
  return n;
}
// One function per nonterminal. Must remove left recursion first.

Eliminate Left Recursion

A -> A α | β      becomes      A  -> β A'
                                A' -> α A' | ε

Conflicts

shift/reduce   -> usually resolve by precedence/associativity (dangling else)
reduce/reduce  -> grammar genuinely ambiguous; rewrite it

IR & SSA

Three-Address Code

x = a + b * c
-------------------
t1 = b * c
t2 = a + t1
x  = t2

SSA + phi

// each variable assigned exactly once; phi merges CFG paths
x1 = ...
if c goto L2
x2 = ...
L2: x3 = phi(x1, x2)

Basic block = straight-line code, one entry/exit. CFG = blocks + edges. Most analyses run on the CFG.

Optimizations

Pass	Effect
Constant folding	3*4 → 12 at compile time
Constant propagation	replace var known constant
CSE	reuse repeated subexpression
Dead code elim	drop unused results
Strength reduction	x*2 → x<<1
LICM	hoist loop-invariant code
Inlining	splice callee body inline

Code Generation

Problem	Approach
Instruction selection	tree/DAG tiling
Register allocation	graph coloring + spilling
Scheduling	list scheduling, hide latency

x = a + b * c  =>
mov  rax, [b]
imul rax, [c]
add  rax, [a]
mov  [x], rax

AOT: GCC/Clang (before run). Bytecode: JVM, CPython. JIT: V8, HotSpot (compile hot paths at runtime).