16.5.1 Integrating Unification into an Earley Parser

We have two goals in integrating feature structures and unification into the Earley algorithm: to use feature structures to provide a richer representation for the constituents of the parse, and to block entry into the chart of ill-formed constituents that violate unification constraints. As we will see, these goals can be accomplished by fairly minimal changes to the original Earley scheme given on page \ref{page_scheme}.

The first change involves the various representations used in the original code. Recall that the Earley algorithm operates by using a set of unadorned context-free grammar rules to fill in a data-structure called a chart with a set of states. At the end of the parse, the states that make up this chart represent all possible parses of the input. Therefore, we begin our changes by altering the representations of both the context-free grammar rules, and the states in the chart.

The rules are altered so that in addition to their current components, they also include a feature structure derived from their unification constraints. More specifically, we will use the constraints listed with a rule to build a feature structure, represented as a DAG, for use with that rule during parsing.

Consider the following context-free rule with unification constraints.

$$ S\to NP VP $$

$$ \langle N P\ \mathrm{H E A D}\ \mathrm{A G R E E M E N T}\rangle=\langle V P\ \mathrm{H E A D}\ \mathrm{A G R E E M E N T}\rangle $$

$$ \left\langle S\ \mathrm{H E A D}\right\rangle=\left\langle V P\ \mathrm{H E A D}\right\rangle $$

Converting these constraints into a feature structure results in the following structure:

$$ \begin{aligned}&\begin{bmatrix}S&\begin{bmatrix}HEAD&\text{□}\end{bmatrix}\\ NP&\begin{bmatrix}HEAD&\begin{bmatrix}AGREEMENT&\text{②}\end{bmatrix}\end{bmatrix}\end{bmatrix}\\ VP&\begin{bmatrix}HEAD&\text{①}\begin{bmatrix}AGREEMENT\text{②}\end{bmatrix}\end{bmatrix}\end{bmatrix}\\ \end{aligned} $$

In this derivation, we combined the various constraints into a single structure by first creating top-level features for each of the parts of the context-free rule, s, NP, and VP in this case. We then add further components to this structure by following the path equations in the constraints. Note that this is a purely notational conversion; the DAGs and the constraint equations contain the same information. However, tying the constraints together in a single feature structure puts it in a form that can be passed directly to our unification algorithm.

The second change involves the states used to represent partial parses in the Earley chart. The original states contain fields for the context-free rule being used, the position of the dot representing how much of the rule has been completed, the

positions of the beginning and end of the state, and a list of other states that represent the completed sub-parts of the state. To this set of fields, we simply add an additional field to contain the DAG representing the feature structure corresponding to the state. Note that when a rule is first used by PREDICTOR to create a state, the DAG associated with the state will simply consist of the DAG retrieved from the rule. For example, when PREDICTOR uses the above S rule to enter a state into the chart, the DAG given above will be its initial DAG. We'll denote states like this as follows, where $ D_{ag} $ denotes the feature structure given above.

$$ S\to\bullet\;N P\;V P,\;[0,0],[],\nonumber D a g $$

Given these representational additions, we can move on to altering the algorithm itself. The most important change concerns the actions that take place when a new state is created by the extension of an existing state, which takes place in the COMPLETER routine. Recall that COMPLETER is called when a completed constituent has been added to the chart. Its task is to attempt to find, and extend, existing states in the chart that are looking for constituents that are compatible with the newly completed constituent. COMPLETER is, therefore, a function that creates new states by combining the information from two other states, and as such is a likely place to apply the unification operation.

To be more specific, COMPLETER adds a new state into the chart by finding an existing state whose • can be advanced by the newly completed state. A • can be advanced when the category of the constituent immediately following it matches the category of the newly completed constituent. To accommodate the use of feature structures, we can alter this scheme by unifying the feature structure associated with the newly completed state with the appropriate part of the feature structure being advanced. If this unification succeeds, then the DAG of the new state receives the unified structure and is entered into the chart. If it fails, then no new state is entered into the chart. The appropriate alterations to COMPLETER are shown in Figure 16.11.

Consider this process in the context of parsing the phrase That flight, where the That has already been seen, as is captured by the following state.

NP $ \rightarrow $ Det $ \bullet $Nominal[0,1],[S_{Det}],Dag1

Now consider the later situation where the parser has processed flight and has sub-

sequently produced the following state.

$$ Nominal\to Noun\bullet,[1,2],[S_{Noun}],Dag_2 $$

