4
$\begingroup$

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: enter image description here

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

  • 1
    I have cross-posted this question onto http://cs.stackexchange.com/questions/290/understanding-texthandle-in-parsing-problem 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.2012-03-13

1 Answers 1

1

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 underlined non-terminals are the ones replaced in the next step of the derivation; each is replaced by the colored substring in the next word of the derivation.

The last production that was employed to reach $aaAbBb$ is $B\to bB$, so $bB$ is the handle of $aaAbBb$.

You may find this PDF to be of some use.