Constituency and Dependency Parsing › Constituency Parsing

A chart parser reuses analyses of smaller spans instead of rebuilding them for every larger tree. We first make the grammar assumptions explicit, then examine that reuse.

We describe the continuous constituency grammars here using a context-free grammar:

[ G = (N, \Sigma, R, S) ]

where:

• $N$: a finite set of nonterminal symbols, the syntactic categories
• $\Sigma$: a finite set of terminal symbols, the words; $N$ and $\Sigma$ are disjoint
• $R$: a finite set of production rules of the form $A \to \alpha$ with $A \in N$ and $\alpha \in (N \cup \Sigma)^*$
• $S$: the designated start symbol for complete sentence derivations ($S \in N$)

A rule such as

[ NP \to Det\ N ]

says that a noun phrase can consist of a determiner followed by a noun. A parse tree records hierarchical rule applications. It does not fix the order of expanding independent branches: after applying (S\to A\ B), expanding (A) before (B), or (B) before (A), can give the same tree. Reading its leaves left to right recovers the sentence, and its internal categories describe the constituent structure.

For example, a small grammar might derive "the man saw the dog" with a tree like this:

S
├── NP
│   ├── Det: the
│   └── N: man
└── VP
    ├── V: saw
    └── NP
        ├── Det: the
        └── N: dog

The leaves are the tokens. Internal nodes carry syntactic categories, including phrase categories and preterminal part-of-speech categories. The root here is the sentence category S. Every internal node spans a contiguous run of leaves: "the man" and "saw the dog" are examples. This follows from the way ordered context-free rules combine adjacent yields and supplies the span decomposition used by CKY.

A context-free grammar can generate the same token sequence with more than one tree. That is syntactic ambiguity. A probabilistic context-free grammar, or PCFG, attaches a probability to each rule and defines the probability of a tree as the product of its rule probabilities:

[ P(T) = \prod_{r \in T} P(r) ]

where:

• $T$: a parse tree, understood as the multiset of rules applied in the derivation
• $r$: a rule occurrence in that derivation, drawn from the set $R$ of grammar rules
• $P(r)$: the probability the PCFG assigns to rule $r$. For each $A \in N$, $\sum_{r \in R:\operatorname{lhs}(r)=A} P(r) = 1$, where $\operatorname{lhs}(r)$ is the rule's left-hand side.

The product gives the probability of the rule choices generating that tree. Normalizing productions for each left-hand side specifies the local choices. A proper distribution over finite complete derivations additionally requires consistency: termination with probability one. Recursive PCFGs can violate this even when each local rule distribution sums to one. Each finite derivation still has a well-defined product weight, but a fixed sentence need not have finitely many derivations. For example, (S\to S) and (S\to a), each with probability (1/2), give a distinct parse of "a" at every unary-chain length (k\geq0). Its probability is (2^{-(k+1)}), and these infinitely many finite-derivation probabilities sum to one.

The most likely tree is the one that maximizes this product. In a bare, unlexicalized PCFG, a structural rule such as (PP \to P\ NP) has the same probability regardless of the head words involved. Its lexical productions still assign probabilities to words, but its structural rule choices do not directly condition on lexical heads. Lexicalized grammars add head words to the conditioning context. Latent-variable PCFGs instead refine coarse observed categories with hidden states. Neural chart parsers can score spans from contextual representations without requiring a PCFG rule-probability table. These approaches change what is scored while retaining a structured decoding problem.

The "ordered" part of the definition matters: the children of a node have a left-to-right order that matches the word order. This is what distinguishes a constituency tree from an unordered tree of categories, and it is what allows the tree to be read back as a sentence.

Chart parsing stores partial analyses in a chart. In the CKY setup here, a cell (\text{chart}[i,j]) stores the nonterminals that can derive the half-open span containing tokens (i, i+1, \ldots, j-1). A larger-span analysis combines shorter-span analyses. Keeping their results lets different larger analyses reuse the same subproblem values.

CKY uses grammars in Chomsky normal form. In the nonempty CNF convention here, every rule is either:

• A lexical rule (A \to w), where (w) is a terminal.
• A binary rule (A \to B\ C), where (B) and (C) are nonterminals.

For nonempty strings, a context-free grammar can be converted to an equivalent CNF grammar, though the conversion may introduce nonterminals and increase grammar size. A grammar that licenses the empty string needs a separate empty-string convention; unary productions also need treatment. A ternary production (A \to B\ C\ D) can be replaced by (A \to B\ X) and (X \to C\ D), with a fresh helper (X). In a PCFG, giving the first rule the original probability and the helper rule probability one preserves that rule occurrence's contribution to the derivation probability. Other transformations, especially eliminating unary cycles or empty productions, require their own probability accounting.

For a sentence with tokens indexed so that the span from $i$ to $j$ (half-open) contains tokens $i, i+1, \ldots, j-1$, the inside probability is the total probability of all subtrees rooted at nonterminal $A$ that derive that span. For a PCFG in CNF it is:

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

where:

