Introduction to the CYK Algorithm

Deciding whether a string belongs to a context-free language is a fundamental question in the theory of computation: given a grammar and a word, does the grammar derive it? Recursive-descent search over all possible derivations is hopeless in general, since the number of candidate derivations grows exponentially with the length of the input. The Cocke-Younger-Kasami algorithm, usually abbreviated CYK or CKY, answers the question in cubic time by restructuring the search as dynamic programming over substrings, provided the grammar has been normalized into a restricted form first. Beyond a yes/no answer, the algorithm builds a complete chart of which nonterminal derives every contiguous span of the input, and that chart is enough to recover every parse the grammar admits. Every step below can be followed interactively with a CYK visualizer that animates the same chart construction on concrete grammars.

Chomsky Normal Form

CYK requires every production of the grammar to have one of two shapes:

where \(A, B, C\) are nonterminals and \(a\) is a terminal. A grammar restricted to these two production shapes is in Chomsky normal form (CNF). Unit productions \(A\to B\), rules with three or more symbols on the right-hand side, and rules mixing terminals and nonterminals on the right-hand side are all excluded. Any context-free grammar without the empty word in its language can be converted into an equivalent CNF grammar: eliminate \(\varepsilon\)-productions by inlining their effect at every occurrence of the nonterminal they define, eliminate unit productions by transitively substituting their right-hand sides, replace terminals that appear alongside nonterminals in a rule with fresh nonterminals that generate only that terminal, and break right-hand sides longer than two symbols into a chain of binary rules using additional helper nonterminals.

Strict CNF cannot derive the empty word, since every right-hand side contains at least one terminal or two nonterminals that must themselves eventually expand to at least one terminal each. If the empty word belongs to the original language, that fact has to be tracked separately during conversion; a common convention permits the single exception \(S\to\varepsilon\) for the start symbol, and membership of the empty word is then decided by a direct check rather than by the chart construction.

The Recognition Table

Let the input be \(w = w_1 w_2 \cdots w_n\). Define \(T_{i,\ell}\) as the set of nonterminals that derive the substring of length \(\ell\) starting at position \(i\), for \(1 \le i \le n\) and \(1 \le \ell \le n-i+1\). Spans of length one are determined directly by the terminal productions:

A span of length \(\ell > 1\) can only be produced by a binary rule \(A \to BC\) applied at some internal split point: the left part covers the first \(k\) symbols of the span and the right part covers the remaining \(\ell - k\) symbols, for every possible \(k\) between \(1\) and \(\ell - 1\). Collecting every nonterminal that arises this way gives the recurrence

Because \(T_{i,\ell}\) depends only on cells covering strictly shorter spans, filling the table by increasing \(\ell\) guarantees every value it needs is already available. The word is accepted exactly when the start symbol \(S\) occurs in the cell spanning the whole input:

Arranging the cells \(T_{i,\ell}\) as a triangular grid, with length-one spans along the bottom edge and the full-length span \(T_{1,n}\) at the apex, gives the familiar CYK chart: each cell above the base is built from a pair of smaller cells below and to its left and right, one from each of the two subspans that meet at the chosen split point.

Ambiguity and Parse Trees

A cell can receive the same nonterminal from more than one combination of rule and split point. Every one of those combinations is a distinct way of deriving that substring, so a cell containing several derivations for the same symbol signals local ambiguity: the grammar generates that substring through more than one structurally different parse. Because each entry records which rule and which split point produced it, a complete parse tree can be reconstructed by following those back-pointers recursively from the top cell down to the length-one cells at the base, branching whenever a cell offers more than one derivation for the same nonterminal.

Reference Implementation

The recurrence translates directly into code once a span is represented explicitly instead of only symbolically. The grammar is assumed already grouped by left-hand side: unary maps a nonterminal to the set of terminals it derives directly, and binary maps a nonterminal to the list of symbol pairs it derives. The table itself stores, for every span length len and start index i (zero-based, so table[len][i] corresponds to \(T_{i+1,\,len}\) above), a map from nonterminal to every way that nonterminal derives the span - a terminal for length-one spans, or a split point together with the two nonterminals combined there for longer spans. Keeping every derivation rather than only the first one found is what makes the ambiguity check and the parse-tree reconstruction below possible afterward.

