CYK algorithm
The Cocke–Younger–Kasami (CYK) algorithm is a dynamic programming-based bottom-up parsing method for determining whether a given string belongs to the language generated by a context-free grammar (CFG) and, if so, constructing one or more corresponding parse trees.[1][2] It requires the grammar to be in Chomsky normal form (CNF), where productions are limited to A → BC (two non-terminals) or A → a (a single terminal), and fills an n × n triangular table (for input length n) by iteratively combining non-terminals over increasingly longer substrings, starting from single terminals.[3] The algorithm achieves O(n³) time complexity and O(n²) space usage, enabling efficient recognition and syntax analysis without exponential growth in computation relative to input size.[1][2]
The algorithm was first published by Itiroo Sakai in 1961.[4] It was independently developed in the mid-1960s by Tadao Kasami in a 1965 technical report on efficient recognition and syntax analysis for context-free languages, followed by Daniel H. Younger's 1967 publication detailing its application to parsing in cubic time, and later by John Cocke in approximately 1970 as part of broader work on compiler optimization.[5][1][2] Kasami's formulation emphasized the algebraic properties of context-free languages to avoid exhaustive enumeration, while Younger's version explicitly constructed a parsing matrix to handle ambiguity by tracking multiple derivations.[1][2]
In practice, the CYK algorithm underpins probabilistic parsing models like probabilistic CFGs (PCFGs) in natural language processing, where it is extended to compute the most likely parse by associating probabilities with grammar rules and selecting the highest-scoring tree.[3] Its tabular structure naturally accommodates structural ambiguities in sentences, making it foundational for applications in syntax analysis, machine translation, and compiler design, though it is typically preceded by grammar conversion steps that may introduce minor overhead.[3] Despite its cubic time bound, optimizations and parallel implementations have extended its utility to larger inputs in modern computational linguistics.[1]
Fundamentals
Definition and Purpose
The CYK algorithm, also known as the Cocke–Younger–Kasami algorithm, is a bottom-up dynamic programming parser for determining membership in the language generated by a context-free grammar (CFG) when the grammar is in Chomsky Normal Form (CNF).[6][2][7] It operates by systematically building possible parses from smaller substrings to the full input string, enabling efficient recognition of valid derivations.[6][2]
The algorithm was independently developed by Tadao Kasami in a 1965 technical report, Daniel H. Younger in a 1967 journal article, and John Cocke in an unpublished IBM technical report from around 1970.[6][2][7] These contributions established a foundational method for CFG parsing that remains influential in theoretical computer science.[6][2]
Its primary purpose is to solve the membership problem for CFGs in CNF—verifying if a string of length n belongs to the grammar's language—in cubic time, specifically O(n3) worst-case complexity.[6][2] This efficiency stems from the algorithm's reliance on a triangular table structure that stores nonterminal sets for all substrings, consuming O(n2) space.[8] It solves the membership problem and, with appropriate bookkeeping, supports the construction of parse trees for valid derivations, accommodating ambiguity by tracking multiple possible nonterminals.[2][8]
The CYK algorithm underpins applications in natural language processing for syntactic analysis of sentences, compiler design for efficient syntax checking during code compilation, and formal verification for validating properties in systems modeled by context-free languages.[9][10][2]
Context-Free Grammars and Chomsky Normal Form
A context-free grammar (CFG) is a formal system for generating strings in a language, defined as a quadruple G = (V, \Sigma, P, S), where V is a finite set of nonterminal symbols (variables), \Sigma is a finite set of terminal symbols (the alphabet), P is a finite set of production rules each of the form A \to \alpha with A \in V and \alpha \in (V \cup \Sigma)^*, and S \in V is the designated start symbol.[11] The language generated by G, denoted L(G), consists of all terminal strings derivable from S via applications of the productions in P.[11]
In the Chomsky hierarchy of formal grammars, CFGs occupy Type-2, positioned between Type-3 regular grammars and Type-1 context-sensitive grammars.[12] The class of context-free languages (CFLs) they generate exhibits closure properties under key operations: specifically, if L_1 and L_2 are CFLs, then so are their union L_1 \cup L_2, concatenation L_1 L_2, and Kleene star L_1^*.[11] These properties facilitate the construction of CFGs for combined languages without altering the context-free nature.
Chomsky normal form (CNF) restricts a CFG to simplify analysis while preserving the generated language. A grammar G is in CNF if every production rule is either A \to B C (where A, B, C \in V and B, C \neq S) or A \to a (where a \in \Sigma), except possibly for the start symbol production S \to \epsilon if the empty string is in the language.[11] This binary or unary structure eliminates longer chains, epsilon rules (beyond the start), and unit productions.
Converting an arbitrary CFG to CNF involves a systematic sequence of transformations that maintain equivalence. First, eliminate all \epsilon-productions by identifying nullable variables (those deriving \epsilon) and substituting them in other rules, adjusting for the start symbol if necessary.[13] Next, remove unit productions (A \to B) by replacing each with the productions of B, iteratively until none remain.[13] Finally, handle productions with more than two nonterminals or intermixed terminals by introducing new nonterminals to binarize chains (e.g., A \to B C D becomes A \to B X, X \to C D) and replace terminals in non-unary rules (e.g., A \to a B becomes A \to X B, X \to a).[13]
The CNF restriction is essential for efficient parsing of CFLs, as it enables dynamic programming algorithms to recognize membership in O(n^3) time for strings of length n by limiting combinations to pairs of nonterminals, mirroring binary derivation trees.[2] This form underpins the CYK algorithm's table-filling procedure, where subproblem solutions build upon binary splits of the input.[2]
Core Algorithm
Dynamic Programming Approach
The CYK algorithm utilizes a bottom-up dynamic programming strategy to solve the membership problem for context-free grammars in Chomsky normal form (CNF), constructing parses for increasingly longer substrings of the input string. This approach systematically builds solutions to larger parsing subproblems by combining results from smaller ones, ensuring that each substring is analyzed only once to avoid redundant computations. The core data structure is a triangular table T[1..n, 1..n], where n is the length of the input string w = w_1 w_2 \dots w_n, and each entry T[i,j] contains the set of non-terminals that derive the substring w_i \dots w_{i+j-1} according to the grammar. For base cases where j = 1, T[i,1] is populated with non-terminals A such that there exists a production A \to w_i.[1][14]
The fundamental recurrence relation for filling the table when j > 1 is defined as follows:
T[i,j] = \left\{ A \ \middle|\ A \to BC \in [P](/page/P′′), \exists k \in \{1, \dots, j-1\} \text{ s.t. } B \in T[i,k] \text{ and } C \in T[i+k, j-k] \right\}
where P is the set of productions in the CNF grammar. This relation composes binary productions to derive non-terminals for longer spans by considering all possible split points k, effectively building a parse bottom-up from terminal symbols to the full string. The table is filled in order of increasing j, and for each j, over all starting positions i from 1 to n-j+1. This process captures the compositional nature of context-free languages, where substrings are parsed independently before integration into larger constituents.[1][14]
The time complexity of the CYK algorithm is O(n^3 |G|), where |G| represents the number of productions in the grammar, arising from the O(n^2) table entries, each requiring up to O(n |G|) work to compute via the recurrence. Space complexity is O(n^2), dominated by the storage of the table itself. A string is accepted by the grammar if and only if the start symbol S appears in T[1,n], confirming that the entire input derives from S. This dynamic programming framework provides an efficient, tabular method for parsing, leveraging memoization to eliminate overlapping subproblems inherent in recursive descent approaches.[1][14]
Pseudocode Implementation
The CYK algorithm is typically implemented using a dynamic programming table T, where each entry T[i,j] is a set of non-terminals that can derive the substring w_i \dots w_j of the input string w of length n. This set-based representation accommodates ambiguity by allowing multiple non-terminals per cell without duplication.[15]
For substrings of length 1, the table is initialized by adding each non-terminal A to T[i,i] if there is a production A \to w_i in the grammar.[15]
The full pseudocode for the standard membership version, assuming a context-free grammar in Chomsky normal form (CNF), is as follows:
algorithm CYK_membership(w, G = (V, Σ, P, S))
n ← length(w)
if n = 0 then
return (S → ε) ∈ P // Handle empty string if ε-rule for start symbol exists
T ← array[1..n, 1..n] initialized to empty sets
// Base case: single terminals
for i ← 1 to n do
for each production A → a ∈ P s.t. a = w[i] do
T[i, i] ← T[i, i] ∪ {A}
// Inductive case: longer substrings
for j ← 2 to n do // length of substring
for i ← 1 to n - j + 1 do // starting index
end ← i + j - 1
for split ← i to end - 1 do // split position k
for each production A → B C ∈ P do
if B ∈ T[i, split] and C ∈ T[split + 1, end] then
T[i, end] ← T[i, end] ∪ {A}
return S ∈ T[1, n]
end
algorithm CYK_membership(w, G = (V, Σ, P, S))
n ← length(w)
if n = 0 then
return (S → ε) ∈ P // Handle empty string if ε-rule for start symbol exists
T ← array[1..n, 1..n] initialized to empty sets
// Base case: single terminals
for i ← 1 to n do
for each production A → a ∈ P s.t. a = w[i] do
T[i, i] ← T[i, i] ∪ {A}
// Inductive case: longer substrings
for j ← 2 to n do // length of substring
for i ← 1 to n - j + 1 do // starting index
end ← i + j - 1
for split ← i to end - 1 do // split position k
for each production A → B C ∈ P do
if B ∈ T[i, split] and C ∈ T[split + 1, end] then
T[i, end] ← T[i, end] ∪ {A}
return S ∈ T[1, n]
end
This implementation assumes no ε-rules in the grammar except possibly S \to \epsilon for the empty string case, as required by CNF.[15]
A basic probabilistic extension for probabilistic CFGs replaces the set unions with computations of summed or maximized probabilities over productions, yielding the inside probabilities for total likelihood or Viterbi scores for the most probable parse.[16]
Step-by-Step Execution
The execution of the CYK algorithm commences with the initialization of an n × n dynamic programming table, where n denotes the length of the input string, arranged in a triangular fashion to represent substrings. All cells begin empty, and the base case for substrings of length 1 is populated first: for each position i ranging from 1 to n, the diagonal cell T_{i,i} receives all non-terminals A for which a production A → w_i exists, with w_i being the terminal symbol at that position.[17] This step identifies the fundamental units derivable directly from the grammar's terminal rules.[18]
Subsequent iterations proceed in a bottom-up manner, processing substrings of increasing length k from 2 to n. For each k, the algorithm iterates over all starting positions i from 1 to n - k + 1, targeting the substring spanning i to i + k - 1. Within each such substring, it examines every possible split point j from i to i + k - 2. At each split, the contents of T_{i,j} and T_{j+1,i+k-1} are consulted; if a binary production A → B C holds where B belongs to the first cell's set and C to the second, then A is incorporated into T_{i,i+k-1}. This ordered filling—by length, then position, then split—leverages previously computed subresults to build longer derivations systematically.[17][18]
The combination mechanism hinges on efficient matching of binary rules, assuming the grammar adheres to Chomsky normal form with productions limited to two non-terminals on the right-hand side or a single terminal. To expedite this, productions are typically preprocessed into indexed structures, such as sets or hash tables mapping pairs of non-terminals to deriving non-terminals, thereby avoiding exhaustive grammar scans during table filling.[17] Multiple additions to a cell may occur across splits, accumulating all viable non-terminals that can derive the substring.
Verification concludes the process by inspecting the root cell T_{1,n}: the input string belongs to the language if the start symbol S appears therein. Ambiguity arises if multiple derivation paths lead to S, though the algorithm itself does not enumerate them.[19][18]
A frequent implementation challenge involves inadequate rule indexing, which forces repeated full grammar traversals and inflates time complexity beyond the standard O(n^3). Proper preprocessing mitigates this, ensuring lookups remain constant time per check.[17]
Illustrative Example
Grammar Setup
To illustrate the CYK algorithm, consider a context-free grammar G = (V, \Sigma, P, S) in Chomsky normal form (CNF), where V = \{S, A, B, C\} is the set of nonterminals, \Sigma = \{a, b\} is the set of terminals, S is the start symbol, and P consists of the following productions:
\begin{align*}
S &\to AB \mid BC, \\
A &\to BA \mid a, \\
B &\to CC \mid b, \\
C &\to AB \mid a.
\end{align*}
This grammar is in CNF because every production is of the form X \to YZ (where X, Y, Z are nonterminals) or X \to \sigma (where \sigma \in \Sigma).[20]
The input string to parse is w = baaba, with length n = 5. The symbols are positioned as w_1 = b, w_2 = a, w_3 = a, w_4 = b, w_5 = a. This example is selected for its moderate size, which facilitates a clear visualization of the dynamic programming table without excessive complexity, while demonstrating the algorithm on a string accepted by the grammar.[20]
Table Construction and Results
The CYK algorithm constructs a triangular table T, where T[i,j] represents the set of non-terminals that derive the substring starting at position i and ending at position j (with j \geq i). For the example grammar in Chomsky normal form and input string "baaba" of length n=5, the table is filled bottom-up by increasing substring length l = j - i + 1.
For the base case of length 1 substrings, each cell is populated by matching the terminal symbol to applicable unit productions. Thus, T[1,1] = \{B\} since the first "b" matches B \to b; T[2,2] = \{A, C\} for the first "a" via A \to a and C \to a; T[3,3] = \{A, C\} for the second "a"; T[4,4] = \{B\} for "b"; and T[5,5] = \{A, C\} for the last "a).
For length 2 substrings, the algorithm examines possible splits at each k between i and j. For T[1,2] ("ba"), the only split is at k=1, yielding T[1,1] = \{B\} and T[2,2] = \{A, C\}; matching productions include A \to BA (adding A) and S \to BC (adding S), so T[1,2] = \{S, A\}. For T[2,3] ("aa"), split at k=2: T[2,2] = \{A, C\} and T[3,3] = \{A, C\}, matching B \to CC (adding B), so T[2,3] = \{B\}. For T[3,4] ("ab"): T[3,3] = \{A, C\} and T[4,4] = \{B\}, matching S \to AB and C \to AB (adding S, C), so T[3,4] = \{S, C\}. For T[4,5] ("ba"): similar to T[1,2], T[4,5] = \{S, A\}.
Higher lengths are filled similarly by checking all possible splits and applicable productions. The completed table is:
| Length \ Starting | 1 | 2 | 3 | 4 | 5 |
|---|
| 5 | {A,S,C} | | | | |
| 4 | ∅ | {A,S,C} | | | |
| 3 | ∅ | {B} | {B} | | |
| 2 | {S,A} | {B} | {S,C} | {S,A} | |
| 1 | {B} | {A,C} | {A,C} | {B} | {A,C} |
Advanced Features
Parse Tree Generation
To generate a parse tree from the CYK table after determining membership, the algorithm is modified to augment each table entry with backpointers during the filling phase. These backpointers are typically stored as tuples consisting of a production rule (e.g., A \to B C) and the split position k that led to the non-terminal in the cell, allowing traceability of the derivation path.[21][22]
The backtracking process begins with a recursive descent from the root cell T[1,n], where n is the input string length, assuming the start symbol S is present. Starting at this cell, a suitable production S \to A B is selected from the backpointers, along with a corresponding split position k; the process then recurses on the subintervals T[1,k] for A and T[k+1,n] for B, continuing until reaching the base case of single-word spans with terminal productions. This yields a hierarchical structure representing the derivation.[21][22]
In cases of ambiguity, where multiple productions or splits apply to a cell, the standard augmented CYK recovers one valid parse tree via the backpointers. To enumerate all possible trees, the algorithm must explore every alternative backpointer in the relevant cells, potentially producing an exponential number of outputs relative to the degree of ambiguity in the grammar and input.[21][22]
The resulting parse tree is output as a rooted structure, with internal nodes labeled by non-terminals and edges connecting via production rules, terminating in leaves that match the input terminals in order. For the illustrative example discussed earlier, these backpointers would enable reconstruction of the specific derivation tree leading to acceptance without refilling the table.[21][22]
Constructing a single parse tree via backtracking requires O(n^2) time, proportional to the table size, following the O(n^3) table-filling phase; however, full enumeration of ambiguous parses can incur exponential time due to branching over multiple backpointers.[21][22]
Non-CNF Grammar Parsing
The standard CYK algorithm is limited to context-free grammars (CFGs) in strict Chomsky normal form (CNF), where all productions are of the form A \to BC (with B and C nonterminals) or A \to a (with a a terminal), and it does not directly handle ε-productions or unit productions (A \to B), requiring preprocessing to avoid incorrect results or infinite loops. These limitations arise because the dynamic programming table in CYK relies on binary combinations of nonterminals to fill spans of length greater than 1, making mixed or longer right-hand sides incompatible without adaptation.[23]
To apply CYK to a general CFG G, the grammar must first be converted to an equivalent CNF grammar G' that generates the same language. To achieve polynomial size growth, the conversion follows an optimal order of steps: (1) Introduce a new start symbol S_0 if the original start symbol appears on any right-hand side, adding the production S_0 \to S; (2) Binarize productions with more than two symbols on the right-hand side by iteratively introducing new nonterminals (e.g., for A \to X_1 X_2 X_3 X_4, create A \to X_1 A_1, A_1 \to X_2 A_2, A_2 \to X_3 X_4), handling mixed RHS with terminals; (3) Remove ε-productions by computing the set of nullable nonterminals via fixed-point iteration and adding new productions for all non-empty subsets of RHS symbols (now at most 3 per binary rule), while removing original ε-rules; (4) Eliminate unit productions by computing the transitive closure of unit chains and substituting direct non-unit productions; (5) Separate terminals from nonterminals in mixed productions by replacing each terminal a with a new nonterminal A_a and adding A_a \to a. This process runs in O(|G|^2) time overall and produces a grammar with O(|G|^2) productions; suboptimal orders (e.g., ε-removal before binarization) can cause exponential growth.[23][24]
The conversion enlargement affects CYK's time complexity, raising it from O(n^3) to O(|G| n^3) with a larger constant factor, where n is the input string length.[23]
As an alternative to full CNF conversion, a generalized CYK algorithm can parse general CFGs directly by extending the recurrence relation to match productions of arbitrary length and form, using precomputed sets for nullable symbols and unit chains to handle ε- and unit productions efficiently.[23] This variant first transforms the grammar to binary normal form (allowing single terminals but requiring binary nonterminal combinations), computes nullable nonterminals and the inverse unit relation in O(|G|) time, then fills the DP table by applying all matching productions over sub-spans, yielding O(|G| n^3) time with only linear grammar size increase (O(|G|)) and no need for terminal-specific nonterminals.[23] However, it incurs higher constants from scanning longer productions during table filling compared to strict CNF.
The choice between CNF conversion and direct generalized CYK depends on the trade-off: conversion preprocessing takes O(|G|^2) time but enables the optimized binary-only recurrence, suitable for small-to-medium grammars where blowup is tolerable; direct methods are preferable for large grammars to avoid size explosion, despite slightly slower per-span computations, especially when repeated parsing on the same grammar is needed.[23]
Probabilistic and Weighted Variants
The probabilistic variant of the CYK algorithm, often denoted as PCKY, extends the standard algorithm to handle probabilistic context-free grammars (PCFGs) in Chomsky normal form, where each production rule is assigned a probability.[16] Instead of determining mere membership by set union, PCKY computes the probability of a nonterminal deriving a substring, addressing ambiguity by quantifying the likelihood of parses rather than just their existence.[25] For Viterbi parsing, which finds the most probable parse tree, the table entries store the maximum probability, replacing union with maximization over split points and rules.
The core recurrence for Viterbi PCKY is as follows: for a span from position i to j, the probability P(A \to w_{i..j}) is computed as
P(A \to w_{i..j}) = \max_{k} \left[ P(A \to B C) \cdot P(B \to w_{i..k}) \cdot P(C \to w_{k+1..j}) \right],
where the maximum is taken over all rules A \to B C and split points k between i and j.[16] This formulation corresponds to the inside probabilities in the inside-outside algorithm, originally developed for training PCFGs via expectation-maximization, where Viterbi approximates the most likely derivation.[26] For the total probability of a string (summing over all parses), the algorithm uses summation instead of maximization, yielding the inside probability \alpha_{i,j}(A) = \sum_{k} P(A \to B C) \cdot \alpha_{i,k}(B) \cdot \alpha_{k+1,j}(C).[16]
Weighted variants generalize PCKY further by operating over semirings, abstract algebraic structures that replace the Boolean operations of standard CYK (logical OR for union, AND for concatenation) with custom addition (\oplus) and multiplication (\otimes) operations.[27] This allows the same dynamic programming table to compute diverse quantities, such as costs or counts, without altering the structure. For instance, the tropical semiring (\mathbb{R} \cup \{\infty\}, \min, +, \infty, 0) computes minimum-cost parses by using minimization for \oplus and addition for \otimes, applicable to optimization problems like finding the lowest-weight derivation.[27] The probabilistic case uses the standard semiring (\mathbb{R}_+ \cup \{0\}, +, \times, 0, 1) for summing probabilities.[27]
Numerical stability poses challenges in probabilistic and weighted CYK due to underflow from repeated multiplications of small probabilities, especially for long sentences.[16] Solutions include working in log-space, where products become sums of log-probabilities (e.g., \log P(A \to w_{i..j}) = \max_k [\log P(A \to B C) + \log P(B \to w_{i..k}) + \log P(C \to w_{k+1..j})]), or scaling probabilities during computation to prevent overflow/underflow.[16] Inside-outside variants also incorporate scaling factors for stability during parameter estimation.[28]
These variants find key applications in natural language processing, particularly speech recognition, where PCFGs model syntactic structure from acoustic inputs, and the inside-outside algorithm trains grammars on corpora for improved accuracy.[26] In machine translation, probabilistic CYK enables efficient parsing of source sentences to guide rule-based or statistical transfer, handling ambiguity by selecting high-probability structures.[29]
Valiant's Generalization
In 1975, Leslie Valiant provided a significant generalization of the CYK algorithm by reformulating context-free language recognition as an algebraic computation over semirings, thereby extending its scope to a wider range of problems involving matrix operations.[30] This approach represents the grammar using matrices indexed by non-terminals, where the entry X_{A,B} is defined as the semiring sum over all production rules of the form A \to w B (with w a terminal matching the input symbol) for unary contributions, while binary rules A \to B C are captured through matrix multiplication, which combines substructures B and C.[30] For an input string of length n, the algorithm computes the n-th power of this rule matrix X to determine if the start symbol derives the string.[31]
The core computation involves a chain of multiplications on upper-triangular matrices to evaluate X^n via exponentiation by squaring, yielding a time complexity of O(n^3 \log n) using standard matrix multiplication algorithms, though the structure lends itself to high parallelizability with depth O(\log n).[30] Valiant's method achieves sub-cubic performance, such as O(n^{2.81}), when incorporating fast matrix multiplication techniques like Strassen's algorithm.[30]
This formulation unifies context-free parsing with broader algebraic paradigms, allowing application across semirings including the Boolean semiring for simple recognition and weighted semirings for variants like probabilistic parsing.[31] For grammars in Chomsky normal form, it is computationally equivalent to the standard CYK algorithm but offers greater generality, enabling solutions to non-linguistic problems such as all-pairs shortest paths via the min-plus semiring.[31] Historically, Valiant's work deepened the theoretical foundations of dynamic programming in formal languages and inspired advancements in parallel computing for algebraic problems.[30]