Treebanks and Lexicalized Grammars

This builds on constituency grammars, which fixed the context-free formalism and the phrase structure of English. A hand-written grammar is one source of that structure; the other, and the one that powers modern parsing, is a corpus of trees. We start there, then normalize the grammar for the parser and push its knowledge into the lexicon.

Treebanks

A grammar robust enough to parse any sentence makes it possible to build a corpus in which every sentence is paired with its parse. Such a corpus is a treebank.¹ Treebanks are usually made by running a parser over the text and then having linguists hand-correct the results. The Penn Treebank is the canonical example, with treebanks over the Brown, Switchboard, ATIS, and Wall Street Journal corpora of English (and Arabic and Chinese). Its trees use LISP-style parenthesized notation — the same idea as the bracketed notation above.

Two Penn Treebank features are worth noting. Function tags decorate nodes with grammatical or semantic function: NP-SBJ is a surface subject, NP-TMP a temporal phrase, ADJP-PRD a predicate adjective. And traces are empty -NONE- nodes that mark the position of a moved constituent — the treebank's answer to the long-distance dependencies above. A fronted quotation, for instance, leaves a -NONE- node co-indexed (say with index 2) at the position the complement of said would occupy, so a parser can recover that the fronted material is that complement.

A treebank is a grammar

The key fact for parsing: the sentences in a treebank implicitly define a grammar. Read every local tree — every parent with its children — as a CFG rule, and the union of all such rules is a grammar for the corpus. The trees above yield $\text{S}\to \text{NP-SBJ VP}$, $\text{VP}\to \text{MD VP}$, $\text{PP}\to \text{IN NP}$, and so on. No linguist ever wrote those rules; they fall out of the annotation.

The extracted grammar is very flat — many long, specific rules rather than a few deep recursive ones. The WSJ treebank has roughly 4,500 distinct rules just for VP, including separate productions for every arity of PP sequence ($\text{VP}\to \text{VBD PP}$, $\text{VP}\to \text{VBD PP PP}$, ... up to $\text{VP}\to \text{VBP PP PP PP PP PP PP ADVP PP}$), and thousands of NP rules. Viewed as one large grammar the corpus has about a million rule tokens and about 17,500 distinct rule types. This flatness is convenient for coverage but hard on parsing algorithms — one reason grammars extracted from treebanks are usually transformed before use.

Heads and head finding

Each constituent has a lexical head — the word in the phrase that is grammatically most important. N is the head of an NP, V of a VP. In a lexicalized model each CFG rule designates one right-hand child as the head child, and the head word is passed up the tree, so every nonterminal ends up annotated with its head word.

Choosing the head child is easy for textbook cases (NN heads NP) but genuinely controversial for others — is the complementizer to or the verb the head of an infinitival VP? In practice most systems skip declaring heads in the grammar and instead identify them after parsing, walking the finished tree and decorating each node using a hand-written head percolation table (the standard one is Magerman's 1995 / Collins' 1999 rules). A typical rule for finding an NP's head: if the last word is tagged POS, return it; else search right-to-left for the first NN/NNP/...; else search left-to-right for the first NP; ... Heads are the bridge to dependency grammar, where the head-of relation is the structure.

Grammar equivalence and normal form

It is often useful to force every production into a fixed shape — a normal form. The one that matters for parsing is Chomsky Normal Form (CNF).²

Binary branching is the property the CKY parsing algorithm requires, because CKY fills a chart by combining two adjacent sub-constituents at a time. Any CFG can be converted into a weakly equivalent CNF grammar — same language, possibly different trees. The core move is binarization: a rule with a right-hand side longer than two is split by introducing fresh nonterminals.

Binarization can even make a grammar smaller. The flat treebank family $\text{VP}\to {\text{VBD NP PP}}^{\ast }$ (an unbounded run of PPs) needs a separate rule for each PP count — $\text{VP}\to \text{VBD NP PP}$, $\text{VP}\to \text{VBD NP PP PP}$, and so on — but two rules generate the whole infinite family:

Generating a symbol $A$ followed by an unbounded sequence of $B$s via a rule $A\to AB$ is called Chomsky-adjunction. Full CNF conversion also removes $ϵ$-productions and collapses unit chains, but binarization is the piece that CKY depends on.

Lexicalized grammars

The phrase-structure approach so far puts almost everything in the rules and very little in the lexicon — and we have seen the cost twice. Subcategorization forced us to split Verb into subtypes and clone VP rules; agreement forced us to clone every S rule per number and person. The rules multiply, the grammar grows redundant and brittle. Lexicalized grammars invert the emphasis: push the grammatical facts into rich lexical entries and keep the combinatory rules few and general. Lexical-Functional Grammar (LFG), Head-Driven Phrase Structure Grammar (HPSG), and Tree-Adjoining Grammar (TAG) all take this route to different degrees. We develop one clean example: Combinatory Categorial Grammar (CCG).³

In HPSG and its relatives the lexical head is the organizing principle: a word's entry carries its category, its subcategorization frame, its agreement features, and constraints on its arguments, and phrases are built by unifying a head with arguments that satisfy those constraints. The head-annotated trees of the previous section are the same intuition in a lighter form. CCG makes the lexicalization total.

Categorial categories

A categorial grammar has three parts: a set of categories, a lexicon mapping words to categories, and a tiny set of combination rules.⁴ Categories are either atomic (a small set, typically including S for sentence and NP) or functional, built with a slash notation:

• $X/Y$ is a function that wants a $Y$ to its right and yields an $X$.
• $X\backslash Y$ is a function that wants a $Y$ to its left and yields an $X$.

