8,937 views

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?

1. i and ii
2. ii and iii
3. i and iii
4. None of the above

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

1. $S→S∗.E$
1. $E→F.+E$
1. $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

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

Correct Answer: $D$

by

ans is D.

by

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.

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.

There will be 9 sets I0 to I8

(I) will be in set I5

(II) will be in set I3

(III) will be in set I6

So (D)

by

Given Grammar is left Recursive.

### 1 comment

Right recursive also.