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.

A constituent is a span of words that behaves as a unit. Some groups of words can be replaced, moved, coordinated, or used as answers, while other groups cannot. In the continuous tree model used here, a constituent occupies a contiguous stretch of the sentence, with a particular order and boundaries. The phrase "the small dog" is a constituent because it occupies a continuous region and behaves as a single syntactic object. The words "the" and "dog" are also constituents, but they are smaller ones. Constituency is hierarchical because constituents can contain other constituents.

Consider the sentence:

The small dog barked.

The span "the small dog" behaves like a unit. It passes several constituency tests:

• Replacement: It can be replaced with a pronoun: "It barked."
• Coordination: It can be coordinated: "The small dog and the cat barked."
• Clefting: It can be moved into a cleft construction: "It was the small dog that barked."
• Answer: It can be used as an answer: "Who barked? The small dog."

By contrast, the span "small dog barked" does not behave like a unit in the same way. You cannot naturally replace it with a single pronoun or coordinate it with another span of the same kind. This suggests that "the small dog" is a constituent, while "small dog barked" is not. Constituency makes a testable claim about which spans pattern together under grammatical operations.

These constituency tests are useful diagnostics, but they are not mathematical proofs. Different tests can disagree, and some constructions are awkward. Replacement with a pronoun works cleanly for many noun phrases, but not for every phrase type. Some analyses allow coordination of nonconstituents, so use more than one diagnostic when arguing for a phrase structure. For NLP, constituency is a hypothesis about hierarchical organization, and a grammar is a compact way to state that hypothesis. The hypothesis may be refined or replaced, but it gives the parser something precise to compute with.

Constituency is not the only way to represent syntax. Dependency grammar, which we will meet in the next chapter, represents syntactic structure as links between words rather than nested phrases. The two views are related but not identical. A constituency tree emphasizes phrases and their internal composition. A dependency tree emphasizes head-dependent relations. For now, we focus on the phrase-structure view because it gives the cleanest introduction to formal grammars and chart parsing. It also makes recursion visually obvious: a phrase node can contain another phrase node of the same type, and that containment is exactly what a CFG rule describes.

It also helps to keep four things distinct:

• Tokens are the surface words or word pieces, such as "the", "dog", and "chased".
• Preterminal categories are labels attached to individual tokens, such as Det, N, and V. These are closely related to the POS tags from the previous part.
• Phrasal categories are labels for constituents, such as NP, VP, and PP.
• The sentence root is the largest constituent, usually S, which dominates the entire token sequence.

In the nonempty lexicalized examples here, a parse tree connects all four. Its leaves are tokens, its lowest internal nodes are preterminal categories, its higher internal nodes are phrases, and its root is the sentence category. This layering is important because it separates lexical information from structural information. The token "dog" is a string. The preterminal N says that this string is functioning as a noun here. The phrasal node NP says that a larger span is functioning as a noun phrase. The root S says that the whole span is a sentence. A complete constituency parse connects these layers; a parser may infer them jointly or take some, such as tokens and POS tags, as input.

A context-free grammar is a finite set of rules that recursively defines which strings belong to a language and how those strings are structured. The formal definition is compact.

The phrase "regardless of context" is the key. A context-sensitive rule could say "rewrite A as a nonempty sequence $\alpha$ only when it appears between B and C." A context-free rule cannot require that surrounding context. For CFGs, we can use the span-based parsing method developed below. The bare rule $S \to NP\ VP$ does not encode subject-verb agreement because its categories contain no number features. A CFG can enforce finite agreement distinctions by refining these categories. Context-free does not mean that a grammar cannot constrain lexical environments; it means that each production applies to its left-hand-side category without inspecting surrounding symbols. The context-free restriction is therefore both a simplification and a limitation.

Here is a small grammar for a fragment of English:

The vertical bar means "or". So $NP$ can be either $Det\ N$ or $NP\ PP$. The symbols S, NP, VP, PP, Det, N, V, and P are nonterminals. The words "the", "a", "dog", "cat", "telescope", "chased", and "with" are terminals. The grammar is tiny, but it already supports recursion. An NP can contain a PP, and that PP contains another NP. A VP can contain a PP, and that PP contains another NP. This is enough to generate an unbounded family of structures from a finite set of rules.

