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

VERY CLEAR EXPLANATION @JashanArora

---

very nice explanation. thanks bro

---

@JashanArora
I wish every answer on this website, is as clear and easy to understand as yours :)

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.