GATE 2025 CS2 Q.51: solution and answer

GATE 2025 · CS2Q.51 · 2 marks · MSQ

Consider two grammars $G_{1}$ and $G_{2}$ with the production rules given below:

$G_{1}$ : $S \to i f E t h e n S ∣ i f E t h e n S e l se S ∣ a$ ; $E \to b$

$G_{2}$ : $S \to i f E t h e n S ∣ M$ ; $M \to i f E t h e n M e l se S ∣ c$ ; $E \to b$

where $i f, t h e n, e l se, a, b, c$ are the terminals. Which of the following option(s) is/are CORRECT?

(A)
$G_{1}$ is not $LL (1)$ and $G_{2}$ is $LL (1)$ .
(B)
$G_{1}$ is $LL (1)$ and $G_{2}$ is not $LL (1)$ .
(C)
$G_{1}$ and $G_{2}$ are not $LL (1)$ .
(D)
$G_{1}$ and $G_{2}$ are ambiguous.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Official answer: C, DSource: Official answer key, GATE 2025 CS2 (IIT Roorkee)

An $LL (1)$ grammar needs, for every nonterminal, the FIRST sets of its alternatives to be pairwise disjoint (and, for a nullable alternative, disjoint from FOLLOW). No nonterminal here is nullable, so only the FIRST sets matter. Any ambiguous grammar is also not $LL (1)$ .
$G_{1}$ : both $S \to i f E t h e n S$ and $S \to i f E t h e n S e l se S$ have $FIRST = {i f}$ . They overlap, so $G_{1}$ is not $LL (1)$ .
$G_{1}$ is the dangling-else grammar, so it is ambiguous. The string if b then if b then a else a has two parse trees: the else can belong to the inner if ( $S \to i f E t h e n S$ outside, $S \to i f E t h e n S e l se S$ inside) or to the outer if ( $S \to i f E t h e n S e l se S$ outside, $S \to i f E t h e n S$ inside).
$G_{2}$ : $FIRST (M) = {i f, c}$ . The alternatives of $S$ are $i f E t h e n S$ with $FIRST = {i f}$ and $M$ with $FIRST = {i f, c}$ . Both contain $i f$ , so on input $i f$ the parser cannot choose between them. $G_{2}$ is not $LL (1)$ . So (A) and (B) are false and (C) is true.
Is $G_{2}$ ambiguous? The else-part of $M \to i f E t h e n M e l se S$ is an $S$ , and an $S$ can be an unmatched $i f E t h e n S$ . So an else written after it can attach in two places. Take the string if b then if b then c else if b then c else c, and number its keywords if1 … if2 … else1 if3 … else2.
Parse 1 (else2 belongs to if1): $S \Rightarrow M \Rightarrow i f_{1} E t h e n M_{1} e l s e_{2} S$ with $S \Rightarrow M \Rightarrow c$ . Here $M_{1} \Rightarrow i f_{2} E t h e n M e l s e_{1} S^{'}$ with $M \Rightarrow c$ and $S^{'} \Rightarrow i f_{3} E t h e n S \Rightarrow i f_{3} b t h e n c$ (using $S \to M \to c$ ). Every step uses a production of $G_{2}$ .
Parse 2 (else2 belongs to if3): $S \Rightarrow i f_{1} E t h e n S_{1}$ . Then $S_{1} \Rightarrow M \Rightarrow i f_{2} E t h e n M e l s e_{1} S_{2}$ with $M \Rightarrow c$ , and $S_{2} \Rightarrow M \Rightarrow i f_{3} E t h e n M e l s e_{2} S$ with $M \Rightarrow c$ and $S \Rightarrow M \Rightarrow c$ . Every step is again valid.
The two trees are different (in one else2 pairs with if1, in the other with if3) and they produce the same string. So $G_{2}$ is ambiguous. It is not the standard unambiguous matched/unmatched grammar, because there the else-part of a matched statement must itself be matched, while $G_{2}$ allows any $S$ .
Both grammars are ambiguous, so (D) is true. (C) is true as well. Correct options: (C) and (D).

KEY IDEA

FIRST sets clash for both grammars on the token $i f$ , so neither is $LL (1)$ . $G_{1}$ is the classic dangling-else grammar. $G_{2}$ only looks like the fix: the else-part of $M$ is a general $S$ , which can be an unmatched if, so a later else can still attach in two places, as in if b then if b then c else if b then c else c.

WATCH OUT FOR

Treating $G_{2}$ as the textbook unambiguous dangling-else grammar. In that grammar the else-part of a matched statement must itself be matched. $G_{2}$ writes $M \to i f E t h e n M e l se S$ , which lets an unmatched if sit inside a matched one. A short test string like if b then if b then c else c has only one parse, so you need a longer string with two elses to see the ambiguity.

From the GATE 2025 CS2 paper. Every question of this paper · Download the full paper · All 13 Parsing questions, with notes

GATE 2025 CS2 Q.51: solution and answer

Answer and solution

More Parsing questions