13.2.4 Chart Parsing

What we now have to do is to devellop a parser which can deal with rules of a unification-based grammars according to the format given above. This is actually quite easy but there is one point that should be treated carefully namely, coreference checking.

Essentially, the idea for chart parsing with unification-based grammars is the same as for context free pasing. The only change consists in that the edges of a chart need carry structured categories. As we have already seen before, such categories can be represented by feature terms. Whereas previously, we could check for identity of categories, we cannot do so for feature terms, since they contain variables in order to express coreferences. Instead we have to unify such feature terms whereby coreferences are treated in the right way.

The only subtle point is the following: When unifiying categories of two edges, then we are not allowed to change these edges since might be needed again for other combinations. We also have to take care that unifiation does not raise a programming error due to failure. Actually, we know already how to do this: We simply encode the feature terms of the categories as predicates.

To illustrate the problem more concretely, we consider the following example:

  
Any employees with two supervisors can apply

Initially, "can apply" is a verb phase whose number is unspecified (it can be plural or singular). It can therefore combine with "two supervisors" and assuming that the sentence rule (s -> np vp) enforces number agreement between subject np and vp, yields a plural sentence. The point is that as the category for "can apply" is matched against the vp category of the rule through unification, it should NOT be the case that this category suddenly be changed from being an np unspecified for number to being a plural np. Else it would no longer be able to combine with its real (singular) subject "Any employee with two supervisors" and a parse would fail to be found for a perfectly grammatical sentence.

To avoid that problem, the general strategy consists in creating copies of categories and of unifying these copies rather than the originals. In Oz, we do this by encapsulating constraints into predicates.