13.4.2 The Earley Algorithm

In contrast to the bottom-up search implemented by the CKY algorithm, the Earley algorithm (Earley, 1970) uses dynamic programming to implement a top-down search of the kind discussed earlier in Sec. 13.1.1. The core of the Earley algorithm is a single left-to-right pass that fills an array we'll call a chart that has $ N+1 $ entries. For each word position in the sentence, the chart contains a list of states representing the partial parse trees that have been generated so far. As with the CKY algorithm, the indexes represent the locations between the words in an input (as in $ _{0} $ Book $ _{1} $ that $ _{2} $ flight $ _{3} $). By the end of the sentence, the chart compactly encodes all the possible parses of the input. Each possible subtree is represented only once and can thus be shared by all the parses that need it.

The individual states contained within each chart entry contain three kinds of information: a subtree corresponding to a single grammar rule, information about the progress made in completing this subtree, and the position of the subtree with respect to the input. We'll use a • within the right-hand side of a state's grammar rule to indicate the progress made in recognizing it. The resulting structure is called a dotted rule. A state's position with respect to the input will be represented by two numbers indicating where the state begins and where its dot lies.

Consider the following example states, which would be among those created by the Earley algorithm in the course of parsing Ex. 13.7:

Book that flight.

$$ S\ \to\ \bullet\,VP,\ [0,0] $$

$$ {N P}~\to~{D e t}\bullet{N o m i n a l},[1,2] $$

$$ VP\ \to\ VNP\bullet,\ [0,3] $$

The first state, with its dot to the left of its constituent, represents a top-down prediction for this particular kind of S. The first 0 indicates that the constituent predicted by this state should begin at the start of the input; the second 0 reflects the fact that the dot lies at the beginning as well. The second state, created at a later stage in the processing of this sentence, indicates that an NP begins at position 1, that a Det has been successfully parsed and that a Nominal is expected next. The third state, with its dot to the right of all its two constituents, represents the successful discovery of a tree corresponding to a VP that spans the entire input.

The fundamental operation of an Earley parser is to march through the $ N + 1 $ sets of states in the chart in a left-to-right fashion, processing the states within each set in order. At each step, one of the three operators described below is applied to each state depending on its status. In each case, this results in the addition of new states to the end of either the current, or next, set of states in the chart. The algorithm always moves forward through the chart making additions as it goes; states are never removed and the algorithm never backtracks to a previous chart entry once it has moved on. The presence of a state $ S \to \alpha $, $ [0,N] $ in the list of states in the last chart entry indicates a successful parse. Fig. 13.13 gives the complete algorithm.

The following three sections describe in detail the three operators used to process states in the chart. Each takes a single state as input and derives new states from it. These new states are then added to the chart as long as they are not already present. The PREDICTOR and the COMPLETER add states to the chart entry being processed, while the SCANNER adds a state to the next chart entry.

Predictor

As might be guessed from its name, the job of PREDICTOR is to create new states representing top-down expectations generated during the parsing process. PREDICTOR is applied to any state that has a non-terminal immediately to the right of its dot that is not a part-of-speech category. This application results in the creation of one new state for each alternative expansion of that non-terminal provided by the grammar. These new states are placed into the same chart entry as the generating state. They begin and end at the point in the input where the generating state ends.

For example, applying PREDICTOR to the state $ S \to \bullet VP $, $ [0,0] $ results in the addition of the following five states

$$ VP\ \to\bullet\,Verb,\ [0,0] $$

VP $ \rightarrow $ $ \bullet $ Verb NP, [0,0]

VP $ \rightarrow $ $ \bullet $ Verb NP PP, [0,0]

VP $ \rightarrow $ $ \bullet $ Verb PP, [0,0]

$$ VP\ \to\ \bullet\,VP\,PP,\ [0,0] $$

to the first chart entry.

function EARLEY-PARSE(words, grammar) returns chart

ADDTOCHART(( $ \gamma \rightarrow \bullet S $, [0,0]), 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 \bullet B\beta $, [i,j]))

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

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

end

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

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

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

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

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

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

end

procedure ADDTOCHART(state, chart-entry)

if state is not already in chart-entry then

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

end

Figure 13.13 The Earley algorithm

Scanner

