How to Learn the CYK Algorithm: Chomsky Normal Form, Span Charts, Split Points, Parse Reconstruction and Cubic-Time Parsing

How can a program decide whether an entire sentence can be built from a grammar when the sentence may have many possible internal structures? The CYK algorithm answers by refusing to guess one full parse from left to right. Instead, it solves every smaller span, stores what each span can become, and builds larger spans from those verified pieces.

This Learning Hall article develops Cocke–Younger–Kasami parsing from beginner grammar intuition to chart construction, proof reasoning, parse reconstruction and professional implementation. It complements the broader Parsing Algorithms article and the separate Earley Parsing article; it does not replace either canonical job.

Quick Read

CYK is a bottom-up dynamic-programming algorithm for context-free grammar recognition and parsing.
The standard presentation assumes a grammar in Chomsky normal form (CNF).
A chart cell records which nonterminals can derive a particular contiguous input span.
For a span of length greater than one, CYK tries every split point and combines compatible left/right nonterminals.
Backpointers turn a recognizer into a parser that can reconstruct one or many parse trees.
The standard worst-case running time is O(n³·|G|) under a straightforward grammar scan, with O(n²·|N|) Boolean chart space.
Professional implementations care about grammar indexing, ambiguity, unary/epsilon handling, parse forests, weights, memory layout and whether CYK is actually the right parser for the receiver.

1. Beginner Level: A Grammar Builds Structure

A context-free grammar has terminal symbols, nonterminal symbols, a start symbol and production rules. Terminals are the visible input symbols. Nonterminals name structural categories. A rule says how one category may expand.

Consider this small grammar:

S -> A B
A -> a
B -> B C
B -> b
C -> c

It can derive strings such as ab, abc, abcc and so on. The question CYK answers is: given an input such as abcc, can the start symbol S derive the whole string?

2. Why Chomsky Normal Form Matters

In standard CYK, productions are normalised so that their useful forms are essentially:

A → a, where a is a terminal; or
A → B C, where B and C are nonterminals.

This restriction gives the dynamic program a clean binary decomposition. Any non-trivial parse of a span must split that span into a left part derived by one child and a right part derived by another child. The representation is doing algorithmic work.

General context-free grammars can be transformed into CNF under the usual conditions, but conversion can introduce artificial nonterminals and make the grammar less readable. Professional systems therefore distinguish between the mathematical convenience of CNF and the human meaning of the original grammar.

3. The Chart: Solve Every Span Once

For an input of length n, imagine a triangular table. A cell identified by start position i and span length L stores all nonterminals that can derive exactly that substring.

For abcc, the length-one cells are easy:

span "a"  contains A
span "b"  contains B
span "c"  contains C
span "c"  contains C

Longer cells are built only after their shorter components are known. This ordering is the dynamic-programming dependency graph made visible.

4. Split Points Are the Core Search

Suppose we want to know what can derive the span bcc. It may split after the first symbol as b | cc, or after the second as bc | c. For each split, CYK asks whether some grammar rule X → Y Z has Y in the left chart cell and Z in the right chart cell.

For our grammar, B → B C lets a B span grow by attaching a C on the right. Once bc is known to be B, combining that B with the final C proves that bcc is also B. Then S → A B combines a with bcc, placing S over the whole input.

If S appears in the full-span cell, the string is recognised by the grammar.

5. The Dynamic-Programming Recurrence

Let chart[i, j] be the set of nonterminals that derive the half-open substring input[i:j]. For a terminal at position i, insert every A such that A → input[i]. For a longer span:

for every split k between i and j:
    for every Y in chart[i, k]:
        for every Z in chart[k, j]:
            add every X with production X -> Y Z
                to chart[i, j]

This recurrence is the reason the algorithm is usually taught with three structural loops: span length, span start and split point. Grammar lookup happens inside that structure.

6. A Transparent Python Recognizer

The following implementation indexes the grammar in the direction the algorithm queries it. That is an important engineering improvement over rescanning every production for every split.

from collections import defaultdict

def cyk_recognize(tokens, start_symbol, terminal_rules, binary_rules):
    # terminal_rules[token] -> set of parents A with A -> token
    # binary_rules[(B, C)] -> set of parents A with A -> B C
    n = len(tokens)
    if n == 0:
        return False

    chart = [[set() for _ in range(n + 1)] for _ in range(n)]

    for i, token in enumerate(tokens):
        chart[i][i + 1].update(terminal_rules.get(token, ()))

    for length in range(2, n + 1):
        for i in range(0, n - length + 1):
            j = i + length
            cell = chart[i][j]

            for k in range(i + 1, j):
                left = chart[i][k]
                right = chart[k][j]

                for B in left:
                    for C in right:
                        cell.update(binary_rules.get((B, C), ()))

    return start_symbol in chart[0][n]

The code is intentionally explicit. A learner should be able to point at each loop and say which part of the recurrence it implements.

7. Recognition Is Not Yet Parsing

A Boolean recognizer answers only whether the whole string is derivable. To recover a parse tree, store evidence whenever a nonterminal is inserted: which split point was used, and which left and right child nonterminals supported it.

One backpointer per successful cell/category can recover one parse. If the grammar is ambiguous and every parse matters, a cell may need multiple backpointers. Storing shared substructure yields a packed parse forest rather than copying common subtrees many times.

8. The Correctness Invariant

The central invariant is:

After a span length L has been processed, chart[i, i+L] contains exactly the nonterminals that derive that span under the CNF grammar.

The length-one base case is correct because CNF terminal productions identify exactly which nonterminals derive each token. For a longer span derived by X, a CNF parse tree must have a binary root X → Y Z and therefore some split where Y derives the left substring and Z derives the right. By induction, those children are already present in their smaller chart cells, so CYK will add X. Conversely, CYK adds X only when a real production and two valid child derivations exist. That establishes both completeness and soundness.

9. Why the Standard Bound Is Cubic

There are O(n²) spans in a string of length n. A span can have O(n) split points. That gives the familiar O(n³) structural search. The grammar factor depends on representation and lookup strategy; a straightforward statement is often O(n³·|G|), while indexed binary-rule lookup can make the constant factors and practical behaviour much better.

The Boolean chart itself has O(n²) cells, each capable of containing nonterminals from the grammar. Backpointers can use substantially more space when ambiguity is high because one category can have several derivations.

10. Ambiguity Is Evidence, Not an Error

If two different parse structures derive the same input, CYK can preserve both. A recognizer that stores only sets intentionally discards that distinction. A parser that needs ambiguity information must retain multiple derivational witnesses.

This is a general systems lesson: two algorithms can produce the same yes/no result while preserving very different amounts of evidence. The right representation depends on what the next consumer needs.

11. Weighted and Probabilistic Variants

The chart recurrence can be generalized from Booleans to scores. In probabilistic context-free grammars, each derivation carries a probability or log-score. Replacing “can derive” with “best score for deriving” produces a Viterbi-style CKY parser; summing over alternatives supports inside computations. The same span/split skeleton survives while the algebra performed in each cell changes.

This is one reason CYK is educationally valuable even when another parser is chosen in production: it exposes how dynamic programming, grammar structure and algebraic combination fit together.

12. CYK Versus Earley, LL and LR Parsing

CYK is not the universal answer to parsing. Earley parsing handles arbitrary context-free grammars directly and can behave especially well on restricted grammar classes. LL and LR families exploit grammar structure to parse efficiently and are common in programming-language tooling. CYK offers a regular cubic worst-case framework and a particularly clean dynamic-programming chart.

A professional chooses based on the grammar, ambiguity, latency requirements, error recovery, incremental editing, semantic actions and maintainability—not on which algorithm has the simplest textbook recurrence.

13. Failure Modes and Implementation Traps

Grammar not actually in the assumed normal form: valid derivations disappear.
Epsilon productions: empty-string handling requires explicit treatment.
Unary nonterminal chains: standard binary-only recurrence will miss them unless grammar conversion or closure logic handles them.
Index convention errors: inclusive versus half-open spans cause subtle off-by-one failures.
Lost ambiguity: storing only one backpointer can silently discard other parses.
Repeated grammar scans: an unindexed rule representation creates avoidable work.
Tokenisation mismatch: the parser cannot repair a lexer/input representation it was not designed to receive.
CNF artefacts: reconstructed trees may need denormalisation before they match the original grammar’s meaning.

14. Professional Engineering Improvements

Index terminal rules by token and binary rules by child pair. Represent small nonterminal sets as bitsets when that improves memory locality. Skip a split immediately if either child cell is empty. Process chart diagonals in a dependency-safe order that can expose parallelism. Use packed backpointers for ambiguous grammars rather than materialising every tree eagerly.

For weighted parsing, use log probabilities where multiplication would underflow, define tie policy, and distinguish the best parse from total probability mass. For large grammars, profile grammar lookup and memory movement rather than assuming the cubic loop count is the only cost that matters.

15. Learn the Algorithm by Reading the Chart

Programming-education research supports worked examples and staged movement from code reading to independent construction. CYK is well suited to that progression because the chart makes hidden state visible. First predict which categories belong in a cell. Then run a completed implementation. Investigate a single split. Modify the grammar or input. Finally build the parser again from the recurrence.

Do not let a learner copy three nested loops without being able to answer: “What does this cell mean?” and “Why are all the cells I depend on already complete?” Those two questions recover the algorithm when syntax is forgotten.

16. Beginner-to-Professional Progression

Beginner: derive short strings by hand and fill terminal cells in a triangular chart.
Intermediate: implement recognition, trace every split and state the chart invariant.
Advanced: add backpointers, reconstruct parse trees, preserve ambiguity and prove correctness by induction on span length.
Professional: index grammar rules, manage CNF conversion/denormalisation, support weights or parse forests, profile memory and compare CYK with alternative parser families against the actual receiver requirements.

17. Practice Problems

Fill the complete CYK chart for the grammar above and input abcc.
Change the final symbol to b. Which cells become empty, and where does recognition fail?
Add backpointers and reconstruct one parse tree.
Create an ambiguous grammar and store every alternative derivation without duplicating common subtrees.
Convert a small non-CNF grammar into CNF, then explain which introduced symbols should disappear from the final user-facing parse tree.
Benchmark indexed versus full-rule-scan implementations on the same grammar and corpus.
Replace Boolean membership with a numeric score and implement a best-parse recurrence.

18. Sources and Further Reading

Final idea: CYK turns a seemingly global question—“Can this entire string have a legal structure?”—into a disciplined accumulation of local evidence. Its transferable lesson is to define the meaning of each subproblem so precisely that larger structures can be assembled from smaller verified ones without guessing the whole answer at once.

Small Group Tutorials