We talk about handles when we talk about bottom-up parsing. Bottom-up parsing during a left-to-right scan of the input constructs a rightmost derivation in reverse. Informally, a handle is a substring that matches the body of a production, and whose reduction represents one step along the reverse of a rightmost derivation.
In other words, handles are substrings of sentential forms:
- A substring that matches the right hand side of a production
- Reduction using that rule can lead to the start symbol
- The rule forms one step in a rightmost derivation of the string
The most common bottom-up parsers are the shift-reduce parsers. These parsers examine the input symbols and either shift (push) them onto a stack or reduce elements at the top of the stack, replacing a right-hand side by a left-hand side. A shift-reduce parser is most commonly implemented using a stack, where we proceed as follows:
start with an empty stack
a "shift" action corresponds to pushing the current input symbol onto the stack
a "reduce" action occurs when we have a handle on top of the stack. To perform the reduction, we pop the handle off the stack and replace it with the nonterminal on the LHS of the corresponding rule.