The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+5 votes
648 views
Consider the following grammaer:
S->0S1 | 01

How many of the following  are the viable prefixes of the grammar?
i.  01   
ii. 001
iii. 00011
iv. 00S1

PS: given answer i, ii and iv , please explain!
asked in Compiler Design by Boss (17.2k points)
edited by | 648 views

2 Answers

+7 votes
Best answer

Check the link for explaination :- https://gateoverflow.in/68764/bottom-up-parsing


$S\rightarrow 01$

$S\rightarrow 0S1\rightarrow 0011$

$S\rightarrow 0S1\rightarrow 00S11$


Set of Viable Prefix $V = \left \{ \epsilon ,0,1,01,0S,0S1,00,001,00S,00S1 \right \}$

answered by Veteran (50.6k points)
selected by
+1
not readable!
0
@kapil why iii) is not viable?
0
Latex was not working :)
0
@Anusha, its not !! Instead $0001$ or $000S1$ is VP.
+1
sorry got it! 00011 never appears on top of the stack isnt it @kapil?
upto 0001 appears on top then 01 reduces S..so 00S will be stack content
but 00011 will never be stack content
+1
yes got it
0

I am not getting one thing..According to the link u given..can't we write like this:

S->0S1-->00S11-->000111{Bold one's are handle}

{VIABLE PREFIX--> epsilon,0,0S,0S1,00,00S,00S1,00S11,000,0001,00011,000111}

What is wrong in this??

0

@Lucky.

See here

0
please expain how you taken  1,0S as a viable prefix
0

@Kapil sir i dont think 1 would be viable prefix 

0 votes
....
answered by Boss (12.4k points)
edited by

Related questions

+2 votes
1 answer
1
asked Nov 12, 2016 in Compiler Design by KISHALAY DAS Loyal (6.6k points) | 1k views
+2 votes
1 answer
3
asked Jul 18, 2015 in Compiler Design by Suvam Chatterjee Junior (523 points) | 782 views


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

47,080 questions
51,342 answers
177,712 comments
66,675 users