GATE CSE 2005 | Question: 59

Question

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:

• A. $n, E + n$ and $E + n \times n$

• B. $n, E + n$ and $E + E \times n$

• C. $n, n + n$ and $n + n \times n$

• D. $n, E + n$ and $E \times n$

Comments

Can you make it clear how is this a right most derivation?

---

Easiest, Detailed Explanation of Handles and Viable Prefixes, with the solution of this GATE 2005 Question :

https://youtu.be/0q1BEXFUaBE

Answer 1

• $\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

Comments

 Arpit Dhuriya  Derive the given string using right most derivation. This will give you steps of how to obtain the string from the given grammar. After that follow the derivation in reverse order; you'll see that as you climb up the steps of derivation - some part of the string in step i will reduce to a one of the LHS of the given grammar in the step i-1. The reductions which you are making in each step while going up are called the "right sentential form of reductions".

This is how bottom up parsers work. They start from a given string and reduce it to start symbol. Sentential form is a fancy name for the intermediate results you obtain in the process. Also, this is why bottom-up parsers are known to use "reverse of RMD" and not just RMD.

---

@rishi71662data4

from where you get that definition ?

 

---

If you don’t understand the answer then read this, it clears this concept beautifully.

https://gatecse.in/viable-prefixes-and-handle-in-lr-parsing/

Answer 2

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$

Comments

for LMD & RMD can go here ..!

https://www.youtube.com/watch?v=u4-rpIlV9NI

---

@Mk Utkarsh

thanks for such a detailed answer.

can you explain what will be answer if asked about left most derivation instead of right most derivation.?

---

Handles are only a term used for Bottom up parsing. In SR parsers we shift and then reduce so handle comes into picture when reduction is done.

Answer 3

Ans- (D)

To know more about handles: https://gateoverflow.in/409/gate2008-11

Answer 4

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