left-branching

Tomas Lozano-Perez (tlp@ai.mit.edu)
Fri, 6 Mar 1998 23:20:57 -0500 (EST)

Since the backward chainer uses a depth-first left-right search
strategy, rules like
NP PP -> NP
cause infinite recursion. To show that one has an NP, then one tries
to show one has an NP, and so on.
NP
/ \
NP PP
/ \
NP PP
...

So, please avoid such rules. Instead, one can do things like this
he -> NP2
Det N -> NP2
NP2 PP -> NP
NP2 -> NP
P NP -> NP
NP VP -> S
Note that here there is no infinite branching on the leftmost symbol.
Here an NP2 is a "primitive" NP, one that doesn't have an embedded PP.
Then we say that an NP is either an NP2 or an NP2 followed by a PP.
The PP in turn has an NP in it.

Tomas