Dark Mode

10,485 views

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

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

0 votes