Understanding $\text{handle}$ in parsing problem

Originally https://math.stackexchange.com/questions/22614/help-understand-texthandle-in-parsing-problem but unaswered there

The BNF is defined as followed:

S -> aAb | bBA
A -> ab | aAB
B -> bB | b

The sentence is:

aaAbBb

And this is the parse tree: Phrases: aaAbBb, aAbB, bB
Simple Phrases: bB
Handle: ?

From the book, handle is defined as followed: B is the handle of the right sentential from $y = aBw$ if and only if:
$S \to_{rm} \cdot aAw \to_{rm} aBw$

So in my case, what's the handle? Any idea?

• What book? What is the handle supposed to do? What are $a$ and $w$? As it stands, there does not necessarily exist a handle because it requires a chain rule (which your example grammar does not have). – Raphael Mar 13 '12 at 7:21
• Not every parsing strategy makes use of a “handle”. Which parsing strategy is used here? – uli Mar 13 '12 at 8:10

I'll assume you talk about the 'handle' as often defined in the context of LR-parsing. I'm not entirely sure if the definition you use is the proper definition: $A$ and $B$ seem to stand for nonterminals, but $B$ should really stand for some string of terminals and nonterminals (as the right hand side of a production of $A$, to be precise) to have a proper meaning.

Let's parse your example using LR machinery, and illustrate what happens. In particular, we'll find multiple handles during the parse. The dot '$\bullet$' will show where in the parse we are at the moment. We're looking for suffixes of the part to the left of the bullet that exactly match productions of our grammar.

• $\bullet aaAbBb$ - we're starting at the beginning.
• $a \bullet aAbBb$ - moving on, '$a$' is not a handle as it is not a production.
• $aa \bullet AbBb$ - moving on, '$aa$' or '$a$' is not a handle as it is not a production.
• $aaA \bullet bBb$ - '$A$', '$aA$' and '$aaA$' are not productions.
• $aaAb \bullet Bb$ - '$b$' and '$aAb$' are candidate handles (they are right-hand sides of productions), but your parse tree shows that neither gets reduced, so we ignore them.
• $aaAbB \bullet b$ - '$bB$' is a handle! We reduce it to $B$.
• $aaAB \bullet b$ - '$aAB$' is a handle! We reduce it to $A$.
• $aA \bullet b$ - '$A$' and '$aA$' are not productions.
• $aAb \bullet$ - '$aAb$' is a handle! We reduce it to $S$.
• $S \bullet$ - Oh hey, we're done: the input was part of the grammar.
• Does LR parsing not reduce whenever it can? I assume to chose not to in order to fit the example? – Raphael Mar 14 '12 at 7:04
• @Raphael: they need not reduce a candidate handle if their lookahead or left context predicts that this is not the right handle. As there are no LR automatons or tables given in this example, my example follows the derivation as given in the question. – Alex ten Brink Mar 14 '12 at 15:12

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:

1. A substring that matches the right hand side of a production
2. Reduction using that rule can lead to the start symbol
3. 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: