in Compiler Design retagged by
10,485 views
2 votes
2 votes
Can someone describe what is a viable prefix with an example?
in Compiler Design retagged by
10.5k views

1 comment

2 Answers

24 votes
24 votes
if β.γ is a state of bottom-up parser then β is a viable prefix.

consider this grammar-

S→ aaA | b
A→ b

when u start parsing for "aab" [obviously it belongs to given grammar] u will encounter following steps
a.ab
aa.b
aab.
aaA.
S.

here viable prefixes are - {a,aa,aab,aaA,S}

I just showed viable prefixes for given string, if we collect all viable prefixes for all strings possible in the grammar then this set is ALWAYS a regular set.
And in usual practice when u draw DFA for bottom-up parser, that DFA is for this regular set (set of all viable prefixes.)
edited by

2 Comments

S->aaA.  And A->b. Are handles right? How are they viable prefixes ?
1
1

@xylene

viable prefix  are prefix of  a sentential form that can extends up to but not past the handle.

S->aaA.  and A->b. are handles for  given grammar.

Here aaA. is trivial viable prefix as it is an handle. However A->b. is a handle but  b is not viable prefix here (see the derivation)

3
3
0 votes
0 votes

4 Comments

thnk u so much :)
0
0
welcome :)
0
0
Reminded about my gate prep time when I asked this question on stackoverflow :)
2
2
:D
0
0