799 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 | 799 views
0

In the options, Option a is correct but it need slightly correction that in option "a" it should have

“(E+F ∗” is a viable prefix

“E+F ∗” is a viable prefix.

+1

this is a good link for viable prefix

https://gateoverflow.in/68764/bottom-up-parsing

chk once

+1

Thanks @ srestha,

I have checked that thread, in that also, the prefix starts from the left side,

and in this question if we start from left side then “(E+F ∗” should be the viable prefix because, when we start to deriving the string "(id + id * id)", then "(" should be pushed into the stack, but in the question they missed "(" to attach in the begining of option (a).

0
it will derive like

E->T->F->(E)->(E+T)->(E+T*F)->(E+T*id)->(E+id*id)->(id+id*id)

So, handles are{T,F,(E),E+T,T*F,id}

So, I think a) shouldnot be answer

Instead C) should be ans
0

@srestha It will go like this

Note :- We will Evalute the right most Variable always.

E

T

F

(E)

(E+T)

(E+T*F)

(E+T*id)

(E+F*id)

(E+id*id)

(T+id*id)

(F+id*id)

(id+id*id)

In this bolded letters "E+F*" they are taking as prefix, which is wrong they should do like "(E+F* ".

0
T*F is one of the handle,rt?

then why it couldnot be a viable prefix?
+1

T*F is one of the handle,rt?

Agreed

then why it could not be a viable prefix?

Why it should be??

@Srestha,

Acc to this question https://gateoverflow.in/92242/%23compiler

The Right most derivation of the string id + id * id is as follow:-

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 = { ϵ , E , E + , E + E , E + E * E , E + E *  , E + E * id , E + id , id  }

In this question also, we are taking we are taking prefix of right sentential form simply say prefix. And as we know that Prefix of any string is starts from left most char of that string.

If you are talking about that why T*F is not viable prefix, then see in the 6th step we have

Step 6)  (E+T*F)

Viable prefix should be (E+T*F or (E+T*F) if you want to include T*F, in the viable prefix.

0

yes, that is correct :)

but chk again

from

(E+T*id) we are deriving (E+F*id)

and not the * included in handle,rt?

So, if we take (E+F* as a viable prefix, it is crossing the limit of handle.

because * is not inside handle

So, (E+F* cannot be viable prefix

Am I missing something?

0

i am also getting the same.

whenever F is coming on the top of stack it is reduced to T immediately (before allowing next shift).

 Stack top Input String $(E+ id * id )$ $(E+id * id )$ $(E+F * id )$ $(E+T * id )$ $(E+T* id )$

how can ( E+F*  is a Viable Prefix?

0

Why are you not reducing (E+T  to (E in the second last row?

0

@srestha mam Ans should be: None of these ?

$E$

$\underline{T}$

$\underline{F}$

$\underline{(E)}$

$(\ \underline{E+T}\ )$

$(\ {E+\underline{T*F}}\ )$

$(\ {E+T*\underline{id}}\ )$

$(\ {E+\underline{F}*id}\ )$

$(\ {E+\underline{id}*id}\ )$

$(\ {\underline{T}+id*id}\ )$

$(\ {\underline{F}+id*id}\ )$

$(\ {\underline{id}+id*id}\ )$

0

yes, all four options are wrong

a) should be $(E+T*$

@Kushagra गुप्ता

0

HOW E+F* is a viable Prefix?

a viable prefix is the prefix of the right sentential form that appears on the parser stack

But E+F* will never appear on the stack

as before pushing/shifting " * " on to the stack we would have the F in to T to give E+T  , so why is every one trying to justify the wrong answer?

the correct answer should be "(E+T* " is a viable prefix i.e the options itself are wrong.

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.7k 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 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 point. E -> T -> F -> (E) -> (E+T) -> (E+T*F) -> (T+T*F) -> (F+T*F) -> (F+F*F) -> (id+F*F) -> (id+id*F) -> (id+id*id (Bold part is a handle) Now, by the definition of Viable Prefix for right sentential form (E+T*F) , where T*F is a handle, any prefix of this (E+T*F) is a viable prefix i.e. E+T* is a viable prefix Answer is a by Junior (577 points) 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*idE\underline{E*E}E*\underline{id}\underline{E+E}*idE+\underline{id}*id\underline{id}+id*id$by Active (2k points) edited 0 votes First check the handles$\left ( id+id*id \right ),id\left ( F+id*id \right ),F\left ( T+id*id \right ),T\left ( E+id*id \right ),id\left ( E+F*id \right ),F\left ( E+T*id \right ),id\left ( E+T*F \right ),T*F\left ( E+T \right ),E+T\left ( E \right ), \left ( E \right )F,FT,TE$So, handles are$\left (id,F,T,T*F,E+T,\left ( E \right ) \right )$Now, check viable prefix$.\left ( id+id*id \right )\left (. id+id*id \right )\left ( id.+id*id \right )\left ( F.+id*id \right )\left ( T.+id*id \right )\left ( E.+id*id \right )\left ( E+.id*id \right )\left ( E+id.*id \right )\left ( E+F.*id \right )\left ( E+T.*id \right )\left ( E+T*.id \right )\left ( E+T*id. \right )\left ( E+T*F. \right )\left ( E+T. \right )\left ( E. \right )\left ( E \right ).F.T.E$Viable Prefix are$(, (id,(F,(T,(E,(E+,(E+id,(E+F,(E+T,(E+T*,(E+T*id,(E+T*F,(E+T,(E,(E),F,T,E\$

by Veteran (117k points)

+1 vote