Chart parser

A chart parser represents the input sentence as a sequence of words and builds a chart, a data structure that records completed and incomplete constituents spanning contiguous substrings. The parser applies grammar rules to combine these constituents, storing each partial analysis in the chart so that it can be reused whenever the same span and category are needed again. This memoization eliminates the exponential blow-up of naive backtracking parsers, achieving polynomial time for many grammar classes.

The chart is typically organized as a set of edges or states, each labeled with a category, a span (start and end positions), and a record of how much of the constituent has been recognized. Two main strategies exist: top-down (goal-directed) and bottom-up (data-driven), which differ in how edges are proposed and combined. The algorithm's correctness and efficiency depend on the grammar being in a suitable form, such as Chomsky normal form for some variants.

The most famous chart parsing algorithms are the CYK algorithm (Cocke–Younger–Kasami) and Earley's algorithm. CYK operates bottom-up and requires a context-free grammar in Chomsky normal form, achieving O(n^3) time and O(n^2) space for a fixed grammar. Earley's algorithm is more flexible, handling arbitrary context-free grammars and providing efficient performance on many practical grammars, with worst-case O(n^3) but often better on unambiguous inputs.

Other variants include left-corner parsing, which combines top-down prediction with bottom-up recognition, and chart-based implementations of unification grammars such as Lexical-Functional Grammar and Head-Driven Phrase Structure Grammar. These extend the basic chart framework to handle feature structures and long-distance dependencies. Chart parsers also underpin probabilistic parsing, where each edge carries a probability, enabling selection of the most likely analysis.

Chart parsers are widely used in natural language processing tasks such as syntactic analysis, machine translation, and information extraction. They serve as the backbone of many grammar formalisms and are integrated into toolkits like the Stanford Parser and NLTK. In speech recognition, chart parsing helps integrate acoustic and linguistic constraints, and in bioinformatics, similar dynamic programming methods are applied to RNA secondary structure prediction.

Beyond linguistics, chart parsing techniques have been adapted for programming language analysis and graph parsing, where the input is a graph rather than a linear string. The ability to handle ambiguity and partial results makes chart parsers suitable for incremental parsing, where analyses are updated as new input arrives, useful in interactive systems and grammar checking.

Early chart parsing ideas predate the CYK and Earley algorithms: Martin Kay's 1967 paper introduced the concept of a chart for natural language parsing, and Sheila Greibach contributed to the theoretical foundations. The term 'chart' itself comes from the idea of a 'chart' of constituents, akin to a map of the sentence's structure.

Chart parsers have been extended to mildly context-sensitive formalisms like tree-adjoining grammars (TAGs), which require more complex chart structures. In semantic parsing, charts are used to build logical forms incrementally. A notable edge case is packed charts, which compactly represent multiple analyses by sharing substructures, crucial for efficient ambiguity packing in machine translation. Additionally, chart parsing has been applied to optical character recognition (OCR) post-processing, where it helps correct errors by parsing character sequences.

Chart

A data structure storing partial parse results (edges) for spans of the input.

Edge

A record in the chart representing a constituent or a partial constituent with a category and span.

Dynamic programming

A method of solving problems by breaking them into overlapping subproblems and storing results.

Context-free grammar

A formal grammar consisting of production rules that replace nonterminals with sequences of terminals and nonterminals.

Chomsky normal form

A restricted form of context-free grammar where productions are of the form A → BC or A → a.