Question

Consider two grammars \( G_1 \) and \( G_2 \) with the production rules given below:

\[ G_1: \begin{aligned} S &\to \text{if } E \text{ then } S \,|\, \text{if } E \text{ then } S \text{ else } S \,|\, a \\ E &\to b \end{aligned} \] \[ G_2: \begin{aligned} S &\to \text{if } E \text{ then } S \,|\, M \\ M &\to \text{if } E \text{ then } M \text{ else } S \,|\, c \\ E &\to b \end{aligned} \] where if, then, else, 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.

Hint:

A grammar is $LL(1)$ if it can be parsed top-down using a single token lookahead. Ambiguity or left-recursion typically disqualifies a grammar from being $LL(1)$.

Answer 1

The Correct Option is C, D

To determine if a grammar is \( LL(1) \), we check for ambiguity and left-recursion.

• \( G_1 \) contains the well-known "dangling else" problem, making it ambiguous. This ambiguity arises because the parser cannot determine whether the "else" clause is associated with the closest "if" or another one further up the stack. Since ambiguous grammars cannot be \( LL(1) \), \( G_1 \) is not \( LL(1) \).
• \( G_2 \) also exhibits ambiguity because the nonterminal \( M \) introduces multiple possible derivations for statements containing \( \text{if-else} \). The ambiguity comes from the fact that the grammar allows different parse trees for the same input, leading to confusion in a top-down parsing approach.

Since both grammars are ambiguous, neither can be \( LL(1) \).

Thus, the correct options are (C) and (D).