13.4.3 Chart Parsing

In both the CKY and Earley algorithms, the order in which events occur (adding entries to the table, reading words, making predictions, etc.) is statically determined by the procedures that make up these algorithms. Unfortunately, dynamically determining the order in which events occur based on the current information is often necessary for a variety of reasons. Fortunately, an approach advanced by Martin Kay and his colleagues (Kaplan, 1973; Kay, 1986) called Chart Parsing facilitates just such dynamic determination of the order in which chart entries are processed. This is accomplished through the introduction of an agenda to the mix. In this scheme, as states (called edges

in this approach) are created they are added to an agenda that is kept ordered according to a policy that is specified separately from the main parsing algorithm. This can be viewed as another instance of state-space search that we've seen several times before. The FSA and FST recognition and parsing algorithms in Chs. 2 and 3 employed agendas with simple static policies, while the A* decoding algorithm described in Ch. 9 is driven by an agenda that is ordered probabilistically.

Fig. 13.16 presents a generic version of a parser based on such a scheme. The main part of the algorithm consists of a single loop that removes a edge from the front of an agenda, processes it, and then moves on to the next entry in the agenda. When the agenda is empty, the parser stops and returns the chart. The policy used to order the elements in the agenda thus determines the order in which further edges are created and predictions are made.

function CHART-parse(words, grammar, agenda-strategy) returns chart

INITIALIZE(chart, agenda, words)

while agenda

current-edge ← POP(agenda)

PROCESS-EDGE(current-edge)

return(chart)

procedure PROCESS-EDGE(edge)

ADD-TO-CHART(edge)

if INCOMPLETE?(edge)

FORWARD-FUNDAMENTAL-RULE(edge)

else

BACKWARD-FUNDAMENTAL-RULE(edge)

MAKE-PREDICTIONS(edge)

procedure FORWARD-FUNDAMENTAL((A → α • B β, [i,j]))

for each(B → γ •, [j,k]) in chart

ADD-TO-AGENDA(A → α B • β, [i,k])

procedure BACKWARD-FUNDAMENTAL((B → γ •, [j,k]))

for each(A → α • B β, [i,j]) in chart

ADD-TO-AGENDA(A → α B • β, [i,k])

procedure ADD-TO-CHART(edge)

if edge is not already in chart then

Add edge to chart

procedure ADD-TO-AGENDA(edge)

if edge is not already in agenda then

APPLY(agenda-strategy, edge, agenda)

Figure 13.16 A Chart Parsing Algorithm

The key principle in processing edges in this approach is what Kay termed the fundamental rule of chart parsing. The fundamental rule states that when the chart contains two contiguous edges where one of the edges provides the constituent that

the other one needs, a new edge should be created that spans the original edges and incorporates the provided material. More formally, the fundamental rule states the following: if the chart contains two edges $ A \to \alpha \bullet B\beta, [i,j] $ and $ B \to \gamma \bullet, [j,k] $ then we should add the new edge $ A \to \alpha B \bullet \beta [i,k] $ to the chart. It should be clear that the fundamental rule is a generalization of the basic table-filling operations found in both the CKY and Earley algorithms.

The fundamental rule is triggered in Fig. 13.16 when an edge is removed from the agenda and passed to the PROCESS-EDGE procedure. Note that the fundamental rule itself does not specify which of the two edges involved has triggered the processing. PROCESS-EDGE handles both cases by checking to see whether or not the edge in question is complete. If it is complete then the algorithm looks earlier in the chart to see if any existing edge can be advanced; if it is incomplete then it looks later in the chart to see if it can be advanced by any pre-existing edge later in the chart.

The next piece of the algorithm that needs to be filled in is the method for making predictions based on the edge being processed. There are two key components to making predictions in chart parsing: the events that trigger predictions, and the nature of a predictions. The nature of these components varies depending on whether we are pursuing a top-down or bottom-up strategy. As in Earley, top-down predictions are triggered by expectations that arise from incomplete edges that have been entered into the chart; bottom-up predictions are triggered by the discovery of completed constituents. Fig. 13.17 illustrates how these two strategies can be integrated into the chart parsing algorithm.

procedure MAKE-PREDICTIONS(edge)

