The Gateway to Computer Science Excellence
+7 votes
780 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 by Loyal (6.9k points) | 780 views

4 Answers

+23 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 \}$

 

 

by Boss (35.7k points)
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
by Active (3.3k points)
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
by (163 points)
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\}$

 

by Active (1.9k points)
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,644 questions
56,503 answers
195,553 comments
101,039 users