The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+13 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$

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

5 Answers

+23 votes
Best answer




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

So, answer is D
answered by Boss (31.9k 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.

+3 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$
answered by Boss (29.3k 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!!
0 votes
ans d)
answered by Loyal (5.3k points)
your answers are some of most useless answers on GO
0 votes

Ans- (D)

To know more about handles:

answered by (269 points)
0 votes
Handles in Shift Reduce Parsing (Bottom Up Parsing), Solved Example [GATE-2005, Que 59]
answered ago by (395 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

44,199 questions
49,669 answers
65,818 users