Chapter 4, Problem 21RQ

Explanation of Solution

Handle of a sentential form:

A bottom up parser attempts for a reduction from right hand side of right sentential form ($\gamma$) by replacing the right most sub-string (assume it be $\beta$) of terminals and non-terminals. From the grammar rule the most appropriate rule with $\beta$ on RHS is to be selected. The correct RHS is called handle.

• A handle of a sentential form is a substring $\beta$ such that, $\beta$ matches with a rule A $\beta$ in the grammar and replacing $\beta$ with A is a step in the reverse of the right most derivation of a string.
• The formal definition of a handle can be given as: For a right sentential form $\gamma =\alpha \beta w$, $\beta$ is the handle if and only if $\text{S }\Rightarrow </$