GATE Compiler Design previous year questions

S1 opens a string literal that never closes on the line: the lexer cannot form a valid token, a lexical error. S2 is a valid string literal "Hello;" followed by ';': no error. S3 is syntactically a valid declaration but assigns a char* (string literal) to an int*: a type mismatch, found during semantic analysis. Answer: (C) S1 has a lexical error and S3 has a semantic error.

Concept: Classify errors by compiler phase: bad tokens are lexical, bad structure is syntactic, type rules are semantic. The ';' inside quotes in S2 is just a character.

LL(1) is predictive and never backtracks (A false). An LL(1) grammar cannot be left-recursive (B false). Common prefixes make two productions share a FIRST symbol, so an LL(1) grammar must be left-factored (C true). Every LL(1) grammar is not necessarily SLR and vice versa, and LR-family parsers are in general the more powerful; LL(1) is not more powerful than SLR (D false). Answer: (C).

Concept: LL(1) prerequisites: no left recursion, left-factored, disjoint FIRST/FOLLOW sets. Bottom-up parsers handle left recursion that LL(1) cannot.

An expression is redundant at a point if it is available: computed on every path reaching it with no later redefinition of its operands. g * k: computed in B2 and in B3, and neither g nor k is redefined afterwards, so it is available at B4 entry: redundant in B4. b + i: computed in B1, but B3 redefines b, so on the B3 path it is killed: not redundant. c + m: computed in B3 only, not on the path B1 → B2 → B4, so not available at B5: not redundant. Answer: (D) B4: { g * k }, B5: { }.

Concept: Global CSE uses available-expressions analysis, an all-paths (intersection) problem. Traps: b + i looks repeated but b is reassigned; c + m appears earlier but only on one branch.

G1: D → T V with V → V id | id gives T id id ... id (one or more ids). G2: D → D id | T id gives the same T id⁺. So P = Q (A true). In SDD2, D.type and T.type are both computed from children only: synthesized, S-attributed (B true). In SDD1, V.type is inherited (from parent D or V), but T.type and D.type are synthesized, so SDD1 is L-attributed but does not contain only inherited attributes (C false). Both put every id with the declared type, so the symbol table gets the same entries (D true). Answer: (A), (B), (D).

Concept: Synthesized attributes flow up from children; inherited ones flow down or across from parent/left siblings. SDD1 mixes both, so 'only inherited' is the trap.

Static variables live in the data/BSS segment. A local array is on the stack in the function's activation record. The return address is also on the stack. Memory obtained with malloc() comes from the heap. Answer: (C).

Concept: Memory layout of a C program: text, data/BSS, stack, heap. The trap is (A): a static local has function scope but static storage duration, so it is in the data segment, not the stack or heap.

Use longest match. x1 → id (1). 23mm → number 23, id mm (2). 78 → number (1). y → id (1). 7z → number 7, id z (2). zz5 → id (1). 14A → number 14, id A (2). 8H → number 8, id H (2). AaYcD → id (1). Total = 1+2+1+1+2+1+2+2+1 = 13. Answer: 13.

Concept: An id must start with a letter, so a word beginning with digits splits into a number followed by an id. The trap is counting each blank-separated word as one token (giving 9).

Augment with S' → S. I0 = {S' → .S, S → .ACB, A → .aA, A → .}: shift on a and reduce A → ε (LR(0) reduces in every column) - conflict 1. I(a) = {A → a.A, A → .aA, A → .}: shift a vs reduce - conflict 2. I(A) = {S → A.CB, C → .cC, C → .}: shift c vs reduce - conflict 3. I(c) = {C → c.C, C → .cC, C → .}: conflict 4. I(AC) = {S → AC.B, B → .bB, B → .b}: shifts only. I(b) = {B → b.B, B → b., B → .bB, B → .b}: shift b vs reduce B → b - conflict 5. Other states have no conflict. Total = 5. Answer: (D) 5.

Concept: In LR(0), a state with a completed item reduces on every terminal, so any shift in that state conflicts. ε-productions create a completed item in every state that predicts them. The trap is missing the B → b. state or forgetting I0.

