GATE CS Parsing Previous Year Questions

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

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

	\(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\)