The Gateway to Computer Science Excellence
+2 votes
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
in Compiler Design by Boss (25.5k points)
retagged by | 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

instead of

“E+F ∗” is a viable prefix.

+1

@ LeenSharma 

@ Shubhanshu

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

@newdreamz a1-z0 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}\ )$

 

Ref: https://gateoverflow.in/70738/madeeasy-test-series-compiler-design-viable-prefix

0

yes, all four options are wrong

a) should be $(E+T*$

@Kushagra गुप्ता

check answered

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.

4 Answers

+10 votes
Best answer

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*id$


$E$

$\underline{E*E}$

$E*\underline{id}$

$\underline{E+E}*id$

$E+\underline{id}*id$

$\underline{id}+id*id$

by Active (2k points)
edited by
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,F$

$T,T$

$E$

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)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,596 answers
195,824 comments
102,073 users