6.5.2 With Depth-First Search

Explore one possibility at a time.

Depth first search means that whenever there is more than one rule that could be applied at one point, we first explore one possibility (and all its consequences). Only if we fail, we consider the alternative(s) following the same strategy. So, we stick to a decision as long as possible.

Let's look at an example. Here's part of the grammar ourEng.pl again:

s     ---> [np, vp].

np    ---> [pn].

vp    ---> [iv].

vp    ---> [dv, np, pp].

lex(vincent,pn).

lex(mia,pn).

lex(loved,tv).

lex(knew,tv).

lex(gave,dv).

The sentence ``Mia loved vincent'' is admitted by this grammar. Let's see how a top-down parser using depth first search would go about showing this. The following table shows the steps a top-down depth first parser would make. The second row gives the categories the parser tries to recognize in each step and the third row the string that has to be covered by these categories.

It should be clear why this approach is called top-down: we clearly work from the abstract to the concrete, and we make use of the CFG rules left-to-right.

And why was this an example of depth first search? Because when we were faced with a choice, we selected one alternative, and worked out its consequences. If the choice turned out to be wrong, we backtracked. For example, above we were faced with a choice of which way to try and build a VP --- using an intransitive verb or a transitive verb. We first tried to do so using an intransitive verb (at state 4) but this didn't work out (state 5) so we backtracked and tried a transitive analysis (state 4'). This eventually worked out.