A derivation shows how the start symbol rewrites step by step into a string of terminals. For example:

Continuing, we can derive:

At each step, we choose a nonterminal and replace it using one of its rules. The sequence of rewrites is a derivation. The final string contains only terminals. Different choices about which nonterminal to rewrite next can produce different derivations of the same string. That is why derivations and parse trees are not in one-to-one correspondence unless we fix a convention, such as always rewriting the leftmost nonterminal first. The tree, rather than the linear derivation, is usually the cleaner object for representing constituency.

The language generated by a grammar is the set of all terminal strings that can be derived from the start symbol:

The star on $\Rightarrow^*$ means "derives in zero or more steps." A string is grammatical with respect to $G$ if it belongs to $L(G)$. A string is ungrammatical if it does not. This notion of grammaticality is relative to a grammar. A sentence that is ungrammatical under one grammar may be grammatical under another, richer grammar. The formal definition does not tell us whether the grammar is linguistically correct. It only tells us what the grammar generates.

This definition is abstract, and that is deliberate. A CFG does not say how to find a derivation. It only defines which derivations exist. A parser is the algorithm that searches for those derivations. The grammar is the specification; the parser is the implementation, a distinction also illustrated in the NLTK book's syntax chapter. This separation is useful because the same grammar can be used by many parsers, and the same parser can be used with many grammars. It also clarifies what a parsing failure means. If a parser fails, either the sentence is outside the grammar's language, or the parser failed to find a derivation that exists. Those are different problems.

Derivations are linear sequences of rewrites. Parse trees are the same information in hierarchical form. The tree makes constituency visible. It also removes the irrelevant order in which independent rewrites happened. Two derivations that differ only in the order of rewriting unrelated nonterminals can correspond to the same tree.

For the sentence "the dog chased the cat", one parse tree has the following bracketed form:

(S
  (NP (Det the) (N dog))
  (VP
    (V chased)
    (NP (Det the) (N cat))))

The same tree can be written as a bracketed string:

[S [NP [Det the] [N dog]] [VP [V chased] [NP [Det the] [N cat]]]]

Both notations say the same thing. The sentence splits into a subject NP and a predicate VP. The subject NP splits into a determiner and a noun. The VP splits into a verb and an object NP. The object NP splits into a determiner and a noun. Each local split corresponds to a grammar rule. The root rule is $S \to NP\ VP$. The subject rule is $NP \to Det\ N$. The predicate rule is $VP \to V\ NP$. The object rule is another $NP \to Det\ N$.

The leaves are the tokens. The internal nodes are constituents. The root S dominates the whole sentence. The NP "the dog" dominates the tokens "the" and "dog". The VP dominates "chased the cat". This is the sense in which a CFG captures constituency: every nonterminal node corresponds to a span, and the rules determine how spans can combine. The tree is not a decoration added after parsing. It is the object that the grammar licenses, and the yield is the sentence that the tree derives.

CFGs are more powerful than regular expressions in an important way. A regular language can be recognized by a finite-state automaton, which has no memory beyond a finite set of states. A CFG can generate languages with unbounded nested structure. The difference is not about the number of rules. It is about the kind of memory the formalism can use. A finite-state automaton has a fixed amount of memory encoded in its states. A CFG can use recursion to keep track of nested structure without a fixed bound.

The classic example is:

This grammar generates strings like $ab$, $aabb$, $aaabbb$, and so on. The language is $\{a^n b^n : n \ge 0\}$. No finite-state automaton can recognize this language, because it would need to count arbitrarily many $a$'s and then check that the same number of $b$'s follow. A CFG does it with recursion. Each recursive expansion of $S$ adds one $a$ on the left and one $b$ on the right, so the two counts stay synchronized. The grammar does not count in the arithmetic sense. It encodes the matching dependency in the recursive structure itself.

Natural language has similar nested dependencies. Relative clauses can nest:

the cat that chased the rat that ate the cheese

The phrase "that chased the rat that ate the cheese" modifies "cat", and inside it another relative clause modifies "rat". Each relative clause can contain another. In principle, the nesting can continue indefinitely. A CFG expresses this recursive phrase analysis directly. The displayed right-branching chain alone does not prove that its string language is nonregular: a regular grammar can also generate unbounded right-branching sequences. The earlier $a^n b^n$ example establishes the formal separation by requiring an unbounded match between two counts. Tree depth and the class of generated strings are different questions.

