---
title: Constituency Parsing
module: Linguistic Structure
moduleNumber: 6
lessonNumber: 1
order: 601
summary: >
  A constituency parse groups a sentence into nested phrases described by a
  context-free grammar. We build the CFG formalism, read the phrase structure of
  English off a treebank, confront the structural ambiguity that makes parsing
  hard, convert to Chomsky normal form, and then solve it with CKY — the
  dynamic-programming chart that fills a triangular table bottom-up. Probabilistic
  and neural span parsers, evaluation, and shallow parsing follow in the companion
  lesson.
topics: [Structure]
sources:
  - book: Jurafsky
    ref: "Ch. 12 — Constituency Grammars; §12.1 Constituency; §12.2 Context-Free Grammars"
  - book: Jurafsky
    ref: "§12.3 Grammar Rules for English; §12.4 Treebanks; §12.5 Grammar Equivalence and Normal Form"
  - book: Jurafsky
    ref: "Ch. 13 — Constituency Parsing; §13.1 Ambiguity; §13.2 CKY 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.[^jm-constituency]

**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.[^jm-parsing-intro] This
lesson develops the grammar that describes constituents, the ambiguity that makes
recovering them hard, and the [dynamic-programming](/algorithms/dynamic-programming/principles)
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_).[^jm-cfg] 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:

$$
\begin{aligned}
\text{NP} &\rightarrow \text{Det}\;\;\text{Nominal} \\
\text{NP} &\rightarrow \text{ProperNoun} \\
\text{Nominal} &\rightarrow \text{Noun} \mid \text{Nominal}\;\;\text{Noun} \\
\text{Det} &\rightarrow \textit{a} \mid \textit{the} \\
\text{Noun} &\rightarrow \textit{flight}
\end{aligned}
$$

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.

$$
% caption: A parse tree for "a flight": the derivation NP -> Det Nominal ->
% Det Noun -> a flight, drawn with the start symbol NP at the root and words at
% the leaves. NP immediately dominates Det and Nom.
\begin{tikzpicture}[>=stealth, font=\small, level distance=10mm,
  every node/.style={inner sep=1.5pt},
  level 1/.style={sibling distance=26mm},
  level 2/.style={sibling distance=22mm}]
  \definecolor{acc}{HTML}{2348F2}
  \node[text=acc] {NP}
    child { node {Det} child { node {\textit{a}} } }
    child { node {Nom}
      child { node {Noun} child { node {\textit{f\/light}} } } };
\end{tikzpicture}
$$

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 \rightarrow \beta$ with $A \in N$ and $\beta \in (\Sigma \cup N)^{\ast}$, and $S \in
N$ a designated **start symbol**.[^jm-formal] The **language** $L_G$ that $G$
generates is the set of terminal strings derivable from $S$:

$$
L_G = \{\, w \mid w \in \Sigma^{\ast} \text{ and } S \stackrel{\ast}{\Rightarrow} w \,\},
$$

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

> **Definition (Context-free grammar).** A 4-tuple $G = (N, \Sigma, R, S)$ of
> nonterminals $N$, terminals $\Sigma$, productions $R$ of the form $A \rightarrow
> \beta$ (one nonterminal $A$ rewriting to a string $\beta$ over $\Sigma \cup N$),
> and a start symbol $S$. It is "context-free" because a rule for $A$ applies
> regardless of the symbols surrounding $A$.

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:

$$
\begin{aligned}
\text{S} &\rightarrow \text{NP}\;\;\text{VP} \\
\text{VP} &\rightarrow \text{Verb}\;\;\text{NP} \mid \text{Verb}\;\;\text{NP}\;\;\text{PP} \mid \text{Verb}\;\;\text{PP} \\
\text{PP} &\rightarrow \text{Preposition}\;\;\text{NP}
\end{aligned}
$$

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.

