13,330 views
59 votes
59 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

3 Answers

Best answer
81 votes
81 votes

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

edited by
17 votes
17 votes
Answer is (D)

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

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.

Answer:

Related questions

37 votes
37 votes
3 answers
1
Kathleen asked Sep 12, 2014
15,661 views
An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only ifThe SLR(1) parser for G has S-R conflictsThe LR(1) parser for G has S-R conflictsThe...