This does not mean that every aspect of natural language is context-free. It means that context-free recursion is a useful and surprisingly powerful approximation. Later we will see where that approximation strains. For now, the important point is that CFGs give us a way to describe nested structure without enumerating every possible depth. A finite grammar can describe an infinite set of nested sentences.

A parse tree is an ordered tree, which means the left-to-right order of children matters. That order is what connects the tree to the original token sequence: the yield of a parent is the concatenation of its children's yields in order. Reversing two children can therefore change the token sequence even when their labels and dominance relations remain the same. Order is part of the representation, not an afterthought.

Several structural relations are useful when discussing trees:

• Dominance: A node $A$ dominates a node $B$ if $B$ is a descendant of $A$, including $A$ itself in the reflexive case. The root dominates every node.
• Immediate dominance: $A$ immediately dominates $B$ if $B$ is a child of $A$.
• Precedence: A node $A$ precedes a node $B$ if every leaf dominated by $A$ comes before every leaf dominated by $B$ in the yield.
• Yield: The yield of a node is the sequence of terminal leaves it dominates. In a constituency tree, the yield of every node is a contiguous span of the sentence.
• Head: Under a head-selection convention, many phrase types have a distinguished head child. The parent's lexical head is inherited from that child: usually a noun in an NP and a verb in a VP. In $NP \to NP\ PP$, for example, the head child can be the inner NP while the headword lies deeper in the tree. For ordinary compositional phrases, heads contribute category and lexical meaning.

Under the reflexive definition above, dominance is a partial order. For nodes with nonempty yields, precedence is a strict partial order: it is transitive and irreflexive, so a node does not precede itself. They let us talk about structure without constantly referring to the original token positions. Immediate dominance is the local relation that grammar rules license. If a node labeled VP immediately dominates a V and an NP, then the rule $VP \to V\ NP$ must be in the grammar. Precedence tells us how sister constituents are ordered. The yield connects the abstract tree back to the concrete sentence.

The head relation is not built into the bare definition of a CFG. A CFG rule such as $NP \to Det\ N$ does not formally say that N is the head. Linguists often annotate headedness separately. But headedness is why constituency and dependency grammar are not as far apart as they first appear. A dependency tree makes the head-dependent relations explicit. A bare constituency tree does not identify head-dependent links by itself. Given additional head-selection conventions, you can derive a dependency representation from many constituency analyses.

An ordinary ordered CFG tree gives each node a contiguous substring as its yield. It therefore does not directly represent a constituent whose words are separated by material outside that constituent. Some linguistic analyses use discontinuous constituents; treebanks may instead introduce empty categories and links to represent displaced material. This continuity property should not be confused with dependency projectivity, which concerns head-dependent links over token positions and will be defined in the next chapter. Head conventions and treatment of empty categories matter when converting between the representations.

A parse tree has a yield, a root, nonterminal nodes, and production rules that license each local configuration. Parsing searches for a tree whose root is the start symbol, whose terminal leaves are the input tokens in order, and whose local configurations are licensed by the grammar.

Ambiguity is a central practical problem in parsing. A grammar can assign more than one parse tree to the same token sequence. When that happens, the grammar is ambiguous for that sentence. Ambiguity is a property of the mapping between strings and structures. A grammar designed to preserve distinct structural readings can license alternative trees. Preserving those analyses is stronger than simply covering the same set of strings: two grammars can generate the same language while assigning different trees.

There are two broad kinds of ambiguity.

Lexical category ambiguity occurs when a word can belong to more than one syntactic category. The word "duck" can be a noun or a verb. The financial-institution and river-side senses of "bank" illustrate word-sense ambiguity, another form of lexical ambiguity: both can have the same noun category, so a bare N-to-bank rule does not distinguish them. In a CFG, category ambiguity appears as multiple preterminal rules for the same terminal:

A sentence like "I saw her duck" can then have multiple parses. In the noun reading, "duck" heads the noun phrase "her duck"; in the verb reading, it describes her action. This is closely related to the POS tagging problem from Part-of-Speech Tagging, but here the category analysis affects the larger phrase structure, not just the label of one token. Choosing a lexical category restricts which grammar rules and phrase structures the parser can use.

