Introduction

Every time you type code, write a mathematical formula, or ask a voice assistant a question, some program must decide: does this string of symbols follow the rules? That question is parsing, and for the broadest useful class of grammars — context-free grammars — the answer has been known since 1965 thanks to an algorithm built around a single elegant idea.

The Cocke-Younger-Kasami algorithm (CYK, independently discovered by John Cocke, Daniel Younger, and Tadao Kasami) decides whether a given sentence of length n belongs to a context-free language in time O(n3⋅∣G∣)O(n^{3} \cdot |G|), where |G| is the size of the grammar. It does this by filling a triangular table of subproblems: can the non-terminal symbol A generate the substring from position i to position j? The answer for short substrings feeds into the answer for longer ones, bottom-up.

That cubic bound is not just theoretical. It is the reason every production compiler, every code editor with syntax highlighting, and every natural-language parser begins with the same idea: build the triangle, read the answer from the top cell.

Watch the Table Fill

The demo below uses a small arithmetic grammar in Chomsky Normal Form (every rule is either A → BC or A → a). Type a sentence from the symbols aa, +, *, (, ) — for example a + a * a — then click Parse to watch the CYK table fill bottom-up and learn whether the sentence is grammatically valid.

<div class="controls">
  <label for="sentence">Sentence (tokens: <code>a + * ( )</code>):</label>
  <div class="input-row">
    <input id="sentence" type="text" value="a + a * a" spellcheck="false" autocomplete="off" />
    <button id="parseBtn" type="button">Parse</button>
    <button id="clearBtn" type="button" class="ghost">Clear</button>
  </div>
