GATE CSE 2007 | Question: 52

Question

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:

• A. it is left recursive

• B. it is right recursive

• C. it is ambiguous

• D. it is not context-free

Comments

The language generated by this grammar is inherently ambiguous. So all the grammar possible for this language will be ambiguous. We can not remove ambiguity from this grammar(though removal of ambiguity is an undecidable problem).

---

Classic danging if else problem

---

ibtibtaea

Answer 1

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.

Comments

@ankit bro

----------

S→ aSb|epsilon(middle recursion which is direct)

---------

S→ aA|b

A->bS| a

This is indirect right recursion. S→ A → S

------------

---

Thanks bhai @raja11sep.

---

can someone give me two  different parse tree generate same string for this condition

Answer 2

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>$

Comments

Is it right recursive or not?

---

indirect right recursion

Answer 3

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 .

Comments

How to test whether this grammar is context free or not?

---

@Hirak

Condition for a grammar to be CFG:

A $\rightarrow$ $\alpha$

where A $\in$ non-terminal. (We can't have more than one non-terminal in LHS. Ex: AA $\rightarrow$ $\alpha$ is not allowed.).

and $\alpha$ $\in$ stream of terminals and non-terminals.

Answer 4

it is ambiguous grammer answer c is correct

Answer 5

Given grammar is not LL(1) it doesn't mean it is ambiguous....it can be unambiguous also......

So u need to check ...for string for which it is ambiguous...then option c is correct...

In this case definitely option elimination give u option c... easy one only.

Answer 6

for option C can we say that ?

there are two entries for S1 for terminal ‘e’  in parsing table….so grammar couldn’t decide whether to use S-->epsilon or

S-->eS

Hence grammar is ambigious.