Chart Parser

A chart parser is a type of bottom-up parser that produces all parses in a triangular array called the chart; each chart cell contains a set of nonterminals. The bottom level of the array contains all possible parts of speech for each input word. Successive levels contain reductions that span the items in levels below: cell a_i,k contains nonterminal N iff there is a parse of N beginning at word i and spanning k words.

5 S
1 Art Adj, N N, V Art N
0 The old man the boats
1 2 3 4 5

The chart parser eliminates the redundant work that would be required to reparse the same phrase for different higher-level grammar rules.

The Cocke-Kasami-Younger (CKY) parser is a chart parser that guarantees to parse any context-free language in at most O(n^3) time.

Contents    Page-10    Prev    Next    Page+10    Index