Structural ambiguity occurs when the same words and the same word categories can combine into different phrase structures. The classic example is prepositional phrase attachment:

the dog chased the cat with a telescope

The phrase "with a telescope" can attach to the object noun phrase "the cat":

[S
  [NP [Det the] [N dog]]
  [VP
    [V chased]
    [NP
      [NP [Det the] [N cat]]
      [PP [P with] [NP [Det a] [N telescope]]]]]]

Or it can attach to the verb phrase "chased the cat":

[S
  [NP [Det the] [N dog]]
  [VP
    [VP [V chased] [NP [Det the] [N cat]]]
    [PP [P with] [NP [Det a] [N telescope]]]]]

Both trees yield the same string. The first says the cat has a telescope. The second says the dog used a telescope to chase the cat. The grammar alone does not choose between them. Contextual information and plausibility judgments can guide a reader. To rank the alternatives, a parser can use a scoring model, a preference heuristic, or a probabilistic grammar. The structural difference is small in terms of the number of nodes, but it is large in terms of meaning. This is why attachment ambiguity is such a central test case for parsing models.

Coordination also creates structural ambiguity. The phrase "old men and women" can mean "old men and old women" or "old men and women who are not necessarily old". The string does not tell you which grouping is intended. A grammar can enumerate these structures, but it cannot decide which reading a speaker intends without extra information.

The number of possible structures can grow extremely quickly. For $n \ge 1$ tokens, the number of ordered full binary bracketings, before a grammar constrains which ones are licensed, is the Catalan number:

Equivalently, using the standard indexing $C_m = \frac{1}{m+1}\binom{2m}{m}$, the number of ordered full binary tree shapes with $n$ leaves is $C_{n-1}$. This counts possible bracketings before grammar labels and productions restrict them; it is not the number of parses licensed by every binary grammar.

The growth is exponential with a power-law correction. For large Catalan index $m$, the standard asymptotic estimate is

Here $m=n-1$ for a sentence with $n$ tokens, $\pi$ is the circle constant, and $\sim$ means that the ratio of the two expressions tends to one. The numerator supplies exponential growth; the denominator reduces it by a power of $m$. This is an approximation for large $m$, not an exact count for a finite sentence. In particular, the exact identity $C_{m+1}/C_m=(4m+2)/(m+2)$ tends to 4 from below. Calling the counts faster than every exponential would therefore be wrong.

For $n = 20$, that is already $C_{19} = 1{,}767{,}263{,}190$ possible binary bracketings. A grammar may rule out many of these shapes, but unrestricted enumeration still faces this worst-case growth. Chart parsers address it by sharing substructure. Pruning can further restrict which candidates are explored, although discarding candidates can lose a valid or best parse. Probabilistic ranking alone does not remove the need for efficient search: a parser that scores every complete tree still has to construct those trees.

The growth is easier to see on a log scale. The rising counts explain why chart parsers share subproblems: compact recognition avoids listing every complete tree, while explicit enumeration remains output-sensitive.

A probabilistic context-free grammar, or PCFG, adds probabilities to rules and gives each tree a probability. We will define PCFGs shortly. A probabilistic model can assign different weights to the permitted analyses. A probabilistic parser can return a highest-probability tree or represent the remaining uncertainty. This shifts the question from which structures are possible to how their probabilities compare.

A parser analyzes a token sequence using a grammar; on a successful parse, it can return one or more licensed trees. For CFGs, the most important teaching algorithm is the Cocke-Kasami-Younger algorithm, usually called CKY. It is a dynamic programming algorithm that fills a table of spans. The table is often called a chart, and each cell records the nonterminals that can derive a particular substring. Because subspans are reused many times, CKY avoids the combinatorial explosion of enumerating full trees independently.

CKY requires the grammar to be in Chomsky Normal Form.

The grammar from earlier is already in CNF. Every rule is either a binary nonterminal rule, such as $S \to NP\ VP$, or a lexical rule, such as $Det \to \text{the}$. There are no rules with three or more symbols on the right-hand side, and no empty productions. This makes the CKY recurrence especially simple: every span longer than one token must be split into exactly two smaller spans.

A CFG can contain rules outside these forms. For example:

has three children. It can be binarized by introducing a fresh nonterminal:

The new nonterminal $X_1$ is an artificial intermediate constituent introduced by binarization. It is absent from the original ternary analysis and lets the parser decompose that rule into two binary steps. The original tree can be recovered by collapsing the artificial nodes after parsing. This is a common pattern in parsing: introduce auxiliary symbols to satisfy a normal form, then undo the auxiliary structure when presenting the final analysis.

Converting an arbitrary CFG to CNF also involves eliminating empty productions other than the permitted start-to-empty exception, and unit productions such as $A \to B$. These conversions can change the shape of the parse tree. To recover original trees, retain a mapping from transformed rules back to the original grammar. Any CFG can be converted to an equivalent CNF grammar under the stated empty-string convention, possibly with a larger set of nonterminals. The equivalence is in the generated language, not necessarily in the exact tree shapes. A parser that needs linguistically faithful trees must therefore reconstruct the original rule applications.

Suppose the input tokens are $w_0, w_1, \ldots, w_{n-1}$. We use half-open spans $[i, j)$, where $i$ is the start index and $j$ is one past the end. The span $[i, j)$ covers tokens $w_i$ through $w_{j-1}$. Half-open intervals are convenient because adjacent spans meet cleanly: the left span $[i, k)$ and the right span $[k, j)$ share the boundary $k$ without overlapping.

The following chart recurrence assumes $n \geq 1$. For empty input, accept exactly when the CNF grammar contains $S \to \varepsilon$; if a tree is requested, return the start node expanded by that empty production. Our later toy grammar has no empty production and therefore rejects empty input.

Let $\text{chart}[i][j]$ be the set of nonterminals that can derive the span $[i, j)$. The base case handles single tokens:

The recursive case handles longer spans. A nonterminal $A$ derives $[i, j)$ if there is a split point $k$ and a binary rule $A \to B\ C$ such that $B$ derives the left span $[i, k)$ and $C$ derives the right span $[k, j)$:

The sentence is accepted if the start symbol $S$ is in $\text{chart}[0][n]$.

This recurrence is the heart of CKY. It is also the reason CNF matters. With binary rules, every span is split into exactly two parts. If rules could have three children, the recurrence would need to consider two split points at once, which is more complex. Binarization removes that complexity by turning one ternary rule into two binary rules. The parser then only needs to consider one split point per span.

The algorithm fills spans in increasing order of length. First all one-token spans, then all two-token spans, then all three-token spans, and so on. By the time we need a longer span, all of its subspans have already been computed. This is the same dynamic programming principle you saw with the Viterbi algorithm in Part VI, Ch 6, but here the table is indexed by spans rather than by time steps. In HMM Viterbi, a subproblem scores a prefix ending at a particular state. In CKY, it concerns a contiguous substring and its possible root category. The principle is the same: solve small problems once, store the results, and combine them to solve larger problems.

The fill order is triangular. Each cell is completed only after the smaller spans on both sides of its split have been completed.

The time complexity is:

where $n$ is the number of tokens and $|R|$ is the number of grammar rules. For a fixed grammar, this is $O(n^3)$. For the recognition chart, which stores nonterminal membership rather than every tree, space is $O(n^2 |N|)$, where $|N|$ is the number of nonterminals. With a fixed grammar it is $O(n^2)$. Explicitly enumerating all parse trees adds output-sensitive work and storage beyond these bounds. The cubic bound grows quickly with input length; actual runtime also depends on the grammar and implementation. Binarization enables the binary recurrence, neural scores can rank structures, and pruning can reduce work by discarding candidates, with a possible loss of exactness. Where a grammar and input produce a sparse chart, a parser can also avoid work on absent constituents. Sparsity depends on the grammar and sentence; it is not guaranteed.

CKY is not the only CFG parsing algorithm. The Earley parser works on arbitrary CFGs without requiring CNF, and it has an $O(n^2)$ time bound for unambiguous grammars and a linear bound for more restricted classes such as fixed LR($k$) grammars. For the distinctions among Earley grammar classes and runtime bounds, see the discussion in Opedal et al. (2023). Generalized LR parsers are another family used in compiler construction. But CKY is the cleanest algorithm for understanding the span-based dynamic programming that underlies many statistical parsers. Once you understand CKY, the inside algorithm, Viterbi parsing, and many neural chart parsers become much easier to read.

