The Gateway to Computer Science Excellence
+2 votes
269 views

Consider the following grammar:

S-->XX

X-->b

X-->aX

Which of the following can be the viable prefixes?

  1. baab
  2. aab
  3. aaabab
  4. bbbaX
in Compiler Design by Active (3.9k points)
edited by | 269 views
0
B?
0
Yes. How? I know how to recognize viable prefixes when a string to be parsed is given, but here no string is given??
+2

1. baab 

b will be pushed and before pushing next letter b will be reduced to X, so baab as viable prefix is not possible

with similar reason 3 and 4 are not viable prefixes,

but aab is 

.aab

a.ab  (a is pushed,no handle found)

aa.b (a is pushed and viable prefix is aa still no handle found)

aab. (b is pushed and handle found and will be reduced in next step but aab is a valid viable prefix)

For practice you can refer this one

+1

2 Answers

0 votes
viable prefixes which  is collection of symbol on top of the stack which prefixes is not replaced by any production  of the cfg.
by Junior (909 points)
0 votes
Viable prefix is nothing but stack content in LR Parsing ....in this ques check option if it is visible is stack while doing parsing .. that's it...B
by (339 points)
0
This method of your is good but checking four option with complete parsing method will take a lot of time, don't you have any less time taking method?
0

Why can't C be the answer? 

By following MK Utkarsh sir's method for option C - 

.aaabab

a.aabab

aa.abab

aaa.bab

aaab.ab  [ b is reducible to X]  

aaaX.ab  [ aX is reducible to X]

aaX.ab    [ aX is reducible to X]

aX.ab      [ aX is reducible to X]

X.ab

Xa.b

Xab.        [ b is reducible to X]

XaX.        [ aX is reducible to X]

XX.          [ XX is reducible to S]

S  

Where am I going wrong ? Can someone please point out ? 

 sir,  @  sir.

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
50,737 questions
57,379 answers
198,523 comments
105,317 users