in Compiler Design retagged by
447 views
2 votes
2 votes
S - >aSb | c

Give viable prefix for this with details of how to find viable prefix? for string - - aacbb
in Compiler Design retagged by
447 views

2 Comments

Viable prefix is found with respect to a string as we need to know the contents of the stack at each shift - reduce step which is possible only if we know the string in addition to the grammar given.
0
0
Updated
0
0

1 Answer

4 votes
4 votes
Best answer

First of all we have to know a few points regarding viable prefix :

a) Viable prefixes w.r.t a string to be parsed are those which  appear in the stack during the process of reduction.

b) And secondly this should be a prefix of some right sentential form

STACK                     INPUT                      ACTION  

   $                          aacbb                          Shift

   $a                        acbb                            Shift

   $aa                      cbb                              Shift

   $aac                    bb                                Reduce

   $aaS                    bb                                Shift

   $aaSb                  b                                  Reduce

   $aS                     b                                  Shift

   $aSb                   $                                  Reduce

   $S                      $                                   Accept

Now we write the right sentential forms of the string "aacbb"

S  -->   aSb  --> aaSbb  -->  aacbb

One can verify that all of the given stack contents are prefix of one of the given 4 right sentential forms of the given string.

Hence the viable prefixes are : 

a , aa , aac , aaS , aaSb , aS , aSb , S 

selected by

3 Comments

Any reference material link ?
1
1
Will $\varepsilon$ not be a viable prefix?
0
0