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?

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.

StackExchange Computer Science Q#290, answer score: 4