---
title: Constituency Grammars
module: Linguistic Structure
moduleNumber: 6
lessonNumber: 19
order: 619
summary: >
  A constituency grammar is the declarative theory of sentence structure that a
  parser operates on. We build the context-free grammar formalism from its four
  parts, show how derivations become parse trees, and work through the phrase
  structure of English — noun phrases, verb phrases and their subcategorization
  frames, agreement, coordination, and long-distance dependencies. The treebank,
  normal-form, and lexicalized views 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 Some Grammar Rules for English"
---

Recovering the structure of a sentence requires a theory of what
that structure _is_. A parser is an algorithm; the object it computes over is a
**grammar** — a finite, declarative description of which strings of words are
sentences and how their pieces nest. This lesson is about the grammar itself: the
context-free formalism and the phrase structure of English it captures. Where that
structure comes from in practice — a hand-written grammar or a treebank — and how
it is normalized and lexicalized for a parser, is taken up in the companion lesson,
[treebanks and lexicalized grammars](/natural-language-processing/linguistic-structure/treebanks-and-lexicalized-grammars).
The [algorithms that search the grammar](/natural-language-processing/linguistic-structure/constituency-parsing)
are a separate concern again; here we fix the theory they run on.

The word **syntax** comes from the Greek _sýntaxis_, "setting out together" — the
way words are arranged. Ordering (which word may follow which), part-of-speech
categories (a grammatical equivalence class over words), and probabilities over
word sequences are all partial views of syntax. A constituency grammar goes
further: it says that words group into nested **phrases**, and that this hierarchy
governs where words may appear, how they agree, and what a sentence means.[^jm-intro]

## Constituency

The founding claim is simple: some groups of words behave as a single unit, a
**constituent**. The **noun phrase** — a sequence of words surrounding at least one
noun — is the standard example. _Harry the Horse_, _the Broadway coppers_, _a
high-class spot such as Mindy's_, _three parties from Brooklyn_: each is a lump
that acts as one thing.[^jm-constituency] The question is _what evidence_
we have that these words form a unit rather than just sitting next to each other.

The first kind of evidence is **substitution in the same environment**. Whole noun
phrases can all appear in the same slot — for instance, right before a verb — and
the sentence stays grammatical, whereas the individual words inside cannot:

$$
% caption: Substitution evidence. Whole noun phrases (top) drop into the pre-verb
% slot and stay grammatical; single fragments of them (bottom, marked with a
% star) do not. The phrase moves as a unit.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  ok/.style={draw, minimum width=52mm, minimum height=7mm, align=left, inner xsep=3pt},
  bad/.style={draw, minimum width=52mm, minimum height=7mm, align=left, inner xsep=3pt, text=red}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[ok, draw=acc]  (a) at (0,2.1)  {they \textit{sit} ...};
  \node[ok, draw=acc]  (b) at (0,1.2)  {the Broadway coppers \textit{love} ...};
  \node[ok, draw=acc]  (c) at (0,0.3)  {three parties from Brooklyn \textit{arrive} ...};
  \node[bad] (d) at (0,-0.9) {(*) the \textit{is} ...};
  \node[bad] (e) at (0,-1.8) {(*) from \textit{arrive} ...};
  \node[bad] (f) at (0,-2.7) {(*) spot \textit{sat} ...};
  \node[text=acc, anchor=west, font=\scriptsize] at (3.0,1.2)  {grammatical: a noun phrase f\/its the slot};
  \node[text=red, anchor=west, font=\scriptsize] at (3.0,-1.8) {ungrammatical: a fragment does not};
\end{tikzpicture}
$$

A second kind of evidence is **movement**. A prepositional phrase such as _on
September seventeenth_ can be **preposed** to the front, left in the middle, or
**postposed** to the end, and each placement is fine:

- _**On September seventeenth**, I'd like to fly from Atlanta to Denver._
- _I'd like to fly **on September seventeenth** from Atlanta to Denver._
- _I'd like to fly from Atlanta to Denver **on September seventeenth**._

But the words of the phrase cannot be scattered independently — _(*)On I'd like to
fly September seventeenth ..._ is not English. The whole phrase relocates together
or not at all. Substitution and movement are the two operational tests: a
constituent is whatever _substitutes_ into a common environment and
_moves_ as a block. Everything that follows is machinery for writing those
groupings down.

> **Definition (Constituent).** A group of words that behaves as a single
> syntactic unit — it can substitute into a common environment (e.g. before a
> verb), move as a block (preposing, postposing), and be coordinated with another
> unit of the same type. Constituents nest to form the phrase structure of a
> sentence.

