GATE2005-59

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

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

selected
0

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

9

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 ??
6

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

@rishi71662data4

from where you get that definition ?

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$

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.

3

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 ..!

0

@Mk Utkarsh

thanks for such a detailed answer.

1
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.

Ans- (D)

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

ans d)
8

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

Related questions

1
6.4k views
The grammar $A \rightarrow AA \mid (A) \mid \epsilon$ is not suitable for predictive-parsing because the grammar is: ambiguous left-recursive right-recursive an operator-grammar
Consider the following expression grammar. The semantic rules for expression evaluation are stated next to each grammar production. ... to $7$ Precedence of $+$' is higher than that of $\times$', and both operators are left associative; expression is evaluated to $9$
Consider line number $3$ of the following C-program. int main() { /*Line 1 */ int I, N; /*Line 2 */ fro (I=0, I<N, I++); /*Line 3 */ } Identify the compiler’s response about this line while creating the object-module: No compilation error Only a lexical error Only syntactic errors Both lexical and syntactic errors
Consider the grammar: $S \rightarrow (S) \mid a$ Let the number of states in SLR (1), LR(1) and LALR(1) parsers for the grammar be $n_1, n_2$ and $n_3$ respectively. The following relationship holds good: $n_1 < n_2 < n_3$ $n_1 = n_3 < n_2$ $n_1 = n_2 = n_3$ $n_1 \geq n_3 \geq n_2$