GATE CS Compiler Design Previous Year Questions

GATE CS 2024 Set 1 | Question 37

MCQ · 2 marks · −0.66

Consider the following syntax-directed definition (SDD).

${S \to DHTU}$	$\{\ S.\mathit{val} = D.\mathit{val} + H.\mathit{val} + T.\mathit{val} + U.\mathit{val};\ \}$
${D \to \text{``M''}D_{1}}$	$\{\ D.\mathit{val} = 5 + D_{1}.\mathit{val};\ \}$
${D \to \epsilon}$	$\{\ D.\mathit{val} = -5;\ \}$
${H \to \text{``L''}H_{1}}$	$\{\ H.\mathit{val} = 5 * 10 + H_{1}.\mathit{val};\ \}$
${H \to \epsilon}$	$\{\ H.\mathit{val} = -10;\ \}$
${T \to \text{``C''}T_{1}}$	$\{\ T.\mathit{val} = 5 * 100 + T_{1}.\mathit{val};\ \}$
${T \to \epsilon}$	$\{\ T.\mathit{val} = -5;\ \}$
${U \to \text{``K''}}$	$\{\ U.\mathit{val} = 5;\ \}$

Given "MMLK" as the input, which one of the following options is the CORRECT value computed by the SDD (in the attribute $S.\mathit{val}$)?

45 50 55 65

Explanation

Answer: (A)

For "MMLK", the rule $S \to DHTU$ uses $D$ for "MM", $H$ for "L", $T$ for the empty string and $U$ for "K". Evaluating the attributes bottom-up:

$D$: the innermost $D \to \epsilon$ gives $-5$, then $5 + (-5) = 0$, then $5 + 0 = 5$.
$H$: $H \to \epsilon$ gives $-10$, then $5 * 10 + (-10) = 40$.
$T \to \epsilon$ gives $-5$, and $U$ gives 5.

So $S.\mathit{val} = 5 + 40 + (-5) + 5 = 45$. Ignoring the negative values of some of the $\epsilon$-productions leads to the other options, 50, 55 or 65.

Answer: A

GATE CS 2024 Set 1 | Question 38

MCQ · 2 marks · −0.66

Consider the following grammar $G$, with $S$ as the start symbol. The grammar $G$ has three incomplete productions denoted by (1), (2), and (3).

$S \to daT \mid \underline{\quad (1) \quad}$
$T \to aS \mid bT \mid \underline{\quad (2) \quad}$
$R \to \underline{\quad (3) \quad} \mid \epsilon$

The set of terminals is $\{a, b, c, d, f\}$. The FIRST and FOLLOW sets of the different non-terminals are as follows.

FIRST($S$) = $\{c, d, f\}$, FIRST($T$) = $\{a, b, \epsilon\}$, FIRST($R$) = $\{c, \epsilon\}$

FOLLOW($S$) = FOLLOW($T$) = $\{c, f, \$\}$, FOLLOW($R$) = $\{f\}$

Which one of the following options CORRECTLY fills in the incomplete productions?

(1) $S \to Rf$ (2) $T \to \epsilon$ (3) $R \to cTR$ (1) $S \to fR$ (2) $T \to \epsilon$ (3) $R \to cTR$ (1) $S \to fR$ (2) $T \to cT$ (3) $R \to cR$ (1) $S \to Rf$ (2) $T \to cT$ (3) $R \to cR$

Explanation

Answer: (A)

(2): FIRST($T$) contains $\epsilon$ but not $c$, so the missing rule is $T \to \epsilon$. $T \to cT$ (options C, D) would put $c$ into FIRST($T$) and leave $\epsilon$ out.
(1): $c \in$ FIRST($S$) can only come through $R$. With $S \to Rf$ and $R$ nullable, FIRST($Rf$) = $\{c, f\}$, so FIRST($S$) = $\{c, d, f\}$. $S \to fR$ would miss $c$ and would also put $\$$ into FOLLOW($R$).
(3): $R \to cTR$ gives FIRST($R$) = $\{c, \epsilon\}$. In it $T$ is followed by $R$, so FOLLOW($T$) gets $c$ and, because $R$ can vanish, also FOLLOW($R$) = $\{f\}$, which comes from $S \to Rf$. With $S \to daT$ and $T \to aS$, FOLLOW($S$) = FOLLOW($T$) = $\{c, f, \$\}$, exactly the given sets.

Answer: A

GATE CS 2024 Set 1 | Question 39

MCQ · 2 marks · −0.66

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 one of the following options CORRECTLY specifies the number of basic blocks and the number of instructions in the largest basic block, respectively ?

6 and 6 6 and 7 7 and 7 7 and 6

Explanation

Answer: (D)

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

L1 is the first instruction.
L11, L4 and L3 are the targets of the jumps in L9, L12 and L14.
L10, L13 and L15 each follow a conditional jump.