• $A, B, C$: nonterminal symbols, with $A$ the parent and $B, C$ its two children in a binary rule
• $\alpha_{i,j}(A)$: the inside probability that $A$ derives the span from token $i$ up to (but not including) token $j$
• $P(A \to B C)$: the probability assigned to the binary rule $A \to B C$ by the PCFG
• $k$: the split point; the left child $B$ spans $i$ to $k$ and the right child $C$ spans $k$ to $j$
• $\alpha_{i,k}(B)$ and $\alpha_{k,j}(C)$: the inside probabilities of the two children on their respective sub-spans

The base case is a lexical rule, where a preterminal $A$ derives a single token $w_i$:

[ \alpha_{i,i+1}(A) = P(A \to w_i) ]

where $P(A \to w_i)$ is the probability of the lexical rule that rewrites $A$ as the word $w_i$.

For Viterbi parsing, we want one highest-probability tree rather than the summed probability over all trees, so we replace the sum over splits with a max and keep backpointers:

[ \delta_{i,j}(A) = \max_{A \to B C} \max_{k=i+1}^{j-1} P(A \to B C),\delta_{i,k}(B),\delta_{k,j}(C) ]

where $\delta_{i,j}(A)$ is the maximum probability of any $A$-rooted subtree deriving the span $i$ to $j$, and the backpointer records the split point $k$ and rule $A \to B C$ that achieved the maximum.

The recurrence says something simple: a constituent spanning (i) to (j) can be split at some (k). The left child spans (i) to (k), the right child spans (k) to (j), and a binary rule combines them. Because every split uses smaller spans, the chart can be filled bottom-up. The algorithm starts with spans of length one, then length two, and so on, until the full sentence span is reached. At each step, the answers for the smaller spans are already available, so the larger span can be computed in a single pass over its possible split points. This is the same dynamic-programming pattern you see in sequence alignment and shortest-path problems: solve the small subproblems, memoize the answers, and combine them.

The chart's work can be viewed as a triangular table: each valid span owns one cell, and each cell scans the internal boundaries where a split could occur.

Unpruned compact CNF CKY takes (O(n^3 |R|)) time and (O(n^2 |N|)) memory with bounded scores and backpointers per state. The cubic factor comes from choosing a split point (k) for every span; grammar size also enters the bound. Pruning can reduce retained search space while losing the optimal tree. Neural span scoring changes the model but does not by itself remove the cubic bound of exact span decoding. Counting each span and each internal split once gives (n(n-1)(n+1)/6) span-split combinations: 4,495 at 30 tokens and 1,333,300 at 200 tokens, before checking grammar rules. This count separates the combinatorial work from a loose (n^3) upper bound.

Unpruned Viterbi CKY finds a highest-probability tree for its specified CNF PCFG. That guarantee concerns model optimization, not agreement with a reference analysis. A bare unlexicalized PCFG cannot directly condition a structural rule choice on lexical heads. An exact optimizer can therefore select a wrong analysis under its model, while an approximate search under a different model may select the reference tree. Comparing the resulting predictions requires an evaluation protocol.

CKY is simple, but it requires CNF. The Earley algorithm parses arbitrary context-free grammars, including left-recursive and unary rules, without converting to CNF. It maintains a set of dotted rules at each position. A dotted rule such as (NP \to Det \cdot N) means the parser has recognized a determiner and is waiting for a noun. The dot is a cursor that records how much of a rule's right-hand side has been matched so far.

Earley parsing proceeds by three operations. Prediction adds new dotted rules for the categories the parser expects next. Scanning advances the dot past a terminal when the next input token matches. Completion advances rules that were waiting on a nonterminal once that nonterminal has been fully recognized. The set of states at each position is called an Earley set, and the algorithm processes these sets left to right. Because it tracks the origin position of each dotted rule, it can handle the full generality of context-free grammars without the binary-branching restriction.

For a fixed grammar, the classical Earley bounds are (O(n^3)) in general, (O(n^2)) for unambiguous grammars, and (O(n)) for the bounded-state grammar class under the relevant algorithm conditions. Here bounded-state means that each Earley set contains at most a grammar-dependent constant number of states, including their distinct origin positions, independent of sentence length. Under the stated algorithm conditions, processing each input position then takes bounded work. Implementation details and grammar preprocessing matter to these bounds. Earley parsing is useful when the grammar should remain in its original, potentially nonbinary form. Weighted Earley algorithms also support probabilistic computation, so handling a general grammar does not exclude statistical training. Opedal et al. (2023) give a reference formulation and explain the grammar-size factors hidden by fixed-grammar notation.

Consider the sentence "the man saw the dog". A chart parser fills cells like this:

• Span [0,2] for "the man": NP; Det and N occupy [0,1] and [1,2].
• Span [2,3] for "saw": V.
• Span [3,5] for "the dog": NP; Det and N occupy [3,4] and [4,5].
• Span [2,5] for "saw the dog": VP, because VP (\to) V NP.
• Span [0,5] for the whole sentence: S, because S (\to) NP VP.

CKY builds larger analyses from smaller constituents, reusing each chart cell's results. This reuse does not imply streaming: the implementation below allocates its chart from the complete token sequence, and a contextual scorer may inspect the entire sentence. The span [0,2] for "the man" is a single NP cell in the chart, built from the Det cell at [0,1] and the N cell at [1,2]. This particular span has only one category under the tiny grammar. More generally, a chart can retain competing categories and derivations until a larger constituent uses them, rather than committing to one early attachment. The later eight-token telescope example exhibits two complete derivations.