Grammars and Constituency Structure

The string "the dog chased the cat with a telescope" can mean that the dog used a telescope to chase the cat, or that the dog chased a cat that happened to have a telescope. The words are identical. What changes is where "with a telescope" attaches: to the chase event or to the cat. A parser has to represent these different phrase groupings before it can rank the readings.

That grouping is the subject of this chapter. We will formalize constituency: the idea that words combine into nested phrases, phrases combine into larger phrases, and the whole sentence has a hierarchical structure. The central formalism is the context-free grammar, or CFG. CFGs give us a precise language for describing phrase structure, they connect naturally to parsing algorithms, and they expose both the power and the limits of symbolic approaches to syntax. A CFG is a compact specification. It does not list every sentence. Instead, it lists a finite set of rules that can generate an unbounded family of sentences and assign each generated sentence a hierarchical structure. That combination of finite description and infinite reach is what makes grammars useful.

This chapter builds directly on the sequence-labeling material from earlier. In Part-of-Speech Tagging, each token received a label such as noun or verb. In Chunking, we grouped adjacent tokens into shallow spans such as noun phrases. Constituency grammar goes further: it lets those spans nest recursively, so a noun phrase can contain a prepositional phrase, which contains another noun phrase, and so on. The move from tagging to chunking is already a move from labels to spans. The move from chunking to constituency is a move from flat spans to recursive structure. Recursive constituency can represent nested phrase groupings that flat chunk spans leave unspecified. Parsing now has to decide how those groupings fit together.

We will proceed in layers:

• First, what constituency is and why linguists and NLP systems care about it.
• Then the formal definition of a CFG and the trees it generates.
• Then ambiguity, the central practical problem for parsing.
• Then the CKY parsing algorithm and probabilistic CFGs.
• Then a complete worked example and a small implementation.
• Finally, the limitations of symbolic grammars and their contribution to parsing.

The order is deliberate. We begin with linguistic intuition, then move to formal objects, then to algorithms, and only then to implementation. Each layer answers a question raised by the previous one. Constituency tests provide evidence for phrases. CFGs tell us how to state phrase structure precisely. Parse trees make that structure visible. Ambiguity shows why a grammar alone is not enough. CKY shows how to search the space of trees efficiently. PCFGs show how to rank that space. The final discussion shows where the entire framework strains and why modern parsing looks the way it does.