Compiler Design · Reading course
Follow a program
from source to machine.
Every section from your supplied notes, including lexical analysis, parsing, syntax-directed translation, runtime environments, intermediate code, and optimization.
90 reading items · 9 phases · Worked examples & practice
0%
0 of 90 reading items completed
Complete an item when you’re ready. Your place is saved in this browser.Your path through Compiler Design
Lessons, chapter reviews, and checkpoints—in reading order.
Begin hereStart here0 / 1 complete
01Phase 0Foundations0 / 8 complete
0.1.1Programs, machine code and why we translate; compiler vs interpreterLesson0.1.2The toolchain: preprocessor, compiler, assembler, linker, loaderLesson0.1.3The phases of a compiler; symbol table; error handler; which phase catches which errorLesson0.2.1Alphabets, strings, languages; sets, union, intersectionLesson0.2.2Regular expressions (what lexical analysis needs)Lesson0.2.3Finite automata: DFA, NFA and the idea of converting NFA to DFALesson0.2.4Data structures: stack, tree, hash table, directed graphLessonCP0FoundationsCheckpoint
02Phase 1Lexical Analysis0 / 6 complete
1.1.1Tokens, lexemes, patterns and attributes; how the lexer works with the parser and symbol tableLesson1.1.2Counting tokens in C code: whitespace, comments, string literals, ++ and >=Lesson1.2.1Writing token definitions as regular expressionsLesson1.2.2Transition diagrams; longest match and priority rules; lookaheadLesson1.3Lexical errors and recovery; how a lexer generator (Lex/Flex) is structuredLessonCP1Lexical analysisCheckpoint
03Phase 2Syntax Analysis (Parsing)0 / 14 complete
2.1.1Context-free grammar primer: productions, derivations (leftmost/rightmost), parse treesLesson2.1.2Ambiguity; encoding operator precedence and associativity in a grammarLesson2.2Grammar transformations: eliminating left recursion (direct and indirect); left factoringLesson2.3.1Recursive-descent parsing and backtrackingLesson2.3.2FIRST and FOLLOW setsLesson2.3.3LL(1) table construction; the LL(1) test and conflicts; stack trace of parsing a stringLesson2.4.1Shift-reduce parsing; handles; viable prefixes; shift/reduce and reduce/reduce conflictsLesson2.4.2LR(0) items, CLOSURE, GOTO, the canonical collection and the LR(0) tableLesson2.4.3SLR(1)Lesson2.4.4Canonical LR(1) (CLR) items with lookaheadsLesson2.4.5LALR(1): merging states and which conflicts merging can createLesson2.4.6Power and state-count comparison of LL(1), LR(0), SLR, LALR, CLR; grammar-classification drillsLesson2.4.7Operator-precedence parsing (brief); YACC conflict resolution with precedence and associativity; panic-mode error recovery (brief)LessonCP2Syntax analysisCheckpoint
04Phase 3Syntax-Directed Translation0 / 5 complete
3.1Syntax-directed definitions: attributes, semantic rules, synthesized vs inherited, annotated parse trees, dependency graphs and evaluation orderLesson3.2S-attributed and L-attributed definitions; which parsers can evaluate whichLesson3.3Translation schemes with embedded actions; tracing what an SDT prints or computesLesson3.4Applications: building syntax trees; basic type checking (brief)LessonCP3Syntax-directed translationCheckpoint
05Phase 4Intermediate Code Generation0 / 7 complete
4.1Why an intermediate representation; syntax trees vs DAGs; counting nodes in a DAGLesson4.2.1Three-address code instruction forms; quadruples, triples, indirect triplesLesson4.2.2TAC for expressions and array accesses (address calculation)Lesson4.2.3TAC for if/while and Boolean expressions (short-circuit; backpatching brief)Lesson4.3Static single assignment (SSA) form; counting variables and temporariesLesson4.4Basic blocks: leader rules and partitioning; control flow graphs (the second meaning of “CFG”); counting blocks and edgesLessonCP4Intermediate code generationCheckpoint
06Phase 5Runtime Environments0 / 6 complete
5.1Storage organization: code, static, stack, heapLesson5.2Activation records, activation trees, the call stack; caller vs callee duties; recursionLesson5.3Static vs dynamic scoping; tracing program output under each; access links and displays (brief)Lesson5.4Parameter passing: by value, by reference, by value-result, by name; output tracingLesson5.5Static vs stack vs heap allocation: which language features force whichLessonCP5Runtime environmentsCheckpoint
07Phase 6Optimization0 / 7 complete
6.1Local optimization: constant folding, algebraic simplification, strength reduction, copy propagation, dead-code elimination, local CSE with the block DAG, peephole optimizationLesson6.2The data-flow analysis framework: gen/kill sets, in/out equations, forward vs backward, meet operator, iterating to a fixed pointLesson6.3Constant propagationLesson6.4Liveness analysis: live variables at each point; what liveness is used forLesson6.5Global common-subexpression elimination via available expressionsLesson6.6Loop optimizations: code motion, induction variables (brief, low weight)LessonCP6OptimizationCheckpoint
08Phase 7Integration & Final Test0 / 36 complete
LI.0.1What a compiler isChapter reviewLI.0.2PrimersChapter reviewLI.1.1Role of the lexical analyzerChapter reviewLI.1.2Specifying and recognizing tokensChapter reviewLI.1.3Lexical errors and LexChapter reviewLI.2.1GrammarsChapter reviewLI.2.2Grammar transformationsChapter reviewLI.2.3Top-down parsingChapter reviewLI.2.4Bottom-up parsingChapter reviewLI.3.1Syntax-directed definitionsChapter reviewLI.3.2S- and L-attributed definitionsChapter reviewLI.3.3Translation schemesChapter reviewLI.3.4SDT applicationsChapter reviewLI.4.1Syntax trees and DAGsChapter reviewLI.4.2Three-address codeChapter reviewLI.4.3SSA formChapter reviewLI.4.4Basic blocks and flow graphsChapter reviewLI.5.1Storage organizationChapter reviewLI.5.2Activation recordsChapter reviewLI.5.3ScopingChapter reviewLI.5.4Parameter passingChapter reviewLI.5.5Allocation strategiesChapter reviewLI.6.1Local optimizationChapter reviewLI.6.2Data-flow frameworkChapter reviewLI.6.3Constant propagationChapter reviewLI.6.4Liveness analysisChapter reviewLI.6.5Global CSEChapter reviewLI.6.6Loop optimizationsChapter review7.1Master Rule Sheet: every rule card from Phases 0–6Revision7.2The full journey: one program traced through every phaseRevision7.3.1Mixed practice set 1Revision7.3.2Mixed practice set 2Revision7.3.3Mixed practice set 3Revision7.4GATE pattern drillRevision7.5Final TestFinal test7.4-keyFinal Test — Answer Key🛑Stop here until you have finished the 90-minute final test.Q1 Answer: (C)1 markDeclarations are checked against the symbol table during semantic analysis.(A) is wrong: An identifier is a valid token.(B) is wrong: The statement is well formed.(D) is wrong: Too late; caught earlier.Re-read: Lesson 0.1.3 — The phases of a compiler; symbol table; error handler; which phase catches which errorQ2 Answer: 131 markif ( x >= 10 ) y = x -- − 2 ; → 13; the comment gives none (computed).Re-read: Lesson 1.1.2 — Counting tokens in C code: whitespace, comments, string literals, ++ and >=Q3 Answer: 31 mark> then = then = : 3.Re-read: Lesson 1.2.2 — Transition diagrams; longest match and priority rules; lookaheadQ4 Answer: (C)1 markA B can derive ε, so ε ∈ FIRST(S) (computed).(A) is wrong: B is nullable, so b counts too.(B) is wrong: Misses ε.(D) is wrong: Misses b and c.Re-read: Lesson 2.3.2 — FIRST and FOLLOW setsQ5 Answer: (C)2 marksF is followed by T′, whose FIRST is { * } and which is nullable, so FOLLOW(T′) = FOLLOW(T) = { +, ), $ } joins in (computed).(A) is wrong: T′ can vanish.(B) is wrong: Misses ) and $.(D) is wrong: That is FOLLOW(T′).Re-read: Lesson 2.3.2 — FIRST and FOLLOW setsQ6 Answer: (B)2 marksOnly B has no conflicts (computed for all four).(A) is wrong: Common prefix a.(C) is wrong: Left recursive.(D) is wrong: Both alternatives start with a.Re-read: Lesson 2.3.3 — LL(1) table construction; the LL(1) test and conflicts; stack trace of parsing a stringQ7 Answer: 71 markComputed: 7.Re-read: Lesson 2.4.2 — LR(0) items, CLOSURE, GOTO, the canonical collection and the LR(0) tableQ8 Answer: (B)2 marksFIRST of the two alternatives are { a } and { b }: LL(1). In I0 both A → · and B → · reduce on FOLLOW(A) = FOLLOW(B) = { a, b }: SLR R/R conflict; LR(1) lookaheads separate them (computed).(A) is wrong: SLR has R/R conflicts.(C) is wrong: The FIRST sets are disjoint.(D) is wrong: LR(0) has conflicts.Re-read: Lesson 2.4.6 — Power and state-count comparison of LL(1), LR(0), SLR, LALR, CLR; grammar-classification drillsQ9 Answer: (A) (C) (D)2 marksComputed: CLR conflict-free; LALR has 2 R/R conflicts. Merging never adds S/R conflicts.Re-read: Lesson 2.4.5 — LALR(1): merging states and which conflicts merging can createQ10 Answer: 21 mark(id * id) + id and id * (id + id): 2 (computed).Re-read: Lesson 2.1.2 — Ambiguity; encoding operator precedence and associativity in a grammarQ11 Answer: 82 marksF → id three times, T → F twice, T → T * F, E → T, E → E + T: 8 (computed from the trace).Re-read: Lesson 2.4.1 — Shift-reduce parsing; handles; viable prefixes; shift/reduce and reduce/reduce conflictsQ12 Answer: (B)1 markDefault: shift (and the earlier production for reduce-reduce).(A) is wrong: Opposite.(C) is wrong: It warns and continues.(D) is wrong: That is the reduce-reduce rule.Re-read: Lesson 2.4.7 — Operator-precedence parsing (brief); YACC conflict resolution with precedence and associativity; panic-mode error recovery (brief)Q13 Answer: 182 marks3 × (2 + 4) × 1 = 18 (computed).Re-read: Lesson 3.1 — Syntax-directed definitions: attributes, semantic rules, synthesized vs inherited, annotated parse trees, dependency graphs and evaluation orderQ14 Answer: (B)2 marksPrefix order (computed: + a * b c).(A) is wrong: Postfix.(C) is wrong: Wrong nesting.(D) is wrong: Wrong nesting.Re-read: Lesson 3.3 — Translation schemes with embedded actions; tracing what an SDT prints or computesQ15 Answer: (A)1 markIt uses only synthesized attributes, which L-attributed definitions allow.(B) is wrong: It always is.(C) is wrong: Bottom-up parsers evaluate it naturally.(D) is wrong: It has only synthesized attributes.Re-read: Lesson 3.2 — S-attributed and L-attributed definitions; which parsers can evaluate whichQ16 Answer: 71 markOperators −, *, + and leaves a, b, c, d: 7 (parentheses vanish).Re-read: Lesson 3.4 — Applications: building syntax trees; basic type checking (brief)Q17 Answer: 72 marksLeaves a, b, c; then a + b, (a + b) − c (shared by both uses), * and the final +: 7 (computed).Re-read: Lesson 4.1 — Why an intermediate representation; syntax trees vs DAGs; counting nodes in a DAGQ18 Answer: 41 markt1 = a * b; t2 = c * d; t3 = t1 + t2; t4 = t3 − e: 4.Re-read: Lesson 4.2.1 — Three-address code instruction forms; quadruples, triples, indirect triplesQ19 Answer: 25282 marks2000 + ((4 − 1) × 20 + (7 − 1)) × 8 = 2528.Re-read: Lesson 4.2.2 — TAC for expressions and array accesses (address calculation)Q20 Answer: 72 marksLeaders 1, 3, 4, 6, 8, 9; edges B1→B2, B2→B6, B2→B3, B3→B2, B3→B4, B4→B2, B5→B6: 7 (computed).Re-read: Lesson 4.4 — Basic blocks: leader rules and partitioning; control flow graphs (the second meaning of “CFG”); counting blocks and edgesQ21 Answer: 71 markComputed: t1 = a + b; t2 = minus t1; t3 = t2 * c; t4 = a + b; t5 = minus t4; t6 = t3 + t5; y = t6 → 7.Re-read: Lesson 4.2.1 — Three-address code instruction forms; quadruples, triples, indirect triplesQ22 Answer: (A)2 marksf always sees the global x = 5; g prints its own x + 1 = 11 (computed).(B) is wrong: That is dynamic scoping.(C) is wrong: Not under either rule.(D) is wrong: g prints 11.Re-read: Lesson 5.3 — Static vs dynamic scoping; tracing program output under each; access links and displays (brief)Q23 Answer: (C)2 marksCopies x = 2, y = 3; x = 5, y = 2, a = 20; on return a ← 5, b ← 2 (computed).(A) is wrong: By value.(B) is wrong: By reference / name.(D) is wrong: The copy-back overwrites a.Re-read: Lesson 5.4 — Parameter passing: by value, by reference, by value-result, by name; output tracingQ24 Answer: (C)2 marksx means a[i], re-evaluated each time: after i = 2, x = x + 5 updates a[2] (computed).(A) is wrong: By value.(B) is wrong: By reference / value-result.(D) is wrong: Only one element changes.Re-read: Lesson 5.4 — Parameter passing: by value, by reference, by value-result, by name; output tracingQ25 Answer: 111 markComputed: 11.Re-read: Lesson 5.2 — Activation records, activation trees, the call stack; caller vs callee duties; recursionQ26 Answer: (C)1 markTheir lifetime is not tied to a call.(A) is wrong: Stack.(B) is wrong: Stack frames suffice.(D) is wrong: Static.Re-read: Lesson 5.5 — Static vs stack vs heap allocation: which language features force whichQ27 Answer: (A)2 marksB1 reads x and y before writing anything else; a and b are written first (computed: { x, y }).(B) is wrong: That is LIVE-OUT of B1.(C) is wrong: y is read too.(D) is wrong: a is written before being read.Re-read: Lesson 6.4 — Liveness analysis: live variables at each point; what liveness is used forQ28 Answer: (B)1 markAvailable only if computed on every path.(A) is wrong: That is for may problems.(C) is wrong: Not a meet.(D) is wrong: It is global.Re-read: Lesson 6.5 — Global common-subexpression elimination via available expressionsQ29 Answer: 22 marksx = 1 → z = 3 → x = 1 again: the back edge brings x = 1, so x stays 1 and w = 1 × 2 = 2 (computed).Re-read: Lesson 6.3 — Constant propagationQ30 Answer: 21 markc = 7 * x; f = c + c → 2 (computed).Re-read: Lesson 6.1 — Local optimization: constant folding, algebraic simplification, strength reduction, copy propagation, dead-code elimination, local CSE with the block DAG, peephole optimizationAnswer key
A good way to read
01 · Think before revealingTry the Predict First and self-test questions. Open the Answer Vault when you’re ready.
02 · Keep track of understandingMark each reading item complete yourself. The reading-position bar simply shows where you are on the page.
03 · Revisit what mattersUse chapter reviews, checkpoints, and revision pages to connect ideas. The imported practice is self-checked against the supplied answers.
Your progress, your copy.
Saved in this browser. Export a backup to move your Compiler Design progress to another device.
Adapted from your supplied Compiler Design notes. Source answers and claims in the notes have not been independently fact-checked. Reading progress is separate from the Atlas topic checklist.