CD Notes
Quick reference guide for compiler design concepts and formulas
Introduction
This cheatsheet is your one-page survival guide for compiler design exams, interviews, and quick reviews. It distills the most critical information into a compact, scannable format. Print it, bookmark it, or keep it open during study sessions. Every formula, comparison table, and decision rule here represents something that frequently appears in exam questions or interview discussions.
The Ten Compilation Phases (In Order)
Memorize this sequence — exam questions constantly ask "which phase detects X" or "what is the output of phase Y":
Grammar Rules Quick Reference
Left Recursion Elimination:
Left Factorization:
Chomsky Normal Form (CNF): Every production is A → BC or A → a Greibach Normal Form (GNF): Every production is A → aα (terminal first)
FIRST and FOLLOW: The Complete Rules
| FIRST(A | Y₁Y₂...Yₖ): |
| If ε ∈ FIRST(Y₁) | add FIRST(Y₂) - {ε} |
| If ALL Yᵢ have ε in FIRST | add ε |
| For B | αAβ: FOLLOW(A) includes FIRST(β) - {ε} |
| For B | αA or B → αAβ with ε ∈ FIRST(β): FOLLOW(A) includes FOLLOW(B) |
LL(1) Table Construction
| For each production A | α: |
| ∀ a ∈ FIRST(α): table[A,a] = "A | α" |
| If ε ∈ FIRST(α): ∀ b ∈ FOLLOW(A): table[A,b] = "A | α" |
Parser Comparison Table
| Property | LL(1) | SLR(1) | LALR(1) | CLR/LR(1) |
|---|---|---|---|---|
| Direction | Top-down | Bottom-up | Bottom-up | Bottom-up |
| Derivation | Leftmost | Rightmost (rev) | Rightmost (rev) | Rightmost (rev) |
| Left recursion | Cannot handle | OK | OK | OK |
| Power | Least | Medium | High | Highest |
| Table size | Small | Small | Small | Very large |
| Used by | Hand-written | Academic | Bison/YACC | Academic |
| Lookahead | 1 token | FOLLOW set | Per-state | Per-item |
Power hierarchy: Regular < LL(1) < SLR(1) < LALR(1) < CLR(1) < Unambiguous CFG < All CFG
LR Parsing Actions Explained
Given stack top state s and input token a
ACTION[s, a] = shift t → Push a and go to state t
ACTION[s, a] = reduce r → Pop |RHS(r)| symbols, push LHS(r),
goto GOTO[new_top_state, LHS(r)]
ACTION[s, a] = accept → Parse successful!
ACTION[s, a] = empty → Syntax error
Conflict types
Shift-reduce: same cell has both shift and reduce
Reduce-reduce: same cell has two different reduces
Type System Rules
Arithmetic (both operands must be numeric)
int OP int = int
float OP float = float
int OP float = float (int widened to float)
Comparison (operands must be compatible, result is bool):
int CMP int = bool
float CMP float = bool
Assignment compatibility
Same type: always OK
Narrow → wide (int → float): OK (implicit widening)
Wide → narrow (float → int): WARNING (truncation)
Incompatible (string → int): ERROR
Type promotion ladder
char < short < int < long < float < double
Three-Address Code Patterns
| Assignment | x = y op z (binary operation) |
| Conditional | if x relop y goto L |
| Array access | x = y[i] (indexed read) |
| Function call | param x (push argument) |
Optimization Techniques Summary
| Constant Folding: x = 3 + 5 | x = 8 |
| Constant Propagation: x = 5; y = x+1 | y = 6 |
| Dead Code Elimination: if(false){...} | (removed) |
| Common Subexpression: a=b+c; d=b+c | d=a |
| Loop Invariant Motion: loop{x=a+b} | x=a+b; loop{} |
| Strength Reduction: x*2 | x<<1 |
| Peephole: MOV R1,R2; | MOV R1,R2 |
| Copy Propagation: x=y; z=x+1 | z=y+1 |
| Inlining: small_func() | (body inserted) |
Memory Layout (Low to High Address)
Symbol Table: Implementation Comparison
| Hash Table | O(1) lookup — ALWAYS USE THIS for compilers |
| BST | O(log n) lookup — acceptable alternative |
| Array | O(n) lookup — only for tiny programs |
| Linked list | O(n) lookup — only for scope chain representation |
| Enter scope | push new hash table onto scope stack |
| Exit scope | pop top hash table |
| Lookup | search from top to bottom (innermost first) |
Register Allocation Key Facts
Array Address Formulas
| 1D | addr(A[i]) = base + (i - lower) × size |
| 2D row-major | addr(A[i][j]) = base + ((i-lr)×cols + (j-lc)) × size |
| 2D col-major | addr(A[i][j]) = base + ((j-lc)×rows + (i-lr)) × size |
Key Decision Rules for Exams
"Is this grammar LL(1)?" → Check: no left recursion, FIRST sets of alternatives don't overlap, at most one alternative derives ε per nonterminal.
"Which phase detects this error?" → Syntax error if it violates grammar structure. Semantic error if grammar is fine but meaning is wrong (type mismatch, undeclared variable).
"What type of conflict?" → Shift-reduce: parser unsure whether to extend current handle or reduce it. Reduce-reduce: parser unsure which of two rules to reduce by.
"SLR vs LALR vs CLR?" → SLR uses FOLLOW for reduce decisions (sometimes over-reduces). LALR uses merged per-item lookahead (almost always sufficient). CLR uses full per-item lookahead (maximum power, large tables).
Common Notation
| ε | empty string |
| $ | end of input marker |
| ⇒ | derivation step |
| ⇒* | zero or more derivation steps |
| • | dot in LR items (position marker) |
| | : alternative (A | α | β) |
| FIRST | set of terminals that can begin a derivation |
| FOLLOW | set of terminals that can follow a nonterminal |
| $$ | value of LHS in Bison semantic actions |
| $1,$2 | values of RHS symbols in Bison |
Interview Quick Answers
- Compiler vs interpreter: Compiler translates all then runs. Interpreter executes line-by-line.
- Why IR?: Machine-independent optimization, M+N instead of M×N for M languages × N targets.
- Why separate lexing from parsing?: Simpler design, faster DFA-based scanning, cleaner grammar.
- Most powerful parser?: CLR(1) / LR(1). Most practical? LALR(1).
- GC types: Reference counting (immediate but can't handle cycles), Mark-sweep (handles cycles but pauses), Generational (exploits "most objects die young").
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Compiler Design Cheatsheet.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, interview, preparation, cheatsheet, compiler design cheatsheet
Related Compiler Design Topics