These 7 leaders give 7 blocks: L1–L2, L3, L4–L9, L10, L11–L12, L13–L14 and L15. The largest is L4–L9, with 6 instructions; it ends at the jump in L9. Missing L3 or L4 as a leader merges two blocks, which leads to the 6-block options A and B.

Answer: D

GATE CS 2024 Set 2 | Question 21

MCQ · 1 mark · −0.33

Consider the following two sets:

Set X	Set Y
P. Lexical Analyzer	1. Abstract Syntax Tree
Q. Syntax Analyzer	2. Token
R. Intermediate Code Generator	3. Parse Tree
S. Code Optimizer	4. Constant Folding

Which one of the following options is the CORRECT match from Set X to Set Y ?

P – 4; Q – 1; R – 3; S – 2 P – 2; Q – 3; R – 1; S – 4 P – 2; Q – 1; R – 3; S – 4 P – 4; Q – 3; R – 2; S – 1

Explanation

Answer: (B)

Match each phase with what it produces or does:

P → 2. The lexical analyzer groups the input characters into lexemes and passes them on as tokens.
Q → 3. The syntax analyzer checks the token stream against the grammar; the derivation it finds is a parse tree.
R → 1. An abstract syntax tree, a compact tree of operators and operands without the parse tree's extra grammar nodes, is a common intermediate representation.
S → 4. Constant folding, such as replacing 2 * 3 by 6 at compile time, is a code optimization.

This gives P – 2; Q – 3; R – 1; S – 4. Option C swaps the two trees, and A and D misplace tokens and constant folding.

Answer: B

GATE CS 2024 Set 2 | Question 29

MSQ · 1 mark

Which of the following statements is/are FALSE?

An attribute grammar is a syntax-directed definition (SDD) in which the functions in the semantic rules have no side effects The attributes in a L-attributed definition cannot always be evaluated in a depth-first order Synthesized attributes can be evaluated by a bottom-up parser as the input is parsed All L-attributed definitions based on LR(1) grammar can be evaluated using a bottom-up parsing strategy

Explanation

Answer: (B), (D)

The question asks for the false statements.

A is true. That is the usual definition: the semantic rules of an attribute grammar just compute attribute values, without printing, updating tables or other side effects.
B is false. In an L-attributed definition an inherited attribute depends only on the parent and on siblings to its left, so a single left-to-right depth-first traversal always works, computing inherited attributes on the way down and synthesized ones on the way up.
C is true. An LR parser computes a synthesized attribute when it reduces by a production, keeping the values on its stack.
D is false. Inserting marker nonterminals to compute inherited attributes is guaranteed to work for LL grammars, but in an LR(1) grammar the markers can create parsing conflicts, so not every such definition can be evaluated bottom-up.

Answer: B, D

GATE CS 2024 Set 2 | Question 40

MCQ · 2 marks · −0.66

Consider the following context-free grammar where the start symbol is $S$ and the set of terminals is $\{a,b,c,d\}$.

$S \to AaAb \mid BbBa$
$A \to cS \mid \epsilon$
$B \to dS \mid \epsilon$

The following is a partially-filled LL(1) parsing table.

	$a$	$b$	$c$	$d$
$S$	$S \to AaAb$	$S \to BbBa$	(1)	(2)
$A$	$A \to \epsilon$	(3)	$A \to cS$
$B$	(4)	$B \to \epsilon$		$B \to dS$

Which one of the following options represents the CORRECT combination for the numbered cells in the parsing table?

Note: In the options, “blank” denotes that the corresponding cell is empty.

(1) $S \to AaAb$ (2) $S \to BbBa$ (3) $A \to \epsilon$ (4) $B \to \epsilon$ (1) $S \to BbBa$ (2) $S \to AaAb$ (3) $A \to \epsilon$ (4) $B \to \epsilon$ (1) $S \to AaAb$ (2) $S \to BbBa$ (3) blank (4) blank (1) $S \to BbBa$ (2) $S \to AaAb$ (3) blank (4) blank

Explanation

Answer: (A)

Fill each cell from FIRST and FOLLOW sets.

$\text{FIRST}(A) = \{c, \epsilon\}$, so $\text{FIRST}(AaAb) = \{c, a\}$: $S \to AaAb$ goes under $a$ and under $c$, which is cell (1).
$\text{FIRST}(B) = \{d, \epsilon\}$, so $\text{FIRST}(BbBa) = \{d, b\}$: $S \to BbBa$ goes under $b$ and under $d$, which is cell (2).
In $S \to AaAb$ the two $A$s are followed by $a$ and by $b$, so $\text{FOLLOW}(A) = \{a, b\}$ and $A \to \epsilon$ fills both the $a$ column and cell (3).
Likewise $\text{FOLLOW}(B) = \{a, b\}$ from $S \to BbBa$, so $B \to \epsilon$ fills cell (4).

