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

No it is not  necessary that if a grammar has left and right recursion it must be ambiguous.

---

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

Answer 1

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 2

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.