16.4.2 The Unification Algorithm

The unification algorithm that we have been leading up to is shown in Figure 16.8. This algorithm accepts two feature structures represented using the extended DAG representation and returns as its value a modified version of one of the arguments, or a failure signal in the event that the feature structures are incompatible.

The first step in this algorithm is to acquire the true contents of both of the arguments. Recall that if the pointer field of an extended feature structure is non-null, then the real content of that structure is found by following the pointer found in pointer field. The variables $ f1 $ and $ f2 $ are the result of this pointer following process, often referred to as dereferencing.

As with all recursive algorithms, the next step is to test for the various base

function UNIFY(f1-orig, f2-orig) returns f-structure or failure

f1 ← Dereferenced contents of f1-orig

f2 ← Dereferenced contents of f2-orig

if f1 and f2 are identical then

f1.pointer ← f2

return f2

else if f1 is null then

f1.pointer ← f2

return f2

else if f2 is null then

f2.pointer ← f1

return f1

else if both f1 and f2 are complex feature structures then

f2.pointer ← f1

for each f2-feature in f2 do

f1-feature ← Find or create a corresponding feature in f1

if UNIFY(f1-feature.value, f2-feature.value) returns failure then

return failure

return f1

else return failure

Figure 16.8 The unification algorithm.

cases of the recursion before proceeding on to a recursive call involving some part of the original arguments. In this case, there are three possible base cases:

• The arguments are identical

• One or both of the arguments has a null value

• The arguments are non-null and non-identical

If the structures are identical, then the pointer of the first is set to the second and the second is returned. It is important to understand why this pointer change is done in this case. After all, since the arguments are identical, returning either one would appear to suffice. This might be true for a single unification but recall that we want the two arguments to the unification operator to be truly unified. The pointer change is necessary since we want the arguments to be truly identical, so that any subsequent unification that adds information to one will add it to both.

In the case where either of the arguments is null, the pointer field for the null argument is changed to point to the other argument, which is then returned. The result is that both structures now point at the same value.

If neither of the preceding tests is true then there are two possibilities: they

are non-identical atomic values, or they are non-identical complex structures. The former case signals an incompatibility in the arguments that leads the algorithm to return a failure signal. In the latter case, a recursive call is needed to ensure that the component parts of these complex structures are compatible. In this implementation, the key to the recursion is a loop over all the features of the second argument, f2. This loop attempts to unify the value of each feature in f2 with the corresponding feature in f1. In this loop, if a feature is encountered in f2 that is missing from f1, a feature is added to f1 and given the value NULL. Processing then continues as if the feature had been there to begin with. If every one of these unifications succeeds, then the pointer field of f2 is set to f1 completing the unification of the structures and f1 is returned as the value of the unification.

An Example

To illustrate this algorithm, let's walk through the following example.

$$ \begin{bmatrix}\text{AGREEMENT}&\text{①}\left[\text{NUMBER}s g\right]\\ \text{SUBJECT}&\left[\text{AGREEMENT}\text{①}\right]\end{bmatrix} $$

$$ \triangleledsetbar\left[SUBJECT\quad\left[AGREEMENT\begin{bmatrix}PERSON&3rd\end{bmatrix}\right]\right] $$

Figure 16.9 shows the extended representations for the arguments to this unification. These original arguments are neither identical, nor null, nor atomic, so the main loop is entered. Looping over the features of $f2$, the algorithm is led to a recursive attempt to unify the values of the corresponding SUBJECT features of $f1$ and $f2$.

$$ \begin{bmatrix}\text{AGREEMENT}&\boxed{1}\end{bmatrix}\sqcup\begin{bmatrix}\text{AGREEMENT}&\begin{bmatrix}\text{PERSON}&3rd\end{bmatrix}\end{bmatrix} $$

These arguments are also non-identical, non-null, and non-atomic so the loop is entered again leading to a recursive check of the values of the AGREEMENT features.

$$ \begin{bmatrix}\text{NUMBER}&sg\end{bmatrix}\sqcup\begin{bmatrix}\text{PERSON}&3rd\end{bmatrix} $$

In looping over the features of the second argument, the fact that the first argument lacks a PERSON feature is discovered. A PERSON feature initialized with a NULL value is, therefore, added to the first argument. This, in effect, changes the previous unification to the following.

$$ \begin{bmatrix}NUMBER&sg\\ PERSON&null\end{bmatrix}\triangleleft\begin{bmatrix}PERSON&3rd\end{bmatrix} $$

After creating this new PERSON feature, the next recursive call leads to the unification of the NULL value of the new feature in the first argument with the 3rd value of the second argument. Since there are no further features to check in the f2 argument at any level of recursion, each of the recursive calls to UNIFY returns. The result is shown in Figure 16.10.

16.5 PARSING WITH UNIFICATION CONSTRAINTS

We now have all the pieces necessary to integrate feature structures and unification into a parser. Fortunately, the order-independent nature of unification allows us to largely ignore the actual search strategy used in the parser. Once we have associated unification constraints with the context-free rules of the grammar, and feature structures with the states of the search, any of the standard search algorithms described in Ch. 13 can be used.

Of course, this leaves a fairly large range of possible implementation strate-

gies. We could, for example, simply parse as we did before using the context-free components of the rules, and then build the feature structures for the resulting trees after the fact, filtering out those parses that contain unification failures. Although such an approach would result in only well-formed structures in the end, it fails to use the power of unification to reduce the size of the parser's search space during parsing.

The next section describes an approach that makes better use of the power of unification by integrating unification constraints directly into the Earley parsing process, allowing ill-formed structures to be eliminated as soon as they are proposed. As we will see, this approach requires only minimal changes to the basic Earley algorithm. We then move on to briefly consider an approach to unification-based parsing that moves even further away from standard context-free methods.