The CYK Parsing Algorithm

What problem CYK actually solves

Given a context-free grammar G and a string w = w₁w₂…wₙ, the membership problem asks a single yes/no question: can G derive w from its start symbol? A naive answer — try every derivation — is hopeless, because the number of derivations can be exponential or even infinite. CYK answers it in polynomial time by never re-deriving a substring it has already solved.

The trick is a classic dynamic-programming subproblem decomposition. Define T[i, j] as the set of nonterminals that can derive the substring wᵢ…wⱼ. If we can fill this table for every span, then the string is in the language exactly when the start symbol S appears in the cell covering the whole string. The overlapping-subproblem structure is obvious: a long span is built from shorter spans that appear in many places, so we solve each short span once and reuse it.

Why Chomsky Normal Form is non-negotiable

CYK depends on grammars in Chomsky Normal Form (CNF), where every production is one of exactly two shapes:

• A → BC — a binary rule of two nonterminals.
• A → a — a single terminal.

(With the sole optional exception S → ε to admit the empty string.) That binary shape is the whole point. To decide whether nonterminal A derives a span, you split the span into a left part and a right part and ask: is there a rule A → BC where B derives the left and C derives the right? Because every rule is binary, there is always exactly one split to reason about, and the recursion has a clean two-way branching structure that yields the n³ table fill. A rule like A → BCD would demand a three-way split and wreck the bound.

Every context-free grammar can be mechanically converted to CNF (eliminate ε-productions, remove unit productions, bin the long right-hand sides into fresh nonterminals, and replace stray terminals). The conversion at most squares the grammar size, which is why the |G| factor in the running time matters in practice.

How CYK fills the table

Index substrings by their start position and length. The algorithm proceeds in two phases.

Base case (length 1). For each single character wᵢ, put every nonterminal A with a rule A → wᵢ into the length-1 cell for position i. This is the diagonal of the table.

Combine (length ℓ = 2 … n). For a span of length ℓ starting at i, try every split point that divides it into a nonempty left span and a nonempty right span. For each split, look at the two smaller cells you already solved; for every binary rule A → BC, if B is in the left cell and C is in the right cell, add A to the current cell.

Accept. After the top cell (the span covering the whole string) is filled, the string is in the language iff the start symbol S is in that cell.

The three nested loops make the cost transparent: Θ(n²) cells to fill, up to n−1 split points per cell, and a constant-per-rule check inside — Θ(n³·|G|) overall, with Θ(n²) space for the table.

CYK vs Earley vs LL/LR

	CYK	Earley	LL(k)	LR(1)
Grammar class	Any CFG (needs CNF)	Any CFG (as written)	LL(k) subset	Deterministic CFG
Direction	Bottom-up	Left-to-right, chart	Top-down	Bottom-up
Worst-case time	Θ(n³·|G|)	O(n³)	O(n)	O(n)
Unambiguous time	Still Θ(n³)	O(n²)	O(n)	O(n)
Handles ambiguity	Yes (parse forest)	Yes (parse forest)	No	No
Left recursion	Fine	Fine	Breaks it	Fine
Best for	PCFG parsing, teaching, general CFGs	Natural language, general CFGs	Hand-written recursive descent	Compiler front ends

The key contrast: LL and LR parsers are linear but only accept restricted grammar classes. CYK and Earley accept every context-free grammar, paying an n³ worst case for the generality. CYK's charm is that its dynamic program is dead simple and its cell contents give you a probabilistic parser almost for free.

CYK in Python

Below is a recognizer that also stores back-pointers so you can reconstruct a parse tree. The grammar is given in CNF as two maps: unit for A → a and binary for A → BC.

