The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+12 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 (69k points) | 1.2k views
Can you make it clear how is this a right most derivation?

3 Answers

+23 votes
Best answer





 string in red indicates handle here

so ans is d


answered by Veteran (34.3k 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.

0 votes
ans d)
answered by Boss (5.1k points)
–1 vote

Ans- (D)

To know more about handles:

answered by (239 points)

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

33,646 questions
40,193 answers
38,664 users