All PYQs: Compiler Design
53 real GATE CSE questions from 2012 to 2025, with the official answer key and a worked solution for each. Filter by year, topic, type, marks or keyword.
Questions belong to the GATE organising institutes; this copy is for personal study. Coverage varies by year: questions that need a figure I could not read, or whose answer I could not verify, were left out.
Showing 53 of 53 questions · 0 correct of 0 attempted · marks 0 / 84
GATE 2025 CS1 · Q12MCQ1 markPhases of a Compiler
Which ONE of the following statements is FALSE regarding the symbol table?
GATE 2025 CS1 · Q13MCQ1 markCode Optimisation & Data-Flow
Which ONE of the following techniques used in compiler code optimization uses live variable analysis?
GATE 2025 CS2 · Q21MCQ1 markIntermediate Code Generation
Consider the following statements about the use of backpatching in a compiler for intermediate code generation:
(I) Backpatching can be used to generate code for Boolean expressions in one pass.
(II) Backpatching can be used to generate code for flow-of-control statements in one pass. Which ONE of the following options is CORRECT?
(I) Backpatching can be used to generate code for Boolean expressions in one pass.
(II) Backpatching can be used to generate code for flow-of-control statements in one pass. Which ONE of the following options is CORRECT?
GATE 2025 CS2 · Q22MCQ1 markSyntax-Directed Translation
Given the following syntax directed translation rules: Rule 1: R → A B {B.i = R.i − 1; A.i = B.i; R.i = A.i + 1}. Rule 2: P → C D {P.i = C.i + D.i; D.i = C.i + 2}. Rule 3: Q → E F {Q.i = E.i + F.i}. Which ONE is the CORRECT option?
GATE 2025 CS2 · Q40MCQ2 marksBottom-up Parsing (LR family)
Given a Context-Free Grammar G:
S → A a | b A c | d c | b d a A → dWhich ONE of the following statements is TRUE?
GATE 2025 CS1 · Q46MSQ2 marksGrammars, Derivations & FIRST/FOLLOW
Which of the following statement(s) is/are TRUE while computing First and Follow during top down parsing by a compiler?
One or more options may be correct. Select all that apply, then submit.
GATE 2025 CS2 · Q51MSQ2 marksTop-down Parsing (LL(1))
Consider two grammars G1 and G2
G1: S → if E then S | if E then S else S | a E → b
G2: S → if E then S | M M → if E then M else S | c E → b. (if, then, else, a, b, c are terminals.)Which of the following option(s) is/are CORRECT?
One or more options may be correct. Select all that apply, then submit.
GATE 2025 CS1 · Q52NAT2 marksIntermediate Code Generation
Refer to the given 3-address code sequence, split into basic blocks. The number of basic blocks is ______.
1001: i = 1 1002: j = 1 1003: t1 = 10*i 1004: t2 = t1+j 1005: t3 = 8*t2 1006: t4 = t3-88 1007: a[t4] = 0.0 1008: j = j+1 1009: if j <= 10 goto 1003 1010: i = i+1 1011: if i <= 10 goto 1002 1012: i = 1 1013: t5 = i-1 1014: t6 = 88*t5 1015: a[t6] = 1.0 1016: i = i+1 1017: if i <= 10 goto 1013
GATE 2024 CS2 · Q21MCQ1 markPhases of a Compiler
Consider the following two sets: Set X: P. Lexical Analyzer, Q. Syntax Analyzer, R. Intermediate Code Generator, S. Code Optimizer. Set Y:
1. Abstract Syntax Tree,
2. Token,
3. Parse Tree,
4. Constant Folding. Which one of the following options is the CORRECT match from Set X to Set Y?
1. Abstract Syntax Tree,
2. Token,
3. Parse Tree,
4. Constant Folding. Which one of the following options is the CORRECT match from Set X to Set Y?
GATE 2024 CS1 · Q26MSQ1 markBottom-up Parsing (LR family)
Which of the following is/are Bottom-Up Parser(s)?
One or more options may be correct. Select all that apply, then submit.
GATE 2024 CS2 · Q29MSQ1 markSyntax-Directed Translation
Which of the following statements is/are FALSE?
One or more options may be correct. Select all that apply, then submit.
GATE 2024 CS1 · Q33NAT1 markGrammars, Derivations & FIRST/FOLLOW
Consider the operator precedence and associativity rules for the integer arithmetic operators given below. +: highest precedence, left associative; −: high, right associative; ∗: medium, right associative; /: low, right associative. The value of the expression 3 + 1 + 5 ∗ 2 / 7 + 2 − 4 − 7 − 6 / 2 as per the above rules is ______.
GATE 2024 CS1 · Q37MCQ2 marksSyntax-Directed Translation
Consider the syntax-directed definition:
S → D H T U {S.val = D.val + H.val + T.val + U.val}
D → "M" D₁ {D.val = 5 + D₁.val}
D → ε {D.val = −5}
H → "L" H₁ {H.val = 5*10 + H₁.val}
H → ε {H.val = −10}
T → "C" T₁ {T.val = 5*100 + T₁.val}
T → ε {T.val = −5}
U → "K" {U.val = 5} Given "MMLK" as input, the value computed by the SDD in S.val isGATE 2024 CS1 · Q38MCQ2 marksTop-down Parsing (LL(1))
Consider the following grammar G with S as the start symbol, with three incomplete productions (1), (2), (3):
S → d a T | (1) T → a S | b T | (2) R → (3) | εThe set of terminals is {a, b, c, d, f}. FIRST(S) = {c, d, f}, FIRST(T) = {a, b, ε}, FIRST(R) = {c, ε}. FOLLOW(S) = FOLLOW(T) = {c, f, $}, FOLLOW(R) = {f}. Which option CORRECTLY fills in the incomplete productions?
GATE 2024 CS1 · Q39MCQ2 marksIntermediate Code Generation
Consider the following pseudo-code. L1: t1 = −1; L2: t2 = 0; L3: t3 = 0; L4: t4 = 4 ∗ t3; L5: t5 = 4 ∗ t2; L6: t6 = t5 ∗ M; L7: t7 = t4 + t6; L8: t8 = a[t7]; L9: if t8 <= max goto L11; L10: t1 = t8; L11: t3 = t3 + 1; L12: if t3 < M goto L4; L13: t2 = t2 + 1; L14: if t2 < N goto L3; L15: max = t1. Which option CORRECTLY specifies the number of basic blocks and the number of instructions in the largest basic block, respectively?
GATE 2024 CS2 · Q40MCQ2 marksTop-down Parsing (LL(1))
Consider the context-free grammar with start symbol S and terminals {a, b, c, d}:
S → A a A b | B b B a A → c S | ε B → d S | εA partially filled LL(1) parsing table has: M[S,a] = S → AaAb, M[S,b] = S → BbBa, cell (1) = M[S,c], cell (2) = M[S,d]; M[A,a] = A → ε, cell (3) = M[A,b], M[A,c] = A → cS; cell (4) = M[B,a], M[B,b] = B → ε, M[B,d] = B → dS. Which option represents the CORRECT combination for the numbered cells?
GATE 2024 CS2 · Q43MCQ2 marksIntermediate Code Generation
Consider the expression x[i] = (p + r) * −s[i] + u / w. The list of triples representing it has missing entries (1), (3) and (6): (0) + p r; (1) ?; (2) uminus (1); (3) ?; (4) / u w; (5) + (3) (4); (6) ?; (7) = (6) (5). Which option fills in the missing entries CORRECTLY? (A) (1) =[] s i, (3) * (0) (2), (6) []= x i. (B) (1) []= s i, (3) − (0) (2), (6) =[] x (5). (C) (1) =[] s i, (3) * (0) (2), (6) []= x (5). (D) (1) []= s i, (3) − (0) (2), (6) =[] x i.
GATE 2024 CS2 · Q65NAT2 marksBottom-up Parsing (LR family)
Consider the following augmented grammar, to be parsed with an SLR parser. Terminals: {a, b, c, d, #, @}
S′ → S S → S S | A a | b A c | B c | b B a A → d # B → @Let I0 = CLOSURE({S′ → • S}). The number of items in the set GOTO(I0, S) is ______.
GATE 2023 · Q19MCQ1 markLexical Analysis
Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions: letter → [A-Za-z]; digit → [0-9]; id → letter (letter | digit)*. Which one of the following Non-deterministic Finite-state Automata with ε-transitions accepts the set of valid identifiers? (A double circle denotes a final state.)
(A) start → letter → final state with a self-loop labelled letter/digit, plus an ε-edge from the first state straight to the final state. (B) start → letter → final state, with ε-edges to two further final states, one looping on letter and one looping on digit. (C) start → letter → final state; from the final state ε to a "letter" branch and ε to a "digit" branch, both ε-joined into a state that has an ε-edge back to the final state. (D) start → letter → final state; then letter → digit leading to a state with an ε-edge back to the final state.
(A) start → letter → final state with a self-loop labelled letter/digit, plus an ε-edge from the first state straight to the final state. (B) start → letter → final state, with ε-edges to two further final states, one looping on letter and one looping on digit. (C) start → letter → final state; from the final state ε to a "letter" branch and ε to a "digit" branch, both ε-joined into a state that has an ε-edge back to the final state. (D) start → letter → final state; then letter → digit leading to a state with an ε-edge back to the final state.
GATE 2023 · Q36MCQ2 marksRuntime Environments
Consider the program:
(A) main → f1, f2, f3; the f2 node has children f3, f2; the inner f2 has children f3, f1. (B) main → f1, f2, f3; f2 has children f3, f1. (C) a chain main → f1 → f2, with f2 having children f3, f1. (D) main → f1, f2, f3; f2 has three children f3, f2, f1.
int main() {
f1();
f2(2);
f3();
return(0);
}
int f1() {
return(1);
}
int f2(int X) {
f3();
if (X==1) return f1();
else return (X*f2(X-1));
}
int f3() {
return(5);
} Which one of the following represents the activation tree corresponding to the main function? (A) main → f1, f2, f3; the f2 node has children f3, f2; the inner f2 has children f3, f1. (B) main → f1, f2, f3; f2 has children f3, f1. (C) a chain main → f1 → f2, with f2 having children f3, f1. (D) main → f1, f2, f3; f2 has three children f3, f2, f1.
GATE 2023 · Q37MCQ2 marksCode Optimisation & Data-Flow
Consider the control flow graph:
ENTRY → B1 (i = m − 1; j = n; a = 10) → B2 (i = i + 1; j = j − 1) → B3 (a = 20) and B2 → B4 (i = a + 1) B3 → B4 B4 → B2 (back edge) and B4 → EXITWhich one of the following lists correctly the set of live variables at the exit point of each basic block?
GATE 2023 · Q60NAT2 marksSyntax-Directed Translation
Consider the syntax directed translation:
N → I # F {N.val = I.val + F.val}
I → I₁ B {I.val = 2·I₁.val + B.val}
I → B {I.val = B.val}
F → B F₁ {F.val = ½(B.val + F₁.val)}
F → B {F.val = ½·B.val}
B → 0 {B.val = 0}
B → 1 {B.val = 1} N is the start symbol, and #, 0, 1 are tokens. The value computed by the translation scheme for the input string 10#011 is ______ (rounded off to three decimal places).GATE 2022 · Q13MCQ1 markBottom-up Parsing (LR family)
Which one of the following statements is TRUE?
GATE 2022 · Q29NAT1 markBottom-up Parsing (LR family)
Consider the augmented grammar with {+, *, (, ), id} as the set of terminals:
S′ → S S → S + R | R R → R * P | P P → ( S ) | idIf I0 is the set of two LR(0) items {[S′ → S•], [S → S• + R]}, then goto(closure(I0), +) contains exactly ______ items.
GATE 2022 · Q65NAT2 marksSyntax-Directed Translation
Consider the grammar with translation rules:
S → S₁ # T {S.val = S₁.val * T.val}
S → T {S.val = T.val}
T → T₁ % R {T.val = T₁.val ÷ R.val}
T → R {T.val = R.val}
R → id {R.val = id.val} Here # and % are operators and id is a token representing an integer. The computed value of S.val for the root of the parse tree for the expression 20#10%5#8%2%2 is ______.GATE 2021 Set 1 · Q4MCQ1 markRuntime Environments
Consider the following statements. S1: The sequence of procedure calls corresponds to a preorder traversal of the activation tree. S2: The sequence of procedure returns corresponds to a postorder traversal of the activation tree. Which one of the following options is correct?
GATE 2021 Set 1 · Q5MCQ1 markBottom-up Parsing (LR family)
Consider the following statements. S1: Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1). S2: For any context-free grammar, there is a parser that takes at most O(n³) time to parse a string of length n. Which one of the following options is correct?
GATE 2021 Set 1 · Q26MCQ2 marksSyntax-Directed Translation
Consider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax directed translation (SDT) actions, given as pseudo-code:
P → D* E*
D → int ID {record that ID.lexeme is of type int}
D → bool ID {record that ID.lexeme is of type bool}
E → E₁ + E₂ {check that E₁.type = E₂.type = int; set E.type := int}
E → !E₁ {check that E₁.type = bool; set E.type := bool}
E → ID {set E.type := int} With respect to the above grammar, which one of the following choices is correct?GATE 2021 Set 1 · Q31MCQ2 marksTop-down Parsing (LL(1))
Consider the following context-free grammar where the set of terminals is {a, b, c, d, f}:
S → d a T | R f T → a S | b a T | ε R → c a T R | εThe following is a partially-filled LL(1) parsing table (columns a, b, c, d, f, $): M[S,d] = S → daT; M[T,a] = T → aS; M[T,b] = T → baT; M[T,f] = T → ε; M[R,c] = R → caTR; M[R,f] = R → ε; cell ① = M[S,c], cell ② = M[S,f], cell ③ = M[T,c], cell ④ = M[T,$]. Which one of the following choices represents the correct combination for the numbered cells (blank denotes that the cell is empty)?
GATE 2021 Set 1 · Q50NAT2 marksIntermediate Code Generation
Consider the following C code segment:
a = b + c; e = a + 1; d = b + c; f = d + 1; g = e + f;In a compiler, this code segment is represented internally as a directed acyclic graph (DAG). The number of nodes in the DAG is ______.
GATE 2020 · Q9MCQ1 markPhases of a Compiler
Consider the following statements. I. Symbol table is accessed only during lexical analysis and syntax analysis. II. Compilers for programming languages that support recursion necessarily need heap storage for memory allocation in the run-time environment. III. Errors violating the condition "any variable must be declared before its use" are detected during syntax analysis. Which of the above statements is/are TRUE?
GATE 2020 · Q24NAT1 markBottom-up Parsing (LR family)
Consider the following grammar:
S → aSB | d B → bThe number of reduction steps taken by a bottom-up parser while accepting the string aaadbbb is ______.
GATE 2020 · Q33MCQ2 marksSyntax-Directed Translation
Consider the productions A → PQ and A → XY. Each of the five non-terminals A, P, Q, X and Y has two attributes: s is a synthesized attribute, and i is an inherited attribute. Consider the following rules. Rule 1: P.i = A.i + 2, Q.i = P.i + A.i, and A.s = P.s + Q.s. Rule 2: X.i = A.i + Y.s and Y.i = X.s + A.i. Which one of the following is TRUE?
GATE 2019 Set 2 · Q3MCQ1 markBottom-up Parsing (LR family)
Which one of the following kinds of derivation is used by LR parsers?
GATE 2019 Set 2 · Q19NAT1 markGrammars, Derivations & FIRST/FOLLOW
Consider the grammar:
S → Aa A → BD B → b | ε D → d | εLet a, b, d and $ be indexed as follows: a = 3, b = 2, d = 1, $ = 0. Compute the FOLLOW set of the non-terminal B and write the index values for the symbols in the FOLLOW set in the descending order. (For example, if the FOLLOW set is {a, b, d, $}, the answer should be 3210.) Answer: ______.
GATE 2019 Set 2 · Q36MCQ2 marksSyntax-Directed Translation
Consider the following grammar and semantic actions to support inherited type declaration attributes. Let X1, X2, X3, X4, X5 and X6 be the placeholders for the non-terminals D, T, L or L1 in the following table. D → T L: X1.type = X2.type. T → int: T.type = int. T → float: T.type = float. L → L1 , id: X3.type = X4.type; addType(id.entry, X5.type). L → id: addType(id.entry, X6.type). Which one of the following are the appropriate choices for X1, X2, X3 and X4?
GATE 2019 Set 2 · Q43NAT2 marksBottom-up Parsing (LR family)
Consider the augmented grammar:
S′ → S S → ⟨L⟩ | id L → L, S | SLet I0 = CLOSURE({[S′ → •S]}). The number of items in the set GOTO(I0, ⟨) is ______.
GATE 2018 · Q8MCQ1 markPhases of a Compiler
Which one of the following statements is FALSE?
GATE 2018 · Q37MCQ2 marksLexical Analysis
A lexical analyzer uses the following patterns to recognize three tokens T1, T2 and T3 over the alphabet {a, b, c}. T1: a? (b|c)* a T2: b? (a|c)* b T3: c? (b|a)* c. Note that "x?" means 0 or 1 occurrence of the symbol x. The analyzer outputs the token that matches the longest possible prefix. If the string bbaacabc is processed by the analyzer, which one of the following is the sequence of tokens it outputs?
GATE 2018 · Q38MCQ2 marksGrammars, Derivations & FIRST/FOLLOW
Consider the following parse tree for the expression a#b$c$d#e#f, involving two binary operators $ and #. (Tree: the root is #, with left child a and right child #. That # has left child $ and right child #(e, f). That $ has left child $(b, c) and right child d.) Which one of the following is correct for the given parse tree?
GATE 2017 Set 1 · Q10MCQ1 markGrammars, Derivations & FIRST/FOLLOW
Consider the following context-free grammar over the alphabet Σ = {a, b, c} with S as the start symbol:
S → abScT | abcT T → bT | bWhich one of the following represents the language generated by the above grammar?
GATE 2017 Set 1 · Q17MCQ1 markGrammars, Derivations & FIRST/FOLLOW
Consider the following grammar:
P → x Q R S Q → y z | z R → w | ε S → yWhat is FOLLOW(Q)?
GATE 2017 Set 1 · Q52NAT2 marksCode Generation & Register Allocation
Consider the expression (a − 1) * (((b + c) / 3) + d). Let X be the minimum number of registers required by an optimal code generation (without any register spill) algorithm for a load/store architecture, in which (i) only load and store instructions can have memory operands and (ii) arithmetic instructions can have only register or immediate operands. The value of X is ______.
GATE 2016 Set 1 · Q45NAT2 marksGrammars, Derivations & FIRST/FOLLOW
The attributes of three arithmetic operators in some programming language are given below. + : precedence High, associativity Left, arity Binary. − : precedence Medium, associativity Right, arity Binary. * : precedence Low, associativity Left, arity Binary. The value of the expression 2 − 5 + 1 − 7 * 3 in this language is ______.
GATE 2016 Set 1 · Q46MCQ2 marksSyntax-Directed Translation
Consider the following Syntax Directed Translation Scheme (SDTS), with non-terminals {S, A} and terminals {a, b}:
S → aA {print 1}
S → a {print 2}
A → Sb {print 3} Using the above SDTS, the output printed by a bottom-up parser, for the input aab is:GATE 2014 Set 1 · Q17MCQ1 markCode Optimisation & Data-Flow
Which one of the following is FALSE?
GATE 2014 Set 1 · Q34MCQ2 marksBottom-up Parsing (LR family)
A canonical set of items is given below: S → L . > R and Q → R . . On input symbol < the set has
GATE 2013 Code A · Q9MCQ1 markBottom-up Parsing (LR family)
What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production (i.e., of type A → ε and A → a) to parse a string with n tokens?
GATE 2013 Code A · Q40MCQ2 marksBottom-up Parsing (LR family)
Consider the following two sets of LR(1) items of an LR(1) grammar. Set 1:
1. Cannot be merged since look aheads are different.
2. Can be merged but will result in S-R conflict.
3. Can be merged but will result in R-R conflict.
4. Cannot be merged since goto on c will lead to two different sets.
X → c.X, c/d X → .cX, c/d X → .d, c/dSet 2:
X → c.X, $ X → .cX, $ X → .d, $Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE?
1. Cannot be merged since look aheads are different.
2. Can be merged but will result in S-R conflict.
3. Can be merged but will result in R-R conflict.
4. Cannot be merged since goto on c will lead to two different sets.
GATE 2013 Code A · Q48MCQ2 marksCode Generation & Register Allocation
(Same code segment as the previous question.) Suppose the instruction set architecture of the processor has only two registers. The only allowed compiler optimization is code motion, which moves statements from one place to another while preserving correctness. What is the minimum number of spills to memory in the compiled code?
GATE 2013 Code A · Q49MCQ2 marksCode Generation & Register Allocation
The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have at most two source operands and one destination operand. Assume that all variables are dead after this code segment.
c = a + b;
d = c * a;
e = c + a;
x = c * c;
if (x > a) {
y = a * a;
} else {
d = d * d;
e = e * e;
} What is the minimum number of registers needed in the instruction set architecture of the processor to compile this code segment without any spill to memory? Do not apply any optimization other than optimizing register allocation.GATE 2012 Code A · Q52MCQ2 marksGrammars, Derivations & FIRST/FOLLOW
For the grammar below, a partial LL(1) parsing table is also presented (entries E1, E2, E3 are to be filled). ε is the empty string, $ indicates end of input
S → a A b B | b A a B | ε A → S B → STable: M[S,$] = S → ε; M[A,a] = A → S; M[A,b] = A → S; M[A,$] = error; M[B,a] = B → S; M[B,b] = B → S; E1 = M[S,a]; E2 = M[S,b]; E3 = M[B,$]. The FIRST and FOLLOW sets for the non-terminals A and B are
GATE 2012 Code A · Q53MCQ2 marksTop-down Parsing (LL(1))
(Same grammar and partial LL(1) table as the previous question.) The appropriate entries for E1, E2 and E3 are