The Gateway to Computer Science Excellence
+21 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$

in Compiler Design by Veteran (52.2k points) | 3k views
Can you make it clear how is this a right most derivation?

5 Answers

+31 votes
Best answer
  • $\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

by Boss (31.4k points)
selected by

here handles in the right-sentential form means steps of reductions in Bottom up Parser??


The right sentential form is the sentential form in which the input string when parsed from right-to-left and reduced whenever possible would give final output as the start symbol

According to above defination, should not we parse the string from right to left, like this






I maybe wrong, correct me

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





I am getting this too. How is it you're getting a different order?

How can we say that X has higher precedence than + ?

on scanning the stack symbol we need to select the appropriate Handle. The grammar is left recursive and + and X has the same precedence.

then why are you reducing * first ??

 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.



from where you get that definition ?


+14 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 \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$


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$
by Boss (36.6k points)
edited by

u have taken n*n+n  string in the beginning, but u have derived n+n*n;

pls check whether u have written it correctly or not, bcause am not getting your solution due to that line


Gate Fever edited thanks


Mk Utkarsh, pls tell me why u solved n*n+n ; when actual (given ) string is n+n*n


got it!!
Nicely explained



I think here leftmost derivation instead of right most derivation in your answer$?$

Deriving the above string with rightmost derivation,


$E \times n$

$E + n \times n $

$n + n \times n$


 it is rightmost derivation check again


@Mk Utkarsh

You replace left most variable, so how it is right most derivation.


Left one is left most derivation and right one is right most derivation. you can check answer given above


ohh sorry

Now I got it


for LMD & RMD can go here ..!


@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.
+2 votes

Ans- (D)

To know more about handles:

by (297 points)
0 votes
ans d)
by Loyal (5.2k points)
your answers are some of most useless answers on GO
0 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 

by Loyal (7k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,388 answers
105,416 users