When a state has a part-of-speech category to the right of the dot, SCANNER is called to examine the input and incorporate a state corresponding to the prediction of a word with a particular part-of-speech into the chart. This is accomplished by creating a new state from the input state with the dot advanced over the predicted input category. Note that unlike CKY, Earley uses top-down input to help deal with part-of-speech ambiguities; only those parts-of-speech of a word that are predicted by some existing state will find their way into the chart.

Returning to our example, when the state $ VP \to \bullet \text{Verb} NP $, $ [0,0] $ is processed, SCANNER consults the current word in the input since the category following the dot is

a part-of-speech. It then notes that book can be a verb, matching the expectation in the current state. This results in the creation of the new state $ Verb \to book \bullet $, [0,1]. This new state is then added to the chart entry that follows the one currently being processed. The noun sense of book never enters the chart since it is not predicted by any rule at this position in the input.

Completer

COMPLETER is applied to a state when its dot has reached the right end of the rule. The presence of such a state represents the fact that the parser has successfully discovered a particular grammatical category over some span of the input. The purpose of COMPLETER is to find, and advance, all previously created states that were looking for this grammatical category at this position in the input. New states are then created by copying the older state, advancing the dot over the expected category, and installing the new state in the current chart entry.

In the current example, when the state $NP \to Det$ Nominal$\bullet$, [1,3] is processed, COMPLETER looks for incomplete states ending at position 1 and expecting an $NP$. It finds the states $VP \to Verb \bullet NP$, [0,1] and $VP \to Verb \bullet NP$ $PP$, [0,1]. This results in the addition of the new complete state $VP \to Verb$ $NP \bullet$, [0,3], and the new incomplete state $VP \to Verb$ $NP \bullet PP$, [0,3] to the chart.

A Complete Example

Fig. 13.14 shows the sequence of states created during the complete processing of Ex. 13.7; each row indicates the state number for reference, the dotted rule, the start and end points, and finally the function that added this state to the chart. The algorithm begins by seeding the chart with a top-down expectation for an S. This is accomplished by adding a dummy state $ \gamma \to \bullet S $, [0,0] to Chart[0]. When this state is processed, it is passed to PREDICTOR leading to the creation of the three states representing predictions for each possible type of S, and transitively to states for all of the left-corners of those trees. When the state VP $ \to \bullet $ Verb, [0,0] is reached, SCANNER is called and the first word is read. A state representing the verb sense of Book is added to the entry for Chart[1]. Note that when the subsequent sentence initial VP states are processed, SCANNER will be called again. However, new states are not added since they would be identical to the Verb state already in the chart.

When all the states of Chart[0] have been processed, the algorithm moves on to Chart[1] where it finds the state representing the verb sense of book. This is a complete state with its dot to the right of its constituent and is therefore passed to COMPLETER. COMPLETER then finds the four previously existing VP states expecting a Verb at this point in the input. These states are copied with their dots advanced and added to Chart[1]. The completed state corresponding to an intransitive VP then leads to the creation of an S representing an imperative sentence. Alternatively, the dot in the transitive verb phrase leads to the creation of the three states predicting different forms of NPs. The state NP $ \rightarrow \bullet $Det Nominal, [1,1] causes SCANNER to read the word that and add a corresponding state to Chart[2].

Moving on to Chart[2], the algorithm finds the state representing the determiner sense of that. This complete state leads to the advancement of the dot in the NP state

| Chart[0] | S0 | $ \gamma \rightarrow \bullet S $ | [0,0] | Dummy start state |

| --- | --- | --- | --- | --- |

| | S1 | $ S \rightarrow \bullet NP VP $ | [0,0] | Predictor |

| | S2 | $ S \rightarrow \bullet Aux NP VP $ | [0,0] | Predictor |

| | S3 | $ S \rightarrow \bullet VP $ | [0,0] | Predictor |

| | S4 | $ NP \rightarrow \bullet Pronoun $ | [0,0] | Predictor |

| | S5 | $ NP \rightarrow \bullet Proper-Noun $ | [0,0] | Predictor |

| | S6 | $ NP \rightarrow \bullet Det Nominal $ | [0,0] | Predictor |

| | S7 | $ VP \rightarrow \bullet Verb $ | [0,0] | Predictor |

| | S8 | $ VP \rightarrow \bullet Verb NP $ | [0,0] | Predictor |

| | S9 | $ VP \rightarrow \bullet Verb NP PP $ | [0,0] | Predictor |

| | S10 | $ VP \rightarrow \bullet Verb PP $ | [0,0] | Predictor |

