Is chart parsing one algorithm?

No. It is a family of approaches with different item definitions and processing strategies.

Must a chart contain only complete phrases?

No. Many implementations also store partial rule applications.

Does a full-span S item always supply every tree?

Only if the representation retains enough derivation information to reconstruct them; membership alone is insufficient.

AI Glossary / Natural language and speech / Advanced

Chart parsing

Definition

Chart parsing is a family of parsing methods that store and reuse hypotheses about the structure of portions of an input. The stored collection is called a chart. By combining previously established partial results, a parser can avoid rediscovering the same substructure repeatedly and can preserve competing analyses licensed by a grammar.

What it means

A sentence may contain a phrase that several larger analyses share. Instead of rebuilding that phrase independently for every possibility, a chart parser records it once in a reusable representation. Different ways of combining stored results can still produce different complete trees.
The word chart refers to a computational data structure, not a business graph or visual dashboard. A chart can be displayed for teaching or debugging, but the algorithm's benefit comes from the information it stores and the rules for combining that information.

How it works

The parser identifies positions between input tokens and records items associated with those positions. Depending on the algorithm, an item may describe a complete constituent or an incomplete rule application. A dotted rule, for example, can indicate how much of a proposed production has already been recognized and what remains to be found.
Inference rules add items when existing items and grammar rules justify them. An agenda can organize pending work, and duplicate detection avoids repeatedly inserting equivalent states. Backpointers or child links preserve how an item was derived, allowing trees to be recovered later.
Different chart parsers use different strategies, including bottom-up, top-down, and combinations. A successful full parse requires a suitable start-symbol analysis covering the complete input. Merely finding several well-formed fragments does not establish that the whole sentence is licensed by the grammar.

Three practical examples

A grammar-development team inspects the chart for a sentence that unexpectedly fails to parse. It locates the span where the available constituents cannot combine under the current rules.
An information-extraction prototype keeps alternative phrase attachments instead of committing immediately to the first tree. A later scoring or interpretation step selects among the stored alternatives.
A teaching tool shows how one recognized noun phrase contributes to several larger analyses.

Think of it this way

Think of a workshop that labels completed components and stores them for reuse in several possible assemblies. The inventory tells workers which components are available; assembly records tell them how each finished object can be built. Reusing a component does not mean there is only one possible finished object.

Worked example

Use an original deliberately tiny grammar with two rules: S → S S and S → x. Here S is the start symbol, x is the sole terminal token, and juxtaposed S symbols mean two consecutive constituents. The input is three tokens: x x x.
Number the boundaries 0, 1, 2, and 3. Write a span [i,j) for the tokens beginning at i and ending just before j. A simple bottom-up chart first records S over [0,1), [1,2), and [2,3), using S → x.
Next, it records S over [0,2) by combining [0,1) with [1,2), and S over [1,3) by combining [1,2) with [2,3). These two-token constituents can be reused when building the full span.
For [0,3), two split points work. Splitting at boundary 1 combines [0,1) and [1,3). Splitting at boundary 2 combines [0,2) and [2,3). The two full trees group the tokens as x (x x) and (x x) x.
There are six distinct completed category-span records in this simplified representation: three length-one spans, two length-two spans, and one length-three span. Yet there are two complete parses. The top S record must retain both derivations if the objective is to recover every parse. A boolean record that only says S exists on [0,3) proves recognition but does not by itself record both trees.
With four x tokens, the same grammar has five complete binary trees while there are only ten nonempty spans. This shows how a compact collection of reusable span results can stand for multiple trees. It does not mean that every chart implementation has exactly these item counts: dotted states, lexical edges, and other bookkeeping can add records.

Illustrative case study

Fictional example: ParseDesk builds a grammar-based assistant for reviewing short instructions. Its first prototype repeatedly analyzes the same phrase when exploring different attachments. The team introduces a chart and stores the alternatives that depend on each recognized phrase.
A review then finds that the export routine writes only the first child combination for an ambiguous item. Recognition still succeeds, but some valid analyses disappear from the exported results. The team preserves the alternative derivation links and tests tree recovery separately from recognition. The scenario illustrates two distinct responsibilities; it reports no measured speedup or evidence that the grammar captures every intended instruction.

Common misconceptions and mistakes

A chart is not necessarily a single parse tree. One chart item can participate in several trees, and one span can have several category labels. Deduplicating equivalent items must not accidentally erase distinct derivations needed for the requested output.
Chart parsing also does not choose the most plausible meaning automatically. Grammar recognition, parse enumeration, and scoring are different tasks. Finally, compact storage of alternatives does not make listing all trees inexpensive: an ambiguous grammar can license a very large number of trees even when many substructures are shared.

Business use

Chart parsing can be useful when an application needs transparent grammatical analyses, explicit ambiguity handling, or reusable intermediate results. Define whether the required output is acceptance, all parses, the best-scoring parse, or a compact representation of alternatives. Measure memory and runtime with representative sentence lengths and ambiguity levels. If the grammar is incomplete, distinguish a missing parse from proof that the user's language is invalid.

Check your understanding

How many full parses does x x x have under the example grammar?

Answer: Two.

Why are there six completed category-span records?

Answer: Every nonempty span has S, giving three plus two plus one.

What would be lost by storing only one derivation for the full span?

Answer: One of the two valid trees.

Related terms

Dynamic programming
Context-free grammar
Constituency parsing
Ambiguity
CKY algorithm
Earley parsing
parse forest
backpointer

Learn next

Reconstruct both trees from the three-token chart, then extend the example to four tokens. Next, compare completed-span items with dotted-rule states and separate recognition, tree recovery, and scoring when evaluating a parser.

Sources

NLTK, chart parsing module, chart items, inference rules, and child-pointer lists: https://www.nltk.org/api/nltk.parse.chart.html Jurafsky and Martin, Speech and Language Processing, context-free grammars and constituency parsing: https://web.stanford.edu/~jurafsky/slp3/19.pdf

Previous: Characters Next: Chatbot