function cyk(grammar, tokens) {
  const n = tokens.length;

  // table[len][i] maps a nonterminal to the list of ways it derives
  // the span of "len" tokens starting at index i.
  const table = Array.from({ length: n + 1 }, () =>
    Array.from({ length: n }, () => new Map())
  );

  // Base case: T_{i,1} = { A | A -> w_i }.
  for (let i = 0; i < n; i++) {
    for (const [nonterminal, terminals] of grammar.unary) {
      if (terminals.has(tokens[i])) {
        table[1][i].set(nonterminal, [{ terminal: tokens[i] }]);
      }
    }
  }

  // Inductive case: try every split point k and every binary rule
  // A -> BC against the two shorter spans it would combine.
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      for (let k = 1; k < len; k++) {
        const left = table[k][i];
        const right = table[len - k][i + k];

        for (const [nonterminal, productions] of grammar.binary) {
          for (const [B, C] of productions) {
            if (left.has(B) && right.has(C)) {
              const derivations = table[len][i].get(nonterminal) || [];
              derivations.push({ splitAt: i + k, left: B, right: C });
              table[len][i].set(nonterminal, derivations);
            }
          }
        }
      }
    }
  }

  return { table, accepted: table[n][0].has(grammar.start) };
}

Reconstructing a parse tree is a matter of following the stored derivations back down to the length-one base case. Because a cell can hold more than one derivation for the same nonterminal, the function below follows just the first one; iterating over every stored derivation at every ambiguous cell instead would enumerate every parse admitted by the grammar.

function parseTree(table, i, len, symbol) {
  const [derivation] = table[len][i].get(symbol);

  if ('terminal' in derivation) {
    return { symbol, terminal: derivation.terminal };
  }

  const { splitAt, left, right } = derivation;
  return {
    symbol,
    left: parseTree(table, i, splitAt - i, left),
    right: parseTree(table, splitAt, i + len - splitAt, right)
  };
}

Worked Example

Consider a grammar recognizing words formed by a block generated by a nonterminal \(A\), followed by one or more terminal c symbols generated by a nonterminal \(B\). For the input aaabbbcc, the length-one row is filled first from the terminal productions, placing the nonterminals that generate single characters into their respective cells. Longer spans are then assembled bottom-up: each binary rule combines two adjacent, already-computed spans into a wider one, until the top cell is reached. If the start symbol appears in that top cell, the word is accepted; every possible split at every length has been checked exhaustively, so absence of the start symbol is a structural rejection rather than an inconclusive search.

Complexity

The chart has \(n(n+1)/2\) cells, one for every pair \((i,\ell)\) with \(i+\ell \le n+1\). A span of length \(\ell\) has \(\ell - 1\) possible split points, so summing the work over all cells gives cubic dependence on the input length. With the grammar's productions indexed by right-hand side for constant-time lookup during the union step, the standard bound is

where \(|G|\) is the number of productions and \(|N|\) the number of nonterminals. Cubic time is an excellent general-purpose bound for context-free recognition, though deterministic parsers exploiting stronger grammar restrictions run faster on the grammars used for programming languages. Converting to CNF can also obscure the original grammar structure, which is why CYK is most often used as a reference algorithm, a tool for analyzing ambiguity in a grammar, or a parser for inputs of moderate length rather than a production compiler front end.

Historical Notes

The algorithm is named for John Cocke, Tadao Kasami, and Daniel Younger, who developed the underlying idea independently around the same time. Kasami described the recognition method in a 1965 technical report, and Younger published a closely related algorithm for context-free recognition and parsing in 1967. The recurrence is a textbook example of dynamic programming: every contiguous span is solved exactly once, and the result is reused by every larger span that contains it, rather than being recomputed.

References

• Kasami1965T. Kasami (1965) An Efficient Recognition and Syntax-Analysis Algorithm for Context-Free Languages. AFCRL-65-758.
• Younger1967D. H. Younger (1967) Recognition and Parsing of Context-Free Languages in Time n³. Information and Control, 10(2), 189-208.