Compiler Design/Phase 7 · Integration & Final Test

Answer key 7.4-key · Item 90 of 90

Final 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 optimization

Read at your own pace. Try the questions before opening the answers.