The Gateway to Computer Science Excellence
+8 votes
908 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 (7k points) | 908 views

4 Answers

+25 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 (36.5k 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.4k 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 (4.1k points)
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

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,737 questions
57,292 answers
198,229 comments
104,909 users