GATE CS Compiler Design Previous Year Questions

GATE CS 2025 Set 1 | Question 12

MCQ · 1 mark · −0.33

Which ONE of the following statements is FALSE regarding the symbol table?

Symbol table is responsible for keeping track of the scope of variables. Symbol table can be implemented using a binary search tree. Symbol table is not required after the parsing phase. Symbol table is created during the lexical analysis phase.

Explanation

Answer: (C)

The symbol table is used by nearly every phase of the compiler, not only up to parsing. Semantic analysis uses it for type and scope checks, and intermediate code generation and code generation read the type, size and memory offset of each name from it, so statement (C) is false. The other statements are true: the table records the scope of names (A), it can be organised as a list, a binary search tree or a hash table (B), and entries for identifiers are first made while the lexical analyser scans the source (D).

Answer: C

GATE CS 2025 Set 1 | Question 13

MCQ · 1 mark · −0.33

Which ONE of the following techniques used in compiler code optimization uses live variable analysis?

Run-time function call management Register assignment to variables Strength reduction Constant folding

Explanation

Answer: (B)

A variable is live at a point if its current value may still be read later, before it is overwritten; live variable analysis works this out for every point of the program. Register allocation needs exactly this: a register can be handed to another variable once its variable is dead, and two variables that are live at the same time cannot share a register. Strength reduction (cheaper operations on loop induction variables), constant folding (evaluating constant expressions at compile time) and run-time call management (activation records and calling sequences) do not depend on liveness.

Answer: B

GATE CS 2025 Set 1 | Question 46

MSQ · 2 marks

Which of the following statement(s) is/are TRUE while computing First and Follow during top down parsing by a compiler?

For a production $A \to \epsilon$, $\epsilon$ will be added to $First(A)$. If there is any input right end marker, it will be added to $First(S)$, where $S$ is the start symbol. For a production $A \to \epsilon$, $\epsilon$ will be added to $Follow(A)$. If there is any input right end marker, it will be added to $Follow(S)$, where $S$ is the start symbol.

Explanation

Answer: (A), (D)

(A) True: $\epsilon \in First(A)$ whenever $A$ can derive the empty string, and $A \to \epsilon$ does so directly.
(B) False: $First$ sets contain the terminals (and possibly $\epsilon$) that can begin a string derived from a symbol; the end marker $\$$ never goes into a $First$ set.
(C) False: $Follow(A)$ contains the terminals (and $\$$) that can appear just after $A$ in a sentential form; $\epsilon$ is never added to a $Follow$ set.
(D) True: the first rule for $Follow$ sets puts the right end marker $\$$ into $Follow(S)$, because the input ends right after a string derived from $S$.

Answer: A, D

GATE CS 2025 Set 1 | Question 52

NAT · 2 marks

Refer to the given 3-address code sequence. This code sequence is split into basic blocks. The number of basic blocks is ________. (Answer in integer)

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

Your answer

Explanation

Answer: 6

A new basic block starts at every leader: the first instruction, every jump target, and every instruction right after a jump.

First instruction: 1001.
Jump targets: 1003, 1002 and 1013.
Instructions after a jump: 1010 (after 1009) and 1012 (after 1011); 1017 is the last line.

The six leaders 1001, 1002, 1003, 1010, 1012 and 1013 give the blocks 1001 | 1002 | 1003–1009 | 1010–1011 | 1012 | 1013–1017.

Answer: 6

GATE CS 2025 Set 2 | Question 21

MCQ · 1 mark · −0.33

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 expression 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?

Only (I) is correct. Only (II) is correct. Both (I) and (II) are correct. Neither (I) nor (II) is correct.

Explanation

Answer: (C)

In one-pass code generation, a jump is often emitted before the address it should jump to is known. Backpatching handles this: the jump is emitted with an empty target, its position is added to a list, and every jump on the list is filled in once the target becomes known.

(I) is correct. For Boolean expressions with short-circuit evaluation, the jumps taken when the expression is true or false are collected in truelist and falselist and patched later.
(II) is correct. If, if-else and while statements patch their jumps the same way, using these lists and a nextlist, without a second pass.

