Log In
3 votes
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
retagged by

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.


@ LeenSharma 

@ Shubhanshu

this is a good link for viable prefix

chk once


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

it will derive like


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

So, I think a) shouldnot be answer

Instead C) should be ans

@srestha It will go like this 

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













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

T*F is one of the handle,rt?

then why it couldnot be a viable prefix?

T*F is one of the handle,rt?


then why it could not be a viable prefix?

Why it should be??


Acc to this question

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. 


yes, that is correct :)

but chk again


(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?


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?



@newdreamz a1-z0 Why are you not reducing (E+T  to (E in the second last row?


@srestha mam Ans should be: None of these ?





$(\  \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}\ )$




yes, all four options are wrong

a) should be $(E+T*$

@Kushagra गुप्ता

check answered


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

12 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  }

selected by

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



id,is the handle so it is viable prefix.

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

          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

 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 


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

0 votes


$Viable\ prefixes=\{id,E,E+,E+id,E+E,E+E*,E+E*id,E+E*E\}$













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




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 (*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 ).$




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$

Mam, can you please explain the following:

In the 6th Line: (E + T * id), id

Why is "T" not considered as the handle? why did you take "id" as the handle?

Related questions

1 vote
0 answers
Describe all the viable prefixes for the following grammars: The grammar $S\rightarrow 0S1\mid 01$ of Question $4.2.2(a)$. The grammar $S\rightarrow SS+\mid SS\ast\mid a$ of Question $4.2.1$. The grammar $S\rightarrow S(S)\mid \epsilon$ of Question $4.2.2(c)$.
asked Aug 20, 2019 in Compiler Design Lakshman Patel RJIT 115 views
2 votes
2 answers
1 vote
0 answers
I have one doubt regarding getting viable prefixes for a grammar. Suppose I am given a grammar G which is told to be LR(0).I have observed, if I draw LR(0) DFA for it, and see if there is a path labeled $\gamma$ from initial state to some state of DFA, ... first check directly for LR(1)? I want a good process to give me viable prefix in a reasonable amount of time and accurate answer. Pleas help.
asked Dec 12, 2018 in Compiler Design Ayush Upadhyaya 147 views
0 votes
1 answer
I am confused in the Concept of Handles in right sentential form and Viable Prefix. Can Please anybody explain these two concepts Briefly using Examples :)
asked Jun 8, 2018 in Compiler Design Na462 404 views