GATE CS 2025 Set 2 Q.51: Parsing and Syntax Analysis (LL and LR)

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

$G_1: \; S \rightarrow \textit{if } E \textit{ then } S \mid \textit{if } E \textit{ then } S \textit{ else } S \mid a$
$\phantom{G_1: \; } E \rightarrow b$

$G_2: \; S \rightarrow \textit{if } E \textit{ then } S \mid M$
$\phantom{G_2: \; } M \rightarrow \textit{if } E \textit{ then } M \textit{ else } S \mid c$
$\phantom{G_2: \; } E \rightarrow b$

where $\textit{if}, \textit{then}, \textit{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.

Official answer and solution

Official answer: C and D
From: Official GATE 2025 answer key

Solution

Check both grammars for FIRST/FIRST conflicts on terminal if and for dangling-else ambiguity (noting that in $G_2$ , $M \rightarrow \textit{if } E \textit{ then } M \textit{ else } S$ has $S$ instead of $M$ after else).

Neither $G_1$ nor $G_2$ is LL(1) (Option C is TRUE):
- In $G_1$ , the two $S$ -productions $\textit{if } E \textit{ then } S$ and $\textit{if } E \textit{ then } S \textit{ else } S$ both start with terminal $\textit{if}$ (FIRST/FIRST conflict).
- In $G_2$ , for non-terminal $S$ , $\text{FIRST}(\textit{if } E \textit{ then } S) \cap \text{FIRST}(M) = \{\textit{if}\} \neq \emptyset$ , causing a FIRST/FIRST conflict in the LL(1) parsing table.
Both $G_1$ and $G_2$ are ambiguous (Option D is TRUE):
- $G_1$ is the classic ambiguous dangling-else grammar.
- In the standard unambiguous dangling-else grammar, a matched statement $M$ $M$ requires both branches of if-then-else to be matched ( $M \rightarrow \textit{if } E \textit{ then } M \textit{ else } M \mid c$ $M \to if E then M else M ∣ c$ ). However, $G_2$ $G_{2}$ has $M \rightarrow \textit{if } E \textit{ then } M \textit{ else } S$ $M \to if E then M else S$ , which allows $M$ $M$ to end with an unmatched if inside its else branch! Consequently, the string:
  $w = \textit{if } b \textit{ then if } b \textit{ then } c \textit{ else if } b \textit{ then } c \textit{ else } c$
  has two distinct parse trees in $G_2$ $G_{2}$ :
  - Tree 1: $S \Rightarrow M \Rightarrow \textit{if } E \textit{ then } M_1 \textit{ else } S_1$ , where $M_1 \Rightarrow \textit{if } b \textit{ then } c \textit{ else } (\textit{if } b \textit{ then } c)$ and $S_1 \Rightarrow M \Rightarrow c$ .
  - Tree 2: $S \Rightarrow \textit{if } E \textit{ then } S_1$ , where $S_1 \Rightarrow M_1 \Rightarrow \textit{if } b \textit{ then } c \textit{ else } (\textit{if } b \textit{ then } c \textit{ else } c)$ .
- Since $G_2$ is ambiguous, this also immediately confirms that $G_2$ cannot be LL(1).

Final answer

Options (C), (D)

Common trap

Mistaking $G_2$ for the textbook unambiguous grammar without noticing $S$ (instead of $M$ ) at the end of $M \rightarrow \textit{if } E \textit{ then } M \textit{ else } S$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 2 (CS2)
Question: 51 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source