Formula sheet
Every formula from every topic. Type to filter.
🏭 Phases of a Compiler
Front end
lexical + syntax + semantic + intermediate code generation (machine independent)
Back end
code optimisation (machine dependent part) + code generation + target-specific peephole
Pass
one complete traversal of the source or its intermediate form; several phases can be grouped in one pass
🔤 Lexical Analysis
Thompson NFA size
states ≤ 2 × (#symbols + #operators); every state has at most 2 outgoing transitions
Subset construction worst case
n NFA states → up to 2^n DFA states
Minimal DFA
states = number of Myhill–Nerode equivalence classes (count the dead state only if the DFA must be complete)
Counting tokens
scan with maximal munch; each keyword, identifier, constant, operator, punctuation is one token; string literal = 1 token
🌳 Grammars, Derivations & FIRST/FOLLOW
FIRST(X) for a terminal
FIRST(a) = {a}
FIRST rule
A → Y1 Y2 … Yk: add FIRST(Y1)−ε; if Y1 nullable add FIRST(Y2)−ε, and so on; add ε if all nullable
FOLLOW rule 1
FOLLOW(S) ∋ $
FOLLOW rule 2
A → α B β: FOLLOW(B) ⊇ FIRST(β) − ε
FOLLOW rule 3
A → α B or A → α B β with ε ∈ FIRST(β): FOLLOW(B) ⊇ FOLLOW(A)
FOLLOW never contains ε
FOLLOW sets contain terminals and $ only
⬇️ Top-down Parsing (LL(1))
LL(1) condition
for A → α | β: FIRST(α) ∩ FIRST(β) = ∅; and if ε ∈ FIRST(α) then FIRST(β) ∩ FOLLOW(A) = ∅
Immediate left recursion removal
A → Aα | β ⇒ A → βA′, A′ → αA′ | ε
Left factoring
A → αβ | αγ ⇒ A → αA′, A′ → β | γ
Parser steps (LL(1))
one step per derivation step plus one per matched terminal, so about |derivation| + |tokens|
Not LL(1) if
ambiguous, left-recursive, or not left-factored (commonly)
⬆️ Bottom-up Parsing (LR family)
closure(I)
repeat: for A → α • B β in I and every B → γ, add B → • γ
goto(I, X)
closure of { A → α X • β : A → α • X β ∈ I }
SLR reduce
in state with A → α •, put reduce on every a ∈ FOLLOW(A)
CLR reduce
in state with [A → α •, a], put reduce only on a
State counts
#LR(0) = #SLR = #LALR ≤ #CLR(1)
Stack on reduce
pop 2 × |α| entries (symbol, state pairs), push A and goto[top, A]
Accepting
in the state with S′ → S •, on $ → accept
🧮 Syntax-Directed Translation
S-attributed ⊂ L-attributed
every S-attributed SDD is also L-attributed
L-attributed rule
for A → X1 … Xn, inherited Xi.a may use only A.inherited and attributes of X1 … X(i−1)
Synthesized rule
A.s = f(attributes of the children of A and A.inherited)
Evaluation order
topological order of the dependency graph (acyclic required)
🧱 Runtime Environments
Recursion depth
stack space ≈ depth × activation record size
Access link chain
to reach a variable declared k levels out, follow k access links (static scoping)
Call by name
argument expression is re-evaluated in the caller's environment each time the formal is used
📝 Intermediate Code Generation
Temporaries
#temporaries = #operators (binary and unary) in the expression
Leaders
1st instruction ∪ targets of jumps ∪ instructions following jumps
Basic blocks
#blocks = #leaders
DAG nodes
#nodes = #distinct (op, left, right) values + leaves
🚀 Code Optimisation & Data-Flow
Reaching definitions
OUT[B] = gen[B] ∪ (IN[B] − kill[B]); IN[B] = ∪ OUT[P]
Live variables
IN[B] = use[B] ∪ (OUT[B] − def[B]); OUT[B] = ∪ IN[S]
Available expressions
OUT[B] = gen[B] ∪ (IN[B] − kill[B]); IN[B] = ∩ OUT[P]; IN[entry] = ∅
Very busy expressions
backward, ∩ (used for code hoisting)
Iteration
repeat until no IN/OUT set changes; terminates since sets only move monotonically in a finite lattice
⚙️ Code Generation & Register Allocation
Sethi–Ullman label
leaf: 1 if left child, 0 if right child; node: l1 = l2 → l1 + 1, else max(l1, l2)
Registers needed
= label of the root
Chromatic number
min registers for the interference graph = chromatic number (NP-hard in general)