search
Log In
8 votes
1.5k views
Consider the following Grammar :

S -> ZZ

Z -> xZ|y

Which of following represent a handle in the generation of the string "xxxyxy" ?

A.  ZxZ

B.  Zxy

C.  xZxy

D.  xZ

 

Please explain little about handles too i have little doubt in it. And do explain difference between viable prefix and Handle Please :)
in Compiler Design 1.5k views

4 Answers

30 votes
 
Best answer

A right-sentential form is a sentential form that occurs in the rightmost derivation of some sentence.

String , handle

$xxxyxy$ , y

$xxxZxy$    , xZ 

$xxZxy$ , xZ

$xZxy$ , xZ

$Zxy$ , y

$ZxZ$ , xZ

$ZZ$ , ZZ

$S$

So Handles are y, xZ and ZZ. Hence option D is correct

Viable prefix : viable prefix of a right-sentential form is a prefix which does not extend beyond that form's handle.

The prefixes of right sentential forms that can appear on the stack of a shift reduce
parser are called viable prefixes.

Handle :  it's the sequence of symbols that resulted from the most recently expanded nonterminal.

 

Let's find out all viable prefixes in this question,

We'll parse $xxxyxy$

$.xxxyxy$

$x.xxyxy$

$xx.xyxy$

$xxx.yxy$

$xxxy.xy$

$xxxZ.xy$

$xxZ.xy$

$xZ.xy$

$Z.xy$

$Zx.y$

$Zxy.$

$ZxZ.$

$ZZ.$

$S.$

Let set of viable prefix be $L$,

$L = \left \{ x,xx,xxx,xxxy,xxxZ,xxZ,xZ,Z,Zx,Zxy,ZxZ,ZZ,S \right \}$

 

 


selected by
0
@Mk Utkarsh

what is sentinal means?

how u got xZ as handle here?

xxxZxy    , xZ
2

sentential form is a string which can contain both terminals and non-terminals, a string of terminals and non terminals can be called sentential form iff it can be derived from start symbol.

Suppose that our current sentential form is $αγω$, where $γ$ is the handle and A → γ is a production rule.

After reducing $γ$ back to A, we have the string $αAω$

In $αγω$ our handle was $γ$ because this was reduced to A by a production.

1
but u started from middle y

why not from first symbol or last symbol of string?
5
we pushed all strings till top of stack became handle, but we were unable to find till we pushed $xxx\color{red}{y}$

$x$

$xx$

$xxx$

these are not handles
0
yes , thanks, got it :)
2

this is the best and clear explanation on viable prefix. easy to understand. thanks for your answer 

1
really such a beautiful explanation on this concept 🤩
0

Thanks! @Mk Utkarsh

0
Can null be a viable prefix? Also are viable prefix and handles defined for Left most derivations?
0
"Handles will be always be a string of terminals+NonTerminals which appears on the RHS of a production rule". Is this statement correct?
0 votes
Answer is d.

When we reduce RHS to LHS of a production then RHS of the production is called handle.

If we've a production A -> xyz, then when we reduce xyz to A, So xyz is a handle here.

In this question, only xZ can be a handle
0
handle does bottom up parsing

How xZ will do bottom up parsing?
0
It's not like handle does parsing.

BUP means we start from the string and reduce it to start symbol.In this process of reduction , we'll reduce xZ to Z hence xZ is a handle.
0 votes
Answer is d.

When we reduce RHS to LHS of a production then RHS of the production is called handle.

If we've a production A -> xyz, then when we reduce xyz to A, So xyz is a handle here.

In this question, only xZ can be a handle
0 votes

$Handles=\{y,xZ,ZZ\}$

$Viable\ prefixes=\{x,xx,xxx,xxxy,xxxZ,xxZ,xZ,Z,Zx,Zxy,ZxZ,ZZ\}$


$S$

$\underline{ZZ}$ : $VP=\{Z,ZZ\}$

$Z\underline{xZ}$ : $VP=\{Z,Zx,ZxZ\}$

$Zx\underline{y}$ : $VP=\{Z,Zx,Zxy\}$

$\underline{xZ}xy$ : $VP=\{x,xZ\}$

$x\underline{xZ}xy$ : $VP=\{x,xx,xxZ\}$

$xx\underline{xZ}xy$ : $VP=\{x,xx,xxx,xxxZ\}$

$xxx\underline{y}xy$ : $VP=\{x,xx,xxx,xxxy\}$

 

0

@`JEET @Satbir @chirudeepnamini @Lakshman Patel RJIT

Can someone do the clarification that whether this approach is right or wrong and please check at each step whether the viable prefixes written from bottom to top are right or wrong.

Related questions

0 votes
0 answers
1
437 views
For the grammar S ------> 0 S 1/ 0 1 indicate the handle in each of the following right-sentential forms a) 000111 . b ) 00S11 . Also for the grammar S ----->S S + / SS * / a indicate the handle a) SSS + a * + . b ) SS + a * a+.
asked Oct 3, 2017 in Compiler Design set2018 437 views
1 vote
0 answers
2
145 views
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 145 views
2 votes
2 answers
4
...