The Exam Architecture: Understanding the Paper

Before studying a single topic, understand how the exam is built. Based on 2019–2024 paper analysis across 113 questions:

Paper Structure:

• Total Marks: 70–80 marks (external exam)
• Duration: 3 hours
• Section A: 8–10 MCQs × 2 marks = 16–20 marks (compulsory — all must be answered)
• Section B: 5–6 long-answer questions × 7–14 marks = 50–60 marks (often with internal choices)

The Critical Implication: Section A (MCQs) is worth ~20 marks — nearly 25–30% of the paper — and takes only 15–20 minutes. This is the highest marks-per-minute section. The 2-mark questions consistently test: parser hierarchy, LR properties, ambiguity definitions, token counting, and phase responsibilities.

The 10 Guaranteed Question Types (Appear EVERY Year)

These are questions that have appeared in every exam from 2019 to 2024, or in 3+ of the 4 years. If you master these 10, you can answer at least 55 out of 70 marks on any paper.

---

🔴 GUARANTEED #1: LR/SLR/LALR Parsing Table Construction (14 Marks)

Module 2 | Appeared: 2019, 2022, 2023, 2024

Given a grammar, construct the canonical collection of LR(0) items, build the SLR(1) or LALR(1) parsing table, and trace a string.

What to practice:

• Augment the grammar (S' → S)
• Compute FIRST and FOLLOW sets
• Build all LR(0) states (I₀ through Iₙ) — the expression grammar has 12 states
• Construct ACTION and GOTO tables
• Check for conflicts (S-R, R-R)
• Trace the input string on the stack

Time to solve: 22–28 min

---

🔴 GUARANTEED #2: FIRST/FOLLOW + LL(1) Parsing Table (7 Marks)

Module 2 | Appeared: 2019, 2022, 2023, 2024

Compute FIRST and FOLLOW sets for all non-terminals, construct the LL(1) parsing table, and check for conflicts.

What to practice:

• FIRST rules: terminals, ε-productions, nullable tracking across chain rules
• FOLLOW rules: $ in start symbol, FIRST(β) for A→αBβ, propagate for nullable
• Table construction: FIRST(α) for each production, ε → FOLLOW(A) placement
• Conflict inspection: every cell must have at most one entry

Time to solve: 12–15 min

---

🔴 GUARANTEED #3: Phases of Compilation with Diagram (7 Marks)

Module 1 | Appeared: 2019, 2022, 2024

Explain the working of each phase of a compiler in detail with an example and a neat labeled diagram.

What to practice:

• Draw the 6-phase flowchart + symbol table + error handler
• Use the Dragon Book example: position = initial + rate * 60
• Show output of each phase (tokens → parse tree → annotated AST → TAC → optimized code → assembly)
• Include Lexical, Syntax, Semantic, Intermediate Code Gen, Code Optimization, Code Generation

Time to solve: 10–12 min

---

🔴 GUARANTEED #4: S-Attributed vs L-Attributed SDDs (7 Marks)

Module 3 | Appeared: 2019, 2022, 2023, 2024

Differentiate between S-attributed and L-attributed SDDs with suitable examples.

What to practice:

• 3-column comparison table (property, S-attributed, L-attributed)
• S-attributed: only synthesized, bottom-up eval, LR parser compatible
• L-attributed: synthesized + inherited, left-to-right DFS, LL parser compatible
• One mathematical example for each (e.g., desk calculator for S, type rules for L)

Time to solve: 10–12 min

---

🔴 GUARANTEED #5: Left Recursion Elimination (7 Marks)

Module 2 | Appeared: 2019, 2023

Eliminate left recursion from the given grammar. Also apply left factoring if needed.

What to practice:

• Immediate left recursion formula: A → Aα | β → A → βA', A' → αA' | ε
• Apply to expression grammar: E → E+T | T
• Check for indirect left recursion
• After elimination, state whether grammar is suitable for top-down parsing

Time to solve: 8–10 min

---

🟠 GUARANTEED #6: NFA to DFA Conversion (7 Marks)

Module 1 | Appeared: 2024 (high probability for future years)

Differentiate between DFA and NFA, and explain the procedure to convert NFA to DFA with a suitable example.

What to practice:

• DFA vs NFA comparison table (5+ differences)
• ε-closure and move function definitions
• Subset construction algorithm steps
• Trace example: NFA for (a|b)*abb → DFA

Time to solve: 12–15 min

---

🟠 GUARANTEED #7: Quadruples, Triples, Indirect Triples (7 Marks)

Module 4 | Appeared: 2022, 2023

Translate an arithmetic expression into quadruples and triples representation.

What to practice:

• Break expression into TAC first
• Quadruples: 4 fields (op, arg1, arg2, result)
• Triples: 3 fields (op, arg1, arg2) — results referenced by index
• Indirect Triples: pointer array + triples table
• Example: A = -b * (c + d) / e

Time to solve: 10–12 min

---

🟠 GUARANTEED #8: DAG Construction + Optimization (7 Marks)

Module 4 | Appeared: 2022, 2023, 2024

Construct a DAG for a basic block, identify common subexpressions, and generate optimized TAC.

What to practice:

• Create leaf nodes for constants and variables
• Build interior nodes for each operation
• Node-label merging for copy propagation (e.g., prod = t6 → single node)
• Reuse constant nodes across operations
• Traverse in topological order for optimized TAC

Time to solve: 10–12 min

---

🟠 GUARANTEED #9: Symbol Table / Activation Records (Short Notes — 7 Marks)

Module 3 | Appeared: 2019, 2022, 2023, 2024

Write short notes on: Symbol Table OR Activation Records.

What to practice:

• Symbol Table: Hash table structure, identifier→attribute mapping, scope stack, cross-phase usage (Lexer inserts, Parser structures, Semantic Analyzer checks types)
• Activation Records: Runtime stack frame components (return value, parameters, dynamic link, static link, saved status, local data, temporaries), push/pop on function call

Time to solve: 8–10 min

---

🟠 GUARANTEED #10: Code Optimization Techniques (7 Marks)

Module 4 | Appeared: 2019, 2022, 2024

Discuss code optimization techniques — peephole, code motion, strength reduction, register allocation.

What to practice:

• Peephole: 5 categories (redundant load/store, algebraic simplification, unreachable code, control flow optimization, null sequences)
• Code motion: Hoisting loop-invariant computations to pre-header
• Strength reduction: Replace i*4 with t+=4 in loops
• Register allocation via graph coloring: Build interference graph, k-coloring, spill when degree ≥ k

Time to solve: 10–12 min

Difficulty-Level Segmentation

🟢 Easy (Foundation — Must Score):

• All 2-mark objective questions (30+ across all modules)
• Phases of compilation description + diagram
• Compiler vs Interpreter comparison
• Short notes: Handle Pruning, YACC, Symbol Table, Activation Records
• Peephole optimization definition + examples

🟡 Medium (Application — Requires Practice):

• FIRST/FOLLOW computation
• LL(1) parsing table construction
• Left recursion elimination + left factoring
• NFA → DFA subset construction
• DFA design (complement technique)
• Quadruples/Triples/Indirect Triples conversion
• DAG construction from basic blocks
• S-attributed vs L-attributed comparison
• SDT semantic action tracing
• Symbol table structure & management
• Basic block identification + CFG drawing
• Syntax tree drawing from expressions

🔴 Hard (Mastery — High-Value Targets):

• LR(0) canonical collection of items (12+ states)
• SLR(1) parsing table + conflict detection
• LALR(1) / CLR(1) table construction
• Proof: LL(1) but not SLR(1)
• Reaching definitions — iterative data flow (4+ iterations)
• Register allocation via graph coloring
• 14-mark full parser construction + trace

Figure Integration Guide (Essential Diagrams by Module)

Every 7-mark descriptive question requires a diagram for full marks. Below is the complete figure inventory mapped to specific PYQs:

Module 1 — Introduction & Lexical Analysis:

Module 2 — Syntax Analysis:

Module 3 — Semantic Analysis & Run-time Environment:

Module 4 — Intermediate Code Generation & Optimization:

Module 5 — Advanced Topics:

The 6-Week Study Timeline

The 7-Day Intensive Plan

The 72-Hour Cram Plan

Final Exam Strategy

Order of Execution in Exam:

1. 14-mark numerical first (LR/SLR/LALR table or Reaching Definitions) — mechanical, highest weight, partial marks assured even if incomplete
2. 7-mark numerical questions (FIRST/FOLLOW, Quadruples, DAG) — quick construction, diagram-heavy
3. 7-mark theory questions (short notes, compare/contrast) — write templates from memorized structure
4. 2-mark objectives last — answer concisely, polish wording

Time Allocation (3-hour exam):

Minimum Score Targets by Module:

Diagrams are non-negotiable. For any 7-mark question asking to explain or compare, start with the diagram. Examiners award 2-3 marks for the diagram alone.

Learn the Dragon Book example. The position = initial + rate * 60 trace is universally recognized for the 6 phases question.

Show your work in numericals. Do not jump to the final parsing table. Examiners award partial marks for FIRST/FOLLOW sets, LR(0) items, and intermediate iteration tables in data flow analysis.