Grammars and Constituency Structure › Parsing with CKY

A parser analyzes a token sequence using a grammar; on a successful parse, it can return one or more licensed trees. For CFGs, the most important teaching algorithm is the Cocke-Kasami-Younger algorithm, usually called CKY. It is a dynamic programming algorithm that fills a table of spans. The table is often called a chart, and each cell records the nonterminals that can derive a particular substring. Because subspans are reused many times, CKY avoids the combinatorial explosion of enumerating full trees independently.

CKY requires the grammar to be in Chomsky Normal Form.

The grammar from earlier is already in CNF. Every rule is either a binary nonterminal rule, such as $S \to NP\ VP$, or a lexical rule, such as $Det \to \text{the}$. There are no rules with three or more symbols on the right-hand side, and no empty productions. This makes the CKY recurrence especially simple: every span longer than one token must be split into exactly two smaller spans.

A CFG can contain rules outside these forms. For example:

$$VP \to V\ NP\ PP$$

has three children. It can be binarized by introducing a fresh nonterminal:

$$VP \to V\ X_1, \qquad X_1 \to NP\ PP$$

The new nonterminal $X_1$ is an artificial intermediate constituent introduced by binarization. It is absent from the original ternary analysis and lets the parser decompose that rule into two binary steps. The original tree can be recovered by collapsing the artificial nodes after parsing. This is a common pattern in parsing: introduce auxiliary symbols to satisfy a normal form, then undo the auxiliary structure when presenting the final analysis.

Converting an arbitrary CFG to CNF also involves eliminating empty productions other than the permitted start-to-empty exception, and unit productions such as $A \to B$. These conversions can change the shape of the parse tree. To recover original trees, retain a mapping from transformed rules back to the original grammar. Any CFG can be converted to an equivalent CNF grammar under the stated empty-string convention, possibly with a larger set of nonterminals. The equivalence is in the generated language, not necessarily in the exact tree shapes. A parser that needs linguistically faithful trees must therefore reconstruct the original rule applications.

Suppose the input tokens are $w_0, w_1, \ldots, w_{n-1}$. We use half-open spans $[i, j)$, where $i$ is the start index and $j$ is one past the end. The span $[i, j)$ covers tokens $w_i$ through $w_{j-1}$. Half-open intervals are convenient because adjacent spans meet cleanly: the left span $[i, k)$ and the right span $[k, j)$ share the boundary $k$ without overlapping.

The following chart recurrence assumes $n \geq 1$. For empty input, accept exactly when the CNF grammar contains $S \to \varepsilon$; if a tree is requested, return the start node expanded by that empty production. Our later toy grammar has no empty production and therefore rejects empty input.

Let $\text{chart}[i][j]$ be the set of nonterminals that can derive the span $[i, j)$. The base case handles single tokens:

$$A \in \text{chart}[i][i+1] \quad \text{if} \quad (A \to w_i) \in R$$

The recursive case handles longer spans. A nonterminal $A$ derives $[i, j)$ if there is a split point $k$ and a binary rule $A \to B\ C$ such that $B$ derives the left span $[i, k)$ and $C$ derives the right span $[k, j)$:

$$A \in \text{chart}[i][j] \quad \text{if} \quad \exists k,\ i < k < j,\ (A \to B\ C) \in R,\ B \in \text{chart}[i][k],\ C \in \text{chart}[k][j]$$

The sentence is accepted if the start symbol $S$ is in $\text{chart}[0][n]$.

This recurrence is the heart of CKY. It is also the reason CNF matters. With binary rules, every span is split into exactly two parts. If rules could have three children, the recurrence would need to consider two split points at once, which is more complex. Binarization removes that complexity by turning one ternary rule into two binary rules. The parser then only needs to consider one split point per span.

The algorithm fills spans in increasing order of length. First all one-token spans, then all two-token spans, then all three-token spans, and so on. By the time we need a longer span, all of its subspans have already been computed. This is the same dynamic programming principle you saw with the Viterbi algorithm in Part VI, Ch 6, but here the table is indexed by spans rather than by time steps. In HMM Viterbi, a subproblem scores a prefix ending at a particular state. In CKY, it concerns a contiguous substring and its possible root category. The principle is the same: solve small problems once, store the results, and combine them to solve larger problems.

The fill order is triangular. Each cell is completed only after the smaller spans on both sides of its split have been completed.