in(B) = use(B) ∪ (out(B) - def(B)), out(B) = union of in(successors). B4: out = ∅, in = {d, e}. B2: out = {d, e}, in = {a, e}. B3: in = {a, f} ∪ (out(B3) - {e}), out(B3) = in(B1). B1: in = {b, c} ∪ (out(B1) - {a}), out(B1) = in(B2) ∪ in(B3). Iterate to a fixed point: out(B1) = {a, e} ∪ {a, f, b, c} = {a, b, c, e, f}; in(B1) = {b, c, e, f}; out(B3) = {b, c, e, f}. Answer: (A).

Concept: Backward dataflow analysis with a loop (B3 → B1) needs iteration until nothing changes. The trap is stopping after one pass and missing that e and f flow around the loop, or that e is killed in B3 but live again from B1.

The symbol table records identifiers with their scope, type and storage information (A true). It can be a hash table, list or BST (B true). Entries are created as the lexer meets identifiers (D true). After parsing, semantic analysis (type checking), intermediate code generation and code generation (storage offsets) all still consult it, so it is needed beyond parsing. Statement (C) is false. Answer: (C).

Concept: The symbol table persists through all compiler phases. The trap is thinking it is a front-end-only structure.

Live variable analysis finds, at each point, the variables whose current values may still be used later. Register allocation uses this: two variables whose live ranges do not overlap can share a register, and a dead variable's register can be freed. Strength reduction and constant folding work on expressions and values, not liveness; call management is a runtime concern. Answer: (B).

Concept: Liveness drives register allocation (interference graphs) and dead-code elimination. Constant folding needs constant propagation, not liveness - a common mix-up.

Rule for First: if A → ε is a production, ε ∈ First(A): (A) true. Rule for Follow: the end marker $ is placed in Follow(S) for the start symbol: (D) true. $ is never in a First set (it is not derived from any symbol): (B) false. Follow sets contain terminals and $, never ε: (C) false. Answer: (A), (D).

Concept: First may contain ε; Follow may contain $; never the other way round. Swapping the two is the standard trap.

Leaders: the first statement 1001; jump targets 1003, 1002, 1013; statements after jumps 1010, 1012 (1018 does not exist). Sorted leaders: 1001, 1002, 1003, 1010, 1012, 1013. Blocks: [1001], [1002], [1003-1009], [1010-1011], [1012], [1013-1017]. Answer: 6.

Concept: Leader rules: first instruction, every jump target, every instruction following a jump. Commonly missed: 1002 as a target, making 1001 a block by itself.

Backpatching keeps lists of jumps with unfilled targets (truelist, falselist, nextlist) and fills them in when the target label becomes known. This is exactly what lets a compiler generate code for Boolean expressions with short-circuit jumps and for flow-of-control statements (if, while) in a single pass. Both statements are correct. Answer: (C).

Concept: Backpatching exists to avoid a second pass over generated code; the textbook treatment applies it first to Boolean expressions and then to control flow.

Rule 1: A.i = B.i makes A's attribute depend on its right sibling B, which violates L-attribution; it also has inherited attributes, so it is not S-attributed. Neither. Rule 2: D.i = C.i + 2 is inherited from the left sibling (allowed in L-attributed, not in S-attributed); P.i is synthesized. So L-attributed, not S-attributed. Rule 3: only the head is computed from children: S-attributed and hence also L-attributed. Answer: (C).

Concept: S-attributed means only synthesized attributes. L-attributed allows inherited attributes that depend only on the parent and left siblings. Every S-attributed definition is L-attributed. The trap is missing the right-sibling dependency in Rule 1.

FOLLOW(A) = {a, c}. From I0 on d: {S → d.c, A → d.}. SLR reduces A → d on FOLLOW(A), including c, while S → d.c shifts c: shift-reduce conflict, so not SLR(1). In LR(1) this item is A → d. with lookahead a only, so no conflict. After b then d: {S → bd.a, A → d.} with LR(1) lookahead c, while shift is on a: no conflict (SLR would conflict on a). The two d-states have different cores, so LALR merging joins nothing and introduces no conflict. G is LALR(1) but not SLR(1). Answer: (C).

Concept: Classic grammar separating SLR from LALR: FOLLOW sets are too coarse, while LR(1) lookaheads are context-specific. Check that LALR merging only combines states with identical cores.

