16,008 views
34 votes
34 votes

Consider the grammar:

$$E \rightarrow E + n \mid E \times n \mid n$$

For a sentence $n + n \times n$, the handles in the right-sentential form of the reduction are:

  1. $n, E + n$ and $E + n \times n$

  2. $n, E + n$ and $E + E \times n$

  3. $n, n + n$ and $n + n \times n$

  4. $n, E + n$ and $E \times n$

5 Answers

Best answer
46 votes
46 votes
  • $\color{red}{n}+n*n$
  • $\color{red}{E+n}*n$
  • $\color{red}{E*n}$
  • $E$

String in $\color{red}{\text{RED}}$ indicates handle here

So, answer is D

selected by
29 votes
29 votes

A right-sentential form is a sentential form that occurs in the rightmost derivation of some sentence.

 $E \rightarrow E + n \mid E \times n \mid n$

$n + n \times n$

Deriving the above string with rightmost derivation,

$E$

$E \times n$

$E + n \times n $

$n + n \times n$

But right sentential form is the reverse of rightmost derivation,

$n + n \times n$

$E + n \times n$

$E \times n$

$E$

but why reverse?

While pushing terminals to the stack, handles appear at the top of stack which are reduced with appropriate production,

In this question n is pushed then reduced to E, so n is a handle, next + will be pushed oops no match,

next n will be pushed, Stack elements $E + n$ , where $n$ is on the top

This is a handle which will be reduced by $E \rightarrow E +n$

Now stack contents are $E$

pushed $ \times $ and $n$

Elements in stack are, $E \times n$, where n is on the top

$E \times n$ is a handle and will be reduced with $E \rightarrow E \times n$.

So we got 3 handles in this reduction,

  1. $n$
  2. $E \times n$
  3. $E + n$
edited by
1 votes
1 votes

A handle is a point of reduction that allows further reductions back to the start symbol.

Here, if you make the parse tree of the given string, you'll find that at each level you're reducing something to a variable, and that sequence leads you back to E (the Start Symbol)

 

This "something" is a handle (We only reduce at handles in Bottom Up Parsing)

 

At Arrow 1, n is a handle.

At Arrow 2, E + n is a handle.

At Arrow 3, E * n is a handle.

 

Option D

 

PS: As far as I know, handle is also called a final item 

Answer:

Related questions

37 votes
37 votes
4 answers
1
Kathleen asked Sep 22, 2014
23,300 views
The grammar $A \rightarrow AA \mid (A) \mid \epsilon$ is not suitable for predictive-parsing because the grammar is:ambiguousleft-recursiveright-recursivean operator-gram...
31 votes
31 votes
2 answers
2
go_editor asked Nov 27, 2016
11,371 views
Consider the following expression grammar. The semantic rules for expression evaluation are stated next to each grammar production.$$\begin{array}{l|l} E\rightarrow numbe...
24 votes
24 votes
2 answers
4