Answer: C

GATE CS 2025 Set 2 | Question 22

MCQ · 1 mark · −0.33

Given the following syntax directed translation rules:

Rule 1: $R \rightarrow AB\ \{B.i = R.i - 1;\ A.i = B.i;\ R.i = A.i + 1;\ \}$
Rule 2: $P \rightarrow CD\ \{P.i = C.i + D.i;\ D.i = C.i + 2;\ \}$
Rule 3: $Q \rightarrow EF\ \{Q.i = E.i + F.i;\ \}$

Which ONE is the CORRECT option among the following?

Rule 1 is S-attributed and L-attributed; Rule 2 is S-attributed and not L-attributed; Rule 3 is neither S-attributed nor L-attributed Rule 1 is neither S-attributed nor L-attributed; Rule 2 is S-attributed and L-attributed; Rule 3 is S-attributed and L-attributed Rule 1 is neither S-attributed nor L-attributed; Rule 2 is not S-attributed and is L-attributed; Rule 3 is S-attributed and L-attributed Rule 1 is S-attributed and not L-attributed; Rule 2 is not S-attributed and is L-attributed; Rule 3 is S-attributed and L-attributed

Explanation

Answer: (C)

A definition is S-attributed if it uses only synthesized attributes. It is L-attributed if each inherited attribute of a body symbol depends only on inherited attributes of the head and on attributes of symbols to its left. Every S-attributed definition is also L-attributed.

Rule 1: $A.i$ and $B.i$ are inherited, so it is not S-attributed. $A.i = B.i$ takes its value from $B$, which lies to the right of $A$, so it is not L-attributed either. The rules are even circular: $R.i$ needs $A.i$, which needs $B.i$, which needs $R.i$.
Rule 2: $D.i = C.i + 2$ is inherited, so it is not S-attributed, but it uses only the left sibling $C$, so it is L-attributed.
Rule 3: only the synthesized $Q.i$ is computed, so it is S-attributed and therefore L-attributed.

Answer: C

GATE CS 2025 Set 2 | Question 40

MCQ · 2 marks · −0.66

Given a Context-Free Grammar $G$ as follows:

$S \to Aa \mid bAc \mid dc \mid bda$

$A \to d$

Which ONE of the following statements is TRUE?

$G$ is neither LALR(1) nor SLR(1) $G$ is CLR(1), not LALR(1) $G$ is LALR(1), not SLR(1) $G$ is LALR(1), also SLR(1)

Explanation

Answer: (C)

$\text{FOLLOW}(A) = \{a, c\}$, since $A$ is followed by $a$ in $S \to Aa$ and by $c$ in $S \to bAc$.

Not SLR(1). From the start state, reading $d$ gives the items $S \to d \cdot c$ and $A \to d \cdot$. SLR reduces by $A \to d$ on every symbol of $\text{FOLLOW}(A)$, including $c$, where the first item shifts: a shift-reduce conflict. The state after $bd$ clashes the same way on $a$.
LALR(1). With LR(1) lookaheads, $A \to d \cdot$ has lookahead $a$ only in the first state and $c$ only in the second, so neither conflicts. No two LR(1) states share a core, so the LALR(1) table equals the conflict-free CLR(1) table.

So $G$ is LALR(1) (and CLR(1)) but not SLR(1).

Answer: C

GATE CS 2025 Set 2 | Question 51

MSQ · 2 marks

Consider two grammars $G_1$ and $G_2$ with the production rules given below:

$G_1\colon S \rightarrow \mathit{if}\ E\ \mathit{then}\ S \mid \mathit{if}\ E\ \mathit{then}\ S\ \mathit{else}\ S \mid a$
$\phantom{G_1\colon} E \rightarrow b$

$G_2\colon S \rightarrow \mathit{if}\ E\ \mathit{then}\ S \mid M$
$\phantom{G_2\colon} M \rightarrow \mathit{if}\ E\ \mathit{then}\ M\ \mathit{else}\ S \mid c$
$\phantom{G_2\colon} E \rightarrow b$

