Constituency Parsing

Some groups of words behave as a single unit. In I'd like to fly on September seventeenth from Atlanta to Denver, the phrase on September seventeenth can slide to the front of the sentence, to the very end, or into the middle, and the result is still English — but you cannot move its words one at a time. The whole phrase moves together or not at all. That is the empirical fact behind syntactic constituency: words cluster into phrases, phrases nest inside larger phrases, and this hierarchy governs where words may appear, how they agree, and what a sentence means.¹

Constituency parsing is the task of recovering that hierarchy — mapping a flat string of words to a nested tree of phrases. It underlies grammar checking (a sentence that will not parse is often ungrammatical), and it feeds semantic analysis and question answering: to answer Which flights to Denver depart before the Seattle flight? a system must know that to Denver modifies flights, not depart, and that which flights to Denver is the subject.² This lesson develops the grammar that describes constituents, the ambiguity that makes recovering them hard, and the dynamic-programming algorithm that recovers them anyway.

Context-free grammars

The standard formal system for constituent structure is the context-free grammar, or CFG (equivalently, a phrase-structure grammar).³ A CFG is built from rules (productions), each expressing how a symbol may be rewritten as an ordered sequence of symbols. The symbols split into two classes: terminals, which are the actual words (the, flight), and nonterminals, which are abstractions over them (NP, VP, Noun). Each rule has a single nonterminal on the left of the arrow and a string of terminals and nonterminals on the right:

The rules with a single terminal on the right (Det → a) are the lexicon; the rest are the grammar proper. Reading the arrow as rewrite the left symbol with the right string, a CFG generates strings. Start from NP, rewrite it to Det Nominal, rewrite Nominal to Noun, and rewrite the parts of speech to words: the string a flight has been derived from NP. That sequence of rewrites is a derivation, and it is naturally drawn as a parse tree with the start symbol at the root and the words at the leaves.

We say NP dominates every node beneath it, and immediately dominates its direct children Det and Nom. Formally, a CFG is a 4-tuple $(N,\Sigma ,R,S)$: $N$ a set of nonterminals, $\Sigma$ a disjoint set of terminals, $R$ a set of rules $A\to \beta$ with $A\in N$ and $\beta \in (\Sigma \cup N{)}^{\ast }$, and $S\in N$ a designated start symbol.⁴ The language $L_G$ that $G$ generates is the set of terminal strings derivable from $S$:

where $\stackrel{\ast }{\Rightarrow }$ is the reflexive-transitive closure of directly derives. A string in $L_G$ is grammatical; one outside it is ungrammatical.

Adding a few rules turns this into a grammar for small sentences. A sentence S is a noun phrase followed by a verb phrase; a verb phrase is a verb followed by assorted complements; a prepositional phrase is a preposition followed by a noun phrase:

With this grammar (Jurafsky and Martin call it ${\mathcal{L}}_0$), the sentence I prefer a morning flight has a full derivation from S, shown as a tree.

The same tree has a flat bracketed notation, which packs the structure onto one line by matching brackets and labelling each with its nonterminal:

[S [NP [Pro I]] [VP [V prefer] [NP [Det a] [Nom [N morning] [Nom [N flight]]]]]]

Grammatical phenomena, briefly

The phrase structure of English has enough regularity to fill a chapter; a few patterns recur throughout and motivate the design choices later.⁵

• NP structure. A noun phrase has a head noun with modifiers before it (determiners, numbers, adjectives — the first non-stop flight) and after it (prepositional phrases, relative clauses — flights from Denver that serve dinner). Post-head modifiers are recursive: Nominal → Nominal PP and Nominal → Nominal Noun stack indefinitely, the same recursion the tree above exhibits.
• VP structure and subcategorization. A verb phrase pairs a verb with complements, but not every verb accepts every complement. find requires a direct object (VP → Verb NP), disappear takes none, and want accepts either an NP or an infinitival VP. The set of complements a verb licenses is its subcategorization frame; treating it carelessly forces the grammar to multiply verb classes and rules.⁶
• Agreement. The subject and main verb must match in person and number: this flight serves but not *this flight serve. A pure CFG can only enforce this by doubling every affected rule (a singular copy and a plural copy), one of the redundancies that pushes practitioners toward lexicalized grammars.
• Coordination. Like constituents conjoin into a larger constituent of the same type: NP → NP and NP, VP → VP and VP. The general schema is X → X and X. Conjoinability is itself a test for constituency.
• Long-distance dependencies. In What flights do you have from Burbank?, the wh-phrase what flights is the object of have, yet sits far from it at the front of the sentence. These fronted arguments — in wh-questions, relative clauses, and topicalization — strain a formalism whose rules are local, and treebanks mark them with special empty nodes (below).

Treebanks

A grammar robust enough to parse any sentence lets us build a corpus in which every sentence is paired with its parse tree — a treebank.⁷ The Penn Treebank is the canonical example, with hand-corrected parses of the Brown, Switchboard, ATIS, and Wall Street Journal corpora. Trees are stored in LISP-style parenthesized notation; the ATIS sentence The flight should arrive at eleven a.m. tomorrow is bracketed as:

