Handles in Right-Sentential Forms for Grammar $E \to E + E \mid E * E \mid id$

In bottom-up (shift-reduce) parsing, the parser repeatedly reduces a substring that is a handle of the current right-sentential form . Intuitively, a handle is exactly the piece of the current sentential form that was produced most recently by a rightmost derivation; reducing it simulates reversing that last derivation step. This “rightmost derivation in reverse” viewpoint is standard in LR parsing theory. In LR parsing, the notion is formalized by splitting a right-sentential form into $\alpha \beta \gamma$, where $\beta$ is the handle and $\alpha$ is the viable prefix context.

For the grammar:

and the input string:

we will find the handles of the right sentential forms that appear during the reduction sequence for that specific string. The key idea is: each reduction replaces the RHS $\beta$ by its LHS $A$ in one step, so the handle is the $\beta$ that matches some production $A \to \beta$.

Keyword anchors

• handle
• right-sentential form
• rightmost derivation
• viable prefix

These terms are tightly connected: LR parsing uses viable prefixes built from right-sentential forms, and a reduction occurs when the handle (RHS of a production) can be reduced to the corresponding nonterminal.

Compute the reduction sequence for $id + id * id$

A right-sentential form $\gamma$ is reduced by choosing a substring $\beta$ such that $\beta$ is the RHS of some production $A \to \beta$, and replacing $\beta$ with $A$ in $\gamma$. The handle is precisely that $\beta$.

We will use the natural operator structure implied by the grammar reductions for the specific input:

• $id * id$ forms one $E$
• then $id + E$ forms another $E$

We list the right sentential forms during the bottom-up reduction, from terminals toward the start symbol $E$. (This is the reverse of a rightmost derivation.) The handles are marked at each step.

The handles (explicitly stated)

A clean way to present handles is to write a concrete bottom-up reduction chain (each step reduces one handle $\beta$ to its $A$):

Consider the following reduction sequence (each “$\Rightarrow$” is one reduction step):

1. $id + id * id$

   • handle: $\boxed{id}$ using production $E \to id$
   • result: $E + id * id$

2. $E + id * id$

   • handle: $\boxed{id}$ (the left operand of $*$) using $E \to id$
   • result: $E + E * id$

3. $E + E * id$

   • handle: $\boxed{id}$ (the right operand of $*$) using $E \to id$
   • result: $E + E * E$

4. $E + E * E$

   • handle: $\boxed{E * E}$ using $E \to E * E$
   • result: $E + E$

5. $E + E$

   • handle: $\boxed{E + E}$ using $E \to E + E$
   • result: $E$

Thus, the handles of the right sentential forms during the reduction are, in order:

This matches the LR “reduce the handle” idea: at each step, the handle is the RHS of a production that can be reduced in reverse of a rightmost derivation.