where $\mathit{if}, \mathit{then}, \mathit{else}, a, b, c$ are the terminals.

Which of the following option(s) is/are CORRECT?

$G_1$ is not $LL(1)$ and $G_2$ is $LL(1)$. $G_1$ is $LL(1)$ and $G_2$ is not $LL(1)$. $G_1$ and $G_2$ are not $LL(1)$. $G_1$ and $G_2$ are ambiguous.

Explanation

Answer: (C), (D)

LL(1): in $G_1$ two $S$-productions begin with $\mathit{if}$. In $G_2$, $\mathrm{FIRST}(M) = \{\mathit{if}, c\}$ also contains $\mathit{if}$, so on seeing $\mathit{if}$ the parser cannot choose between $S \rightarrow \mathit{if}\ E\ \mathit{then}\ S$ and $S \rightarrow M$. Neither grammar is LL(1), so (C) holds and (A), (B) fail.

Ambiguity: $G_1$ is the dangling-else grammar; $\mathit{if}\ b\ \mathit{then}\ \mathit{if}\ b\ \mathit{then}\ a\ \mathit{else}\ a$ has two parse trees. $G_2$ tries to force each $\mathit{else}$ onto the nearest $\mathit{if}$, but the $\mathit{else}$ part of $M$ is an $S$, which may end in an unmatched $\mathit{if}$. In $\mathit{if}\ b\ \mathit{then}\ \mathit{if}\ b\ \mathit{then}\ c\ \mathit{else}\ \mathit{if}\ b\ \mathit{then}\ c\ \mathit{else}\ c$, the last $\mathit{else}$ can pair with the first or the third $\mathit{if}$, giving two parse trees. So (D) holds.

Answer: C, D

GATE CS 2024 Set 1 | Question 26

MSQ · 1 mark

Which of the following is/are Bottom-Up Parser(s)?

Shift-reduce Parser Predictive Parser LL(1) Parser LR Parser

Explanation

Answer: (A), (D)

A bottom-up parser starts from the input tokens and repeatedly replaces a substring that matches the right side of a production by its left side, until only the start symbol remains. It traces a rightmost derivation in reverse.

A shift-reduce parser is exactly this method: it shifts tokens onto a stack and reduces the handle on top of it.
LR parsers (SLR, LALR and canonical LR) are table-driven shift-reduce parsers, so they are bottom-up as well.
Predictive and LL(1) parsers start from the start symbol and expand nonterminals to match the input, following a leftmost derivation. They are top-down, so B and C are wrong.

Answer: A, D

GATE CS 2024 Set 1 | Question 33

NAT · 1 mark

Consider the operator precedence and associativity rules for the integer arithmetic operators given in the table below.

Operator	Precedence	Associativity
$+$	Highest	Left
$-$	High	Right
$*$	Medium	Right
$/$	Low	Right

The value of the expression $3 + 1 + 5 * 2 \mathbin{/} 7 + 2 - 4 - 7 - 6 \mathbin{/} 2$ as per the above rules is __________

Your answer

Explanation

Answer: 6

The operator with the lowest precedence is applied last, so the expression splits first at $/$. As $/$ is right-associative, it reads $A \mathbin{/} (B \mathbin{/} C)$ with $A = 3 + 1 + 5 * 2$, $B = 7 + 2 - 4 - 7 - 6$ and $C = 2$.

In $A$, $+$ binds tighter than $*$: $A = (3 + 1 + 5) * 2 = 18$.
In $B$, $+$ binds first, giving $9 - 4 - 7 - 6$; right-associative $-$ groups this as $9 - (4 - (7 - 6)) = 9 - 3 = 6$.
The value is $18 \mathbin{/} (6 \mathbin{/} 2) = 18 \mathbin{/} 3 = 6$, and every division is exact.

The usual C rules would give $-7$ instead.

Answer: 6

Topics