Not LL(1): in G1 two S-productions begin with "if"; in G2, S → if E then S and S → M both have "if" in FIRST (M → if ...). So neither is LL(1). G1 is the classic dangling-else grammar: "if b then if b then a else a" has two parse trees. G2 is also ambiguous because the else-part of M is an unrestricted S. M derives "if b then c else if b then c". Then w = "if b then if b then c else if b then c else c" parses as S → if b then S with S = M = if b then c else (if b then c else c), and also as S → M = if b then M' else c with M' = "if b then c else if b then c". Answer: (C) and (D).

Concept: Any ambiguous grammar is not LL(1), and common prefixes also break LL(1). G2 looks like the standard matched/unmatched fix, but allowing an unmatched S after else reintroduces ambiguity.

Shift-reduce parsers build the parse tree from leaves to root, and LR parsers (SLR, LALR, CLR) are shift-reduce parsers, so both are bottom-up. Predictive and LL(1) parsers are top-down. Answer: (A), (D).

Concept: LL = top-down (leftmost derivation), LR = bottom-up (rightmost derivation in reverse). The trap is mixing up the two L's.

/ binds loosest and is right-associative, so the expression is (3 + 1 + 5 ∗ 2) / ((7 + 2 − 4 − 7 − 6) / 2). Left part: + binds before ∗, so (3 + 1 + 5) ∗ 2 = 18. Middle: + first gives 9 − 4 − 7 − 6, and right-associative − gives 9 − (4 − (7 − 6)) = 9 − 3 = 6. Then 6 / 2 = 3 and 18 / 3 = 6. Answer: 6.

Concept: Split at the lowest-precedence operator first, applying its associativity, then recurse. The trap is evaluating − left to right.

Parse MMLK as D = MM, H = L, T = ϵ, U = K. D.val = 5 + 5 + (−5) = 5. H.val = 50 + (−10) = 40. T.val = −5. U.val = 5. S.val = 5 + 40 − 5 + 5 = 45. Answer: (A) 45.

Concept: Evaluate synthesized attributes bottom-up, remembering the ϵ productions contribute their own (negative) values. The trap is ignoring the ϵ values and getting 65.

ϵ ∈ FIRST(T) and c ∉ FIRST(T), so (2) is T → ϵ, ruling out (C) and (D). S → fR would put R at the end of S, so FOLLOW(R) would include FOLLOW(S) = {c, f, $}, not just {f}; with S → Rf, FIRST(S) = {d} ∪ {c, f} and FOLLOW(R) = {f}. With R → cTR: FOLLOW(T) gets FIRST(R) − ϵ = {c} and, since R is nullable, FOLLOW(R) = {f}; with FOLLOW(S) from T → aS this matches {c, f, $}. Answer: (A).

Concept: Work backwards from the given sets: ϵ in FIRST forces an ϵ production, and a small FOLLOW set means the non-terminal is never at the end of a longer right side. The trap is choosing S → fR, which gives the right FIRST(S) but the wrong FOLLOW(R).

Leaders: L1 (first), L3 (target of L14), L4 (target of L12), L11 (target of L9), and the instructions after each jump: L10, L13, L15. Blocks: L1-L2 (2), L3 (1), L4-L9 (6), L10 (1), L11-L12 (2), L13-L14 (2), L15 (1). That is 7 blocks, the largest with 6 instructions. Answer: (D) 7 and 6.

Concept: Leaders are the first instruction, every jump target, and every instruction following a jump. The trap is missing L3 as a separate leader, which merges it into a 7-instruction block.

The lexical analyzer produces tokens (P-2). The syntax analyzer builds the parse tree (Q-3). The intermediate code generator works with the abstract syntax tree as an intermediate representation (R-1). Constant folding is a code optimization (S-4). Answer: (B) P - 2; Q - 3; R - 1; S - 4.

Concept: Phases of a compiler and their artefacts. Parse tree versus AST is the usual confusion: the parser gives the concrete parse tree, the AST serves as an intermediate representation.

(A) True - the textbook definition of an attribute grammar. (B) False - L-attributed definitions are exactly those that can always be evaluated in one depth-first, left-to-right traversal. (C) True - synthesized attributes are computed at each reduction. (D) False - L-attributed definitions on LL(1) grammars can be evaluated bottom-up (using marker non-terminals), but not every L-attributed definition on an LR(1) grammar can. The FALSE statements are B and D. Answer: (B), (D).

