GATE CSE 2006 | Question: 7

Question

Consider the following grammar

• $S  \rightarrow S * E$
• $S  \rightarrow E$
• $E  \rightarrow F + E$
• $E  \rightarrow F$
• $F  \rightarrow id$

Consider the following LR(0) items corresponding to the grammar above

1. $S  \rightarrow S *.E$
2. $E   \rightarrow F. + E$
3. $E   \rightarrow F + .E$

Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?

• A. i and ii
• B. ii and iii
• C. i and iii
• D. None of the above

Comments

As we can see in the below given LR(0) items, that all three belongs to different state (sets).

---

1. $S→S∗.E$

2. $E→F.+E$

3. $E→F+.E$

Quite intuitively, in very less time, we can say that answer is none i.e. option (D).
Why?

1. means that we have just seen $*$. Now if this item is with item ii, it would mean that we have seen a * and we are about to see a +, a situation as *+ should be there in the string input to the parser. Which is something not generated by the input grammar.
   Similarly, i cannot be with iii, it would mean that we have just seen a * and also we have just seen a +.
2.  means that we are about to see a + next. And iii means we have just seen a +. This would mean, ++ shall be present as a substring in the string input to parser. But this sort of thing cannot be generated by the grammar given.

The grammar generates expressions having + and *.

---

Really good approach HitechGa

Answer 1

Since in first production s->s*.E, in this state the production of E will be there similarly in other 2 also productions can't be together for the same reason.

Answer 2

D. is the answer. 

Also, it is not LL(1) as it is left recursive and also it is not LR(0) because there is shift-reduce conflict and hence it is not SLR(1), LALR(1), CLR(1).

Comments

hence it is not SLR(1), LALR(1), CLR(1).

Can we say that if grammar is not LR(0) then it is not SLR(1), LALR(1), CLR(1)  ?

---

No , because every LR(0) grammar is also SLR(1), but not all SLR(1) grammars are LR(0).

---

Read again