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

Answer 1

$\Rightarrow$ NOT possible for these three items to be in same state

Correct Answer: $D$

Answer 2

ans is D.

 

Comments

answer is (D).. we can quickly observe here, in (i) "." is after *, that means it has just processed * input..

in (ii) "." is after F, it has just processed F.. in (iii) "." is after +.. that means it has just processed +..

So none these belong to the same canonical set of item.!! because "." comes either before all alphabet or just after the alphabet has just processed...

We don't have to draw whole list of canonical item to answer this 1 mark question.. :D

---

your ans is right but i have a doubt in state daigram.for state i0  there will be one  production for F with follow +.

if i am wrong then correct me ...

---

You are right @vaishali above dfa is wrong. F->id look ahead should be + also. Please correct me if I am wrong. Thank you!

---

Just want to clarify,

1) Question is asked on the LR(0) items, so there is no need to add look ahead.

2) In the state I3, there is shift Reduce conflit , E->F.+E and E->F.

Please correct me 

---

@ JPranavc Actually this is the answer. Here we have been tested about LR(0) rules rather than solving capabilities.It was 1 mark question so they dont want to solve the whole question rather use conflict concept.

Answer 3

There will be 9 sets I₀ to I₈ 

(I) will be in set I₅

(II) will be in set I₃

(III) will be in set I₆

So (D)

Answer 4

Answer D.

Given Grammar is left Recursive.

Answer 5

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 6

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).