No cell receives two entries, so the grammar is LL(1) and none of the numbered cells is blank; swapping (1) and (2) would mix up the FIRST sets.

Answer: A

GATE CS 2024 Set 2 | Question 43

MCQ · 2 marks · −0.66

Consider the following expression: $x[i] = (p + r) * -s[i] + u/w$. The following sequence shows the list of triples representing the given expression, with entries missing for triples (1), (3), and (6).

(0)	+	$p$	$r$
(1)
(2)	uminus	(1)
(3)
(4)	/	$u$	$w$
(5)	+	(3)	(4)
(6)
(7)	=	(6)	(5)

Which one of the following options fills in the missing entries CORRECTLY?

(1) =[] $s$ $i$ (3) * (0) (2) (6) []= $x$ $i$ (1) []= $s$ $i$ (3) – (0) (2) (6) =[] $x$ (5) (1) =[] $s$ $i$ (3) * (0) (2) (6) []= $x$ (5) (1) []= $s$ $i$ (3) – (0) (2) (6) =[] $x$ $i$

Explanation

Answer: (A)

Triples have no result names: an operand is either a name or the number of an earlier triple.

(1) =[] s i reads the element $s[i]$, the value that (2) negates. The operator []= stores into an array element and produces no value for uminus to use.
(3) * (0) (2) multiplies $p + r$ by $-s[i]$, which (5) then adds to $u/w$. The expression contains no subtraction, so the options with – fail here too.
(6) []= x i marks the array location $x[i]$, and (7) assigns the value of (5) to it. Putting (5) inside (6) would lose the index $i$ and duplicate the work of (7).

Answer: A

GATE CS 2024 Set 2 | Question 65

NAT · 2 marks

Consider the following augmented grammar, which is to be parsed with a SLR parser. The set of terminals is $\{a,b,c,d,\#,@\}$

$S' \rightarrow S$
$S \rightarrow SS \mid Aa \mid bAc \mid Bc \mid bBa$
$A \rightarrow d\#$
$B \rightarrow @$

Let $I_0 = \mathit{CLOSURE}(\{S' \rightarrow \bullet S\})$. The number of items in the set $\mathit{GOTO}(I_0,\ S)$ is ___________

Your answer

Explanation

Answer: 9

$I_0$ holds $S' \rightarrow \bullet S$, the five items $S \rightarrow \bullet SS$, $S \rightarrow \bullet Aa$, $S \rightarrow \bullet bAc$, $S \rightarrow \bullet Bc$, $S \rightarrow \bullet bBa$, and, from the dots before $A$ and $B$, $A \rightarrow \bullet d\#$ and $B \rightarrow \bullet @$.

$\mathit{GOTO}(I_0, S)$ moves the dot over $S$ in the two items that have $S$ next, giving the kernel $S' \rightarrow S \bullet$ and $S \rightarrow S \bullet S$. Closing the second item adds the five $S$-items with the dot at the start, and these in turn bring in $A \rightarrow \bullet d\#$ and $B \rightarrow \bullet @$.

Total: $2 + 5 + 2 = 9$ items. Stopping at the kernel would give only 2.

Answer: 9

\({S \to DHTU}\)	\(\{\ S.\mathit{val} = D.\mathit{val} + H.\mathit{val} + T.\mathit{val} + U.\mathit{val};\ \}\)
\({D \to \text{``M''}D_{1}}\)	\(\{\ D.\mathit{val} = 5 + D_{1}.\mathit{val};\ \}\)
\({D \to \epsilon}\)	\(\{\ D.\mathit{val} = -5;\ \}\)
\({H \to \text{``L''}H_{1}}\)	\(\{\ H.\mathit{val} = 5 * 10 + H_{1}.\mathit{val};\ \}\)
\({H \to \epsilon}\)	\(\{\ H.\mathit{val} = -10;\ \}\)
\({T \to \text{``C''}T_{1}}\)	\(\{\ T.\mathit{val} = 5 * 100 + T_{1}.\mathit{val};\ \}\)
\({T \to \epsilon}\)	\(\{\ T.\mathit{val} = -5;\ \}\)
\({U \to \text{``K''}}\)	\(\{\ U.\mathit{val} = 5;\ \}\)

	\(a\)	\(b\)	\(c\)	\(d\)
\(S\)	\(S \to AaAb\)	\(S \to BbBa\)	(1)	(2)
\(A\)	\(A \to \epsilon\)	(3)	\(A \to cS\)
\(B\)	(4)	\(B \to \epsilon\)		\(B \to dS\)

(0)	+	\(p\)	\(r\)
(1)
(2)	uminus	(1)
(3)
(4)	/	\(u\)	\(w\)
(5)	+	(3)	(4)
(6)
(7)	=	(6)	(5)