Constituency and Dependency Parsing › The Parsing Problem

Before choosing a decoder, fix the input units and the set of structures it is allowed to return. These choices determine which candidates can be compared.

The parsing algorithms here take a tokenized sentence, optionally accompanied by part-of-speech tags and morphological features. An integrated NLP pipeline may accept raw text and perform tokenization before its parsing stage. A treebank may distinguish syntactic words from surface tokens, especially for clitics and multiword tokens in Universal Dependencies. If your tokenizer produces different units, its tree has different leaves from the reference. Direct comparison then requires an explicit alignment or matching tokenization; a well-formed output alone does not establish compatibility.

The output depends on the annotation scheme:

• A continuous constituency tree assigns syntactic categories to internal nodes, including part-of-speech categories immediately above tokens, and a token to each leaf.
• A dependency tree assigns every token exactly one head and one dependency label, with an artificial root node above the sentence.

These two outputs encode different information. A constituency tree tells you that "the dog" is a noun phrase and that the noun phrase is part of a larger verb phrase. A dependency tree tells you that "dog" is the object of "saw" and that "the" is a determiner of "dog". Converting between them requires conventions about heads and phrase categories; information preserved by a conversion depends on those conventions. The constituency view is convenient when phrase boundaries and nesting matter, while the dependency view is convenient when word-to-word relations matter.

Evaluation also depends on the scheme. Constituency parsing is often evaluated with bracketing precision, recall, and F1, or exact match. Dependency parsing is often evaluated with unlabeled attachment score and labeled attachment score; label accuracy can also be reported. We will return to evaluation in the next chapter.

Accuracy against a treebank is relative to its annotation standard. For an annotation-based comparison, evaluate parsers on the same test annotations and report training conventions or conversions. When deploying a parser, check that its output scheme matches what the downstream application expects.

For a fixed sequence of (n \geq 1) tokens, count unlabeled dependency trees with exactly one token attached to an artificial ROOT at position 0. If crossings are allowed, including both projective and non-projective trees, there are (n^{n-1}) candidates. At (n=10), that is one billion trees.

Projectivity requires each token and its descendants to occupy a contiguous interval of token positions. With ROOT fixed at position zero, this is equivalent to drawing all arcs, including the ROOT arc, without crossings. Requiring projectivity reduces the count to

$$P_n = \frac{1}{n}\binom{3n-2}{n-1}.$$

Here (P_n) counts trees over the same fixed token order, without relation labels and with one ROOT attachment. It counts seven trees for three tokens and 690,690 for ten. The Catalan number (C_n) counts a different family, such as full binary bracketings of (n+1) ordered leaves; it does not count these dependency trees. Constituency parsing also faces many candidate bracketings, before grammar rules and phrase labels are considered. The unrestricted dependency count grows faster than a fixed-base exponential, while the projective count still grows exponentially.

The difference between these candidate sets is easier to see on a log scale.

To choose an analysis without enumerating every tree, the prediction methods here use two ingredients:

1. A scoring function that assigns a preference to a partial or complete structure.
2. A decoder that finds a high-scoring structure without enumerating everything.

Different parsing families make different choices about both ingredients. Under decomposable scores and sufficient chart states, a chart parser can combine best sub-span analyses to find a best larger-span analysis. Transition-based parsers exploit the fact that trees can be built incrementally, so the search becomes a sequence of small local choices. Graph-based parsers exploit the fact that a tree is a constrained graph, so the search becomes a well-studied combinatorial optimization problem. In every case, the trick is to replace brute-force enumeration with a smarter search that respects the structure of the problem.

Prepositional phrase attachment permits competing analyses even in a short sentence:

• "She saw the man with the telescope."
• Reading A: she used a telescope to see the man.
• Reading B: she saw the man who had a telescope.

A constituency parser might produce two trees with different phrase boundaries. A dependency parser might attach "telescope" to "saw" in one tree and to "man" in the other. A probabilistic or neural model learns which attachment is more likely from data and context. A grammar-based parser may need lexicalized rules or preferences to distinguish them. Both readings are licensed by the sentence. World knowledge and surrounding context can favor one reading, including information unavailable to a parser that sees only the sentence.

Related structural choices arise in coordination scope, nominal-compound bracketing and relative-clause attachment. Parsing models can also assign positions to long-distance dependencies. A fixed attachment preference cannot distinguish the two telescope readings when context changes which reading is intended. The scoring model needs evidence that can change with the words and their context. Lexicalized grammars and contextual neural scorers provide ways to include that evidence; they do not guarantee that every ambiguous sentence will be resolved correctly.