Concept: The question asks for FALSE statements. Key facts: L-attributed means depth-first evaluable; bottom-up evaluation of inherited attributes is guaranteed only for L-attributed SDDs on LL grammars.

FIRST(A) = {c, ε}, FIRST(B) = {d, ε}. FIRST(AaAb) = {c, a}, FIRST(BbBa) = {d, b}. So M[S,c] = S → AaAb (1) and M[S,d] = S → BbBa (2). FOLLOW(A): A is followed by a and by b in AaAb, so FOLLOW(A) = {a, b} and A → ε goes in columns a and b: (3) = A → ε. FOLLOW(B) = {b, a} from BbBa, so (4) = B → ε. Answer: (A).

Concept: Filling an LL(1) table: productions go under FIRST of their right side, and ε-productions under FOLLOW of the left side. Forgetting the second occurrence of A (followed by b) leaves (3) blank wrongly.

(1) must fetch s[i] for uminus: an indexed read, written =[] s i. (2) negates it. (3) multiplies (p + r) by −s[i]: * (0) (2). (4) and (5) add u/w. The assignment to x[i] is split into an indexed-store triple that computes the location, []= x i, and triple (7) = (6) (5) assigns the value (5) to it. Answer: (A).

Concept: In triples, an array store x[i] = y needs two triples: []= x i, then an assignment using it. The read s[i] uses =[]. Option C puts (5) inside (6), duplicating (7).

I0 contains S′ → •S, S → •SS, S → •Aa, S → •bAc, S → •Bc, S → •bBa, A → •d#, B → •@. GOTO(I0, S) moves the dot over S in S′ → •S and S → •SS, giving the kernel S′ → S• and S → S•S. Closure of S → S•S adds all S-items S → •SS, S → •Aa, S → •bAc, S → •Bc, S → •bBa, and then A → •d# and B → •@. Total = 2 + 5 + 2 = 9. Answer: 9.

Concept: GOTO = advance the dot, then take the closure. Forgetting to close over A and B (reached via •Aa and •Bc) gives 7.

The front end (lexical, syntax, semantic analysis, intermediate code generation) depends on the source language but not on the target machine, so S1 is true. The back end (target-specific optimisation, code generation, register allocation) depends on the target hardware, so S2 is true. The back end works on the intermediate representation and is independent of the source language, so S3 is false. Answer: (B) Only S1 and S2 are TRUE.

Concept: The front-end/back-end split exists so one front end can target many machines and one back end can serve many languages. The trap is S3: language specifics belong to the front end.

(A) has an ϵ-move from the start straight to the final state, so it accepts the empty string and strings starting with a digit such as "9". (B) commits after the first letter to only letters or only digits, so "a1b" is rejected. (D) after the first letter accepts only repeated "letter digit" pairs, so "ab" is rejected. (C) is the Thompson construction: after one letter, the final state 1 can loop through either a letter branch or a digit branch and return via ϵ to 1, any number of times, giving letter(letter | digit)*. Answer: (C).

Concept: Tests turning a regular definition into an ϵ-NFA. Watch for ϵ-edges that skip the mandatory first letter and for loops that cannot mix letters and digits.

main calls f1(), f2(2), f3() in that order, so its children are f1, f2, f3. f2(2) first calls f3(); since X = 2 ≠ 1 it then calls f2(1). So f2(2) has children f3, f2. f2(1) calls f3(), then, since X == 1, calls f1(). So f2(1) has children f3, f1. f1 and f3 make no calls. Answer: (A).

Concept: An activation tree has one node per call, with children in call order. The trap is (D), which flattens the recursive call f2(1) and its callees into one level.

Use IN(B) = USE(B) ∪ (OUT(B) - DEF(B)). B2: USE {i, j}, DEF {i, j}. B3: DEF {a}. B4: USE {a}, DEF {i}. OUT(B4) = IN(B2) ∪ IN(EXIT) = IN(B2). Iterate to a fixed point: IN(B2) = {i, j} ∪ (OUT(B2) - {i, j}); OUT(B2) = IN(B3) ∪ IN(B4); IN(B4) = {a} ∪ (OUT(B4) - {i}); IN(B3) = OUT(B3) - {a} = IN(B4) - {a}. Fixed point: IN(B2) = {a, i, j}, so OUT(B4) = {a, i, j}, IN(B4) = {a, j}, OUT(B3) = {a, j}, IN(B3) = {j}, OUT(B2) = {a, j}, OUT(B1) = {a, i, j}. Answer: (D) B1: {a, i, j}, B2: {a, j}, B3: {a, j}, B4: {a, i, j}.

