Contents    Page-10    Prev    Next    Page+10    Index   

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 ai,k contains nonterminal N iff there is a parse of N beginning at word i and spanning k words.

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(n3) time.