Grammars and Constituency Structure › Ambiguity

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.