if Top-Down and INCOMPLETE?(edge)

TD-PREDICT(edge)

elsif Bottom-Up and COMPLETE?(edge)

BU-PREDICT(edge)

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

for each(B $ \rightarrow $ $ \gamma $) in grammar do

ADD-TO-AGENDA(B $ \rightarrow $ $ \bullet\gamma $, [j,j])

procedure BU-PREDICT((B $ \rightarrow $ $ \gamma \bullet $, [i,j]))

for each(A $ \rightarrow $ B $ \beta $) in grammar

ADD-TO-AGENDA(A $ \rightarrow $ B $ \bullet\beta $, [i,j])

Figure 13.17 A Chart Parsing Algorithm

Obviously we've left out many of the bookkeeping details that would have to be specified to turn this approach into a real parser. Among the details that have to be worked out are how the INITIALIZE procedure gets things started, how and when words are read, the organization of the chart, and specifying an agenda strategy. Indeed, in describing the approach here, Kay (1986) refers to it as an algorithm!schema rather than an algorithm, since it more accurately specifies an entire family of parsers rather than any particular parser. Exercise 13.7 asks you to explore some of the available

choices by implementing various chart parsers.

13.5 PARTIAL PARSING

Many language-processing tasks simply do not require complex, complete parse trees for all inputs. For these tasks, a partial parse, or shallow parse, of input sentences may be sufficient. For example, information extraction systems generally do not extract all the possible information from a text; they simply identify and classify the segments in a text that are likely to contain valuable information. Similarly, information retrieval systems may choose to index documents based on a select subset of the constituents found in a text.

Not surprisingly, there are many different approaches to partial parsing. Some approaches make use of cascades of FSTs, of the kind discussed in Ch. 3, to produce representations that closely approximate the kinds of trees we've been assuming in this chapter and the last. These approaches typically produce flatter trees than the ones we've been discussing. This flatness arises from the fact that such approaches generally defer decisions that may require semantic or contextual factors, such as prepositional phrase attachments, coordination ambiguities, and nominal compound analyses. Nevertheless the intent is to produce parse-trees that link all the major constituents in an input.

An alternative style of partial parsing is known as chunking. Chunking is the process of identifying and classifying the flat non-overlapping segments of a sentence that constitute the basic non-recursive phrases corresponding to the major parts-of-speech found in most wide-coverage grammars. This set typically includes noun phrases, verb phrases, adjective phrases, and prepositional phrases; in other words, the phrases that correspond to the content-bearing parts-of-speech. Of course, not all applications require the identification of all of these categories; indeed the most common chunking task is to simply find all the base noun phrases in a text.

Since chunked texts lack a hierarchical structure, a simple bracketing notation is sufficient to denote the location and the type of the chunks in a given example. The following example illustrates a typical bracketed notation.

[NP The morning flight] [PP from] [NP Denver] [VP has arrived.]

This bracketing notation makes clear the two fundamental tasks that are involved in chunking: finding the non-overlapping extents of the chunks, and assigning the correct label to the discovered chunks.

Note that in this example all the words are contained in some chunk. This will not be the case in all chunking applications. In many settings, a good number of the words in any input will fall outside of any chunk. This is, for example, the norm in systems that are only interested in finding the base-NPs in their inputs, as illustrated by the following example.

[NP The morning flight] from [NP Denver] has arrived.

The details of what constitutes a syntactic base-phrase for any given system varies according to the syntactic theories underlying the system and whether the phrases

are being derived from a treebank. Nevertheless, some standard guidelines are followed in most systems. First and foremost, base phrases of a given type do not recursively contain any constituents of the same type. Eliminating this kind of recursion leaves us with the problem of determining the boundaries of the non-recursive phrases. In most approaches, base-phrases include the headword of the phrase, along with any pre-head material within the constituent, while crucially excluding any post-head material. Eliminating post-head modifiers from the major categories automatically removes the need to resolve attachment ambiguities. Note that exclusion does lead to certain oddities such as the fact that PPs and VPs often consist solely of their heads. Thus our earlier example a flight from Indianapolis to Houston on TWA is reduced to the following:

(13.10) [NP a flight] [PP from] [NP Indianapolis][PP to][NP Houston][PP on][NP TWA].