## Context-free grammars

The standard formalism for constituent structure is the **context-free grammar**
(CFG), equivalently a **phrase-structure grammar** or **Backus-Naur Form**.[^jm-cfg]
Its history is old — the idea of basing a grammar on constituent structure goes
back to Wilhelm Wundt (1900) and was formalized by Chomsky (1956) and,
independently, Backus (1959). A CFG is built from **rules** (productions), each
stating how one symbol may be rewritten as an ordered sequence of symbols. The
symbols come in two classes: **terminals**, the actual words (_the_, _flight_),
collected in a **lexicon**; and **nonterminals**, 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} \qquad
\text{Noun} \rightarrow \textit{flight}
\end{aligned}
$$

The vertical bar `|` is the **or-symbol**: it lists alternate expansions of the same
nonterminal on one line. A CFG can be read in **two ways**. As a **generator**, the
arrow means "rewrite the left symbol with the string on the right"; repeatedly
applying rules from a start symbol emits sentences. As a **parser**'s target, it
assigns structure to a string already given. Both readings run on the same rules.

### Derivations and parse trees

Reading a CFG as a generator: start from a nonterminal and rewrite until only
terminals remain. Starting at `NP`, apply $\text{NP} \rightarrow \text{Det
Nominal}$, then $\text{Nominal} \rightarrow \text{Noun}$, then the lexical rules,
and out comes the string _a flight_. That sequence of rewrites is a **derivation**;
drawn as a tree (inverted, root at top) it is a **parse tree**.

$$
% caption: A parse tree for "a flight" from the derivation NP -> Det Nominal ->
% Det Noun -> a flight. NP dominates every node below it and 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}
$$

In this tree `NP` **dominates** every node beneath it and **immediately dominates**
its direct children `Det` and `Nom`. 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 with assorted complements, and a prepositional phrase is a
preposition followed by a noun phrase. Jurafsky and Martin call this small grammar
$\mathcal{L}_0$.

$$
\begin{aligned}
\text{S} &\rightarrow \text{NP}\;\;\text{VP} \\
\text{VP} &\rightarrow \text{Verb} \mid \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}
$$

Under $\mathcal{L}_0$, the sentence _I prefer a morning flight_ has a full
derivation from `S`. The recursive rule $\text{Nominal} \rightarrow \text{Nominal
Noun}$ is what lets _morning_ stack onto _flight_.

$$
% caption: The parse tree for "I prefer a morning flight" under grammar L0. The
% top rule is S -> NP VP; the recursive Nominal -> Nominal Noun rule 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 written flat is **bracketed notation** — each opening bracket carries
its node label as a subscript:

$$
[_S\ [_{NP}\ [_{Pro}\ \textit{I}]]\ [_{VP}\ [_V\ \textit{prefer}]\ [_{NP}\ [_{Det}\ \textit{a}]\ [_{Nom}\ [_{Nom}\ \textit{morning}]\ [_{Nom}\ \textit{flight}]]]]
$$

### Formal definition

Stripped to essentials, a CFG is a **4-tuple**.

> **Definition (Context-free grammar).** A 4-tuple $G = (N, \Sigma, R, S)$ where
> $N$ is 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**. It is "context-free" because a rule
> for $A$ applies regardless of what surrounds $A$.

The formalism is defined through **derivation**. If $A \rightarrow \beta$ is a rule
and $\alpha, \gamma$ are any strings in $(\Sigma \cup N)^{\ast}$, then $\alpha A \gamma$ **directly derives**
$\alpha \beta \gamma$, written $\alpha A \gamma \Rightarrow
\alpha \beta \gamma$. Derivation is the transitive closure: $\alpha_1
\stackrel{*}{\Rightarrow} \alpha_m$ if some chain of direct derivations connects
them. The **language** generated by $G$ is the set of terminal strings derivable
from $S$:

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

A string in $L_G$ is **grammatical**; one outside is **ungrammatical**. Because
$L_G$ is defined as the set of strings the grammar "generates," this use of formal
languages to model natural language is called a **generative grammar**. The
convention for the rest of the discussion: capital letters like $A, B, S$ are
nonterminals, lower-case Greek $\alpha, \beta, \gamma$ are strings over $(\Sigma
\cup N)^{*}$, and lower-case Roman $u, v, w$ are strings of terminals.

$$
% caption: A CFG partitions all strings over the vocabulary into the language L_G
% (those derivable from S) and everything else. The hard in/out line is a
% simplification of how natural languages actually work.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[black, thick] (-3.6,-1.9) rectangle (3.6,1.9);
  \node[anchor=north west, font=\scriptsize] at (-3.55,1.85) {all strings over the vocabulary};
  \draw[acc, thick] (-0.6,0) ellipse (2.4 and 1.35);
  \node[text=acc, font=\small] at (-0.6,0.55) {grammatical};
  \node[text=acc, font=\scriptsize] at (-0.6,-0.05) {S derives w};
  \node[text=acc, anchor=center, font=\scriptsize] at (-0.6,-0.85) {(the language LG)};
  \node[text=red, font=\scriptsize, align=center] at (2.55,-1.3) {ungrammatical\\(not derivable)};
\end{tikzpicture}
$$

### Weak vs. strong generative capacity

Two CFGs can generate the exact same set of strings yet differ in the trees they
build. This distinction gives **grammar equivalence** two flavors. Two grammars are
**weakly equivalent** if they generate the same language — the same set of strings —
but may assign different phrase structures. They are **strongly equivalent** if they
generate the same strings _and_ assign each sentence the same tree (up to renaming
nonterminals). Strong equivalence implies weak; the converse fails. The distinction
matters because a parser's output is a _tree_, not just a yes/no on membership, so
two weakly equivalent grammars can disagree about the structure a downstream
semantic component needs.

$$
% caption: Weak vs. strong equivalence. Both grammars accept the string "a b c",
% so they are weakly equivalent, but they bracket it differently -- (a b) c vs.
% a (b c) -- so they are NOT strongly equivalent.
\begin{tikzpicture}[>=stealth, font=\small, level distance=8.5mm,
  every node/.style={inner sep=1.5pt},
  level 1/.style={sibling distance=18mm},
  level 2/.style={sibling distance=12mm}]
  \definecolor{acc}{HTML}{2348F2}
  \begin{scope}
    \node[text=acc] {S}
      child { node {X}
        child { node {\textit{a}} }
        child { node {\textit{b}} } }
      child { node {\textit{c}} };
    \node[font=\scriptsize] at (0,-3.0) {(a b) c};
  \end{scope}
  \begin{scope}[xshift=42mm]
    \node[text=acc] {S}
      child { node {\textit{a}} }
      child { node {Y}
        child { node {\textit{b}} }
        child { node {\textit{c}} } };
    \node[font=\scriptsize] at (0,-3.0) {a (b c)};
  \end{scope}
  \node[font=\scriptsize] at (2.1,1.1) {same string, di\/f\/ferent structure};
\end{tikzpicture}
$$

The problem of mapping a string of words to its parse tree is **syntactic parsing**;
the [constituency-parsing lesson](/natural-language-processing/linguistic-structure/constituency-parsing)
develops the algorithms. The grammar defined here is the declarative object those
algorithms search.

## Some grammar rules for English

$\mathcal{L}_0$ is a toy. Real English needs many more rules, and their shape
reveals how the language is organized. We work through the noun phrase, the verb
phrase and its subcategorization, agreement, the sentence-level constructions,
coordination, and long-distance dependencies. Throughout, examples come from ATIS,
a small air-travel domain (_I'd like to fly from Atlanta_).

### The noun phrase

An `NP` has a **head** — its central noun — surrounded by **premodifiers** before
the head and **postmodifiers** after. Working outward from the head:

**The determiner.** Noun phrases can begin with a lexical determiner (_a stop_, _the
flights_, _this flight_, _those flights_, _some flights_). The determiner slot can
also be filled by a possessive expression — _United's flight_, _Denver's mayor's
mother's canceled flight_ — captured by a **recursive** rule, since an `NP` can
itself start with a `Det`:

$$
\text{Det} \rightarrow \text{NP}\ \textit{'s}
$$

Determiners are optional when the head is plural (_Show me flights from San
Francisco_) or a **mass noun** (_Does this flight serve dinner?_ — _dinner_ takes no
_a_ and does not pluralize).

**The nominal.** Between the determiner and the head sit **premodifiers**: cardinal
numbers (_two friends_), ordinals (_the first one_, _the next day_), quantifiers
(_many fares_), and adjectives (_a first-class fare_, _the least expensive fare_ —
adjectives can group into an **adjective phrase** with their own adverb). The base
case is $\text{Nominal} \rightarrow \text{Noun}$; premodifiers stack via the
recursive $\text{Nominal} \rightarrow \text{Nominal Noun}$ we already met.

**Postmodifiers** follow the head. Three kinds are common: prepositional phrases
(_all flights **from Cleveland**_), non-finite clauses — chiefly **gerundive**
(_-ing_) forms (_any flights **arriving after eleven a.m.**_), infinitives (_the
last flight **to arrive in Boston**_), and _-ed_ forms (_the aircraft **used by this
flight**_) — and **relative clauses** introduced by a relative pronoun (_a flight
**that serves breakfast**_). Each gets a nominal rule:

$$
\begin{aligned}
\text{Nominal} &\rightarrow \text{Nominal PP} \mid \text{Nominal GerundVP} \mid \text{Nominal RelClause}\\
\text{RelClause} &\rightarrow (\textit{who} \mid \textit{that})\ \text{VP}
\end{aligned}
$$

Word classes that appear _before_ the whole `NP` — chiefly _all_ (_all the flights_,
_all non-stop flights_) — are **predeterminers**. Put together, these rules generate
deeply nested noun phrases.

$$
% caption: A parse tree for "all the morning flights from Denver to Tampa". A
% predeterminer (all) sits above a determiner (the); the two prepositional
% postmodifiers stack on the nominal via the recursive rule Nominal -> Nominal PP.
\begin{tikzpicture}[>=stealth, font=\scriptsize, level distance=9mm,
  every node/.style={inner sep=1.3pt},
  level 1/.style={sibling distance=58mm},
  level 2/.style={sibling distance=48mm},
  level 3/.style={sibling distance=40mm},
  level 4/.style={sibling distance=24mm},
  level 5/.style={sibling distance=20mm}]
  \definecolor{acc}{HTML}{2348F2}
  \node[text=acc] {NP}
    child { node {PreDet} child { node {\textit{all}} } }
    child { node {NP}
      child { node {Det} child { node {\textit{the}} } }
      child { node {Nom}
        child { node {Nom}
          child { node {Nom}
            child { node {Nom} child { node {Noun} child { node {\textit{morning}} } } }
            child { node {Noun} child { node {\textit{f\/lights}} } } }
          child { node {PP} child { node {\textit{from Denver}} } } }
        child { node {PP} child { node {\textit{to Tampa}} } } } };
\end{tikzpicture}
$$

### The verb phrase and subcategorization

A `VP` is a verb plus the constituents it selects. In the simple rules so far those
are `NP`s and `PP`s and combinations (_disappear_ / _prefer a morning flight_ /
_leave Boston in the morning_ / _leaving on Thursday_). But a verb can also take an
entire embedded sentence — a **sentential complement** — as in _I think **[S I would
like to take the nine thirty flight]**_, giving $\text{VP} \rightarrow \text{Verb S}$,
or another `VP`, as in _I want **[VP to fly from Milwaukee to Orlando]**_.

The catch: **not every verb accepts every complement.** _want_ takes an `NP` (_I
want a flight_) or an infinitival `VP` (_I want to fly_); _find_ takes an `NP` (_I
found a flight_) but not a `VP` (_(*)I found to fly to Dallas_). Traditional grammar
captured a slice of this with **transitive** verbs (take a direct object, _find_)
versus **intransitive** (do not, _disappear_ — _(*)I disappeared a flight_). Modern
grammars refine it into up to a hundred **subcategories**: we say _find_
**subcategorizes for** an `NP` and _want_ subcategorizes for an `NP` or an
infinitival `VP`. The set of complements a verb permits is its **subcategorization
frame**, and the complements are the verb's **arguments** — a predicate-argument
view, $\textsc{find}(\text{I}, \text{a flight})$.

$$
% caption: Subcategorization frames for example verbs: each verb licenses a
% specific set of complements. A VP rule must match the verb to a frame, or it
% will overgenerate ungrammatical strings like "(*) I disappeared a flight".
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  hd/.style={font=\footnotesize\bfseries},
  cell/.style={anchor=west, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \draw[acc, thick] (-0.3,0.55) -- (11.4,0.55);
  \draw[black] (-0.3,-3.55) -- (11.4,-3.55);
  \node[hd, anchor=west, text=acc] at (0,1.0) {Frame};
  \node[hd, anchor=west, text=acc] at (3.2,1.0) {Verb};
  \node[hd, anchor=west, text=acc] at (6.0,1.0) {Example};
  \node[cell] at (0,0) {empty};
  \node[cell] at (3.2,0) {eat, sleep};
  \node[cell] at (6.0,0) {I ate};
  \node[cell] at (0,-0.65) {NP};
  \node[cell] at (3.2,-0.65) {prefer, \textit{f\/ind}};
  \node[cell] at (6.0,-0.65) {\textit{f\/ind} [the \textit{f\/light}]};
  \node[cell] at (0,-1.30) {NP NP};
  \node[cell] at (3.2,-1.30) {show, give};
  \node[cell] at (6.0,-1.30) {show [me] [airlines]};
  \node[cell] at (0,-1.95) {PP-from PP-to};
  \node[cell] at (3.2,-1.95) {\textit{f\/ly}, travel};
  \node[cell] at (6.0,-1.95) {\textit{f\/ly} [from Boston] [to Rome]};
  \node[cell] at (0,-2.60) {VP-to};
  \node[cell] at (3.2,-2.60) {want, need};
  \node[cell] at (6.0,-2.60) {want [to go by United]};
  \node[cell] at (0,-3.25) {S};
  \node[cell] at (3.2,-3.25) {mean};
  \node[cell] at (6.0,-3.25) {mean [AA has a hub here]};
\end{tikzpicture}
$$

One way to enforce frames is to split `Verb` into subtypes —
`Verb-with-NP-complement`, `Verb-with-S-complement` — and require each `VP` rule to
use the right subtype. It works but multiplies rules and loses generality, and that
hand-labor is what the [lexicalized
grammars](/natural-language-processing/linguistic-structure/treebanks-and-lexicalized-grammars)
of the companion lesson were designed to avoid.

### Agreement

English enforces **agreement** between a subject and its verb in person and number:
_Does **this flight** serve breakfast?_ but _(*)Do this flight serve breakfast?_ A
single rule $\text{S} \rightarrow \text{Aux NP VP}$ overgenerates, because it does
not force _Aux_, _NP_, and _VP_ to share number. The blunt CFG solution is to
**duplicate** every rule per feature value — a $3\text{sg}$ copy and a $\text{non-}3\text{sg}$
copy — with matching nonterminals like $\text{NP}_{sg}$, $\text{VP}_{sg}$. This
doubles (and with person, gender, case, further multiplies) the grammar. The
combinatorial blow-up from agreement, like the one from subcategorization, is a
standing argument that pure phrase-structure rules put too much work in the rules
and too little in the lexicon.

### Sentence-level constructions

Four sentence types recur, each with its own `S` rule.[^jm-sentences] A
**declarative** is a subject `NP` followed by a `VP` (_I want a flight from Ontario
to Chicago_): the familiar $\text{S} \rightarrow \text{NP VP}$. An **imperative**
begins with the `VP` and has no subject (_Show the lowest fare_): $\text{S}
\rightarrow \text{VP}$. A **yes-no question** begins with an auxiliary, then the
subject, then the `VP` (_Do any of these flights have stops?_): $\text{S}
\rightarrow \text{Aux NP VP}$. A **wh-question** contains a **wh-phrase** built on a
wh-word (_who, whose, when, where, what, which, how, why_); when the wh-phrase is the
subject the structure mirrors a declarative (_Which flights serve breakfast?_):
$\text{S} \rightarrow \text{Wh-NP VP}$; when it is not the subject, an auxiliary and
a separate subject follow (_What flights do you have from Burbank?_): $\text{S}
\rightarrow \text{Wh-NP Aux NP VP}$.

$$
% caption: Four sentence-level constructions and their S rules. Each rewrites the
% start symbol S differently; the wh-non-subject form is the one that will create
% a long-distance dependency.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  row/.style={anchor=west, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[row, text=acc] at (0,1.5)  {declarative};
  \node[row] at (3.4,1.5) {S $\to$ NP VP};
  \node[row, font=\scriptsize] at (7.2,1.5) {I want a f\/light};
  \node[row, text=acc] at (0,0.75) {imperative};
  \node[row] at (3.4,0.75) {S $\to$ VP};
  \node[row, font=\scriptsize] at (7.2,0.75) {Show the lowest fare};
  \node[row, text=acc] at (0,0.0)  {yes-no question};
  \node[row] at (3.4,0.0) {S $\to$ Aux NP VP};
  \node[row, font=\scriptsize] at (7.2,0.0) {Do these f\/lights stop?};
  \node[row, text=acc] at (0,-0.75) {wh-subject};
  \node[row] at (3.4,-0.75) {S $\to$ Wh-NP VP};
  \node[row, font=\scriptsize] at (7.2,-0.75) {Which f\/lights serve food?};
  \node[row, text=acc] at (0,-1.5) {wh-non-subject};
  \node[row] at (3.4,-1.5) {S $\to$ Wh-NP Aux NP VP};
  \node[row, font=\scriptsize] at (7.2,-1.5) {What f\/lights do you have?};
  \draw[black] (-0.2,1.15) -- (10.3,1.15);
\end{tikzpicture}
$$

An `S` on the right-hand side of a rule can be embedded inside a larger sentence, so
`S` is not only the top of a tree. What sets the `S` rules apart is that they are in
some sense _complete_ — they correspond to a **clause**, a node whose main verb has
all of its arguments present. In _I prefer a morning flight_, _prefer_ has two
arguments — the subject _I_ (below `S`) and the object _a morning flight_ (below
`VP`) — and both are realized, so the `S` is a clause.

### Coordination

Major phrase types conjoin with **conjunctions** (_and, or, but_) into a larger
constituent of the same type. Two `NP`s make a **coordinate** `NP`: _Please repeat
[NP [NP the flights] and [NP the costs]]_. The same holds for nominals, verb
phrases, and sentences:

$$
\begin{aligned}
\text{NP} &\rightarrow \text{NP}\ \textit{and}\ \text{NP} & \text{Nominal} &\rightarrow \text{Nominal}\ \textit{and}\ \text{Nominal}\\
\text{VP} &\rightarrow \text{VP}\ \textit{and}\ \text{VP} & \text{S} &\rightarrow \text{S}\ \textit{and}\ \text{S}
\end{aligned}
$$

Coordination is itself a **test for constituency**: only true constituents conjoin.
That two nominals can be conjoined under one determiner — _the [Nom [Nom aircraft]
and [Nom flight number]]_ — is direct evidence that the `Nominal` node is real.
Since every major type coordinates the same way, one can state the whole fact with a
single **metarule** $X \rightarrow X\ \textit{and}\ X$, where $X$ ranges over
nonterminals.

### Long-distance dependencies

The wh-non-subject question hides a subtlety. In _What flights do you have?_, the
wh-phrase _what flights_ is the object of _have_, yet it sits at the front of the
sentence, far from the verb it belongs to. The link between _flights_ and _have_ is
a **long-distance dependency** (also called syntactic movement or extraction).

$$
% caption: A long-distance dependency in "What flights do you have (___)?" The
% fronted wh-phrase is the object of "have", which is left with a gap. The dashed
% arc is the dependency the grammar must somehow record.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node (w) at (0,0)   {\textit{What f\/lights}};
  \node (d) at (2.6,0) {\textit{do}};
  \node (y) at (3.6,0) {\textit{you}};
  \node (h) at (4.9,0) {\textit{have}};
  \node[text=red] (g) at (6.4,0) {(gap)};
  \draw[red, thick, dashed, ->] (g.north) .. controls (4.0,1.5) and (1.5,1.5) .. (w.north);
  \node[text=red, font=\scriptsize, anchor=south] at (3.4,1.2) {object of "have", realized far to the left};
\end{tikzpicture}
$$

There are two ways to record it. One treats the relation between _flights_ and
_have_ as **semantic**, resolved during interpretation rather than in the syntax.
The other keeps it **syntactic**, inserting an empty **trace** (a phonetically null
marker) after the verb, co-indexed with the fronted phrase, so the tree literally
shows where the object "belongs." The Penn Treebank takes the second route, and its
empty categories are next.

[^jm-intro]: **Jurafsky & Martin**, _Speech and Language Processing_ (3rd ed.), Ch. 12 — Constituency Grammars: syntax as the arrangement of words, with CFGs as the backbone formalism used across grammar checking, semantic interpretation, and machine translation.
[^jm-constituency]: **Jurafsky & Martin**, §12.1 — Constituency: the noun-phrase examples and the two evidence tests, substitution into a shared environment (before a verb) and preposing/postposing movement, that identify a group of words as a constituent.
[^jm-cfg]: **Jurafsky & Martin**, §12.2 — Context-Free Grammars: rules, terminals/nonterminals and the lexicon, the generative vs. structure-assigning readings, derivations and parse trees, bracketed notation, and the formal 4-tuple definition $(N, \Sigma, R, S)$ with weak vs. strong equivalence.
[^jm-sentences]: **Jurafsky & Martin**, §12.3 — Some Grammar Rules for English: the noun phrase (determiners, nominals, pre- and postmodifiers), the verb phrase and subcategorization frames, agreement, the declarative/imperative/yes-no/wh sentence constructions, coordination, and long-distance dependencies.