$$
% caption: Parse tree for "I prefer a morning flight" under the grammar L0. The
% top rule is S -> NP VP; the recursive rule Nominal -> Nominal Noun stacks
% "morning" onto "flight".
\begin{tikzpicture}[>=stealth, font=\small, level distance=9mm,
  every node/.style={inner sep=1.5pt},
  level 1/.style={sibling distance=44mm},
  level 2/.style={sibling distance=24mm},
  level 3/.style={sibling distance=22mm},
  level 4/.style={sibling distance=18mm}]
  \definecolor{acc}{HTML}{2348F2}
  \node[text=acc] {S}
    child { node {NP}
      child { node {Pro} child { node {\textit{I}} } } }
    child { node {VP}
      child { node {Verb} child { node {\textit{prefer}} } }
      child { node {NP}
        child { node {Det} child { node {\textit{a}} } }
        child { node {Nom}
          child { node {Nom} child { node {Noun} child { node {\textit{morning}} } } }
          child { node {Noun} child { node {\textit{f\/light}} } } } } };
\end{tikzpicture}
$$

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

```text
[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.[^jm-english]

- **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.[^jm-subcat]
- **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**.[^jm-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:

```text
(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.

$$
% caption: A Penn Treebank tree for a Brown-corpus sentence, "That cold, empty sky
% was full of fire and light." The -PRD tag marks a non-VP predicate (here an
% adjective phrase) and -SBJ marks the surface subject.
\begin{tikzpicture}[>=stealth, font=\footnotesize, level distance=8.5mm,
  every node/.style={inner sep=1.4pt},
  level 1/.style={sibling distance=40mm},
  level 2/.style={sibling distance=15mm},
  level 3/.style={sibling distance=15mm}]
  \definecolor{acc}{HTML}{2348F2}
  \node[text=acc] {S}
    child { node {NP-SBJ}
      child { node {DT} child { node {\textit{That}} } }
      child { node {JJ} child { node {\textit{cold}} } }
      child { node {JJ} child { node {\textit{empty}} } }
      child { node {NN} child { node {\textit{sky}} } } }
    child { node {VP}
      child { node {VBD} child { node {\textit{was}} } }
      child { node {ADJP-PRD}
        child { node {JJ} child { node {\textit{fu\/ll}} } }
        child { node {PP}
          child { node {IN} child { node {\textit{of}} } }
          child { node {NP} child { node {\textit{f\/ire, light}} } } } } };
\end{tikzpicture}
$$

## Structural ambiguity