A plain CFG says which trees are possible. A probabilistic context-free grammar says how likely each tree is. A PCFG assigns a probability to every rule with a given left-hand side:

For each nonterminal $A$, the probabilities of all rules with left-hand side $A$ sum to 1:

When treating these weights as a probability distribution over finite sentences, we also assume that generation terminates with probability 1. Local rule normalization alone does not guarantee this: a recursive grammar can put some probability on infinite derivations.

The probability of a finite parse tree is the product of the probabilities of all rule occurrences used in the tree:

The probability of a sentence is the sum of the probabilities of all its parse trees:

A PCFG parser often returns the most likely tree:

Here $w$ is the observed input token sequence, and the maximization ranges only over trees whose yield is $w$. This can be computed with a variant of CKY that stores scores instead of just sets of nonterminals. For each span and nonterminal, we keep the best score and a backpointer to the split point and children that achieved it. The backpointers let us reconstruct the best tree after the chart is filled. This is exactly the same idea as Viterbi decoding in an HMM, generalized from sequence positions to spans.

The inside algorithm computes the total probability of all parses of a span. Let $\beta[i][j][A]$ be the total probability that nonterminal $A$ derives the span $[i, j)$. The base case is lexical:

if that lexical rule exists. The recursive case sums over split points and binary rules:

This is the PCFG analogue of the forward algorithm for HMMs. The root value $\beta[0][n][S]$ gives the sentence likelihood. The Viterbi variant replaces the sum with a max and stores backpointers. Inside values also support training and constituent uncertainty calculations, but an inside value alone is not the posterior probability that a span is a constituent in the observed sentence. That posterior also needs an outside contribution for the surrounding tree and normalization by the sentence probability, assumed positive.

In a PCFG, the probability of a rule depends only on its left-hand-side category. With coarse categories such as NP and VP, all occurrences of the same category share one rule distribution. The model can express a preference for an attachment rule, but cannot change that rule's probability directly in response to a surrounding word or discourse context. Richer categories can encode additional conditioning information. Some modern constituency parsers replace local rule probabilities with neural scores while retaining chart decoding. We will see that story in Constituency and Dependency Parsing.

Let us work through the ambiguous sentence with the grammar from earlier:

the dog chased the cat with a telescope

The tokens are:

the  dog  chased  the  cat  with  a  telescope

The grammar allows two complete S trees.

Parse A: the prepositional phrase modifies the object noun phrase.

[S
  [NP [Det the] [N dog]]
  [VP
    [V chased]
    [NP
      [NP [Det the] [N cat]]
      [PP [P with] [NP [Det a] [N telescope]]]]]]

In this parse, "the cat with a telescope" is a single NP. The cat is the one with the telescope. The VP is "chased the cat with a telescope", where the object is the entire NP. The attachment is noun phrase attachment because the PP is a sister of the inner NP "the cat" inside the larger object NP.

Parse B: the prepositional phrase modifies the verb phrase.

[S
  [NP [Det the] [N dog]]
  [VP
    [VP [V chased] [NP [Det the] [N cat]]]
    [PP [P with] [NP [Det a] [N telescope]]]]]

In this parse, "with a telescope" is a sister of the VP "chased the cat". The dog used a telescope to chase the cat. The object NP is just "the cat". The attachment is verb phrase attachment because the PP combines with the VP rather than with the object NP.

Both trees have the same yield:

the dog chased the cat with a telescope

The grammar does not distinguish them. A PCFG can rank them if its rule probabilities favor one attachment pattern. For example, assuming the shared rule factors have positive probability, if the grammar assigns a higher probability to $VP \to VP\ PP$ than to $NP \to NP\ PP$, Parse B will score higher. When a PCFG is estimated from a treebank, its preferences come from those observed rule uses. In our code example below, we instead assign probabilities by hand to illustrate the scoring calculation. The worked example therefore shows both the strength and the weakness of CFGs. The grammar precisely defines the space of possible structures, but it does not by itself tell us which structure is intended.

