The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+12 votes
1.6k views

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.5k points) | 1.6k views
0
Can you make it clear how is this a right most derivation?

3 Answers

+23 votes
Best answer
n+n*n

E+n*n

E*n

E

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

So, answer is D
answered by Boss (31.4k points)
selected by
0

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

+4

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

n+n*n

n+n*E

n+E

E

--

I maybe wrong, correct me

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

n+n*n

n+n*E

n+E

E

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

0
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 ??
+1

 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 Active (5.2k points)
0 votes

Ans- (D)

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

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

38,112 questions
45,619 answers
132,311 comments
49,295 users