2.7k 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$

| 2.7k views
0
Can you make it clear how is this a right most derivation?

• $\color{red}{n}+n*n$
• $\color{red}{E+n}*n$
• $\color{red}{E*n}$
• $E$

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

by Boss (31.2k points)
selected
0

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

+7

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 ??
+4

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.

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

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

0

Gate Fever edited thanks

0

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

0
got it!!
0
Nicely explained

Thanks
0

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

Deriving the above string with rightmost derivation,

$E$

$E \times n$

$E + n \times n$

$n + n \times n$

0

it is rightmost derivation check again

0

@Mk Utkarsh

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

+1 https://cs.stackexchange.com/questions/54814/different-between-left-most-and-right-most-derivation Left one is left most derivation and right one is right most derivation. you can check answer given above

0
ohh sorry

Now I got it

Thanks
0

for LMD & RMD can go here ..!

Ans- (D)

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

by (297 points)
ans d)
by Loyal (5.2k points)
+6