</div>
<div id="result" class="result"></div>
<div id="tableWrap" class="table-wrap"></div>
<div class="legend">
  <b>Grammar (arithmetic, CNF):</b>
  S→SS' | S→TA | S→a<br>
  SS'→SA&nbsp;&nbsp; A→PT&nbsp;&nbsp; T→a<br>
  P→( &nbsp;&nbsp; Q→) &nbsp;&nbsp; (full CNF rules shown in JS)
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #1a2433; }
label { font-size: .88rem; color: #444; display: block; margin-bottom: .3rem; }
.input-row { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .6rem; }
#sentence { font: 15px ui-monospace, monospace; padding: .4rem .6rem;
            border: 1px solid #b0bec5; border-radius: 7px; flex: 1; min-width: 160px; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.result { font-size: 1rem; font-weight: 700; min-height: 1.3em; margin-bottom: .5rem; }
.result.ok  { color: #0a7d33; }
.result.err { color: #c92f3c; }
.result.info{ color: #555; font-weight: 400; }
.table-wrap { overflow-x: auto; margin-bottom: .6rem; }
table { border-collapse: collapse; font-size: .78rem; }
td { border: 1px solid #cdd9e3; min-width: 46px; max-width: 72px; height: 40px;
     text-align: center; padding: 2px 3px; vertical-align: middle;
     font-family: ui-monospace, monospace; background: #f5f8fa; }
td.diag { background: #e8eef3; font-weight: 700; color: #1d3557; }
td.has-s { background: #c8f0d8; color: #0a7d33; font-weight: 700; }
td.empty  { background: #f5f8fa; color: #aaa; }
td.header { background: #e0e9f2; font-weight: 700; color: #2c4a6e; border: 1px solid #b0c4d8; }
.legend { font-size: .78rem; color: #555; line-height: 1.6; border-top: 1px solid #e0e0e0;
          padding-top: .5rem; margin-top: .4rem; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// CYK algorithm for a small arithmetic grammar converted to Chomsky Normal Form.
// Grammar recognizes: a, a+a, a*a, (a), a+a*a, a*(a+a), etc.
//
// Terminals: a + * ( )
// Non-terminals: S (start), Sp (S'), A, T, M, Lp (L'), P, Q
//   S  → T | M | Lp          (sums, products, parenthesised)
//   T  → S A                  (S followed by [+ S])
//   A  → Pl S                 (plus then S)  ← binary: Pl="+" token rule
//   M  → S B                  (S followed by [* S])
//   B  → St S                 (star then S)  ← binary: St="*" token rule
//   Lp → P Rp                 (open-paren, then [S close-paren])
//   Rp → S Q                  (S then close-paren)
//   P  → "("   Q → ")"   Pl → "+"   St → "*"   S → "a"

const RULES_BIN = [
  // [result, left, right]
  ['T',  'S',  'A' ],
  ['A',  'Pl', 'S' ],
  ['M',  'S',  'B' ],
  ['B',  'St', 'S' ],
  ['Lp', 'P',  'Rp'],
  ['Rp', 'S',  'Q' ],
  ['S',  'T',  null],   // unit: S→T
  ['S',  'M',  null],   // unit: S→M
  ['S',  'Lp', null],   // unit: S→Lp
];
// Unit rules need closure; we handle them separately.
const UNIT_MAP = { T: ['S'], M: ['S'], Lp: ['S'] };

const TERM_MAP = { a: ['S'], '+': ['Pl'], '*': ['St'], '(': ['P'], ')': ['Q'] };

function tokenise(str) {
  // split on whitespace or treat each non-space char as one token
  return str.trim().split(/\s+/).filter(Boolean);
}

function cyk(tokens) {
  const n = tokens.length;
  if (n === 0) return null;

  // table[i][j] = Set of non-terminals that derive tokens[i..j]
  const table = Array.from({length: n}, () =>
    Array.from({length: n}, () => new Set())
  );

  // Fill diagonal: single tokens
  for (let i = 0; i < n; i++) {
    const t = tokens[i];
    const nts = TERM_MAP[t];
    if (!nts) return null; // unknown token
    nts.forEach(nt => table[i][i].add(nt));
    applyUnits(table[i][i]);
  }

  // Fill upper triangle: substrings of length 2..n
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      for (let k = i; k < j; k++) {
        for (const [res, L, R] of RULES_BIN) {
          if (R === null) continue; // unit rules handled separately
          if (table[i][k].has(L) && table[k+1][j].has(R)) {
            table[i][j].add(res);
          }
        }
      }
      applyUnits(table[i][j]);
    }
  }
  return table;
}

function applyUnits(cell) {
  // Fixed-point unit rule closure
  let changed = true;
  while (changed) {
    changed = false;
    for (const [derived, parents] of Object.entries(UNIT_MAP)) {
      if (cell.has(derived)) {
        parents.forEach(p => { if (!cell.has(p)) { cell.add(p); changed = true; } });
      }
    }
  }
}

function renderTable(table, tokens) {
  const n = tokens.length;
  let html = '<table><tr><td class="header"></td>';
  for (let j = 0; j < n; j++) html += `<td class="header">${j}</td>`;
  html += '</tr>';

  for (let i = 0; i < n; i++) {
    html += `<tr><td class="header">${i}·"${tokens[i]}"</td>`;
    for (let j = 0; j < n; j++) {
      if (j < i) { html += '<td></td>'; continue; }
      const cell = table[i][j];
      const text = [...cell].join(' ');
      const cls = cell.has('S') ? 'has-s' : text ? 'diag' : 'empty';
      html += `<td class="${cls}">${text || '—'}</td>`;
    }
    html += '</tr>';
  }
  html += '</table>';
  document.getElementById('tableWrap').innerHTML = html;
}

function run() {
  const raw = document.getElementById('sentence').value;
  const tokens = tokenise(raw);
  const resultEl = document.getElementById('result');

  if (tokens.length === 0) {
    resultEl.textContent = 'Enter a sentence above.';
    resultEl.className = 'result info';
    document.getElementById('tableWrap').innerHTML = '';
    return;
  }

  const unknown = tokens.find(t => !TERM_MAP[t]);
  if (unknown) {
    resultEl.textContent = fmt('Unknown token: "%unknown%". Use: a + * ( )', { unknown: unknown });
    resultEl.className = 'result err';
    document.getElementById('tableWrap').innerHTML = '';
    return;
  }

  const table = cyk(tokens);
  renderTable(table, tokens);

  const n = tokens.length;
  const accepted = table[0][n-1].has('S');
  resultEl.textContent = accepted
    ? fmt('✓ Accepted — S spans [0, %v%]. Grammatically valid!', { v: n-1 })
    : fmt('✗ Rejected — S does not appear in cell [0, %v%].', { v: n-1 });
  resultEl.className = accepted ? 'result ok' : 'result err';

  console.log('CYK table:');
  for (let i = 0; i < n; i++)
    for (let j = i; j < n; j++)
      console.log(`[${i},${j}]`, [...table[i][j]].join(' ') || '(empty)');
}

document.getElementById('parseBtn').addEventListener('click', run);
document.getElementById('clearBtn').addEventListener('click', () => {
  document.getElementById('sentence').value = '';
  document.getElementById('result').textContent = '';
  document.getElementById('tableWrap').innerHTML = '';
});
document.getElementById('sentence').addEventListener('keydown', e => {
  if (e.key === 'Enter') run();
});
run();
Result
Console

Each cell [i, j] shows the set of non-terminals that can derive the substring from position i to j. If the start symbol S appears in the top-right cell spanning the whole input, the sentence is accepted. Notice how the table fills in layers: single tokens first, then pairs, then triples — each layer reuses the layers below it. That reuse is the heart of dynamic programming.

The Real Complexity

CYK was proven correct (not conjectured — proven) in the 1960s, and its time complexity is well-understood:

  • O(n3⋅∣G∣)O(n^{3} \cdot |G|) time to fill the table; with Chomsky Normal Form the grammar constant is absorbed into the rule count.
  • O(n2⋅∣G∣)O(n^{2} \cdot |G|) space for the table itself — polynomial in both input length and grammar size.
  • Decidable and in P: context-free recognition is not NP-hard, undecidable, or even a hard problem in the usual sense. It sits comfortably inside polynomial time.

The deeper question is whether O(n3)O(n^{3}) is tight. Under the widely-studied Boolean Matrix Multiplication (BMM) conjecture, no algorithm can recognize an arbitrary context-free grammar in O(n3−ᵋ)O(n^{3-}ᵋ) time for any ε > 0. The connection is not superficial: CYK can be rephrased as a chain of matrix-multiply-like operations over a Boolean semiring, and breaking the cubic barrier would imply a breakthrough in matrix multiplication.

So context-free parsing is solved in the complexity sense — CYK (and later Earley's algorithm, GLR, GLL) provide exact polynomial-time answers — but the exact exponent remains an open question tied to one of the deepest unsolved problems in fine-grained complexity theory. Compare this with P vs NP: there, we don't even know whether a polynomial-time solution exists; here, we have one, but we argue about whether the exponent 3 can be shaved.

Chomsky Normal Form is what makes CYK clean. Any context-free grammar can be mechanically transformed into CNF (rules of the form A → BC or A → a) without changing the language. CNF is the reason the table has a simple structure: every split of a substring into two halves corresponds to exactly one rule application.

Where It Matters

The CYK idea — fill a triangular table bottom-up over all substrings — turns out to describe a surprising range of real problems:

  • Compiler front-ends: every production parser generator (LALR, GLR, Earley) is a descendant of the same bottom-up dynamic-programming insight. When your IDE flags a syntax error, some variant of CYK's logic is running.
  • Natural-language processing: probabilistic CYK (PCYK) assigns probabilities to each rule and finds the most likely parse tree. It drove statistical NLP for decades before neural models took over — and the parse table structure still underlies many transformer attention patterns.
  • RNA secondary-structure prediction: an RNA strand folds back on itself like nested parentheses. The Nussinov algorithm and its successors (Zuker's mfold, RNAfold) use the exact same O(n3)O(n^{3}) DP table to find the minimum-energy fold — the grammar rules become base-pairing rules.
  • XML and JSON schema validation: deciding whether a document conforms to a schema is a context-free recognition problem. Efficient validators use CYK-derived techniques.
  • Synchronous grammars in machine translation: statistical MT systems use synchronous context-free grammars that parse source and target simultaneously — again, a CYK-shaped algorithm.

In each case the pattern is the same: a problem with nested, recursive structure maps onto a context-free grammar, and CYK's triangle solves it in cubic time. Learn CYK and you have a lens that brings structure to problems across computing, biology, and linguistics. Related algorithms like pattern matching tackle the simpler linear case, while sequence alignment uses the same DP philosophy on a different cost function.

Conclusion

The Cocke-Younger-Kasami algorithm is one of the cleanest examples of dynamic programming: a hard-looking question (does this sentence obey these rules?) dissolves into a triangle of tiny questions, each answered once and reused forever.

Its complexity status is unusual in this field: CYK is provably correct and provably polynomial, neither undecidable like the halting problem nor NP-hard like SAT. The open question is not whether it can be solved efficiently but how efficiently — and that question is tied to the deep mathematics of matrix multiplication.

The next time a text editor instantly highlights a mismatched bracket, or a compiler pinpoints the exact line of a syntax error, something descended from the 1965 CYK idea is drawing its triangle and reading the answer from the top.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/cyk-parsing/Content licensed under CC BY-NC 4.0.