Concept: Backward data-flow analysis with the loop B4 -> B2 carrying i and j back. The trap is ignoring the back edge, which makes i and j look dead at the end of B4.

Integer part "10": I(1) = 1, then I(10) = 2 × 1 + 0 = 2. Fraction part "011" is right-recursive: F(1) = 1/2 × 1 = 0.5; F(11) = 1/2 × (1 + 0.5) = 0.75; F(011) = 1/2 × (0 + 0.75) = 0.375. N.val = 2 + 0.375 = 2.375 (binary 10.011). Answer: 2.375 (key range 2.374 to 2.376).

Concept: The scheme converts a binary fixed-point string to decimal: left recursion doubles for integer digits, right recursion halves for fractional digits. Evaluate F from the rightmost digit.

(A) False: merging LR(1) states with the same core to form LALR(1) can create reduce-reduce conflicts that LR(1) did not have. (B) False: the symbol table is used by later phases too (semantic analysis, code generation). (C) False: data flow analysis is a compile-time optimization tool, not needed for run-time memory management. (D) True: every deterministic context-free language has an LR(1) grammar, so LR(1) parsing suffices. Answer: (D).

Concept: LR(1) grammars generate exactly the DCFLs. Remember LALR merging can introduce reduce-reduce (never shift-reduce) conflicts.

closure(I₀) = I₀ (the dots are at the end or before the terminal +). goto on + gives S → S + .R. Its closure adds R → .R * P, R → .P, and then for P: P → .(S), P → .id. Total = 5 items. Answer: 5.

Concept: goto moves the dot over the symbol, then closure adds productions for every non-terminal right after a dot, repeatedly. The trap is forgetting the P items reached through R → .P.

% is generated lower in the tree (by T), so it binds tighter than #; both are left-recursive, hence left-associative. # means multiply and % means divide. Group: (20) # (10 % 5) # ((8 % 2) % 2). T values: 20; 10 ÷ 5 = 2; (8 ÷ 2) ÷ 2 = 2. S = (20 × 2) × 2 = 80. Answer: 80.

Concept: Precedence comes from grammar depth, associativity from left or right recursion. The trap is evaluating left to right ignoring precedence, or treating % as modulus.

(A) True: lexical rules are regular, and every regular language is context-free. (B) False: type checking is part of semantic analysis, which works on the parse tree produced by the parser, so it is done after parsing. (C) True: three-address code, syntax trees, SSA and so on. (D) True: activation records on the stack commonly hold arguments. Answer: (B).

Concept: Compiler phase order: lexical analysis, parsing, semantic analysis (type checking), IR generation. The trap is option (A); CFGs can describe tokens because regular is a subset of context-free, even though lexers use regular expressions in practice.

Input bbaacabc. Longest matches from the start: T₂ matches "bb" (length 2); T₁ matches "bba" ((b|c)* = bb, then a; length 3); T₃ matches "bbaac" (c? empty, (b|a)* = bbaa, then c; length 5). Longest is T₃ on "bbaac". Remaining "abc": T₁ matches only "a" (length 1), T₂ matches "ab" (length 2), T₃ matches "abc" ((b|a)* = ab, then c; length 3). Longest is T₃. Output: T₃T₃. Answer: (D).

Concept: Maximal munch: at each position try all patterns and take the longest match. The trap is committing to the first pattern that matches (T₁ or T₂ on "bb...") instead of checking which one reaches furthest.

Operators lower in the tree are applied first. The $ operations (b $ c, then $ d) sit below every #, so $ binds tighter: $ has higher precedence. b$c$d is grouped as (b $ c) $ d, so $ is left associative. The # operations group as a # (X # (e # f)), each # taking the rest of the expression on its right, so # is right associative. Answer: (A).

