GATE CS 2005 Q59 — Parsing (LL, LR)

In bottom-up parsing, a handle is a substring that matches the right-hand side of a production rule, and whose reduction to the non-terminal on the left-hand side represents one step along the reverse of a rightmost derivation.

To find the handles, let us first construct the rightmost derivation (RMD) for the input string $n + n \times n$ using the grammar:

The rightmost derivation is as follows:

1. $E \Rightarrow E \times n$    (replacing the start symbol $E$ with $E \times n$)
2. $\Rightarrow E + n \times n$    (replacing the rightmost non-terminal $E$ with $E + n$)
3. $\Rightarrow n + n \times n$    (replacing the rightmost non-terminal $E$ with $n$)

The bottom-up reduction process is the exact reverse of the rightmost derivation:

Thus, the handles in the successive reduction steps are $n$, $E + n$, and $E \times n$.