retagged by
13,951 views
4 votes
4 votes
Can someone describe what is a viable prefix with an example?
retagged by

2 Answers

28 votes
28 votes

if β | γ is a state of bottom-up parser then β is a viable prefix.
Here β is in stack and γ is yet to be read.
It means, whatever you can see in stack is viable prefix.

What is stack in parsing and how it work ? – check this video for in-depth understanding of stack working in parsing.
Consider this grammar-

S→ aaA | b
A→ b

when u start parsing for "aab" [obviously it belongs to given grammar] u will encounter the following steps

| aab $ (Initially stack is empty)
a | ab $
aa|b $
aab| $
aaA| $
S| $

here viable prefixes are - {eps,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
1 votes
1 votes

Related questions

2 votes
2 votes
1 answer
2
4 votes
4 votes
2 answers
3
4 votes
4 votes
3 answers
4