Constituency Grammars

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. The algorithms that search the grammar 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.¹

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.² 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:

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.

Context-free grammars

The standard formalism for constituent structure is the context-free grammar (CFG), equivalently a phrase-structure grammar or Backus-Naur Form.³ 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.

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}\to \text{Det Nominal}$, then $\text{Nominal}\to \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.

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

Under ${\mathcal{L}}_0$, the sentence I prefer a morning flight has a full derivation from S. The recursive rule $\text{Nominal}\to \text{Nominal Noun}$ is what lets morning stack onto flight.

The same tree written flat is bracketed notation — each opening bracket carries its node label as a subscript:

Formal definition

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

The formalism is defined through derivation. If $A\to \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{\ast }{\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$:

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{)}^{\ast }$, and lower-case Roman $u,v,w$ are strings of terminals.

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.

The problem of mapping a string of words to its parse tree is syntactic parsing; the constituency-parsing lesson 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:

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}\to \text{Noun}$; premodifiers stack via the recursive $\text{Nominal}\to \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:

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.

The verb phrase and subcategorization

A VP is a verb plus the constituents it selects. In the simple rules so far those are NPs and PPs 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}\to \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 findsubcategorizes 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, $\text{find}(\text{I},\text{a flight})$.

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 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}\to \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.⁴ A declarative is a subject NP followed by a VP (I want a flight from Ontario to Chicago): the familiar $\text{S}\to \text{NP VP}$. An imperative begins with the VP and has no subject (Show the lowest fare): $\text{S}\to \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}\to \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}\to \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}\to \text{Wh-NP Aux NP VP}$.

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 NPs make a coordinate NP: Please repeat NP NP the flights and NP the costs. The same holds for nominals, verb phrases, and sentences:

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\to X\text{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).

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.