9.1.4 Chart Parsing

How is a chart used by a parser? This is well-known in computational linguistics but also in computer science, where chart parsing is usually called the CYK-algorithm.

The idea is as follows: We start from the chart which edges for all words. We then apply the rules of the grammar to subsequences of adjacent edges. For all binary rule, say C --> C1 C2, and all adjacent edges of categories C1 and C2, we add a combined edge of category C.

An example for "a man runs" to be written"

To problem now is that we have to determine when chart is complete. This means that no further edges can be added to the chart. A simple way to check for the completeness of a chart si provide an additional data structure which contains all those edges, which have to be considered for further rule applications. We call this data structure an agenda which could be realized either as a stack or as a heap.

We call an agenda-chart pair complete if it satisfies the following property:

If two edges in a chart can be combined then the resulting edge belongs either to the chart or to the agenda.

If an agenda-chart pair is complete and the agenda empty, then the chart is complete in the previous sence. Chart parsing now looks as follows: Pick and delete an edge from the agenda, add all combinations of this edge to the agenda, and the edge itself to the chart.

This algorithm terminates since only a quadratic number of edges can be added to a chart. Adding an edge costs linear time such that the all over costs for chart parsing are cubic time.


Denys Duchier, Claire Gardent and Joachim Niehren
Version 1.3.99 (20050412)