CYK Parsing

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(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.

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 $a$, +, *, (, ) — 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">{{lbl_sentence}}</label>
  <div class="input-row">
    <input id="sentence" type="text" value="a + a * a" spellcheck="false" autocomplete="off" />
    <button id="parseBtn" type="button">{{btn_parse}}</button>
    <button id="clearBtn" type="button" class="ghost">{{btn_clear}}</button>
  </div>
</div>
<div id="result" class="result"></div>
<div id="tableWrap" class="table-wrap"></div>
<div class="legend">
  <b>{{legend_heading}}</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; }

// Code not found

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.

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

• $O(n^{3} \cdot |G|)$ time to fill the table; with Chomsky Normal Form the grammar constant is absorbed into the rule count.
• $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(n^{3})$ is tight. Under the widely-studied Boolean Matrix Multiplication (BMM) conjecture, no algorithm can recognize an arbitrary context-free grammar in $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.

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(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.

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.