So a transitive verb like cancel has category $(S\backslash NP)/NP$: it first seeks an object NP on its right, yielding $S\backslash NP$ (the category of a verb phrase), which then seeks a subject NP on its left, yielding S. The subcategorization frame that cost us extra rules in the CFG is now just the verb's category — a fact in the lexicon, not the grammar.

Combining categories

Two rules do the basic work. Forward function application applies a function to the argument on its right; backward function application applies it to the argument on its left:

With these and a lexicon, a derivation grows downward from the words: draw a horizontal line under the elements a rule combines, annotate the end with > for forward or < for backward application, and repeat until a single S spans the sentence. For United serves Miami with serves $:(S\backslash NP)/NP$:

The basic categorial approach has exactly the power of a plain CFG — it just moves information from the grammar into the lexicon. The combinatory in CCG adds operators that act on functions themselves and add real expressive power. Composition combines two adjacent functions into one ($X/YY/Z\Rightarrow X/Z$); type raising turns an argument into a function over functions that expect it ($X\Rightarrow T/(T\backslash X)$, so a subject NP becomes $S/(S\backslash NP)$, a thing that can compose with the verb phrase to its right). Together these give CCG two capabilities a plain CFG cannot manage cleanly: coordination of non-constituents — We flew IcelandAir to Geneva and SwissAir to London, where IcelandAir to Geneva is not a traditional constituent — and a graceful, word-by-word, left-to-right analysis of long-distance dependencies like the flight that United diverted, where the object has moved to the front. Because the derivation proceeds one word at a time, CCG is also a favored model of how humans process language incrementally.

A worked long-distance derivation

The relative clause the flight that United diverted shows both operators at work. Give that the lexical category $(NP\backslash NP)/(S/NP)$: it seeks, on its right, a sentence missing an object (an $S/NP$), and turns it into a postmodifier of a noun phrase ($NP\backslash NP$). The problem is that United diverted is a subject followed by a transitive verb $(S\backslash NP)/NP$ — there is no object, and no ordinary constituent of category $S/NP$ to hand that. Composition and type raising build one.

Type-raise the subject United from $NP$ to $S/(S\backslash NP)$, a function looking for a verb phrase on its right. Then forward-compose it with the verb $(S\backslash NP)/NP$: the raised subject seeks an $S\backslash NP$, the verb provides an $S\backslash NP$ but is still waiting on its object $NP$, and composition fuses them into $S/NP$ — exactly United diverted, still needing an object. That is the $S/NP$ the relative pronoun selects; forward application then yields the $NP\backslash NP$ modifier, and backward application attaches it to the flight.

No trace, no empty category, no movement rule — the gap is a category that never gets its argument, threaded straight through the derivation. This is the same long-distance dependency the Penn Treebank recorded with a co-indexed -NONE- node; CCG dispenses with the empty category and lets the type system carry the gap.

The grammar in the neural era

The CFG is a hand-declared object, and for decades a parser searched it explicitly. Modern constituency parsers keep the tree this grammar defines but stop treating the rule set as a separate artifact — the grammar is folded into a learned scoring model. Three public developments show where the formalism landed.

Span-based neural parsing. Stern, Andreas, and Klein (2017), A Minimal Span-Based Neural Constituency Parser (ACL), reframed parsing as scoring labeled spans directly: a neural encoder assigns every span $(i,j)$ a score for each constituent label, and a chart search (the same CKY dynamic program, but over learned span scores instead of grammar rules) assembles the highest-scoring tree. The grammar's rules become soft, learned compatibilities rather than a hard rewrite system, and the span-chart search works precisely because of the binary-branching CNF structure the lesson insisted on.⁵

Self-attention and pretrained encoders. Kitaev and Klein (2018), Constituency Parsing with a Self-Attentive Encoder (ACL), replaced the recurrent encoder with a transformer-style self-attentive one over the span scorer, and later work fed it contextual embeddings from pretrained models like BERT. That combination pushed English constituency parsing on the Penn Treebank past 95 $F_1$ — accuracy that a hand-written grammar, with its coverage gaps and its combinatorial blow-up under agreement and subcategorization, never approached.⁶ The formalism did not change; the source of the scores did.

Grammar induction. The lesson read a grammar off a treebank by taking each local tree as a rule. A harder question is whether the tree structure itself can be learned from unannotated text. Neural grammar induction — the compound probabilistic context-free grammar of Kim, Dyer, and Rush (2019), Compound Probabilistic Context-Free Grammars for Grammar Induction (ACL), and related latent-tree models — learns a probabilistic CFG and its trees jointly from raw sentences, recovering constituent structure without a treebank. These systems are still weaker than supervised parsers, but they close the loop the chapter opened: the CFG is not only a grammar someone writes or reads off annotations, but one a model can discover.⁷

Where this fits

A constituency grammar is the declarative theory; a parser is the procedure that searches it. We read a grammar off the Penn Treebank as the union of its local trees, normalized it to CNF so the CKY chart can combine constituents two at a time, and watched the lexicalized formalisms move the grammar's knowledge — subcategorization, agreement, long-distance gaps — into rich lexical entries. In the neural era the rule set dissolves into a learned scoring function over spans, but the tree it defines survives.

Two directions follow. The constituency-parsing lesson takes this grammar and gives the dynamic-programming algorithm (CKY) that recovers trees from it, then extends to probabilistic and neural span parsers. The dependency-parsing lesson takes the alternative theory — drop the phrase nodes entirely and let the head-of relation between words be the structure — which the head-finding above already anticipates. Both routes share one goal: turning a flat string of words back into the structure that produced it.