THE CYK PARSER does this grammar make this sentence?
Given a context-free grammar, does a string belong to the language — and how does it parse? CYK answers it by dynamic programming over a triangular table: fill in which grammar symbols can produce each substring, building up from single letters to the whole string. If the start symbol reaches the top cell, the string is accepted.
THE TECHNIQUE substrings up, splits across
Put the grammar in Chomsky Normal Form (rules X→YZ or X→a). Row 1: which symbols make each single letter. Each higher row: for a substring, try every split point — if some rule X→YZ has Y making the left part and Z the right, X makes the whole. The top cell spans the string; if it holds the start symbol, accept. Type a string. live demo
HISTORY & CREDIT three names, three countries, one table
“CYK — one algorithm by three collaborators” — they collaborated never met on it; three independent discoveries, and the acronym even scrambles their order. cited
~1960 · John Cocke has the algorithm — but never publishes it (it circulates in lecture notes). 1965 / 1967 · Tadao Kasami (a USAF technical report) and Daniel Younger (published) reach it independently. Also Sakai (1961). the shape · O(n³) time, O(n²) space — the general CFG parser, requiring Chomsky Normal Form; the price of handling any grammar, ambiguous ones included. the name · “CYK” (Cocke-Younger-Kasami) is just the conventional listing — not by priority (Cocke, ~1960, was first) and not alphabetical: the ordered name is the alternate CKY (Cocke, Kasami, Younger), which is the chronological order too.
Independent triple invention, a scrambled acronym (CKY is the ordered one), and the first inventor unpublished. Cocke ~1960 / Kasami 1965 / Younger 1967
RECOMMEND FOR I-13 a 2-D table, sets as bitmasks
The parse table is 2-D (PS-004) and each cell is a set of symbols packed into a bitmask — and the combine + acceptance run on the compiler:
$ i13 run cyk.i13 # grammar S->AB|BC, ... ; string "baaba"
top = 11 (= S|A|C) accepted = 1 # the start symbol S reaches the top cell
Recommend: the DP runs — the triangular loops, the split loop, and the CNF combine (for each rule X→YZ, AND that Y is in the left set and Z in the right, then OR X in) all execute; a cell’s set of symbols packs into one f64 as a bitmask (S=1, A=2, B=4, C=8), so union is | and membership is & (verified top cell {S,A,C}=11, accepted). The table is a 2-D array — PS-004 — flattened i*(n+1)+l, exactly like Viterbi (080) and knapsack (053). Note: the only want is a native set/union type; the bitmask is the honest workaround for a bounded nonterminal alphabet, and it ties straight to I-13’s own grammar/parser.