Quick Revision Notes for Exams

How to Use These Notes

These revision notes are designed for the night before your exam or during last-minute preparation. They condense the entire compiler design course into key facts, formulas, and decision rules that frequently appear in exam questions. Read through them once to refresh your memory, then focus on areas where you feel least confident. Each section is independent — jump to whatever topic you need.

The Compilation Pipeline (Must Memorize This Order)

The complete journey from source code to execution follows these phases, and exam questions frequently ask you to identify which phase detects a specific error or performs a specific transformation:

Key exam question pattern: "At which phase is error X detected?"

• int x = ; → Syntax analysis (invalid grammar)
• int x = "hello"; → Semantic analysis (type mismatch)
• printf("%d", x) where x is undeclared → Semantic analysis
• Division by zero with variable → Runtime (cannot detect at compile time)
• #include "missing.h" → Preprocessing

Parsing Methods: When to Use Which

LL(1) Parsing

• Direction: Top-down (starts from start symbol, builds tree downward)
• Scan: Left-to-right
• Derivation: Leftmost
• Lookahead: 1 token
• Cannot handle: Left-recursive grammars (infinite loop)
• Requires: Left recursion elimination + left factorization
• Uses: FIRST and FOLLOW sets to build parsing table
• Implementation: Table-driven or recursive descent

LR/SLR/LALR/CLR Parsing

• Direction: Bottom-up (starts from input, builds tree upward)
• Scan: Left-to-right
• Derivation: Rightmost (in reverse)
• Power hierarchy: LR(1) > LALR(1) > SLR(1) > LR(0)
• Can handle: Left-recursive grammars (no problem)
• Uses: Shift-reduce actions with item sets
• Implementation: Table-driven (ACTION and GOTO tables)

Exam tip: If asked "which parser is most powerful?", the answer is CLR(1)/LR(1). If asked "which is most practical?", the answer is LALR(1) (used by Bison).

FIRST and FOLLOW Set Calculation (Critical for Exams)

Rules for FIRST(X):

1. If X is a terminal: FIRST(X) = {X}
2. If X → ε is a production: add ε to FIRST(X)
3. If X → Y₁Y₂...Yₖ: add FIRST(Y₁) - {ε} to FIRST(X). If ε ∈ FIRST(Y₁), also add FIRST(Y₂) - {ε}. Continue until you find Yᵢ where ε ∉ FIRST(Yᵢ). If all Y's can derive ε, add ε.

Rules for FOLLOW(A):

1. If A is start symbol: add $ to FOLLOW(A)
2. If B → αAβ: add FIRST(β) - {ε} to FOLLOW(A)
3. If B → αA, or B → αAβ where ε ∈ FIRST(β): add FOLLOW(B) to FOLLOW(A)

Worked Example:

Grammar Transformations (Frequently Tested)

Left Recursion Elimination:

Example: E → E + T | T becomes E → TE', E' → +TE' | ε

Left Factorization:

Example: S → iCtSa | iCtSeS | a becomes S → iCtSS' | a, S' → a | eS

Type System Quick Reference

Optimization Techniques Summary

Symbol Table Operations

Three-Address Code Generation

For expression a = b * c + d:

For if (x < y) a = 1; else a = 2;:

Common Exam Mistakes to Avoid

1. Forgetting ε in FIRST sets — if a nonterminal can derive empty, ε must be in its FIRST set
2. Not propagating FOLLOW correctly — if A → αB and ε ∈ FIRST of everything after B, then FOLLOW(B) includes FOLLOW(A)
3. Confusing synthesis and inheritance — synthesized attributes flow UP the tree, inherited attributes flow DOWN
4. Wrong conflict type — shift-reduce means parser unsure whether to shift or reduce; reduce-reduce means unsure which rule to reduce by
5. Forgetting augmented grammar — LR parsers add S' → S to detect acceptance
6. Type promotion direction — always narrow → wide (int → float), never implicit narrowing

Problem-Solving Strategies for Exams

For "construct parsing table" questions: Calculate FIRST and FOLLOW first. Then for each production A → α, put it in table[A, a] for each a in FIRST(α). If ε ∈ FIRST(α), also put it in table[A, b] for each b in FOLLOW(A).

For "trace the parser" questions: Show the stack, input, and action at each step. For LR parsing: shift pushes state+token, reduce pops RHS and pushes LHS with GOTO state.

For "generate three-address code" questions: Break complex expressions into simple operations with temporaries. Each instruction has at most one operator on the right side.

For "identify the optimization" questions: Look for patterns — constant expressions (folding), repeated computations (CSE), variables assigned but unused (dead code), computations inside loops that don't change (loop invariant).

Key Formulas to Memorize