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.