MadeEasy Test Series: Compiler Design - Viable Prefix

Question

i think "(E+F*" is viable prefix but "E+F*" is not viable prefix. correct? 

Comments

yes.you are right.

Viable prefix should be (E+T* then (E+F and so on.

---

Right :P

---

Please explain why (E+T* is a viable prefix. Shouldn't "T" be reduced to E because "T" is a handle and prefix viable cannot continue past a handle???

Answer 1

The explanation provided by Manojk is right but we should also include () in the string..

so it should be (E+F* as the viable prefix

Comments

Bold ones are handles.

Using bottom-up parsing:

= (id + id * id)

= (F + id * id)

= (T + id * id)

= (E + id * id)

= (E + F * id)      → (E + F    should be viable prefix

a viable prefix is a prefix of a right sentential form that does not continue past the right end of the rightmost handle

= (E+ T * id)

= (E+T * F)

= (E+T)

= (E)

= F

= T

= E

 

Ref https://gatecse.in/viable-prefixes-and-handle-in-lr-parsing/

Answer 2

The prefixes of right sentential forms that can appear on the stack of a shift-reduce parser are called viable prefixes.

By definition, a viable prefix is a prefix of a right sentential form that does not continue past the right end of the rightmost handle of that sentential form.