12,646 views
34 votes
34 votes

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:

  1. it is left recursive

  2. it is right recursive

  3. it is ambiguous

  4. it is not context-free

6 Answers

Best answer
51 votes
51 votes

Here, we can expand any one of $S_1$ to $\in$ and other to $ea$, but which one will it be need not matter, because in the end we will still get the same string.

This means that the Grammar is Ambiguous. $\text{LL(1)}$ cannot be ambiguous. Here's a Proof for that

$${\color{Magenta}{\underline{\textbf{LL(1) Derivations}}}} $$

${\color{Blue}{\textbf{L}} }$eft to  Right Scan of input

   ${\color{Blue}{\textbf{L}} }$eftmost Derivation

       ${\color{Blue}{\textbf{(1)}} }$ look ahead $1$ token at each step

$\text{Alternative characterization of LL(1) Grammars:}$

Whenever $A \rightarrow \alpha \mid \beta \in G$

  1. $\text{FIRST}(\alpha) \cap \text{FIRST}(\beta) = \{\},$ and
  2. If $\alpha \overset{\ast}{\implies} \varepsilon$ then $\text{FIRST}(\beta) \cap \text{FOLLOW}(A) = \{\}.$

$\textbf{Corollary:}$ No Ambiguous Grammar is $\text{LL(1)}.$

Correct Answer: C.

edited by
9 votes
9 votes

Finding a counter-example for ambiguity is a bit time consuming here. Go for option elimination.

Option A is wrong, because clearly it's not Left Recursive. ( Only A → Aa is Left Recursive )

Option B is wrong, because Right Recusrsion is not an issue for a grammar to be LL(1)

Option D is wrong, because any grammar of the form A → *anything* is Context-free.

So, Option C is correct.


Edit:

This grammar represents the Dangling Else problem. This language is inherently ambiguous.

If $S_1$ then $S_2$  else $S_3$ $|$ If $S_1$ then $S_2$ 

Here, we have an optional else, which creates ambiguity.

 

We'll always have two (exactly two) parse trees for the statement

if $<S>$ then if $<S>$  then $<S>$ else $<S>$

edited by
5 votes
5 votes
It is left factored version of the dangling else grammar. As we know,left factoring eliminates non determinism,but can not eliminate ambiguity,So ans should be (C)  

PS.

1) Surely its not left recursive .

2) Right recursion is not an issue for LL(1) .

3) It is context free .
Answer:

Related questions

75 votes
75 votes
8 answers
3
Kathleen asked Sep 21, 2014
35,337 views
Consider the following two statements:P: Every regular grammar is LL(1)Q: Every regular set has a LR(1) grammarWhich of the following is TRUE?Both P and Q are trueP is tr...
15 votes
15 votes
3 answers
4
Kathleen asked Sep 21, 2014
9,561 views
Which one of the following is a top-down parser?Recursive descent parser.Operator precedence parser.An LR(k) parser.An LALR(k) parser.