795 views
given Grammar

E → E + E

E → E * E

E → ( E )

E → id

Find set of handles and viable prefixes for the input string id1 + id2 * id3

retagged | 795 views

viable prefix is -->

• A string that equals a prefix of right-sentential form upto and even including its unique handle .
• And also any prefix of a string that satisfies first.

E -> E + E -> E + E*E -> E + E * id -> E + id * id -> id + id * id

{Coloured is used to show Handle at each step}

Handle H = { E + E , E*E , Id }

Viable Prefix VP = { $\epsilon$ , E , E + , E + E , E + E * E , E + E *  , E + E * id , E + id , id  }

by Veteran (50.6k points)
selected by
0

@Kapil SIR , how $\epsilon$   viable prefix ? I didn't get that right

0

@gokou

id,is the handle so it is viable prefix.

$\epsilon$,is the prefix of any handle.(E+E,..)

+10
 STACK INPUT ACTION $id1 + id2 * id3 shift$ id1 + id2 * id3 reduce  E-> id1 $E +id2*id3 shift$  E + id2 * id3 shift $E+ id2 * id3 reduce E->id2$ E+E *id3 shift $E +E* id3 shift$E +E*id3 reduce E->id3 $E +E* E reduce E->E*E$ E+E reduce E->E+E $E ACCEPT Viable Prefix : The prefixes of right sentential forms that can appear on the stack of a shift-reduce parser are called viable prefixes. Viable Prefixes are$ id , E , E+ ,E+id, E+E  ,E+E* ,E+ E* id , E+ E*E  $is ϵ stack top ? or empty string ? Handles are E->id E->E*E E->E+E 0 wht about epsilon? 0 votes$Handles=\{id,E+E,E*E\}Viable\ prefixes=\{id,E,E+,E+id,E+E,E+E*,E+E*id,E+E*E\}$ $E\underline{E+E}E+\underline{E*E}E+E*\underline{id}E+\underline{id}*id\underline{id}+id*id$ $E\underline{E*E}E*\underline{id}\underline{E+E}*idE+\underline{id}*id\underline{id}+id*id\$

by Active (1.9k points)
edited