Concept: Reading precedence and associativity from a parse tree: deeper means higher precedence; a left-leaning chain means left associative, a right-leaning chain means right associative. The trap is reading associativity of # from the top-level split alone.

In SSA each variable is assigned exactly once, so every assignment gets a fresh name: x1 = u - t y1 = x1 * v x2 = y1 + w y2 = t - z y3 = x2 * y2 Variables used: the inputs u, t, v, w, z (5) plus x1, y1, x2, y2, y3 (5). Total = 10. Answer: 10.

Concept: SSA renames every definition. The trap is forgetting to count the original input variables (giving 5) or trying to reuse a temporary name.

* has the lowest precedence, so it is applied last: (2 - 5 + 1 - 7) * 3. + has the highest precedence: 5 + 1 = 6, giving 2 - 6 - 7. - is right-associative: 2 - (6 - 7) = 2 - (-1) = 3. Then 3 * 3 = 9. Answer: 9.

Concept: Parsing with non-standard precedence and associativity. The trap is applying the usual rules (giving -30) or treating - as left-associative (giving -33 after multiplying).

The derivation of aab is S ⇒ aA ⇒ aSb ⇒ aab. A bottom-up parser performs the reductions in reverse of this rightmost derivation: 1. Reduce the second a to S by S → a: print 2. 2. Reduce Sb to A by A → Sb: print 3. 3. Reduce aA to S by S → aA: print 1. Output: 2 3 1. Answer: (C).

Concept: Bottom-up parsing executes actions at reductions, i.e. the reverse rightmost derivation. The trap is printing in top-down (derivation) order, giving 1 3 2.

Tokens are specified by regular expressions (P-iii). Top-down parsers build a leftmost derivation (Q-i). Type checking is part of semantic analysis (R-ii). Runtime environments manage activation records on the stack (S-iv). Answer: (B).

Concept: Compiler phases and their core tools. Top-down gives leftmost derivation; bottom-up gives a rightmost derivation in reverse.

(A): A → Aa is immediate left recursion. (C): S → Aa and A → Sc give S ⇒ Aa ⇒ Sca, indirect left recursion. (D): A → Bd and B → Ae give A ⇒ Bd ⇒ Aed, indirect left recursion. (B): S starts with A, B or c; A starts with B or ε; B starts with e. No nonterminal can derive a sentential form starting with itself. Answer: (B).

Concept: Check indirect left recursion by following leftmost symbols through other rules, including through nullable prefixes. Looking only for A → A... misses (C) and (D).

G1: L → id [E and E → num] | num] [E generate id [num] followed by zero or more [num] groups, e.g. int id [num] [num] ; for int a[10][3];. G2: E → E[num] | [num] generates one or more [num] groups (left-recursive), so int id [num][num] ; is also produced. Both generate exactly the declarations with at least one dimension. Answer: (A) Both G1 and G2.

Concept: Grammars can split brackets across productions in unusual ways; derive a sample string to check. Left recursion (G2) does not make a grammar wrong, only unsuitable for top-down parsing.

A is the definition of a basic block - true. B: an expression available at a point need not be recomputed, which is exactly common subexpression elimination - true. C: an assignment to a variable that is not live afterwards is dead and can be removed - true. D: replacing 4 ∗ 5 by 20 at compile time is constant folding, not common subexpression elimination - false. Answer: (D).

Concept: Matching each data-flow analysis to the optimisation it enables. The trap is confusing constant folding (evaluate constant expressions at compile time) with CSE (reuse an already computed value).

Intermediate code separates the front end (language-specific) from the back end (machine-specific). Optimisations written on the intermediate representation are independent of both the source language and the target machine, so the same optimiser can be reused across compilers. Parsing and error reporting happen before IR generation, and register allocation is a back-end concern. Answer: (C).

Concept: Purpose of an IR: retargetability and reuse of machine-independent optimisation. The trap is option D; register allocation is done on target code, not because of the IR.

Recursion needs a fresh activation record for each active call. With purely static allocation there is one record per procedure, so recursion is impossible (1 true) and dynamic allocation of activation records is required (3 true). A stack alone suffices; no heap or garbage collector is needed (2 and 4 false). Answer: (D) 1 and 3 only.

Concept: Run-time storage organisation for recursion. The trap is statement 4: a heap is needed for dynamic data, not for recursion.