Skip to content

Chart Parsing

A parsing method — instantiates Grammar-Guided Structure Recovery

Recovers every licensed parse at once by tabulating partial constituents in a chart and reusing shared sub-analyses, turning ambiguous input into polynomial-time work.

Chart Parsing is a dynamic-programming approach to candidate generation: instead of building one tree and backtracking when it fails, it records every partial constituent it discovers in a chart — a table indexed by the span of input each constituent covers — so that any sub-analysis is computed once and then reused wherever it recurs. Where a backtracking parser re-derives the same sub-tree over and over, chart parsing memoizes it; where a single-result parser commits early, chart parsing keeps all licensed parses at once as a packed forest. Its defining move is to trade memory for time: a table of spans-to-constituents converts what would be exponential ambiguity into polynomial work, and the parse simply stops when the table stops growing.

Example

A language pipeline must parse "I saw the astronomer with the telescope." Two readings are grammatical — the telescope belongs to the seeing, or to the astronomer. A naïve parser would build one, discover the other only by backtracking, and rebuild shared pieces from scratch. Chart parsing instead fills a table bottom-up: it discovers the noun phrase "the astronomer" once, stores it against its span, and then both higher readings reuse that exact constituent rather than recomputing it. When the table is complete, the two readings sit side by side as a packed forest that shares every sub-tree they have in common.

Crucially, the output is a forest, not a verdict: chart parsing reports "here are both licensed structures," not "here is the intended one." Choosing between them is deliberately someone else's job. For an n-token sentence the whole construction stays within roughly O(n³) work, so even a highly ambiguous input parses in predictable time.

How it works

Each chart entry is an edge: a span, a grammatical category, and how complete that category is over the span. The parser repeatedly combines adjacent or overlapping edges according to the grammar's rules, adding any new constituent to the chart keyed by its span — which is what lets identical sub-constituents be packed (stored once, pointed to many times) instead of duplicated. It halts at a fixpoint: a full pass that adds no new edge. The recovered structures are then read out as every complete edge spanning the whole input. Two things distinguish it from its parser siblings: it never discards a partial result (so it is complete over ambiguous grammars) and it never recomputes one (so it is polynomial, not exponential).

Tuning parameters

  • Strategy — bottom-up assembly (as in CYK) vs. top-down prediction (as in Earley). Prediction avoids building constituents the grammar could never use at that position, at the cost of bookkeeping.
  • Packing aggressiveness — share ambiguous sub-parses under one packed node (compact, but disambiguation is deferred) vs. enumerate them as separate trees (explicit, but the forest can blow up).
  • Complexity budget / beam — cap edges per cell or prune low-priority edges to bound the O(n³) cost on long inputs — buying speed by risking completeness.
  • Grammar normal form — some chart algorithms require a binarized grammar (e.g. Chomsky Normal Form); the choice moves constant factors, not asymptotics.
  • Termination sensitivity — stop at the chart's fixpoint (all parses) or short-circuit at the first spanning parse (fast, but no longer complete).

When it helps, and when it misleads

Its strength is genuine ambiguity: when the input really does support many readings and you must keep them all — natural language, RNA secondary structure, expression grammars with overloaded operators — the packed forest is compact and the runtime is bounded and predictable. Its failure modes are the mirror image. It is heavy for input that is actually unambiguous, where a deterministic linear parser would be far faster; the packed forest can hide a combinatorial explosion of readings behind a deceptively small structure; and pruning to satisfy a budget can silently drop the one correct parse. The classic misuse is reaching for chart parsing's generality on a deterministic grammar where it buys nothing — or reading a single tree out of the chart and calling it "the" parse when the chart in fact held thousands. The discipline that guards against this is to measure the input's real ambiguity, hand disambiguation to a dedicated step rather than the parser, and keep any pruning budget explicit.[1]

How it implements the components

Chart Parsing realizes the candidate-generation side of the archetype — producing structure and bounding the cost of doing so, but not choosing among what it produces:

  • candidate_structure_forest — the completed chart is a packed forest holding every parse the grammar licenses over the input.
  • complexity_budget — tabulation caps the work at polynomial (≈O(n³)), and the beam/edge-cap dials bound it further for long inputs.
  • termination_condition — parsing halts deterministically at the chart's fixpoint, when a full pass adds no new edge.

It consumes rather than defines the grammar (Grammar Rule Set) and the token stream (Lexical Scanning and Tokenization); it does not select among the parses it emits — that is Controlled Disambiguation Test and the Ambiguity Register — and it is only one candidate-generation engine among several (Recursive-Descent Parsing, Shift-Reduce Parsing, Probabilistic Grammar Parsing).

Notes

Chart Parsing generates candidates; it deliberately does not rank them by likelihood. Weighting the forest toward a most-probable reading is Probabilistic Grammar Parsing's job, and picking a single winner is the disambiguation step's. Keeping generation and scoring separate is what lets a team swap in a new scoring model without touching the parser.

References

[1] The two canonical chart parsers are CYK (bottom-up, requires a binarized grammar) and Earley (top-down prediction, handles arbitrary context-free grammars). Both run in O(n³) time for an n-token input and O(n²) space, which is the concrete meaning of the polynomial "complexity budget" this mechanism offers over ambiguous grammars. ↩