🎯
Ten question patterns that recur in GATE CS compiler questions, each with where it was taught, the fastest reliable method, and a time target. Then one drill question per pattern. (These are pattern descriptions, not claims about specific past papers.)
| # | Pattern | Taught in | Fast method | Target time |
|---|---|---|---|---|
| 1 | Count tokens in a C fragment | 1.1.2 | Scan left to right, longest match; comments and whitespace give no tokens; a string literal is one token. | 1–2 min |
| 2 | FIRST / FOLLOW of a non-terminal | 2.3.2 | FIRST: look at the leftmost symbols, pass through nullable ones. FOLLOW: scan every right side for the non-terminal. | 2–3 min |
| 3 | Is the grammar LL(1)? / fill a table cell | 2.3.3 | For each pair of alternatives, FIRST sets disjoint; if one is nullable, FIRST of the other disjoint from FOLLOW. | 2–3 min |
| 4 | LR state counts and conflicts | 2.4.2–2.4.5 | Build only the states you need; LALR has as many states as LR(0)/SLR; CLR may have more. | 4–6 min |
| 5 | Which parser class accepts the grammar? | 2.4.6 | Look for the textbook shapes: L = R (SLR conflict), merged c-states (LALR R/R), ε-productions with different followers. | 3–4 min |
| 6 | Evaluate an SDD / print an SDT | 3.1, 3.3 | Build the parse tree respecting the grammar’s precedence (not the usual one), then evaluate bottom-up or walk left to right printing actions. | 3–5 min |
| 7 | Count DAG nodes, temporaries, quadruples | 4.1, 4.2.1 | Value numbering: one node per distinct (operator, operands); leaves count once. | 2–3 min |
| 8 | Basic blocks and flow-graph edges | 4.4 | Leaders: first, every target, every instruction after a jump. Edges: jump + fall-through. | 2–3 min |
| 9 | Program output under scoping or parameter modes | 5.3, 5.4 | Draw the stack; for value-result copy back at return; for name re-evaluate the argument each time. | 3–5 min |
| 10 | Data-flow sets (live, reaching, available, constants) | 6.2–6.5 | Write direction and meet first; iterate in flow order; stop when a round changes nothing. | 4–6 min |
Practice set
Q1NAT1 mark1 Tokens
How many tokens are in x = a[i]++ + *p;?
Numerical answer: ________
Q2MCQ1 mark2 FIRST
For S → A B C, A → a | ε, B → b | ε, C → c, FIRST(S) is:
- (A) { a }
- (B) { a, b }
- (C) { a, b, c }
- (D) { a, b, c, ε }
Q3NAT2 marks3 LL(1) cells
For E → T E', E' → + T E' | ε, T → F T', T' → * F T' | ε, F → ( E ) | id, how many non-empty cells does the LL(1) table have?
Numerical answer: ________
Q4NAT1 mark4 LR states
How many states does the LR(0) collection of E → E + T | T, T → T * F | F, F → ( E ) | id have (including I0)?
Numerical answer: ________
Q5MCQ2 marks5 Class
S → A a | b A c | d c | b d a, A → d is:
- (A) SLR(1)
- (B) LALR(1) but not SLR(1)
- (C) CLR(1) but not LALR(1)
- (D) not LR(1)
Q6NAT2 marks6 SDD
E → E * T {E.val = E.val + T.val} | T; T → T + F {T.val = T.val × F.val} | F; F → n. Value of 2 + 3 * 4?
Numerical answer: ________
Q7NAT1 mark7 DAG
How many nodes does the DAG for a = b + c; d = b + c; e = a * d; f = e − a have?
Numerical answer: ________
Q8NAT2 marks8 Blocks
How many basic blocks?
(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: ________
Q9MCQ2 marks9 Parameters
What is printed under call by value-result (values copied back x first, then y)?
int a = 0;
void f(int x, int y) { x = x + 1; y = y + 10; }
main() { f(a, a); print(a); }
- (A) 0
- (B) 1
- (C) 10
- (D) 11
Q10NAT2 marks10 Liveness
B1: p = 1, q = r + 2 → B2: r = p + q, s = r * 2 → B3: p = s − q (back to B2) and B2 → B4: t = p + r. How many variables are live at the start of B2?
Numerical answer: ________
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: 111 mark
x = a [ i ] ++ + * p ; → 11 (computed).
Re-read: Lesson 1.1.2 — Counting tokens in C code: whitespace, comments, string literals, ++ and >=
Q2 Answer: (C)1 mark
A and B can vanish, C cannot (computed).
- (A) is wrong: A is nullable.
- (B) is wrong: B is nullable too.
- (D) is wrong: C is not nullable, so S is not.
Re-read: Lesson 2.3.2 — FIRST and FOLLOW sets
Q3 Answer: 132 marks
Computed: 13.
Re-read: Lesson 2.3.3 — LL(1) table construction; the LL(1) test and conflicts; stack trace of parsing a string
Q4 Answer: 121 mark
Computed: 12.
Re-read: Lesson 2.4.2 — LR(0) items, CLOSURE, GOTO, the canonical collection and the LR(0) table
Q5 Answer: (B)2 marks
FOLLOW(A) = { a, c } causes SLR conflicts (computed: 2 S/R); LALR lookaheads separate them.
- (A) is wrong: SLR has conflicts.
- (C) is wrong: LALR already works.
- (D) is wrong: It is LR(1).
Re-read: Lesson 2.4.6 — Power and state-count comparison of LL(1), LR(0), SLR, LALR, CLR; grammar-classification drills
Q6 Answer: 102 marks
Here + binds tighter (it is lower in the grammar): T = 2 × 3 = 6, then E = 6 + 4 = 10 (computed).
Re-read: Lesson 3.1 — Syntax-directed definitions: attributes, semantic rules, synthesized vs inherited, annotated parse trees, dependency graphs and evaluation order
Q7 Answer: 51 mark
Leaves b, c (a and d label the same + node), then +, * and −: 5 (computed).
Re-read: Lesson 4.1 — Why an intermediate representation; syntax trees vs DAGs; counting nodes in a DAG
Q8 Answer: 62 marks
Leaders 1, 3, 4, 6, 8, 9: 6 (computed).
Re-read: Lesson 4.4 — Basic blocks: leader rules and partitioning; control flow graphs (the second meaning of “CFG”); counting blocks and edges
Q9 Answer: (C)2 marks
x and y are copies of 0; x = 1, y = 10; copy back x → a = 1, then y → a = 10 (computed). By reference it would be 11.
- (A) is wrong: That is by value.
- (B) is wrong: y is copied back last.
- (D) is wrong: That is by reference.
Re-read: Lesson 5.4 — Parameter passing: by value, by reference, by value-result, by name; output tracing
Q10 Answer: 22 marks
IN[B2] = { p, q }: 2 (computed).
Re-read: Lesson 6.4 — Liveness analysis: live variables at each point; what liveness is used for