The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+21 votes

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

asked in Compiler Design by Veteran (68.8k points) | 1.7k views

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

2 Answers

+36 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.

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

answered by Veteran (30.5k points)
edited by

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

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.

+10 votes
Answer is (D)

Handle is a substring of sentential form from which the start symbol can be reached using reduction at each step.
answered by Boss (6.3k 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

32,619 questions
39,267 answers
36,653 users