The reason parsing is hard is that one grammar routinely assigns many trees to one
sentence — **structural ambiguity**.[^jm-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.

$$
% caption: Two parses of "I shot an elephant in my pajamas." Left: the PP attaches
% inside the NP (the elephant is in the pajamas). Right: the PP attaches to the VP
% (the shooting happens in the pajamas). This is PP-attachment ambiguity.
\begin{tikzpicture}[>=stealth, font=\scriptsize, level distance=8mm,
  every node/.style={inner sep=1.6pt},
  level 1/.style={sibling distance=30mm},
  level 2/.style={sibling distance=22mm},
  level 3/.style={sibling distance=17mm}]
  \definecolor{acc}{HTML}{2348F2}
  % ---- left tree: low attachment (NP) ----
  \begin{scope}
  \node {S}
    child { node {NP} child { node {\textit{I}} } }
    child { node {VP}
      child { node {V} child { node {\textit{shot}} } }
      child { node {NP}
        child { node {Det} child { node {\textit{an}} } }
        child { node {Nom}
          child { node {Nom} child { node {\textit{elephant}} } }
          child { node[text=acc] {PP} child { node {\textit{in my pajamas}} } } } } };
  \node[font=\scriptsize, text=acc] at (0,-5.0) {PP low: inside the NP};
  \end{scope}
  % ---- right tree: high attachment (VP) ----
  \begin{scope}[xshift=78mm]
  \node {S}
    child { node {NP} child { node {\textit{I}} } }
    child { node {VP}
      child { node {VP}
        child { node {V} child { node {\textit{shot}} } }
        child { node {NP}
          child { node {Det} child { node {\textit{an}} } }
          child { node {Nom} child { node {\textit{elephant}} } } } }
      child { node[text=acc] {PP} child { node {\textit{in my pajamas}} } } };
  \node[font=\scriptsize, text=acc] at (0,-5.0) {PP high: inside the VP};
  \end{scope}
\end{tikzpicture}
$$

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.

$$
% caption: Coordination ambiguity in "old men and women." Left: the adjective
% scopes over the whole coordination, so both men and women are old. Right: the
% adjective scopes over "men" only.
\begin{tikzpicture}[>=stealth, font=\scriptsize, level distance=9mm,
  every node/.style={inner sep=1.6pt},
  level 1/.style={sibling distance=20mm},
  level 2/.style={sibling distance=15mm}]
  \definecolor{acc}{HTML}{2348F2}
  % left: wide scope
  \begin{scope}
  \node {Nom}
    child { node {Adj} child { node {\textit{old}} } }
    child { node[text=acc] {Nom}
      child { node {Nom} child { node {\textit{men}} } }
      child { node {Con} child { node {\textit{and}} } }
      child { node {Nom} child { node {\textit{women}} } } };
  \node[font=\scriptsize, text=acc] at (0,-4.0) {old (men and women)};
  \end{scope}
  % right: narrow scope
  \begin{scope}[xshift=64mm]
  \node {Nom}
    child { node[text=acc] {Nom}
      child { node {Adj} child { node {\textit{old}} } }
      child { node {Nom} child { node {\textit{men}} } } }
    child { node {Con} child { node {\textit{and}} } }
    child { node {Nom} child { node {\textit{women}} } };
  \node[font=\scriptsize, text=acc] at (0,-4.0) {(old men) and women};
  \end{scope}
\end{tikzpicture}
$$

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 $\varepsilon$-free and every rule has one of
exactly two shapes: $A \rightarrow B\,C$ (two nonterminals) or $A \rightarrow w$
(one terminal).[^jm-cnf] 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.[^jm-cnf-convert]

- **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 \rightarrow
  \gamma$, add $A \rightarrow \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`.

$$
% caption: Converting the ternary rule A -> B C D to Chomsky normal form. A fresh
% nonterminal X1 absorbs the leftmost pair B C, leaving two binary rules that
% derive the same strings.
\begin{tikzpicture}[>=stealth, font=\small,
  box/.style={draw, minimum width=20mm, minimum height=9mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (a) at (0,0) {A $\to$ B C D};
  \node[box, draw=acc, text=acc] (b) at (5.2,0.8) {A $\to$ X1 D};
  \node[box, draw=acc, text=acc] (c) at (5.2,-0.8) {X1 $\to$ B C};
  \draw[->, thick] (a.east) -- (3.0,0) |- (b.west);
  \draw[->, thick] (a.east) -- (3.0,0) |- (c.west);
  \node[font=\footnotesize] at (3.35,-1.55) {binary branching};
\end{tikzpicture}
$$

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.[^jm-cky]
It is the same idea as [minimum edit distance](/natural-language-processing/foundations/regex-and-text-normalization)
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 \rightarrow B\,C$ 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]$.

$$
% caption: Filling cell [i,j] in the CKY chart. For each split point k, the left
% child comes from cell [i,k] (along row i) and the right child from cell [k,j]
% (down column j); a rule A -> B C combining them adds A to [i,j].
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % grid of cells (partial, schematic)
  \draw[black] (0,0) grid (5,3);
  % target cell [i,j] top-left region
  \fill[acc!12] (0,2) rectangle (1,3);
  \draw[acc, very thick] (0,2) rectangle (1,3);
  \node[text=acc] at (0.5,2.5) {[i,j]};
  % left child along row i
  \fill[red!12] (3,2) rectangle (4,3);
  \draw[red, thick] (3,2) rectangle (4,3);
  \node[text=red] at (3.5,2.5) {[i,k]};
  % right child down column j
  \fill[red!12] (0,0) rectangle (1,1);
  \draw[red, thick] (0,0) rectangle (1,1);
  \node[text=red] at (0.5,0.5) {[k,j]};
  % arrows in from the two children
  \draw[->, red, thick] (3.0,2.5) -- (1.15,2.5);
  \draw[->, red, thick] (0.5,1.0) -- (0.5,1.9);
  \node[font=\scriptsize, text=red, anchor=south] at (2.6,3.15) {left child (row i)};
  \node[font=\scriptsize, text=red, anchor=west] at (1.15,1.35) {right child (col j)};
\end{tikzpicture}
$$

### 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.

```algorithm
caption: $\textsc{CKY-Parse}(\textit{words}, \textit{grammar})$ — fill the constituency chart
input: sentence $\textit{words}[1..n]$, grammar in Chomsky normal form
$\textit{table} \gets$ empty $(n{+}1) \times (n{+}1)$ table
for $j = 1$ to $n$ do
  for each $A$ such that $A \rightarrow \textit{words}[j] \in \textit{grammar}$ do
    add $A$ to $\textit{table}[j{-}1, j]$ // part-of-speech base case
  for $i = j{-}2$ downto $0$ do
    for $k = i{+}1$ to $j{-}1$ do
      for each $A \rightarrow B\,C \in \textit{grammar}$ with $B \in \textit{table}[i,k]$ and $C \in \textit{table}[k,j]$ do
        add $A$ to $\textit{table}[i,j]$ // constituent over span (i, j)
return $\textit{table}$
```

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]$:

$$
\begin{aligned}
[0,1] &= \{\texttt{Verb}, \texttt{Noun}, \texttt{Nominal}, \texttt{VP}, \texttt{S}\} && (\textit{Book}) \\
[1,2] &= \{\texttt{Det}\} && (\textit{the}) \\
[2,3] &= \{\texttt{Noun}, \texttt{Nominal}\} && (\textit{flight}) \\
[3,4] &= \{\texttt{Preposition}\} && (\textit{through}) \\
[4,5] &= \{\texttt{NP}, \texttt{ProperNoun}\} && (\textit{Houston})
\end{aligned}
$$

**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] =
\{\texttt{VP}, \texttt{X2}, \texttt{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`.

$$
% caption: The CKY chart for "Book the flight through Houston" filling by span
% length: length-1 diagonal from the lexicon, then length 2, 3, 4, and finally the
% top cell [0,5] with three S derivations (the PP-attachment ambiguity). Empty
% cells are shown blank.
\begin{tikzpicture}[>=stealth, font=\scriptsize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \tikzset{cc/.style={draw=black, minimum width=20mm, minimum height=10mm, align=center, anchor=south west, inner sep=1pt, font=\scriptsize}}
  \foreach \x/\w in {0/Book, 1/the, 2/f\/light, 3/through, 4/Houston}
    \node[font=\scriptsize] at (\x*2.0+1.0,5.75) {\textit{\w}};
  % length 1 (diagonal) - tinted
  \node[cc, fill=black!5] at (0,4.5) {Verb, Noun,\\Nom, VP, S};
  \node[cc, fill=black!5] at (2.0,3.5) {Det};
  \node[cc, fill=black!5] at (4.0,2.5) {Nom, Noun};
  \node[cc, fill=black!5] at (6.0,1.5) {Prep};
  \node[cc, fill=black!5] at (8.0,0.5) {NP, Proper};
  % length 2
  \node[cc] at (2.0,4.5) {};
  \node[cc] at (4.0,3.5) {NP};
  \node[cc] at (6.0,2.5) {};
  \node[cc] at (8.0,1.5) {PP};
  % length 3
  \node[cc] at (4.0,4.5) {S, VP, X2};
  \node[cc] at (6.0,3.5) {};
  \node[cc] at (8.0,2.5) {Nom};
  % length 4
  \node[cc] at (6.0,4.5) {};
  \node[cc] at (8.0,3.5) {NP};
  % length 5 (top) - accent
  \node[cc, draw=acc, very thick, fill=acc!8] at (8.0,4.5) {\textcolor{acc}{S, VP, X2}};
  \node[text=acc, font=\scriptsize, anchor=west] at (10.3,5.0) {[0,5]:};
  \node[text=acc, font=\scriptsize, anchor=west] at (10.3,4.6) {3 S parses};
\end{tikzpicture}
$$

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.

$$
% caption: Completed CKY chart for "Book the flight through Houston." Each cell
% [i,j] lists the nonterminals spanning words i..j. The top-right cell [0,5] holds
% three S's, one per parse. Empty cells are omitted.
\begin{tikzpicture}[>=stealth, font=\scriptsize]
  \definecolor{acc}{HTML}{2348F2}
  % words along the top
  \foreach \x/\w in {0/Book, 1/the, 2/f\/light, 3/through, 4/Houston}
    \node[font=\footnotesize] at (\x*2.3+1.15,6.6) {\textit{\w}};
  % draw grid cells that are used (upper triangle)
  \tikzset{cell/.style={draw=black, minimum width=23mm, minimum height=12mm, align=center, anchor=south west, inner sep=1pt}}
  % row 0 (i=0): [0,1]..[0,5]
  \node[cell] at (0,5) {Verb, Noun,\\ Nom, VP, S};
  \node[cell] at (2.3,5) {};
  \node[cell] at (4.6,5) {S, VP, X2};
  \node[cell] at (6.9,5) {};
  \node[cell, draw=acc, very thick] at (9.2,5) {\textcolor{acc}{S, VP, X2}};
  % row 1 (i=1): [1,2]..[1,5]
  \node[cell] at (2.3,4) {Det};
  \node[cell] at (4.6,4) {NP};
  \node[cell] at (6.9,4) {};
  \node[cell] at (9.2,4) {NP};
  % row 2 (i=2): [2,3]..[2,5]
  \node[cell] at (4.6,3) {Nom, Noun};
  \node[cell] at (6.9,3) {};
  \node[cell] at (9.2,3) {Nom};
  % row 3 (i=3): [3,4]..[3,5]
  \node[cell] at (6.9,2) {Prep};
  \node[cell] at (9.2,2) {PP};
  % row 4 (i=4): [4,5]
  \node[cell] at (9.2,1) {NP, Proper-Noun};
  % label the whole-sentence cell
  \node[text=acc, font=\scriptsize, anchor=west] at (11.7,5.6) {[0,5]:};
  \node[text=acc, font=\scriptsize, anchor=west] at (11.7,5.15) {3 parses};
\end{tikzpicture}
$$

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](/algorithms/dynamic-programming/principles)
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](/natural-language-processing/linguistic-structure/cky-scoring-and-evaluation).

