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?
Answer
(C), (D)
Explanation
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