| | S11 | $ VP \rightarrow \bullet VP PP $ | [0,0] | Predictor |

| Chart[1] | S12 | Verb $ \rightarrow $ book $ \bullet $ | [0,1] | Scanner |

| | S13 | $ VP \rightarrow Verb $ $ \bullet $ | [0,1] | Completer |

| | S14 | $ VP \rightarrow Verb \bullet NP $ | [0,1] | Completer |

| | S15 | $ VP \rightarrow Verb \bullet NP PP $ | [0,1] | Completer |

| | S16 | $ VP \rightarrow Verb \bullet PP $ | [0,1] | Completer |

| | S17 | $ S \rightarrow VP \bullet $ | [0,1] | Completer |

| | S18 | $ VP \rightarrow VP \bullet PP $ | [0,1] | Completer |

| | S19 | $ NP \rightarrow \bullet Pronoun $ | [1,1] | Predictor |

| | S20 | $ NP \rightarrow \bullet Proper-Noun $ | [1,1] | Predictor |

| | S21 | $ NP \rightarrow \bullet Det Nominal $ | [1,1] | Predictor |

| | S22 | $ PP \rightarrow \bullet Prep NP $ | [1,1] | Predictor |

| Chart[2] | S23 | Det $ \rightarrow $ that $ \bullet $ | [1,2] | Scanner |

| | S24 | $ NP \rightarrow Det \bullet Nominal $ | [1,2] | Completer |

| | S25 | Nominal $ \rightarrow $ $ \bullet Noun $ | [2,2] | Predictor |

| | S26 | Nominal $ \rightarrow $ $ \bullet Nominal Noun $ | [2,2] | Predictor |

| | S27 | Nominal $ \rightarrow $ $ \bullet Nominal PP $ | [2,2] | Predictor |

| Chart[3] | S28 | Noun $ \rightarrow $ flight $ \bullet $ | [2,3] | Scanner |

| | S29 | Nominal $ \rightarrow $ Noun $ \bullet $ | [2,3] | Completer |

| | S30 | $ NP \rightarrow Det Nominal \bullet $ | [1,3] | Completer |

| | S31 | Nominal $ \rightarrow $ Nominal $ \bullet Noun $ | [2,3] | Completer |

| | S32 | Nominal $ \rightarrow $ Nominal $ \bullet PP $ | [2,3] | Completer |

| | S33 | $ VP \rightarrow Verb NP $ $ \bullet $ | [0,3] | Completer |

| | S34 | $ VP \rightarrow Verb NP \bullet PP $ | [0,3] | Completer |

| | S35 | $ PP \rightarrow \bullet Prep NP $ | [3,3] | Predictor |

| | S36 | $ S \rightarrow VP \bullet $ | [0,3] | Completer |

| | S37 | $ VP \rightarrow VP \bullet PP $ | [0,3] | Completer |

predicted in Chart[1], and also to the predictions for the various kinds of Nominal. The first of these causes SCANNER to be called for the last time to process the word flight.

Finally moving on to Chart[3], the presence of the state representing flight leads in quick succession to the completion of an NP, transitive VP, and an S. The presence of the state $ S \to VP \bullet $, [0,3] in the last chart entry signals the discovery of a successful

parse.

It is useful to contrast this example with the CKY example given earlier. Although Earley managed to avoid adding an entry for the noun sense of book, its overall behavior is clearly much more promiscuous than CKY. This promiscuity arises from the purely top-down nature of the predictions that Earley makes. Exercise 13.6 asks you to improve the algorithm by eliminating some of these unnecessary predictions.

Retrieving Parse Trees from a Chart

As with the CKY algorithm, this version of the Earley algorithm is a recognizer not a parser. Valid sentences will simply leave the state $ S \to \alpha\bullet $, $ [0,N] $ in the chart. To retrieve parses from the chart the representation of each state must be augmented with an additional field to store information about the completed states that generated its constituents.

The information needed to fill these fields can be gathered by making a simple change to the COMPLETER function. Recall that COMPLETER creates new states by advancing existing incomplete states when the constituent following the dot has been discovered in the right place. The only change necessary is to have COMPLETER add a pointer to the older state onto a list of constituent-states for the new state. Retrieving a parse tree from the chart is then merely a matter of following pointers starting with the state (or states) representing a complete S in the final chart entry. Fig. 13.15 shows the chart entries produced by an appropriately updated COMPLETER that participate in the final parse for this example.