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

2 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.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}*id$

$E+\underline{id}*id$

$\underline{id}+id*id$

by Active (1.9k points)
edited by

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,648 questions
56,459 answers
195,335 comments
100,186 users