The time complexity is:

$$O(n^3 |R|)$$

where $n$ is the number of tokens and $|R|$ is the number of grammar rules. For a fixed grammar, this is $O(n^3)$. For the recognition chart, which stores nonterminal membership rather than every tree, space is $O(n^2 |N|)$, where $|N|$ is the number of nonterminals. With a fixed grammar it is $O(n^2)$. Explicitly enumerating all parse trees adds output-sensitive work and storage beyond these bounds. The cubic bound grows quickly with input length; actual runtime also depends on the grammar and implementation. Binarization enables the binary recurrence, neural scores can rank structures, and pruning can reduce work by discarding candidates, with a possible loss of exactness. Where a grammar and input produce a sparse chart, a parser can also avoid work on absent constituents. Sparsity depends on the grammar and sentence; it is not guaranteed.

CKY is not the only CFG parsing algorithm. The Earley parser works on arbitrary CFGs without requiring CNF, and it has an $O(n^2)$ time bound for unambiguous grammars and a linear bound for more restricted classes such as fixed LR($k$) grammars. For the distinctions among Earley grammar classes and runtime bounds, see the discussion in Opedal et al. (2023). Generalized LR parsers are another family used in compiler construction. But CKY is the cleanest algorithm for understanding the span-based dynamic programming that underlies many statistical parsers. Once you understand CKY, the inside algorithm, Viterbi parsing, and many neural chart parsers become much easier to read.

A plain CFG says which trees are possible. A probabilistic context-free grammar says how likely each tree is. A PCFG assigns a probability to every rule with a given left-hand side:

$$P(A \to \alpha \mid A)$$

For each nonterminal $A$, the probabilities of all rules with left-hand side $A$ sum to 1:

$$\sum_{\alpha : (A \to \alpha) \in R} P(A \to \alpha \mid A) = 1$$

When treating these weights as a probability distribution over finite sentences, we also assume that generation terminates with probability 1. Local rule normalization alone does not guarantee this: a recursive grammar can put some probability on infinite derivations.

The probability of a finite parse tree is the product of the probabilities of all rule occurrences used in the tree:

$$P(T) = \prod_{(A \to \alpha) \in T} P(A \to \alpha \mid A)$$

The probability of a sentence is the sum of the probabilities of all its parse trees:

$$P(w) = \sum_{T : \text{yield}(T) = w} P(T)$$

A PCFG parser often returns the most likely tree:

$$T^* = \arg\max_{T:\,\mathrm{yield}(T)=w} P(T)$$

Here $w$ is the observed input token sequence, and the maximization ranges only over trees whose yield is $w$. This can be computed with a variant of CKY that stores scores instead of just sets of nonterminals. For each span and nonterminal, we keep the best score and a backpointer to the split point and children that achieved it. The backpointers let us reconstruct the best tree after the chart is filled. This is exactly the same idea as Viterbi decoding in an HMM, generalized from sequence positions to spans.

The inside algorithm computes the total probability of all parses of a span. Let $\beta[i][j][A]$ be the total probability that nonterminal $A$ derives the span $[i, j)$. The base case is lexical:

$$\beta[i][i+1][A] = P(A \to w_i \mid A)$$

if that lexical rule exists. The recursive case sums over split points and binary rules:

$$\beta[i][j][A] = \sum_{k=i+1}^{j-1} \sum_{A \to B\ C} P(A \to B\ C \mid A)\, \beta[i][k][B]\, \beta[k][j][C]$$

This is the PCFG analogue of the forward algorithm for HMMs. The root value $\beta[0][n][S]$ gives the sentence likelihood. The Viterbi variant replaces the sum with a max and stores backpointers. Inside values also support training and constituent uncertainty calculations, but an inside value alone is not the posterior probability that a span is a constituent in the observed sentence. That posterior also needs an outside contribution for the surrounding tree and normalization by the sentence probability, assumed positive.

In a PCFG, the probability of a rule depends only on its left-hand-side category. With coarse categories such as NP and VP, all occurrences of the same category share one rule distribution. The model can express a preference for an attachment rule, but cannot change that rule's probability directly in response to a surrounding word or discourse context. Richer categories can encode additional conditioning information. Some modern constituency parsers replace local rule probabilities with neural scores while retaining chart decoding. We will see that story in Constituency and Dependency Parsing.