Final Test

🏆

Thirty questions in GATE format: 15 one-mark and 15 two-mark questions, 45 marks. Set a timer for 90 minutes, use only paper, and do not open any other section. The answer key, with the lesson to re-read for every question, is the very last section of these notes.

⏱️

30 questions · 45 marks · 90 minutes. Negative marking on MCQ only: −1/3 mark for a wrong 1-mark MCQ, −2/3 for a wrong 2-mark MCQ. No negative marking for MSQ or NAT. The answer key is the very last section of these notes.

Q1MCQ1 markPhases

An undeclared variable is reported by:

• (A) the lexical analyzer
• (B) the syntax analyzer
• (C) the semantic analyzer
• (D) the code generator

Q2NAT1 markTokens

How many tokens are in if (x >= 10) y = x-- - 2; // done?

Numerical answer: ________

Q3NAT1 markLongest match

A lexer has the operators , =, >, =, >, >= and uses longest match. Into how many tokens does it split >==?

Numerical answer: ________

Q4MCQ1 markFIRST

For S → A B | c, A → a A | ε, B → b | ε, FIRST(S) is:

• (A) { a, c }
• (B) { a, b, c }
• (C) { a, b, c, ε }
• (D) { a, ε }

Q5MCQ2 marksFOLLOW

For E → T E', E' → + T E' | ε, T → F T', T' → * F T' | ε, F → ( E ) | id, FOLLOW(F) is:

• (A) { * }
• (B) { +, * }
• (C) { +, *, ), $ }
• (D) { +, ), $ }

Q6MCQ2 marksLL(1)

Which grammar is LL(1)?

• (A) S → a S | a
• (B) S → a B; B → b B | ε
• (C) S → S a | b
• (D) S → A | B; A → a; B → a

Q7NAT1 markLR(0)

How many states does the LR(0) collection of S → A A, A → a A | b have (including I0)?

Numerical answer: ________

Q8MCQ2 marksClasses

For S → A a A b | B b B a, A → ε, B → ε, which is true?

• (A) It is SLR(1).
• (B) It is LL(1) and LALR(1) but not SLR(1).
• (C) It is not LL(1).
• (D) It is LR(0).

Q9MSQ2 marksLALR

For S → a A d | b B d | a B e | b A e, A → c, B → c, which are true?

• (A) It is CLR(1).
• (B) It is LALR(1).
• (C) Merging same-core states creates reduce-reduce conflicts.
• (D) LALR merging can never create shift-reduce conflicts that CLR did not have.

Q10NAT1 markAmbiguity

In E → E + E | E * E | id, how many parse trees does id * id + id have?

Numerical answer: ________

Q11NAT2 marksShift-reduce

With the SLR(1) table for E → E + T | T, T → T * F | F, F → ( E ) | id, how many reduce actions does the parse of id * id + id make?

Numerical answer: ________

Q12MCQ1 markYACC

By default, YACC resolves a shift-reduce conflict without precedence declarations by:

• (A) reducing
• (B) shifting
• (C) reporting an error and stopping
• (D) choosing the earlier production

Q13NAT2 marksSDD

E → E # T {E.val = E.val × T.val} | T; T → T & F {T.val = T.val + F.val} | F; F → n. Value of 3 # 2 & 4 # 1?

Numerical answer: ________

Q14MCQ2 marksSDT

E → {print("+")} E + T | T; T → {print("*")} T * F | F; F → id {print(id.name)}. Output for a + b * c?

• (A) a b c * +
• (B) + a * b c
• (C) * + a b c
• (D) + * a b c

Q15MCQ1 markAttributes

Every S-attributed definition is:

• (A) also L-attributed
• (B) never L-attributed
• (C) only usable with LL parsers
• (D) free of synthesized attributes

Q16NAT1 markSyntax tree

How many nodes does the syntax tree of a * (b + c) − d have?

Numerical answer: ________

Q17NAT2 marksDAG

How many nodes does the DAG of (a + b) * (a + b − c) + (a + b − c) have?

Numerical answer: ________

Q18NAT1 markTAC

Without sharing, how many temporaries does a * b + c * d − e need in three-address code?

Numerical answer: ________

Q19NAT2 marksArrays

double A[1..10][1..20] is stored row-major from address 2000 with 8 bytes per element. Address of A[4][7]?

Numerical answer: ________

Q20NAT2 marksFlow graph

How many edges does the flow graph of this code have?

(1) s = 0
(2) k = 0
(3) if k >= n goto (9)
(4) k = k + 1
(5) if k == 3 goto (3)
(6) s = s + k
(7) goto (3)
(8) s = s * 2
(9) print s

Numerical answer: ________

Q21NAT1 markQuadruples

How many quadruples does y = −(a + b) * c + −(a + b) need without sharing (unary minus is its own instruction, final copy into y included)?

Numerical answer: ________

Q22MCQ2 marksScoping

What does this print under static scoping?

int x = 5;
void f() { print(x); }
void g() { int x = 10; f(); x = x + 1; print(x); }
main() { g(); f(); }

• (A) 5 11 5
• (B) 10 11 5
• (C) 10 11 10
• (D) 5 10 5

Q23MCQ2 marksValue-result

What does this print with call by value-result?

int a = 2, b = 3;
void swapadd(int x, int y) { x = x + y; y = x - y; a = a * 10; }
main() { swapadd(a, b); print(a, b); }

• (A) 20 3
• (B) 50 2
• (C) 5 2
• (D) 20 2

Q24MCQ2 marksBy name

What does this print with call by name?

int i = 1; int a[3];
void f(int x) { i = i + 1; x = x + 5; }
main() { a[0] = 10; a[1] = 20; a[2] = 30; f(a[i]); print(a[0], a[1], a[2], i); }

• (A) 10 20 30 2
• (B) 10 25 30 2
• (C) 10 20 35 2
• (D) 10 25 35 2

Q25NAT1 markActivations

For f(n) = 1 if n ≤ 2 else f(n − 1) + f(n − 3), how many calls of f does f(6) make in total (including the first)?

Numerical answer: ________

Q26MCQ1 markHeap

Which feature forces heap allocation?

• (A) local int variables
• (B) recursion
• (C) objects that outlive the procedure that created them
• (D) global constants

Q27MCQ2 marksLiveness

B1: a = x + y, b = a * x → B2: x = b − 1 → B3: c = a + b, y = c * x → back to B1; also B1 → B3. LIVE-IN of B1 is:

• (A) { x, y }
• (B) { a, b, x }
• (C) { x }
• (D) { a, x, y }

Q28MCQ1 markMeet

The meet operator of available-expressions analysis is:

• (A) union
• (B) intersection
• (C) set difference
• (D) none, it is a local analysis

Q29NAT2 marksConstants

B1: x = 1, y = 2 → B2 (loops to itself): z = x + y, x = z − 2 → B3: w = x * y. What constant value does w have at the end of B3?

Numerical answer: ________

Q30NAT1 markOptimization

Block: a = 5; b = a + 2; c = b * x; d = b * x; e = c + d; f = e * 1; only f is needed after it. How many instructions remain after DAG-based optimization?

Numerical answer: ________