Consider the grammar with non-terminals (formula) , terminals (formula) ,… — GATE CS 2007 Q52

Consider the grammar with non-terminals $N=\left\{S,C,S_1\right\}$ , terminals $T=\left\{a, b, i, t, e\right\}$ , with $S$ as the start symbol, and the following set of rules:

$S \rightarrow iCtSS_1 \mid a$

$S_1 \rightarrow eS \mid \epsilon$

$C \rightarrow b$

The grammar is NOT LL(1) because:

View worked solution

Answer: C

The given grammar represents the classic dangling-else problem in programming languages, where:

$i$ stands for if
$C$ stands for condition
$t$ stands for then
$e$ stands for else

An LL(1) grammar must be unambiguous. Let's analyze why this grammar is not LL(1):

1. Ambiguity Analysis

Consider the string: $w = ibtibtaea$ (which represents if b then if b then a else a).

This string has two distinct leftmost derivations (and thus two different parse trees):

Derivation 1 (associating the else with the inner if):

\begin{aligned} S &\Rightarrow iCtSS_1 \\ &\Rightarrow ibtSS_1 \\ &\Rightarrow ibt(iCtSS_1)S_1 \\ &\Rightarrow ibtibtaS_1S_1 \\ &\Rightarrow ibtibtaeSS_1 \quad (\text{using } S_1 \rightarrow eS) \\ &\Rightarrow ibtibtae a S_1 \\ &\Rightarrow ibtibtaea \quad (\text{using } S_1 \rightarrow \epsilon) \end{aligned}

Derivation 2 (associating the else with the outer if):

\begin{aligned} S &\Rightarrow iCtSS_1 \\ &\Rightarrow ibtSS_1 \\ &\Rightarrow ibtS(eS) \quad (\text{using } S_1 \rightarrow eS) \\ &\Rightarrow ibt(iCtSS_1)eS \\ &\Rightarrow ibtibtaS_1eS \\ &\Rightarrow ibtibtaeS \quad (\text{using } S_1 \rightarrow \epsilon) \\ &\Rightarrow ibtibtaea \end{aligned}

Since the grammar is ambiguous, it cannot be parsed by any LL(1) parser.

2. Elimination of Other Options

Option A: There is no left-recursion in the grammar (no production of the form $A \rightarrow A\alpha$ ).
Option B: Right-recursion (e.g., $S_1 \rightarrow eS$ ) is perfectly fine and does not prevent a grammar from being LL(1).
Option D: The grammar is context-free because every production has a single non-terminal on its left-hand side.

Hence, the correct option is C.

Free practice · Your answers on this page are not saved.

GATE CS 2007 Q52 — Parsing (LL, LR)

1. Ambiguity Analysis

2. Elimination of Other Options

Related questions