The grammar gives us a precise space of possible structures. Ambiguity means that space contains more than one tree for the same string. Scoring can rank the alternatives; identifying a speaker's intended reading may require contextual information.

We will build a small CKY parser from scratch. The grammar is already in CNF, so we can use it directly. We will then add a simple PCFG scorer and show how the number of possible binary bracketings grows. The implementation is deliberately small. It is meant to make the recurrence concrete, not to compete with a production parser. The core parsing and scoring operations follow the definitions from the previous sections.

The parser and scorer use the Python standard library; NumPy and Matplotlib support the figures. No corpus or model downloads are needed. This keeps the algorithm visible while the small grammar makes every result inspectable.

We start with a small Tree class. A tree has a label and a list of children. A child is either another Tree or a terminal string. The class provides three useful views: the yield, an indented pretty print, and a bracketed string. These views correspond to the three ways we have been talking about trees: as token sequences, as hierarchical diagrams, and as compact structural notation.

The leaf_tokens method recovers the yield of a tree. The pretty method prints an indented tree. The bracket method produces the compact bracketed notation we used earlier. Keeping all three views in one class makes it easy to check that every tree has the expected yield.

Each rule is a pair: a left-hand-side nonterminal and a tuple of right-hand-side symbols. Lexical rules have a single terminal on the right. This representation is simple, but it is enough to support the CKY recurrence. The grammar is small on purpose, so every rule can be inspected by eye.

The grammar has 13 rules: 6 binary rules and 7 lexical rules. Every rule is in Chomsky Normal Form, so CKY can use it without any conversion step. The binary rules build phrases, and the lexical rules connect terminals to preterminal categories.

The parser fills a chart indexed by spans. Each chart cell maps a nonterminal to a list of trees for that span. Keeping the trees, rather than just the nonterminals, lets us inspect every parse. This version explicitly enumerates parse trees. Its time and storage can therefore grow exponentially with ambiguity, unlike the membership-only CKY bounds above. We use only a tiny sentence with two parses so the full trees remain practical to inspect.

The base case fills one-token spans from lexical rules. The recursive case loops over span lengths, start positions, split points, and binary rules. If the left and right subspans both contain the required nonterminals, the parser combines every pair of trees into a new tree for the parent nonterminal. The order of the loops matters. By processing spans from short to long, the parser guarantees that chart[i][k] and chart[k][j] are already complete when they are used.

Now we parse the sentence and count the complete S trees.

The output shows the two attachment patterns directly. In one tree, the PP is inside the object NP. In the other, the PP is a child of the VP. The yields are identical, which is exactly the point: the string does not determine the tree.

A plain CFG treats both trees as equally possible. A PCFG can rank them. We assign illustrative probabilities to the rules. For each left-hand side, the probabilities sum to 1.

Finally, let's quantify the combinatorial explosion. The number of binary bracketings of $n$ tokens is the Catalan number $C_{n-1}$.

The numbers grow rapidly. At 20 tokens, there are already more than 1.7 billion binary bracketings before any grammar constraints are applied. A grammar can exclude many of these shapes. Membership-only CKY shares subproblems without enumerating every tree, while the small tutorial implementation deliberately materializes its two complete trees. Unrestricted enumeration can therefore become impractical even for short inputs. Algorithms such as CKY share subproblems to avoid enumerating every complete tree.

Context-free grammars are a major success of formal language theory. They give a precise definition of phrase structure, they support efficient parsing algorithms, and they connect syntax to recursion in a way that regular expressions cannot. CKY, Earley parsing, and probabilistic chart parsing all build on the CFG framework. The Penn Treebank paper describes the annotation of skeletal constituency structures used for syntactic analysis and parser research. The formalism also influenced compiler design, where context-free grammars describe programming language syntax and parser generators turn those grammars into working parsers.

But a CFG is a model, not a complete theory of human language. Its limitations become visible as soon as you try to cover real text. Our symbolic grammar lists its lexical rules explicitly. Broader coverage requires more entries or a strategy for unfamiliar words. A word may have multiple categories, and a fixed list cannot anticipate every new word. A grammar developed for one domain may under-cover text from another domain. Hand-written rules also encode assumptions about what is grammatical, and those assumptions can be brittle in the face of typos, fragments, code-switching, and informal syntax. Treebanks reduce the manual burden, but annotation is expensive and annotators disagree about borderline cases.

