GATE CSE 2008 | Question: 11

Question

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

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

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

• C. 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

• D. 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

Comments

https://gateoverflow.in/244291/Handle-grammar?show=365479#c365479 good read

---

Handle is something that we can reduce to get  the symbol on the right hand side 
NOTE:Here shifts not allowed  so ruling out option c and paving way for D

---

VERY CLEAR EXPLANATION @JashanArora

Answer 1

A 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

Comments

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 ??

---

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.

---

infinite up votes +
nice answer :)

---

@pC Why c) option not correct?

---

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.

---

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.

---

nice explanation @sachin :D

---

NICE

---

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.

---

nice explanation sachin sir

---

thank u so much sir..

---

Please, Can someone elaborate Option C? 

---

@ayushsomani Because of the “Shift” word.

---

nice explanation

---

awsm explanation sachin sir.

Answer 2

Answer is (D)

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

Answer 3

It is the production 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 LR-parsing, a handle is a substring of the right-hand side of a production that matches the right end of the current stack contents. The reduction operation is applied using this handle to replace the matched substring with the non-terminal on the left-hand side of the production. The position in the sentential form indicates where the right-hand side of the production may be found.