menu
search
Log In
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

Subjects

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

GATE2006-7

25 votes
5.5k 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
in Compiler Design
edited by 5.5k views
0

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

6 Answers

27 votes
 
Best answer

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

Correct Answer: $D$


edited by
31 votes

ans is D.

 


edited by
22
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!
4

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 

0

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

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

1 vote
Answer D.

Given Grammar is left Recursive.
0 votes
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.
0 votes

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

← Prev. Next →
← Prev. Qn. in Sub. Next Qn. in Sub. →
Answer:

Related questions

18 votes
3 answers
1
3.7k views
GATE2006-58
Consider the following grammar: $S\rightarrow FR$ $ R\rightarrow * S\mid \varepsilon $ $ F\rightarrow id $ In the predictive parser table $M$ of the grammar the entries $M[S,id]$ and $M[R,\$]$ respectively are $ \left \{ S\rightarrow FR \right \} $ and $ \left \{ ... $ \left \{ F\rightarrow id \right \} $ and $ \left \{ R\rightarrow \varepsilon \right \} $
Consider the following grammar: $S\rightarrow FR$ $ R\rightarrow * S\mid \varepsilon $ $ F\rightarrow id $ In the predictive parser table $M$ of the grammar the entries $M[S,id]$ and $M[R,\$]$ respectively are $ \left \{ S\rightarrow FR \right \} $ and $ \left \{ R\ ... $ \left \{ F\rightarrow id \right \} $ and $ \left \{ R\rightarrow \varepsilon \right \} $
asked Sep 26, 2014 in Compiler Design Rucha Shelke 3.7k views
16 votes
6 answers
2
2.7k views
GATE2006-85
The grammar $S\rightarrow AC\mid CB$ $C\rightarrow aCb\mid \epsilon$ $A\rightarrow aA\mid a$ $B\rightarrow Bb\mid b$ generates the language $ L=\left \{ a^{i}b^{j}\mid i\neq j \right \}$. In this grammar what is the length of the derivation (number of steps starting from $S$) to generate the string $a^{l}b^{m}$ with $l\neq m$ $\max (l,m) + 2$ $l + m + 2$ $l + m + 3$ $\max (l,m) + 3$
The grammar $S\rightarrow AC\mid CB$ $C\rightarrow aCb\mid \epsilon$ $A\rightarrow aA\mid a$ $B\rightarrow Bb\mid b$ generates the language $ L=\left \{ a^{i}b^{j}\mid i\neq j \right \}$. In this grammar what is the length of the derivation (number of steps starting from $S$) to generate the string $a^{l}b^{m}$ with $l\neq m$ $\max (l,m) + 2$ $l + m + 2$ $l + m + 3$ $\max (l,m) + 3$
asked Nov 7, 2016 in Compiler Design jothee 2.7k views
35 votes
4 answers
3
6.2k views
GATE2006-84
Which one of the following grammars generates the language $ L=\left \{ a^{i}b^{j}\mid i\neq j \right \}$? $S\rightarrow AC\mid CB$ $C\rightarrow aCb\mid a\mid b$ $A\rightarrow aA\mid \varepsilon$ $B\rightarrow Bb\mid \varepsilon$ ... $S\rightarrow AC\mid CB$ $C\rightarrow aCb\mid \varepsilon$ $A\rightarrow aA\mid a$ $B\rightarrow Bb\mid b$
Which one of the following grammars generates the language $ L=\left \{ a^{i}b^{j}\mid i\neq j \right \}$? $S\rightarrow AC\mid CB$ $C\rightarrow aCb\mid a\mid b$ $A\rightarrow aA\mid \varepsilon$ $B\rightarrow Bb\mid \varepsilon$ ... $S\rightarrow AC\mid CB$ $C\rightarrow aCb\mid \varepsilon$ $A\rightarrow aA\mid a$ $B\rightarrow Bb\mid b$
asked Sep 26, 2014 in Compiler Design Rucha Shelke 6.2k views
26 votes
3 answers
4
5.2k views
GATE2006-59
Consider the following translation scheme. $ S\rightarrow ER$ $ R\rightarrow ^{*}E\left \{ print('*'); \right \} R\mid \varepsilon $ $ E\rightarrow F+E\left \{ print('+'); \right \}\mid F $ $ F\rightarrow (S)\mid id \left \{ print(id.value); \right \} $ Here id is a token that represents ... $2 * 3 + 4$ $2 * +3 \ 4$ $2 \ 3 * 4 +$ $2 \ 3 \ 4+*$
Consider the following translation scheme. $ S\rightarrow ER$ $ R\rightarrow ^{*}E\left \{ print('*'); \right \} R\mid \varepsilon $ $ E\rightarrow F+E\left \{ print('+'); \right \}\mid F $ $ F\rightarrow (S)\mid id \left \{ print(id.value); \right \} $ Here id is a token that represents an ... $2 * 3 + 4$', this translation scheme prints $2 * 3 + 4$ $2 * +3 \ 4$ $2 \ 3 * 4 +$ $2 \ 3 \ 4+*$
asked Sep 26, 2014 in Compiler Design Rucha Shelke 5.2k views
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...