$$ \begin{array}{l}Dag_{2}\left[\begin{matrix}NOMINAL&\begin{matrix}\mathrm{HEAD}&\boxed{1}\end{matrix}\end{matrix}\\\left[\begin{matrix}NOUN&\begin{matrix}\mathrm{HEAD}&\boxed{1}\end{matrix}\end{matrix}\begin{matrix}\left[\begin{matrix}\mathrm{AGREEMENT}&\boxed{\mathrm{NUMBER}\quad\mathrm{SG}}\end{matrix}\right]\\\end{matrix}\right]\end{array} $$

To advance the NP rule, the parser unifies the feature structure found under the NOMINAL feature of $ Dag_{2} $, with the feature structure found under the NOMINAL feature of the NP's $ Dag_{1} $. As in the original algorithm, a new state is created to represent the fact that an existing state has been advanced. This new state's DAG is given the DAG that resulted from this unification.

The final change to the original algorithm concerns the check for states already contained in the chart. In the original algorithm, the ENQUEUE function refused to enter into the chart any state that was identical to one already present in the chart. “Identical” meant the same rule, with the same start and finish positions, and the same position of the •. It is this check that allows the algorithm to, among other things, avoid the infinite recursion problems associated with left-recursive rules.

The problem, of course, is that our states are now more complex since they have complex feature structures associated with them. States that appeared identical under the original criteria might in fact now be different since their associated DAGs may differ. One solution to this problem is to extend the identity check to include the DAGs associated with the states, but it turns out that we can improve on this solution.

The motivation for the improvement lies in the motivation for the identity check. Its purpose is to prevent the wasteful addition of a state into the chart whose effect on the parse would be accomplished by an already existing state. Put another way, we want to prevent the entry into the chart of any state that would duplicate the work that will eventually be done by other states. Of course, this will clearly be the case with identical states, but it turns out it is also the case for states in the chart that are more general than new states being considered.

Consider the situation where the chart contains the following state, where the Dag places no constraints on the Det.

$$ NP\to\bullet Det NP,[i,i],[],Dag $$

Such a state simply says that it is expecting a Det at position i, and that any Det will do.

Now consider the situation where the parser wants to insert a new state into the chart that is identical to this one, with the exception that its DAG restricts the

function EARLEY-parse(words, grammar) returns chart

ADDTOCHART(( $ \gamma \rightarrow \bullet S, [0,0], dag_{\gamma} $), chart[0])

for i ← from 0 to LENGTH(words) do

for each state in chart[i] do

if INCOMPLETE?(state) and

NEXT-CAT(state) is not a part of speech then

PREDICTOR(state)

else if INCOMPLETE?(state) and

NEXT-CAT(state) is a part of speech then

SCANNER(state)

else

COMPLETER(state)

end

end

return(chart)

procedure PREDICTOR((A $ \rightarrow $ $ \alpha \cdot B \beta $, [i,j], dag_A))

for each (B $ \rightarrow $ $ \gamma $) in GRAMMAR-RULES-FOR(B, grammar) do

ADDTOCHART((B $ \rightarrow $ $ \bullet \gamma $, [j,j], dag_B), chart[j])

end

procedure SCANNER((A $ \rightarrow $ $ \alpha \cdot B \beta $, [i,j], dag_A))

if B $ \in $ PARTS-OF-SPEECH(word[j]) then

ADDTOCHART((B $ \rightarrow $ word[j] $ \bullet $, [j,j+1], dag_B), chart[j+1])

procedure COMPLETER((B $ \rightarrow $ $ \gamma \bullet $, [j,k], dag_B))

for each (A $ \rightarrow $ $ \alpha \cdot B \beta $, [i,j], dag_A) in chart[j] do

if new-dag ← UNIFY-STATES(dag_B, dag_A, B) $ \neq $ Fails!

ADDTOCHART((A $ \rightarrow $ $ \alpha B \bullet \beta $, [i,k], new-dag), chart[k])

end

procedure UNIFY-STATES(dag1, dag2, cat)

dag1-cp ← COPYDAG(dag1)

dag2-cp ← COPYDAG(dag2)

UNIFY(FOLLOW-PATH(cat, dag1-cp), FOLLOW-PATH(cat, dag2-cp))

procedure ADDTOCHART(state, chart-entry)

if state is not subsumed by a state in chart-entry then

PUSH-ON-END(state, chart-entry)

end

Det to be singular. In this case, although the states in question are not identical, the addition of the new state to the chart would accomplish nothing and should therefore be prevented.

To see this let's consider all the cases. If the new state is added, then a subsequent singular Det will match both rules and advance both. Due to the unification of features, both will have DAGs indicating that their Dets are singular, with the net result being duplicate states in the chart. If on the other hand, a plural Det is encountered, the new state will reject it and not advance, while the old rule will advance, entering a single new state into the chart. On the other hand, if the new state is not placed in the chart, a subsequent plural or singular Det will match the more general state and advance it, leading to the addition of one new state into the chart. Note that this leaves us in exactly the same situation as if the new state had been entered into the chart, with the exception that the duplication is avoided. In sum, nothing worthwhile is accomplished by entering into the chart a state that is more specific than a state already in the chart.

Fortunately, the notion of subsumption introduced earlier gives us a formal way to talk about the generalization and specialization relations among feature structures. This suggests that the proper way to alter ENQUEUE is to check whether a newly created state is subsumed by any existing states in the chart. If it is, then it will not be allowed into the chart. More specifically, a new state that is identical in terms of its rule, start and finish positions, subparts, and • position, to an existing state, will be not be entered into the chart if its DAG is subsumed by the DAG of an existing state (ie. if $ D_{agold} \sqsubseteq D_{agnew} $). The necessary change to the original Earley ENQUEUE procedure is shown in Figure 16.11.

The Need for Copying

The calls to COPYDAG within the UNIFY-STATE procedure require some elaboration. Recall that one of the strengths of the Earley algorithm (and of the dynamic programming approach in general) is that once states have been entered into the chart they may be used again and again as part of different derivations, including ones that in the end do not lead to successful parses. This ability is the motivation for the fact that states already in the chart are not updated to reflect the progress of their •, but instead are copied and then updated, leaving the original states intact so that they can be used again in further derivations.

The call to COPYDAG in UNIFY-STATE is required to preserve this behavior because of the destructive nature of our unification algorithm. If we simply unified the DAGs associated with the existing states, those states would be altered by the unification, and hence would not be available in the same form for subsequent uses by the COMPLETER function. Note that this has negative consequences regardless

of whether the unification succeeds or fails, since in either case the original states are altered.

Let's consider what would happen if the call to COPYDAG was absent in the following example where an early unification attempt fails.

(16.22) Show me morning flights.

Let's assume that our parser has the following entry for the ditransitive version of the verb show, as well as the following transitive and ditransitive verb phrase rules.

$$ Verb \to show $$

$$ \langle V e r b\;H E A D\;S U B C A T\;F I R S T\;C A T\rangle=N P $$

$$ \langle V e r b\;H E A D\;S U B C A T\;S E C O N D\;C A T\rangle=N P $$

$$ \langle V e r b\;H E A D\;S U B C A T\;T H I R D\rangle=E N D $$

$$ VP\to Verb NP $$

$$ \langle V P\mathrm{H E A D}\rangle=\langle V e r b\mathrm{H E A D}\rangle $$

$$ \langle V P~H E A D~S U B C A T~F I R S T~C A T\rangle=\langle N P~C A T\rangle $$

$$ \langle V P~H E A D~S U B C A T~S E C O N D\rangle=E N D $$

$$ VP\ \to\ \textit{Verb NP NP} $$

$$ \langle V P\mathrm{~H E A D}\rangle=\langle V e r b\mathrm{~H E A D}\rangle $$

$$ \left\langle V P\ \mathrm{H E A D~S U B C A T}\ \mathrm{F I R S T}\ \mathrm{C A T}\right\rangle=\left\langle N P_{1}\ \mathrm{C A T}\right\rangle $$

$$ \left\langle V P\ \mathrm{H E A D}\ \mathrm{S U B C A T}\ \mathrm{S E C O N D}\ \mathrm{C A T}\right\rangle=\left\langle N P_{2}\ \mathrm{C A T}\ \right\rangle $$

$$ \langle V P~H E A D~S U B C A T~T H I R D\rangle=E N D $$

When the word me is read, the state representing the transitive verb phrase will be completed since its dot has moved to the end. COMPLETER will, therefore, call UNIFY-STATES before attempting to enter this complete state into the chart. This will fail since the SUBCAT structures of these two rules can not be unified. This is, of course, exactly what we want since this version of show is ditransitive. Unfortunately, because of the destructive nature of our unification algorithm we have already altered the DAG attached to the state representing show, as well as the one attached to the VP thereby ruining them for use with the correct verb phrase rule later on. Thus, to make sure that states can be used again and again with multiple derivations, copies are made of the dags associated with states before attempting any unifications involving them.

All of this copying can be quite expensive. As a result, a number of alternative techniques have been developed that attempt to minimize this cost (Pereira, 1985; Karttunen and Kay, 1985; Tomabechi, 1991; Kogure, 1990). Kiefer et al. (1999b) and Penn and Munteanu (2003) describe a set of related techniques used to speed up a large unification-based parsing system.