CD Notes
Reference of key formulas, rules, and equations in compiler design
Introduction
This reference page collects the essential formulas, algorithms, and rules you need for compiler design exams and interviews. Each formula is presented with its context, meaning, and a worked example so you understand not just what the formula is, but when and how to apply it. Keep this page bookmarked for quick reference during problem-solving.
FIRST Set Calculation Rules
The FIRST set of a grammar symbol tells you which terminal symbols can appear at the beginning of strings derived from that symbol. This is fundamental for building LL(1) parsing tables.
Rule 1 — Terminal: FIRST(a) = {a} for any terminal symbol a.
Rule 2 — Epsilon production: If A → ε exists, then ε ∈ FIRST(A).
Rule 3 — Single production A → Y₁Y₂...Yₖ:
Rule 4 — Multiple productions: FIRST(A → α | β) = FIRST(α) ∪ FIRST(β)
Worked Example:
FOLLOW Set Calculation Rules
The FOLLOW set tells you which terminals can appear immediately after a nonterminal in any derivation. Essential for handling epsilon productions in LL(1) tables.
Rule 1: $ ∈ FOLLOW(S) where S is the start symbol ($ represents end-of-input).
Rule 2: For production B → αAβ, add FIRST(β) - {ε} to FOLLOW(A).
Rule 3: For production B → αA, or B → αAβ where ε ∈ FIRST(β), add FOLLOW(B) to FOLLOW(A).
Worked Example:
| Grammar: E | TE', E' → +TE' | ε, T → FT', T' → *FT' | ε, F → (E) | id |
| FOLLOW(E) | Start with {$}. |
| From F | (E), add FIRST()) = {)} |
| FOLLOW(E'): From E | TE', FOLLOW(E') = FOLLOW(E) = {$, )} |
| FOLLOW(T): From E | TE', add FIRST(E') - {ε} = {+} |
| FOLLOW(T'): From T | FT', FOLLOW(T') = FOLLOW(T) = {+, $, )} |
| FOLLOW(F): From T | FT', add FIRST(T') - {ε} = {*} |
LL(1) Parsing Table Construction
For each production A → α:
| Set table[A, a] = "A | α" |
| Set table[A, b] = "A | α" |
| 3. If any cell has two entries | grammar is NOT LL(1) |
Left Recursion Elimination
Immediate left recursion (A → Aα | β):
| Original: A | Aα₁ | Aα₂ | ... | β₁ | β₂ | ... |
| Transformed: A | β₁A' | β₂A' | ... |
| A' | α₁A' | α₂A' | ... | ε |
Example: E → E + T | E - T | T
Indirect left recursion (A → Bα, B → Aβ): First substitute to make it direct, then eliminate.
Left Factorization
When two productions share a common prefix:
| Original: A | αβ₁ | αβ₂ | ... | αβₙ | γ |
| Factored: A | αA' | γ |
| A' | β₁ | β₂ | ... | βₙ |
Example: S → if E then S else S | if E then S
| Common prefix | if E then S |
| Factored: S | if E then S S' |
| S' | else S | ε |
LR Parsing Table Actions
| shift s | Push terminal and state s onto stack |
| reduce r | Pop |RHS| symbols, push LHS, goto GOTO[state, LHS] |
| accept | Input fully parsed successfully |
| error | No valid action (syntax error) |
Type Compatibility Rules
Arithmetic type promotion (implicit widening — always safe):
| char | short → int → long → float → double |
| bool | int (true=1, false=0) |
| Rule | In mixed expressions, narrow type is promoted to wider type |
| int + float | float (int promoted) |
| float + double | double (float promoted) |
| char + int | int (char promoted) |
Incompatible operations (always errors):
| pointer + pointer | ERROR (can subtract pointers, not add) |
| array + scalar | ERROR |
| string × int | ERROR (except in Python) |
| void + anything | ERROR |
| function + anything | ERROR |
Array Address Computation
One-dimensional array A[i]:
Two-dimensional array A[i][j] (row-major order):
Column-major order (Fortran):
Optimization Formulas and Rules
Constant Folding: Replace compile-time evaluable expressions:
| x = 3 + 5 | x = 8 |
| y = 2 * 3 + 1 | y = 7 |
| z = true && false | z = false |
Strength Reduction: Replace expensive operations with cheaper equivalents:
| x * 2 | x << 1 (multiply by power of 2 → shift) |
| x * 15 | (x << 4) - x (multiply → shift and subtract) |
| x / 4 | x >> 2 (divide by power of 2 → shift) |
| x % 8 | x & 7 (modulo power of 2 → bitwise AND) |
Loop Invariant Code Motion: Move computations that produce the same value in every iteration outside the loop:
Scope Lookup Rule (LEGB in Python, similar in C)
Variable lookup order:
1. Local scope (current function's variables)
2. Enclosing scope (outer function, for nested functions)
3. Global scope (module-level variables)
4. Built-in scope (language built-ins)
First match wins. Inner declarations shadow outer ones.Symbol Table Complexity Analysis
| Implementation | Insert | Lookup | Delete | Space |
|---|---|---|---|---|
| Unsorted array | O(1) | O(n) | O(n) | O(n) |
| Sorted array | O(n) | O(log n) | O(n) | O(n) |
| Linked list | O(1) | O(n) | O(n) | O(n) |
| Hash table | O(1) avg | O(1) avg | O(1) avg | O(n) |
| BST (balanced) | O(log n) | O(log n) | O(log n) | O(n) |
| Trie | O(k) | O(k) | O(k) | O(n×k) |
Where n = number of symbols, k = average identifier length. Hash table is the standard choice for compiler symbol tables.
Stack Frame Size Calculation
| Example | Function with int a, int b, double c, char buf[20]: |
| Locals | 4 + 4 + 8 + 20 = 36 bytes |
| Return addr + FP | 8 + 8 = 16 bytes |
| Alignment: round up to multiple of 16 | 48 bytes total |
| Stack adjustment | SUB RSP, 48 |
DFA/NFA Bounds
| NFA to DFA | An NFA with n states can produce a DFA with at most 2ⁿ states |
| Minimal DFA | Unique for any regular language (Myhill-Nerode theorem) |
| Regular expression to NFA | Thompson's construction adds at most 2 states per operator |
| Expression with n symbols | NFA with O(n) states |
Key LL(1) Condition
A grammar is LL(1) if and only if for every pair of productions A → α | β:
1. FIRST(α) ∩ FIRST(β) = ∅
(No token can start both alternatives)
2. If ε ∈ FIRST(α), then FIRST(β) ∩ FOLLOW(A) = ∅
(If α can be empty, the tokens that can follow A must not overlap with tokens starting β)
3. At most one of α, β can derive ε
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Important Formulas and Rules.
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, resources, important, formulas, and
Related Compiler Design Topics