# Help understand $\text{handle}$ in parsing problem

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 ->_{rm} \cdot aAw ->_{rm} aBw$

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

Thanks,
Chan

• Does this go here, or on cstheory.stackexchange.com? Feb 18, 2011 at 2:40
• @Orbling It's not at a high enough level to belong cstheory, but it doesn't seem correct for this site either. Feb 18, 2011 at 2:42
• @Brandon Carter: I don't like there being a level requirement on the sites, unless they are specific overflow in the upwards direction. If it is not suitable for cstheory, then perhaps SO or maybe programmers? Problem is, it uses MathJaX, which only works here... :-/ (for some ungodly reason!) Feb 18, 2011 at 2:46
• @Yuval Filmus: I really hope cstheory will open a section for newbies, since the CS theory is not easy to be self-taught, plus , why limits it to only graduate level.
– Chan
Feb 18, 2011 at 4:58
• I have cross-posted this question onto cs.stackexchange.com/questions/290/… which is probably a better SE for these types of questions, and as an effort to seed the site which is currently in private beta with useful content. Mar 13, 2012 at 6:59

The rightmost derivation of $aaAbBb$ is
$$\underline{S}\Rightarrow\color{red}{a\underline{A}b}\Rightarrow a\color{green}{aA\underline{B}}b\Rightarrow aaA\color{blue}{bB}b\;.$$
The last production that was employed to reach $aaAbBb$ is $B\to bB$, so $bB$ is the handle of $aaAbBb$.