The idea: which pieces of the sentence can each symbol build?

A context-free grammar says how a sentence is built from parts: a sentence S is a noun phrase NP followed by a verb phrase VP, a VP is a verb V followed by an NP, and so on. Parsing asks the reverse question: given the words, can the grammar build them, and how? The CYK algorithm (Cocke, Younger, Kasami) answers it bottom up with dynamic programming. For every piece of the sentence, short ones first, it writes down which nonterminals can build that piece. If the start symbol S can build the whole sentence, the sentence is in the language.

The CYK table for she eats a fish. Bottom row, one cell per word: she gives NP, eats gives VP and V, a gives Det, fish gives N. Span 2: she eats gives S, eats a gives nothing, a fish gives NP. Span 3: she eats a gives nothing, eats a fish gives VP from V NP. Top cell, the whole sentence: S from NP VP, so the sentence is accepted.
The table for "she eats a fish": each row is one span length, and the top cell holds S, so the sentence is accepted.

Chomsky normal form

CYK needs the grammar in Chomsky normal form (CNF). Every rule has one of two shapes:

  • A → B C: a nonterminal is exactly two nonterminals, e.g. S → NP VP.
  • A → a: a nonterminal is one word, e.g. N → fish.

So any piece longer than one word is built from exactly two shorter pieces next to each other. That is what makes a table over pieces work. Every context-free grammar (that does not derive the empty string) can be rewritten into CNF: long right sides are cut into chains of pairs, a word inside a long rule gets its own nonterminal, and unit rules such as A → B are folded away. The page's grammars are already in CNF; the grammar panel lists every rule.

The table T[l, s] and the fill order

For a sentence of n words, cell T[l, s] holds every nonterminal that derives the l words starting at word s. On the canvas the table is a pyramid: the bottom row is span 1 (one cell per word), the row above is span 2, and the single top cell T[n, 1] is the whole sentence. Each cell sits right above the words it covers.

Span 1 uses the word rules: T[1, s] = every A with a rule A → ws. "eats" gets both VP and V, because the grammar has VP → eats and V → eats. Then the table fills by span length: all pairs, then all triples, up to the top. A cell only reads cells of shorter spans, so they are always finished first, the same order as the cost table of matrix chain multiplication.

One split: A → B C from two smaller cells

To fill T[l, s], try every split k = 1 … l − 1. The first k words are the left part, cell T[k, s]; the other l − k words are the right part, cell T[l − k, s + k]. For every rule A → B C with B in the left cell and C in the right cell, A joins T[l, s]. On the canvas each Step is one split: the cell being filled is orange, the left part blue, the right part green, and the rules that fire light up in the grammar panel. When one side is empty, nothing can be combined.

Cell T[4,1] for she eats a fish, split k = 1. Left part T[1,1] she holds NP. Right part T[3,2] eats a fish holds VP. The rule S → NP VP has NP on the left and VP on the right, so S joins T[4,1]. The other splits k = 2 and k = 3 add nothing.
Split k = 1 of T[4,1]: NP from "she" and VP from "eats a fish" match S → NP VP, so S goes into the top cell.

Accept or reject

The grammar derives the sentence exactly when S ∈ T[n, 1]. The top cell turns green or red. A rejected sentence can still have many filled cells: in "she eats fish with a fork", T[2, 1] = {S} because "she eats" alone is a sentence, and "with a fork" is a PP. But "fish" is only an N, and this grammar builds an NP only from Det N, so nothing covers "eats fish" and the top cell stays empty. (Demo: rejected — she eats fish with a fork) In the a/b grammar, "a b a b" ends with T[4, 1] = {B}: the string is derivable from B, but not from S. (Demo: a/b grammar — a b a b is rejected)

From the table to a parse tree

A yes/no answer is not a parse. While filling, CYK keeps a back pointer for each nonterminal in a cell: the split k and the rule A → B C that put it there. Starting from S in the top cell, follow the back pointer to the two children, and their back pointers to theirs, until every leaf is a word. The page draws the tree one depth per Step, with each node right under the table cell of its span. (Demo: accepted — she eats a fish with a fork)

Ambiguity: two trees for one sentence

Add the rule NP → NP PP ("a fish with a fork" is also a noun phrase) and "she eats a fish with a fork" gets two parses. VP over "eats a fish with a fork" is now built twice: by V NP with the NP "a fish with a fork", and by VP PP with "with a fork" attached to the eating. This is PP attachment ambiguity. The cell still holds VP once; it just has two back pointers. Counting trees is the same DP with numbers: the trees of A in a cell are the sum, over its back pointers, of (trees of B) × (trees of C). (Demo: ambiguous — NP → NP PP gives two trees)

Two parse trees for she eats a fish with a fork. Left tree: VP → V NP and NP → NP PP, the fish comes with a fork. Right tree: VP → VP PP, she eats using a fork. Both have S → NP VP at the root.
With NP → NP PP the same words have two trees: the PP attaches to the fish (left) or to the eating (right).

Running time

There are n(n + 1)/2 cells, and a cell of span l tries l − 1 splits. Above span 1 that is (n³ − n)/6 splits in all, each checked against the binary rules: Θ(n³ · |G|) time and Θ(n² · |N|) space for the table.

grammarsentencensplitstop cellresult
Englishshe eats a fish with a fork756{S}accepted, 1 tree
Englishshe eats fish with a fork635∅rejected
English + NP → NP PPshe eats a fish with a fork756{S}accepted, 2 trees
a/bb a a b a520{S, A, C}accepted, 2 trees
a/ba b a b410{B}rejected

Parsing by table is the same "interval DP" shape as matrix chain multiplication: a value for every range, filled by length, with a split in the middle. Compilers use faster linear-time parsers for programming languages, which are designed to be unambiguous; see the recursive-descent parser in Inside a Tiny Compiler, and Regex to NFA to DFA for the simpler, regular languages a lexer handles.

The machine view of the same context-free languages is the Pushdown Automaton, a finite automaton with one stack.

One level above context-free languages, a Turing Machine decides aⁿbⁿcⁿ by marking symbols on its tape and walking back and forth.

What the page leaves out

The grammars and sentences are fixed presets of at most 7 words, already in Chomsky normal form; the page does not convert a grammar to CNF. It leaves out probabilistic CKY (rule probabilities, keeping the most likely tree), Earley and GLR parsing, which handle any context-free grammar directly, Valiant's reduction to matrix multiplication, and grammars that derive the empty string.