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

While parsing a string from a grammar using LR parser (bottom-up parser) when we encounter a reduce move(r_i) 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 r_i in our parsing table) 

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

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

---

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

---

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

---

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

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