5.3.4 Gap Threading

Work with more structure.

The basic idea underlying gap threading is that instead of using simple feature values such as nogap and gap(np) we are going to work with more structure. In particular, the value of the Gap feature is going to be a difference list. Think of the first item (list) as ``what we have before we analyze this category'' and the second one as ``what we have afterwards''. Or more simply: think of the list as the ``in value'', and the second item as the ``out value''.

Here are the new NP rules (found in dCG4GapThreading.pl ):

np(F-F) --> det,n.
np(F-F) --> det,n,rel.
np(F-F) --> pn.
np(F-F) --> pn,rel.
np([gap(np)|F]-F) --> [].       

Note that in the first four rules, the difference list F-F is doing the work that nogap used to do. And this is the way it should be. After all, F-F is a difference list representation of the empty list. So, for example, the first rule says that an NP can consist of a proper name, and when an NP is built that way, no material has been removed. (That is: the in value is the same as the out value.)

What about the last rule? This says that we can build empty NPs, but that when we do so, we have to add gap(np) to the first list. That is, in this case there is a difference between the in value and the out value: the difference is precisely the gap(np) value.

The S rule is analogous to our old one:

s(F-G) --> np(F-F),vp(F-G).     

This says that the subject NP must be an ordinary NP (recall: F-F is essentially the same as nogap) and that the difference list associated with the VP is passed up to the S. That is, just as before we are performing feature passing, except that now the Gap feature is a difference list.

Thus the rules for PPs and relativization should not be puzzling:

pp(F-G) --> p,np(F-G).

rel --> prorel,s([gap(np)|F] - F).
rel --> prorel,vp(F-F).

Once again, these are exact analogs of our earlier rules --- except that we are using complex features.

So we come at last to the critical part: how do we handle VPs? As follows:

vp(F-G) --> v(1),np(F-G).
vp(F-G) --> v(2),np(F-H),pp(H-G).
 % lexicon

This looks nice: we have one rule for each of the verb types. The first rule is is analogous to our earlier V(1) rule. But what about the second rule? Why do we only need one for V(2) verbs?

Think about it. The most complicated feature we have is

[gap(np)|F]-F]

and this indicates that precisely one element is missing. So when we enter the second VP rule, there is only one missing item and two arguments. It may end up in the first position, or the second, but (as there is only one) it cannot end up in both.

This DCG is well worth studying. For a start, you should carefully compare it with our previous DCG (dCG4Gaps2.pl ). Note the systematic link between the two. Second, you really should play with lots of traces so you can see how the gap is threaded in and out of the various categories. Start by running our example queries from before.

This threading technique can be used to thread other things besides gaps. For example, it can be used in computational semantics. There is a simple way of implementing Discourse Representation Theory (DRT): one threads the semantic representations (the DRSs) through the parse tree. In this way, each part of the sentence gets to make its own semantic contribution. You can find a discussion of this in Volume 2 of the textbook on semantics by Blackburn and Bos, which is available at www.comsem.org.