[^jm-parsing-intro]: **Jurafsky & Martin**, Ch. 13 — Constituency Parsing, chapter opening: parsing as assigning syntactic structure, and its use in grammar checking, semantic analysis, and question answering.
[^jm-constituency]: **Jurafsky & Martin**, _Speech and Language Processing_ (3rd ed.), §12.1 — Constituency: the evidence that groups of words act as units (appearing in the same environments, moving together as preposed/postposed phrases).
[^jm-cfg]: **Jurafsky & Martin**, §12.2 — Context-Free Grammars: rules and productions, terminals and nonterminals, the lexicon, derivations, and parse trees.
[^jm-formal]: **Jurafsky & Martin**, §12.2.1 — Formal Definition of Context-Free Grammar: the 4-tuple $(N, \Sigma, R, S)$, direct derivation, and the language $L_G$ generated from the start symbol.
[^jm-english]: **Jurafsky & Martin**, §12.3 — Some Grammar Rules for English: sentence-level constructions, the noun phrase, the verb phrase, and coordination.
[^jm-subcat]: **Jurafsky & Martin**, §12.3.4 — The Verb Phrase: transitive vs. intransitive verbs, subcategorization frames, and complements as logical arguments of the verb.
[^jm-treebank]: **Jurafsky & Martin**, §12.4 — Treebanks: the Penn Treebank, LISP-style bracketed notation, traces / -NONE- nodes for long-distance dependencies, and treebanks read as grammars.
[^jm-ambiguity]: **Jurafsky & Martin**, §13.1 — Ambiguity: structural ambiguity, PP-attachment ("I shot an elephant in my pajamas"), and coordination ambiguity ("old men and women").
[^jm-cnf]: **Jurafsky & Martin**, §12.5 — Grammar Equivalence and Normal Form: Chomsky normal form as $\varepsilon$-free grammars with rules $A \rightarrow B\,C$ or $A \rightarrow a$, and their binary-branching trees.
[^jm-cnf-convert]: **Jurafsky & Martin**, §13.2.1 — Conversion to Chomsky Normal Form: handling terminals mixed with nonterminals, unit productions, and right-hand sides longer than two.
[^jm-cky]: **Jurafsky & Martin**, §13.2 — CKY Parsing: the dynamic-programming chart, fenceposts, the fill order, the recognizer of Fig. 13.5, and its extension to a parser with back-pointers; worked on "Book the flight through Houston."