edited by
2,667 views

3 Answers

5 votes
5 votes

80 . LR(1) item B---> a.B,a  is valid for " aaa ". 

 A---> a'.ß, a'' is valid for viable prefix let y if there is derivation S-rm*-->ØAw---> Øa'ßa''w

here y=Øa' here a'' is lookahead , which is first symbol of w so for given question 

S--> BB---> BaB--->--> Bab---> aBab-*-->aaaBab(rightmost derivation)  so here a''=a , w=ab ,Ø=aa,

viable prefix = aaa 

81. similar here S--> BB --> BaB--> BaaB 

so w=∊ ,a''=$  ,a'=a , Ø=Ba so

y=  Baa..

reference http://www.cs.clemson.edu/course/cpsc827/material/LRk/LR1.pdf

http://tinman.cs.gsu.edu/~raj/4340/sp12/LR1.pdf

1 votes
1 votes

Viable prefix : The prefixes of right sentential forms that can appear on the stack of a shift-reduce parser are called viable prefixes.

Simple design LR(1) DFA. then u get the ans. Ans will be d and b respectively.

follow this : http://www.cs.cornell.edu/courses/cs412/2007sp/lectures/lec09.pdf

edited by
1 votes
1 votes
answer  is option ( c ) aaa

so in B-->a.B,a            a    after ,   is   lookahead   

by   deriving stings  we  have to check rightmost derivation

since vaid  viable prefix for item B-->a.B,a   will   be  'y'  in  S==> yBx   such that there is a  RMD  in which  x  should have starting symbol as   ' a ' (  corresponds to lookahead symbol)

so  according to given derivation-->

S==>BB==>aBB==>aBaB==>aaBaB==>aaaBaB==>aaaBab      here   y=aaa  ,    B=B   ,   x=ab   and  starting symbol of x is ' a ' .

which is given in option is also   ( c ) aaa.

hence answer  is option ( c ) aaa

Related questions

2 votes
2 votes
1 answer
1
4 votes
4 votes
2 answers
3
4 votes
4 votes
2 answers
4
Suvam Chatterjee asked Sep 28, 2015
13,962 views
Can someone describe what is a viable prefix with an example?