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 | ||||
| 4 | |||||
| 3 | NP | VP | |||
| 2 | NP | NP | |||
| 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.