Constituency Parsing with CKY: Spans, Split Points and Inside Scores

Put the grammar into a useful form

The core CKY algorithm assumes rules of the form \(A\to BC\) or \(A\to w\), with special handling for any permitted empty string. Longer productions can be binarised using auxiliary nonterminals; unary rules require elimination or a closure procedure. Those transformations are part of the parser specification.

For a toy sentence robots carry parcels, use:

S  → NP VP
VP → V NP
NP → robots
NP → parcels
V  → carry

The grammar is deliberately tiny. It licenses one simple structure and says nothing about agreement, modifiers or unknown words. Starting with a constrained grammar makes the chart mechanics visible before adding linguistic coverage.

A chart cell names a span

Use half-open boundaries \([i,j)\). The sentence has tokens at positions 0, 1 and 2, and boundaries 0 through 3. Cell \((i,j)\) stores nonterminals that can derive exactly that span.

Initialise one-token spans from lexical rules:

To obtain VP over [1,3), split at 2 and combine V over [1,2) with NP over [2,3). To obtain S over [0,3), split at 1 and combine NP with VP. The chart stores each subanalysis once even if several larger trees reuse it.

The recurrence and its cost

For Boolean recognition,

Best tree versus total probability

A probabilistic context-free grammar assigns probabilities to rules, normalised for each left-hand nonterminal. A tree probability is the product of its rule probabilities. Best-tree CKY chooses the maximum product over each rule and split; the inside algorithm sums those products.

If a sentence has two trees with probabilities 0.3 and 0.2, its total probability under those alternatives is 0.5, while the best-tree score is 0.3. Under a complete set of those alternatives, the posterior probability of the best tree given the sentence is 0.6. Confusing these quantities leads to misleading confidence estimates.

A PCFG also needs a proper termination behaviour for its derivations if it is to define a distribution over finite trees. Locally normalised recursive rules alone do not guarantee that every derivation terminates.

Recover the tree

For best-tree parsing, save the winning rule and split point at each chart entry. Follow the backpointers from the root S over [0,n). Without them, the chart proves that a tree exists but does not tell you its structure.

Binarisation introduces artificial nodes. Remove or interpret those nodes consistently when evaluating against the original treebank. Otherwise a parser may be penalised for implementation-specific structure that the reference never annotated.

What the algorithm cannot fix

CKY searches the structures allowed by its grammar. If the correct tree is not licensed, exact search cannot return it. A strong scoring model cannot fix missing lexical coverage either. Distinguish grammar coverage, scoring mistakes and search approximation when analysing errors.

Plain context-free categories can also miss agreement or lexical preferences. Feature grammars enrich categories; lexicalised or neural scores add contextual evidence. These changes affect which subproblems can still be shared exactly. The dependency chapter explores another representation and its corresponding search choices.

References

1. Younger, D. H. Recognition and Parsing of Context-Free Languages in Time n³. Information and Control, 1967.
2. Bird, Klein and Loper. Analyzing Sentence Structure.
3. Manning and Schütze. Foundations of Statistical Natural Language Processing. MIT Press, 1999.