Abstract flowing gradient in deep indigo and blue tones, smooth and luminous, evoking a modern digital learning atmosphere

Computer Science and programming articles. We do not sell courses.

A practical guide to the Cocke-Younger-Kasami parsing algorithm

The Cocke-Younger-Kasami algorithm, often shortened to CYK, is one of the classical solutions to a fundamental problem in computer science: deciding whether a string can be generated by a context-free grammar. It belongs to the family of dynamic programming parsers and remains a touchstone in compiler construction courses taught at universities across Australia, from the University of Melbourne to the University of New South Wales. While newer algorithms handle richer grammar classes, CYK still appears in research papers, NLP toolchains, and competitive programming competitions because its mechanics are so transparent.

What makes CYK appealing is its reliance on a recogniser table that grows alongside the input, allowing each substring to be classified by the non-terminals capable of deriving it. The algorithm presupposes Chomsky normal form, where every production is either A → BC or A → a. Converting a grammar into this shape is a mechanical preprocessing step, and once it is done, the parser itself is straightforward to implement. For learners who already understand context-free languages, CYK becomes an elegant exercise in tabulation.

Beyond its theoretical role, CYK has practical reach. Probabilistic extensions power some speech recognition pipelines, and the same tabulation idea appears in bioinformatics where it scores RNA secondary structures. Engineers working on tooling for Australian-language data sets, including parsers that handle loanwords from Mandarin and Arabic, often reach for CYK as a baseline because its deterministic runtime makes it easy to audit.

Foundations of context-free grammars and Chomsky normal form

A context-free grammar consists of terminals, non-terminals, a start symbol, and production rules. The parser does not need to understand the application domain, but it does need every rule to fit a specific shape. In Chomsky normal form, each production either rewrites a non-terminal into exactly two non-terminals, or into a single terminal. This restriction is what lets CYK combine pairs of adjacent substrings rather than guessing at arbitrary right-hand sides.

Converting a grammar into CNF involves removing unit productions, eliminating useless symbols, and breaking long right-hand sides into binary chains. Tools such as the Natural Language Toolkit in Python can perform these transformations automatically, but doing them by hand on a small grammar helps build intuition. A typical undergraduate assignment at Monash University or the Australian National University walks students through converting a small English fragment grammar into CNF before feeding it to a CYK implementation.

Once the grammar is normalised, every cell in the recognition table can be filled using a single rule: a non-terminal A belongs to cell [i, j] if there exists a production A → B C such that B covers [i, k] and C covers [k, j] for some split point k. This decomposition is the heart of the algorithm.

How the CYK recognition table works

The recognition table is a triangular structure indexed by the start and end positions of substrings. Cells along the diagonal store non-terminals that derive a single terminal, and longer substrings are computed by combining pairs of shorter cells. This bottom-up approach mirrors how Fibonacci numbers can be computed iteratively rather than recursively, trading recursion for a table that is easy to inspect and verify.

Implementation begins by initialising the diagonal: for each input token, the algorithm scans every production of the form A → token and marks A as present in cell [i, i+1]. Subsequent passes lengthen the span being considered. For span length two, every adjacent pair of cells is checked against binary productions. The process continues until the full string length is reached, and recognition succeeds if the start symbol appears in cell [0, n].

Pseudocode for the core loop resembles a nested structure where the outermost loop controls span length, the middle loop slides the window along the input, and the innermost loop tests split points. Each test is a constant-time lookup if the grammar is stored as a dictionary mapping right-hand sides to sets of left-hand non-terminals. Engineers at Australian fintechs building domain-specific languages sometimes profile CYK on thousands of rule combinations to keep this lookup efficient.

Constructing parse trees from recognition results

Recognition alone answers a yes-or-no question, but most applications need the actual parse tree. CYK records this by storing backpointers: instead of writing only the non-terminal A into a cell, the algorithm saves the production A → B C together with the split point k that proved A viable. Walking the backpointers from the top cell reconstructs the tree by recursively expanding each non-terminal into its two children.

When a string has multiple derivations, several backpointers may live in the same cell. Choosing among them can be done arbitrarily to obtain one parse, or systematically to enumerate every parse, which is useful for grammar debugging. A common technique is to prefer the most probable derivation in probabilistic CYK, where each production carries a weight and the algorithm selects the highest-scoring path. Speech and translation systems used by Sydney-based teams at Canva and Atlassian occasionally incorporate such extensions when post-processing model outputs.

Practical implementations often return the tree as nested tuples or a small class hierarchy. In Python, a namedtuple with fields for the non-terminal symbol and its children works well for small grammars, while larger pipelines serialise the tree to JSON or to an lxml element so downstream consumers can walk it with familiar APIs.

Complexity, variants, and implementation considerations

The textbook running time of CYK is O(n³ · |G|), where n is the length of the input and |G| is the size of the grammar. The cubic term arises from the three nested loops over span length, start position, and split point. Space is O(n²) for the table itself, plus additional room for backpointers. These bounds are acceptable for short sentences and modest grammars, but they explain why CYK is rarely used unmodified on web-scale corpora.

Several variants target specific bottlenecks. Earley parsing handles general CFGs without requiring CNF, and chart parsers in the style of the CYK idea can incorporate left-corner or left-recursion-friendly strategies. For probabilistic grammars inside NLP pipelines, weighted CYK integrates probabilities directly into the table, replacing set membership with maximum-weight tracking. Researchers at CSIRO's Data61 have published work showing how such variants can be parallelised across graphics processing units to process long sentences in reasonable time.

When implementing CYK from scratch, a few habits help. Pre-compute a reverse index from right-hand sides to left-hand non-terminals so each cell test is O(1) per candidate split. Reuse a single table object across multiple inputs to avoid repeated allocation, especially in batch jobs. For very long inputs, consider switching to a packed-chart representation that stores only non-empty cells. The hello ML community has discussed similar trade-offs in adjacent articles, including an a guide to the Shapley value for feature importance which tackles a different kind of combinatoric explosion in interpretability work.

Applications, education, and resources for Australian practitioners

CYK lives at the intersection of theory and practice. Compiler front-ends for languages with well-defined grammars sometimes include CYK as a validation pass, even when the primary parser is hand-written or generated. Bioinformatics pipelines use the same triangular tabulation to fold RNA sequences, since base pairing behaves like a binary grammar production. Educational games that visualise parsing also rely on CYK because every step corresponds to a visible change in the table.

In Australia, several communities help practitioners deepen their understanding. The Melbourne Python User Group occasionally hosts workshops where attendees build a CYK recogniser in an evening. Students at the University of Sydney can enrol in compilers and formal languages courses that include a CYK assignment, while the Brisbane-based Griffith University has run student showcases on probabilistic grammar parsing. For those curious about how ensemble methods in machine learning share the spirit of combining simpler estimators, the article on a guide to ensemble learning bagging and boosting draws an instructive parallel: just as CYK combines substrings into larger phrases, boosting combines weak learners into a stronger one.

Recommendations for building a robust CYK implementation