The Gateway to Computer Science Excellence
+36 votes
4.8k views

Which of the following describes a handle (as applicable to LR-parsing) appropriately?

  1. It is the position in a sentential form where the next shift or reduce operation will occur

  2. It is non-terminal whose production will be used for reduction in the next step

  3. It is a production that may be used for reduction in a future step along with a position in the sentential form where the next shift or reduce operation will occur

  4. It is the production $p$ that will be used for reduction in the next step along with a position in the sentential form where the right hand side of the production may be found

in Compiler Design by | 4.8k views
+15

While parsing a string from a grammar using LR parser (bottom-up parser) when we encounter a reduce move(ri) in the parsing table,

           1) we pop-off 2*x elements (x grammar symbols and x state symbols) from the stack where x is length of RHS of production rule (denoted by ri in our parsing table) 

           2) and we push the LHS of the production rule (which production rule ? the production rule denoted by ri in our parsing table)

Now the x grammar-symbols we popped-off from the stack is called as HANDLE ...

0

@Vicky rix

Why you have written "pop-off 2*x elements"? It should be x elements only and whose size is equal to RHS of any given production rule. 

0

Handle is neither a non-terminal, nor is it used to decide when to shift. Options A, B, C are eliminated straight.

But it's necessary to know why Option D is correct.


In bottom up parsing, we begin with a string and we systematically reduce the string to just a single symbol (the Start symbol). It would be stupid to randomly reduce the literals you see, so we should identify which specific literals or set of literals to reduce, such that eventually we'll get back the Start symbol.

These reductions are called handles. We only want to reduce at handles.

All the strings that we encounter up to the point we reach a handle are called viable prefixes.

 

Given $S \rightarrow Ab; A \rightarrow c$ for the string $cb$

We can say $c$ is a handle (for convenience), or we can also say $A \rightarrow c$ is a handle.

Hence, saying that handle is a substring or saying that handle is a production — both are correct.

 

$A \rightarrow c$ is a handle. We reduce at it. We get $Ab$. Now, we can reduce $Ab$ to $S$ and hence, we reach the start symbol.

Both the productions in this grammar are handles. This was a primitive example. Complex grammars might have many reductions as handles, and many not.

 

To evaluate that a substring can be formed out of a grammar in BUP, we do "handle pruning". In fact, the whole idea of BUP revolves around it. (That DFA construction, GoTo and Action table — all that is handle pruning).

Parsing is a method of identifying handles.


Standard references:

1

2

3

2 Answers

+58 votes
Best answer

sentential form is the start symbol $S$ of a grammar or any string in $(V \cup T)*$ that can be derived from $S$.

Consider the linear grammar

$(\{S, B\}, \{a, b\}, S, \{S  \rightarrow aS, S  \rightarrow B, B  \rightarrow bB, B  \rightarrow \lambda \})$.

A derivation using this grammar might look like this:

$S \Rightarrow aS \Rightarrow aB \Rightarrow abB \Rightarrow abbB \Rightarrow abb$
 

Each of $\{S, aS, aB, abB, abbB, abb\}$ is a sentential form.

Because this grammar is linear, each sentential form has at most one variable. Hence there is never any choice about which variable to expand next.

Here, in option D the sentential forms are same but generated differently coz we are using here Bottom Up production.

Handle:
for example the grammar is:

$$\begin{align*} E &\rightarrow E+n\\ E &\rightarrow E*n\\ E &\rightarrow n \end{align*}$$

then say to derive string $n+n*n$:

these are three different handles shown in $3$ different colors = $\left\{ n, E+n, E*n \right \}$

that's what option D says

by
edited by
0

Here, in option D the sentential forms are same but generated differently coz we are using here Bottom Up production.  

What is the meaning of this line ??

+3

When we are taking second example; then we are doing bottom up parsing and obtaining Handles as well as we can see the Sentential forms getting generated.

But in the first example we start from the start symbol S and then do top-down parsing to obtain string. Here in this case Sentential forms are generated in contrast to the following next example.

+1
infinite up votes +
nice answer :)
+2
@pC Why c) option not correct?
+17
In simple words , handle is a production or a sub-string of right sentential form , which is reduced as soon as encountered in stack while parsing . Because no viable prefix can pass(is more than) a handle.

Now option c , says production is used for reduction in future that means it is allowing shift operation even after encountering a handle . So not correct.
+95
The term "position" means handle is position dependent. Here in string $n+n*n$, there are three $n$'s but only first $n$ is handle and others not.
Handle is not any arbitrary symbol that matches to right hand side of any non-terminal, it has very special property, That is- after reduction we must eventually reach to Start symbol.
eg- Grammar:

$\begin{align*} E \rightarrow E+n\\ E\rightarrow E*n\\ E \rightarrow n \end{align*}$
String: $n+n*n$, first we encounter $n$ and we $\;reduce\;$ it: $E.+n*n$
Now we encounter $+$ we shift (no option for reduce) :  $E+.n*n$
next we encounter $n$  :  $E+n.*n$, now we have 2 cfoices for reduction, either we reduce this $n$ (ofcourse middle $n$) to $E$ or we reduce $E+n$ to $E$.
Here notice that, If we reduce $n$ to $E$ then we get: $E+E*n$ and from here we can never reach to start symbol. therefore middle $n$ is not handle and If we reduce $E+n$ to $E$ then we will eventually reach start symbol. hence $E+n$ is handle.
This explanation shows that handles are reductions which are GUARANTEED to reach start symbol.
Now, you might argue that, why we do parsing and all...Once we know handles, just reduce them and get the starting symbol (as they guarantees to reach start symbol).
My counter question here is, "How will u find handles" ?
And answer of this question is parsing.
Goal of bottom-up parsers is to find handles only. Some parsers are strong enough that they can recognize all handles and some parsers can't.
0
nice explanation @sachin :D
0
NICE
0

Guys I barely see any opton properly imitate essence of any of following definitions:

  1. Informal definition: handle is reduction that allows further reduction back to the start symbol
  2. Formal definition:
    Assume rightmost derivation 
    $S\rightarrow^* \alpha  X \omega\rightarrow^* \alpha  \beta\omega$ 
    then, $\alpha  \beta$ is a handle of $\alpha  \beta \omega$

Selected option id D, which says "it is the production ....". But as can be seen from the definitions above, its not a production.

0
nice explanation sachin sir
0
thank u so much sir..
0

Please, Can someone elaborate Option C

+13 votes
Answer is (D)

Handle is a substring of sentential form from which the start symbol can be reached using reduction at each step.
by
Answer:

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
52,345 questions
60,497 answers
201,862 comments
95,319 users