# CKY Parsing

CKY parsing is a bottom-up dynamic programming algorithm for context-free grammars, published by Itiroo Sakai in 1961 and rediscovered by Cocke, Younger, Kasami, and Schwartz. It runs in O(n^3 · |G|) worst-case time and requires Chomsky normal form.

CKY parsing (also called CYK, for Cocke-Younger-Kasami) is a parsing algorithm for context-free grammars that uses bottom-up parsing and dynamic programming. It was first published by Itiroo Sakai in 1961 and later independently rediscovered by John Cocke, Daniel Younger, Tadao Kasami, and Jacob T. Schwartz, after whom it is named. The algorithm determines whether a given string can be generated by a grammar and, if so, can construct all possible parse trees for that string.

The standard version of CKY operates only on context-free grammars in Chomsky normal form (CNF), where every production rule is either of the form A → BC (two nonterminals) or A → a (a terminal). Any context-free grammar that does not generate the empty string can be algorithmically transformed into an equivalent CNF grammar, so this restriction does not limit the algorithm's applicability in principle. For grammars that generate the empty string, one can explicitly allow a rule S → ε, where S is the start symbol.

The importance of CKY parsing stems from its worst-case time complexity of O(n^3 · |G|), where n is the length of the input string and |G| is the size of the CNF grammar. This makes it one of the most efficient parsing algorithms in terms of asymptotic worst-case behavior, although other algorithms may have better average running times in practical scenarios.

## Algorithm Overview

The algorithm works by filling a three-dimensional table P[l, s, v], where each entry is a Boolean value indicating whether the substring of length l starting at position s can be generated from nonterminal R_v. The table is filled in increasing order of substring length, starting with substrings of length 1.

For each terminal symbol in the input, the algorithm checks all unit productions of the form R_v → a_s and marks the corresponding table entries as true. For longer substrings, it considers every possible partition of the substring into two parts and checks whether there exists a production A → BC such that B generates the first part and C generates the second part. If such a production exists, the entry for A is set to true.

## Pseudocode

let the input be a string I consisting of n characters: a1 ... an.
let the grammar contain r nonterminal symbols R1 ... Rr, with start symbol R1.
let P[n,n,r] be an array of Booleans. Initialize all elements of P to false.
let back[n,n,r] be an array of lists of backpointing triples. Initialize all elements of back to the empty list.

for each s = 1 to n
  for each unit production Rv → as
    set P[1,s,v] = true

for each l = 2 to n -- Length of span
  for each s = 1 to n-l+1 -- Start of span
    for each p = 1 to l-1 -- Partition of span
      for each production Ra → Rb Rc
        if P[p,s,b] and P[l-p,s+p,c] then
          set P[l,s,a] = true,
          append <p,b,c> to back[l,s,a]

if P[n,1,1] is true then
  I is member of language
  return back -- by retracing the steps through back, one can easily construct all possible parse trees of the string.
else
  return "not a member of language"

## Example

Consider the following grammar in CNF:

S → NP VP
VP → VP PP
VP → V NP
VP → eats
PP → P NP
NP → Det N
NP → she
V → eats
P → with
Det → the
N → fish

To parse the string "she eats the fish with the fish", the algorithm first marks all length-1 substrings. For instance, P[1,1,NP] is set to true because NP → she, and P[1,2,VP] is set to true because VP → eats. Then it processes length-2 substrings, such as "she eats", which can be derived as S → NP VP, so P[2,1,S] becomes true. The process continues for longer substrings, considering all partitions. At the end, if P[n,1,S] is true, the string is recognized as part of the language, and the backpointers allow reconstruction of the parse tree.

## Applications and Variants

CKY parsing is widely used in natural language processing and computational linguistics, particularly for parsing with probabilistic context-free grammars. Variants of the algorithm have been developed to handle weighted grammars and to improve average-case performance. The algorithm's dynamic programming approach also connects it to other parsing methods, such as the Earley parser, which handles arbitrary context-free grammars without CNF conversion but has a similar worst-case complexity.

In modern [artificial-intelligence](https://www.wikiprompt.org/wiki/artificial-intelligence) systems, CKY parsing has been largely superseded by [neural-network](https://www.wikiprompt.org/wiki/neural-network) based approaches, particularly [transformer](https://www.wikiprompt.org/wiki/transformer) models used in [large-language-model](https://www.wikiprompt.org/wiki/large-language-model)s. However, the algorithm remains an important foundational technique in formal language theory and is still taught in computer science curricula. Its principles of dynamic programming and bottom-up analysis also appear in other areas, such as [sequence-to-sequence](https://www.wikiprompt.org/wiki/sequence-to-sequence) models and [beam-search](https://www.wikiprompt.org/wiki/beam-search) decoding.

The algorithm's efficiency and clarity have made it a standard example in textbooks on parsing and [machine-learning](https://www.wikiprompt.org/wiki/machine-learning). Research institutions like [mit-csail](https://www.wikiprompt.org/wiki/mit-csail) and [stanford-ai-lab](https://www.wikiprompt.org/wiki/stanford-ai-lab) have contributed to its study and application, and it remains relevant in fields that require exact parsing of structured data, such as bioinformatics and compiler design.

## Limitations

CKY parsing requires the grammar to be in Chomsky normal form, which can increase the number of production rules and the size of the grammar. The O(n^3) worst-case time complexity can be prohibitive for very long input strings, especially in real-time applications. Additionally, the algorithm's space complexity is O(n^2 · r), which can be large for grammars with many nonterminals. Despite these limitations, CKY parsing remains a benchmark for exact parsing algorithms and a key concept in the study of context-free languages.

---
Source: https://www.wikiprompt.org/wiki/cky-parsing
License: CC BY-SA 4.0 (https://creativecommons.org/licenses/by-sa/4.0/)
Last updated: 2026-09-13T04:00:02.719806+00:00