def cyk(words, start, unit, binary):
    """
    words  : list of terminals, length n
    start  : start symbol
    unit   : dict terminal -> set of nonterminals A with A -> a
    binary : dict (B, C) -> set of nonterminals A with A -> B C
    Returns (accepted, table) where table[i][l] is the cell for the
    span starting at i of length l+1.
    """
    n = len(words)
    # table[i][l] : set of nonterminals deriving words[i : i+l+1]
    table = [[set() for _ in range(n - i)] for i in range(n)]

    # Base case: spans of length 1 (the diagonal)
    for i, a in enumerate(words):
        table[i][0] |= unit.get(a, set())

    # Combine: spans of length L = 2 .. n
    for L in range(2, n + 1):
        for i in range(0, n - L + 1):          # start index
            cell = table[i][L - 1]
            for k in range(1, L):              # split point (left length k)
                left  = table[i][k - 1]        # words[i : i+k]
                right = table[i + k][L - k - 1] # words[i+k : i+L]
                for B in left:
                    for C in right:
                        cell |= binary.get((B, C), set())

    return start in table[0][n - 1], table

The three range loops — over length L, start i, and split k — are exactly the n³ structure. The inner double loop over B and C is the |G| factor; a production-indexed grammar keeps it tight.

A worked example

Take the balanced-parentheses-style grammar in CNF with start symbol S:

S → A B    |  S S
A → (
B → )
X → S B          (helper for  ( S )  )
S → A X

On the input ( ) ( ) (four terminals), CYK first fills the diagonal: cells for ( hold {A} and cells for ) hold {B}. Length-2 spans combine A then B into S via S → A B, so both () pairs derive S. The length-4 top cell splits ()() into two S-deriving halves and applies S → S S, so S lands in the top cell and the string is accepted. Note the split at the middle is the only one that succeeds — the algorithm still checks all three split points, which is where the n³ cost comes from.

Ambiguity and the parse forest

Because each cell holds a set, ambiguity costs nothing for membership. The grammar S → S S is ambiguous — ()()() can be bracketed as (()())-style groupings in more than one way — yet S simply appears once in the top cell no matter how many derivations reach it. To recover trees, attach a back-pointer for each successful (rule, split) that put a symbol into a cell. The resulting structure is a shared packed parse forest: it stores an exponential number of parse trees in polynomial space by sharing common subtrees. Deciding membership and even counting parses stays polynomial; only enumerating them all can blow up.

Probabilistic CYK (the Viterbi lift)

The single most important application is parsing with a probabilistic context-free grammar (PCFG). Instead of a set of nonterminals, each cell stores, for every nonterminal, the maximum probability of deriving that span. The combine step becomes: for rule A → BC with probability p, the candidate score for A is p × best(B, left) × best(C, right); keep the maximum and a back-pointer. This is precisely the Viterbi algorithm lifted from a chain to a tree, and it yields the single most probable parse in the same Θ(n³·|G|) time. For decades it was the workhorse of statistical natural-language parsing.

Common misconceptions and pitfalls

• "CYK is O(n³), so it's always slow." The bound is Θ(n³·|G|), and the grammar factor often dominates. A CNF grammar produced from a large natural-language grammar can have thousands of rules, so even short sentences feel heavy. Grammar size is a first-class cost, not a footnote.
• Skipping CNF conversion. Running CYK on a grammar with ternary rules, unit rules, or ε-productions silently produces wrong answers. Convert first — eliminate ε and unit productions, then binarize.
• Forgetting that the diagonal is length-1, not length-0. Off-by-one errors in the length/index math are the number-one bug. Be explicit about whether table[i][ℓ] means length ℓ or length ℓ+1.
• Assuming CYK gives you the parse tree directly. Plain CYK is a recognizer. You must store back-pointers to reconstruct a tree, and even then the tree is in the CNF grammar — you have to un-binarize it to recover the original grammar's structure.
• Confusing it with a linear parser. CYK is not a replacement for LR in a compiler. Use it when you need to parse arbitrary or ambiguous grammars, or probabilities — not to shave constants off a deterministic language.

A note on history

The algorithm carries three names because it was discovered independently: John Cocke, Daniel Younger, and Tadao Kasami all arrived at the same dynamic-programming table in the 1960s (Kasami's technical report is from 1965, Younger's published complexity analysis from 1967). It was among the first demonstrations that general context-free recognition is polynomial — a landmark that anchored later work on Earley's parser, Valiant's O(n^2.37…) reduction of CFG parsing to matrix multiplication, and the whole field of statistical parsing.