The formal power of CFGs is both a strength and a weakness. CFGs capture nested constituents and arbitrarily deep recursion. A small grammar with coarse categories may nevertheless omit agreement, case, or lexical valency constraints; finite category refinement can encode many such distinctions. The issue is the chosen grammar and the particular dependency pattern, not an inability to express any unbounded dependency. A rule like $S \to NP\ VP$ does not require the subject and verb to agree in number. You can encode agreement by splitting categories into $SgNP$, $PlNP$, $SgVP$, and so on. This duplicates compatible productions; with several independent finite features, their category combinations can multiply. Feature-based grammars and unification-based formalisms add features and constraints to handle these dependencies more compactly. Shieber (1985) presents evidence for weak non-context-freeness from Swiss German cross-serial constructions, under the linguistic assumptions made in that argument. Tree-adjoining grammars are one way to extend context-free generative capacity while retaining polynomial parsing. Generative capacity and parsing complexity must be distinguished: even weakly equivalent formalisms can differ when grammar size is included in the analysis, as Kuhlmann, Satta, and Jonsson (2018) show for one CCG formalism versus TAG. Capacity and complexity claims require a specified formalism and explicit restrictions. The debate is subtle, and the practical lesson is not that CFGs are useless. It is that CFGs are a powerful approximation whose limits depend on which linguistic phenomena matter for the task.

Ambiguity is another fundamental limitation. A grammar can generate many trees for the same sentence, and the grammar alone cannot choose among them. PCFGs add probabilities, but their independence assumptions are strong. Rule probabilities depend only on the left-hand side, not on the surrounding lexical context or the larger discourse. A PCFG with coarse nonterminal categories shares rule probabilities across contexts that its category labels do not distinguish. Adding lexical or structural information to those labels can refine the model. Some neural chart-based constituency parsers use learned structural scores in place of local PCFG rule probabilities while retaining chart decoding. Other parsing approaches use different search procedures, so this architecture should not be attributed to every modern parser. The move from symbolic grammars to statistical and neural parsing is not a rejection of constituency. It is a change in how constituency is scored and induced.

The impact of CFGs is therefore double-edged. They gave NLP a formal backbone for syntax, a family of parsing algorithms, and a way to evaluate structural predictions. They also revealed the limits of pure symbolic description. A grammar can tell you that a sentence has two possible structures. It cannot tell you which one a speaker intended. Inferring an intended reading may require context, world knowledge, or clarification from the speaker. The next chapters take up these threads. Dependency syntax offers a different view of structure, constituency and dependency parsing turn grammars into practical predictors, and structured prediction and parsing evaluation give us the tools to measure whether those predictors are any good.

• Constituency is the hierarchical grouping of words into phrases. Constituents can be identified with substitution, movement, coordination, and answer tests, though those tests are diagnostics rather than proofs.
• A context-free grammar is a tuple $(N, \Sigma, R, S)$ with rules $A \to \alpha$. It is context-free because each rule rewrites a single nonterminal regardless of surrounding symbols.
• A parse tree records a derivation hierarchically. Its terminal leaves are tokens, its nonterminal nodes record licensed phrase expansions, and its yield is the terminal sequence.
• Ambiguity arises when one token sequence has multiple parse trees. Lexical category ambiguity comes from words with multiple categories. Structural ambiguity comes from different phrase groupings, such as prepositional phrase attachment.
• CKY parsing uses dynamic programming over spans. In Chomsky Normal Form, a span is built by splitting it into two subspans and applying a binary rule. For a fixed grammar, its compact recognition chart runs in $O(n^3)$ time; enumerating every parse adds output-sensitive work.
• A PCFG assigns probabilities to rules and therefore to trees. The probability of a tree is the product of its rule probabilities. The inside algorithm sums over all parses of a span.
• CFGs capture recursion and nested constituency, including some unbounded dependencies. A particular grammar may need refined categories or feature constraints for agreement and lexical selection. Some dependency patterns motivate richer formalisms, while neural constituency parsers can supply learned structural scores.
• Symbolic grammars specify licensed trees. A parser can recognize or enumerate these structures without ranking them. A model or contextual information can then support the choice of a preferred or intended reading.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about grammars and constituency structure.