(S (NP-SBJ (DT The) (NN flight))   (VP (MD should)       (VP (VB arrive)           (PP-TMP (IN at) (NP (CD eleven) (RB a.m.)))           (NP-TMP (NN tomorrow)))))

Two features matter downstream. First, a treebank is a grammar: read the rules off the trees and you recover a CFG for the corpus. The Wall Street Journal portion (a million words) yields about 17,500 distinct rule types, many of them very flat and very long — there are roughly 4,500 rules just for expanding VP, including monsters like VP → VBP PP PP PP PP PP ADVP PP. Second, Penn Treebank marks long-distance dependencies with traces: an empty -NONE- node holds the position where a moved constituent belongs, co-indexed with the constituent's surface location, so a parser can recover which argument goes with which predicate.

Structural ambiguity

The reason parsing is hard is that one grammar routinely assigns many trees to one sentence — structural ambiguity.⁸ Groucho Marx's line I shot an elephant in my pajamas is the textbook case. The prepositional phrase in my pajamas can attach low, inside the noun phrase headed by elephant (the elephant is wearing the pajamas — the joke), or high, inside the verb phrase headed by shot (the shooting happened in the pajamas). Both are licensed by the same grammar.

This is attachment ambiguity: a constituent can hang from the tree at more than one place. PP-attachment is the most common form, and it compounds — a sentence with several prepositional phrases has a number of parses that grows combinatorially.

A second flavor is coordination ambiguity, where a conjunction leaves the grouping unclear. old men and women can mean old men and women (everyone is old) or old men and women (only the men are old). The two readings correspond to different trees.

Real sentences pile these up. Many grammatically valid parses are semantically absurd, and enumerating them naively is exponential. The engineering response comes in two parts: a dynamic-programming algorithm that represents all parses compactly, and a scoring model that picks the right one. We take them in that order.

Chomsky normal form

The parsing algorithm below needs the grammar in a restricted shape. A CFG is in Chomsky normal form (CNF) if it is $\epsilon$-free and every rule has one of exactly two shapes: $A\to BC$ (two nonterminals) or $A\to w$ (one terminal).⁹ CNF grammars are binary branching: above the part-of-speech level, every node has exactly two children. That property is what makes the chart triangular and the algorithm cubic.

Any CFG can be converted to a weakly equivalent CNF grammar — one generating the same string set — by repairing three kinds of offending rule.¹⁰

• Terminals mixed with nonterminals on the right (INF-VP → to VP): introduce a dummy nonterminal covering the terminal, giving INF-VP → TO VP and TO → to.
• Unit productions — a single nonterminal on the right (A → B): follow each chain $A\stackrel{\ast }{\Rightarrow }B$ and, for every non-unit rule $B\to \gamma$, add $A\to \gamma$, then discard the unit rules. This flattens the grammar and promotes terminals higher in the tree.
• Right-hand sides longer than two (A → B C D): split off the leftmost pair under a fresh nonterminal, A → X1 D and X1 → B C, and iterate until every rule is binary. So S → Aux NP VP becomes S → X1 VP and X1 → Aux NP.

The conversion has a side benefit: binarizing a family of flat rules like VP → VBD NP, VP → VBD NP PP, VP → VBD NP PP PP, ... can be replaced by the compact pair VP → VBD NP and VP → VP PP, generating the same infinite family with two rules.

The CKY algorithm

CKY (Cocke-Kasami-Younger) is the standard dynamic-programming parser.¹¹ It is the same idea as minimum edit distance and Viterbi: fill a table of subproblem solutions bottom-up so that each cell is computed from cells already filled. Here a subproblem is which nonterminals can span this stretch of the input, and the context-free property is what makes it a dynamic program — once a constituent is found over a span, it can be reused in any larger derivation without being reanalyzed.

The chart

Index the fenceposts between words from $0$ to $n$, so the input Book the flight through Houston is read as ${}_0$ Book ${}_1$ the ${}_2$ flight ${}_3$ through ${}_4$ Houston ${}_5$. A cell $\text{table}[i,j]$ holds the set of nonterminals that can span positions $i$ through $j$. Only the upper triangle of the $(n+1)\times (n+1)$ matrix is used, since $i<j$; the cell $[0,n]$ covers the whole sentence, and the sentence is grammatical exactly when $S\in \text{table}[0,n]$.

Because the grammar is in CNF, any constituent spanning $[i,j]$ was built from a rule $A\to BC$ where $B$ spans $[i,k]$ and $C$ spans $[k,j]$ for some split point $k$ with $i<k<j$. Geometrically, the left child $[i,k]$ lies along row $i$ to the left of $[i,j]$, and the right child $[k,j]$ lies down column $j$ beneath it. Filling $[i,j]$ means scanning every split $k$, checking whether any grammar rule combines a nonterminal from $[i,k]$ with one from $[k,j]$.

