what is viable prefix?

Question

Can someone describe what is a viable prefix with an example?

Comments

@Suvam Chatterjee See this https://gatecse.in/viable-prefixes-and-handle-in-lr-parsing/

Answer 1

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.)

Comments

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

---

@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)

Answer 2

refer to this:http://stackoverflow.com/questions/4202181/explanation-about-viable-prefix

Comments

thnk u so much :)

---

welcome :)

---

Reminded about my gate prep time when I asked this question on stackoverflow :)

---

:D