The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
1.8k 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
asked in Compiler Design by Active (3.7k points)
edited by | 1.8k views

4 Answers

+14 votes
Best answer

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

answered by Veteran (57.4k points)
selected by
+21 votes

ans is D.

 

answered by Loyal (8.2k points)
edited by
+16
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
+1
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 ...
–1
You are right @vaishali above dfa is wrong. F->id look ahead should be + also. Please correct me if I am wrong. Thank you!
+1

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 

+2 votes

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)

answered by Active (3.9k points)
0 votes
Answer D.

Given Grammar is left Recursive.
answered by (29 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,855 questions
47,520 answers
145,894 comments
62,278 users