The recognizer

The order of filling matters: to have both children ready, process columns left to right and, within a column, rows bottom to top. The base case fills the diagonal $[j-1,j]$ with the parts of speech of word $j$; then each higher cell combines pairs of lower cells.

Three nested loops over positions ($j$, $i$, $k$) times a scan of the grammar give $O(n^3|G|)$ time — cubic in the sentence length, linear in the grammar size. As written this is a recognizer: it reports grammaticality by testing $S\in \text{table}[0,n]$ but does not return trees. Two changes make it a parser: attach to each table entry back-pointers to the two cells it was built from, and allow multiple copies of a nonterminal (one per way of deriving it). The filled table then encodes every parse; a single tree is read off by picking an $S$ from $[0,n]$ and recursively following its back-pointers.

A worked example

Take the grammar ${\mathcal{L}}_1$ in CNF, whose lexicon includes Book as Verb, Noun, Nominal, VP, and S; the as Det; flight as Noun, Nominal; through as Preposition; and Houston as NP, ProperNoun. Relevant binary rules: S → NP VP, S → VP PP, VP → Verb NP, VP → VP PP, NP → Det Nominal, Nominal → Nominal PP, PP → Preposition NP, plus S → X2 PP and VP → X2 PP with X2 → Verb NP. Parse Book the flight through Houston ($n=5$).

Trace the fill span-length by span-length; the algorithm processes column $j$ left to right and, within a column, row $i$ from the diagonal upward, so every child cell is ready before its parent.

Length 1 (the diagonal). Each word's parts of speech come straight from the lexicon, filling $[j-1,j]$:

Length 2. Each cell has a single split point. $[0,2]$ (Book the) needs a rule combining something in $[0,1]$ with Det in $[1,2]$ — none exists, so $[0,2]=\varnothing$. $[1,3]$ (the flight): Det in $[1,2]$ and Nominal in $[2,3]$ fire NP → Det Nominal, so NP ∈ [1,3]. $[2,4]$ (flight through): no rule takes a Nominal then a Preposition, so it stays empty. $[3,5]$ (through Houston): Preposition in $[3,4]$ meets NP in $[4,5]$ under PP → Preposition NP, giving PP ∈ [3,5].

Length 3. Now two split points must each be tried. $[2,5]$ (flight through Houston): at split $k=3$, Nominal in $[2,3]$ and PP in $[3,5]$ fire Nominal → Nominal PP, so Nominal ∈ [2,5]. $[0,3]$ (Book the flight): at $k=1$, the Verb in $[0,1]$ and NP in $[1,3]$ fire both VP → Verb NP and its binarized helper X2 → Verb NP, and the resulting VP also satisfies S → VP chains, so $[0,3]=\{\text{VP},\text{X2},\text{S}\}$.

Length 4. $[1,5]$ (the flight through Houston): at $k=2$, Det in $[1,2]$ and Nominal in $[2,5]$ fire NP → Det Nominal, so NP ∈ [1,5].

Length 5 (the top cell). $[0,5]$ spans the whole sentence, with four possible splits $k\in \{1,2,3,4\}$. Two of them succeed and produce three S derivations:

• $k=1$: Verb in $[0,1]$ with NP in $[1,5]$ via X2 → Verb NP, and through Houston already folded into the NP — this is the low PP-attachment (the flight through Houston).
• $k=3$: VP/X2 in $[0,3]$ with PP in $[3,5]$ via VP → VP PP and via S → X2 PP — the high PP-attachment (the booking happens through Houston), reached two ways.

So $[0,5]$ holds {S, VP, X2} with three distinct back-pointer sets for S.

The same chart, drawn in the conventional upper-triangular layout with the diagonal along the bottom, is below; the top-right cell $[0,5]$ carries the three-way ambiguity as three back-pointer sets.

The three S entries in $[0,5]$ are the three readings: the prepositional phrase through Houston modifies the flight, or it modifies the booking event via VP → VP PP, or it fills the second argument slot recovered through VP → X2 PP (the binarized form of the original VP → Verb NP PP). CKY has produced all of them in one cubic-time pass and stored them in a table of shared subtrees — this reuse of solved subproblems is dynamic programming exactly as in the algorithms course, the same optimal-substructure argument that underlies edit distance and Viterbi, specialized to the triangular chart of spans.

Where this continues

We have the recognition machinery. A context-free grammar describes how words group into nested phrases; the phrase structure of English fills it out; a treebank turns those trees into a grammar automatically; structural ambiguity — PP-attachment, coordination — is why one grammar assigns many trees to one sentence; and Chomsky normal form binarizes the grammar so the CKY chart can fill a triangular table bottom-up in cubic time, storing every parse compactly.

CKY hands back all parses but does not say which is right. Scoring trees to pick the correct one — probabilistic CFGs and neural span parsers — evaluating a parser against a treebank with PARSEVAL, and the cheaper shallow parsing that skips the full tree continue in CKY scoring, evaluation, and shallow parsing.