Constituency and Dependency Parsing

In "the man saw the dog with a telescope", who had the telescope? Attach the final phrase to "saw", and the man used it to see the dog. Attach it to "dog", and the dog had it. The words alone permit both readings. Parsing turns a flat sequence of tokens into a syntactic structure; the algorithms in this chapter search the possible structures and choose an analysis under a scoring model. The previous chapters introduced the tokens and annotations that these algorithms take as input.

This chapter uses two representations of syntax:

• Constituency parsing groups words into nested phrases such as noun phrases, verb phrases, and sentences.
• Dependency parsing links each word to a syntactic head and labels the relation, such as subject, object, or modifier.

Constituency structure represents phrase boundaries and nested clauses. Dependency structure represents word-to-word relations, including relations used in information extraction. Choosing between them depends on the annotation scheme and the task. For the prediction problem studied here, a parser combines a scoring model with a decoder that searches the candidate trees.

The candidate set can grow rapidly with sentence length. Under a scoring model, choosing between the telescope readings means ranking the available analyses. The ranking depends on the grammar, lexical preferences, context and annotation scheme. Scalable decoders seek a best or approximately best tree without enumerating the full candidate set. We will also use explicit enumeration to check tiny examples.

This chapter covers four families of parsing methods:

• Chart parsing, which uses dynamic programming over spans.
• Transition-based parsing, which treats parsing as a sequence of actions.
• Arc-factored graph-based parsing, which scores possible arcs and finds a highest-scoring permitted tree with a spanning-tree decoder.
• Neural parsing, which learns structural scores or a conditional model for generating an encoded tree.

These families overlap. Neural chart, transition and graph parsers supply learned scores to their respective search procedures. A sequence-to-sequence parser instead generates an encoding of the analysis through successive output decisions. Separating the scoring assumptions from the inference procedure helps identify the source of a parsing error.

For each method, ask what it scores, how it searches, which structures it permits, and what the search costs. These questions separate exact from approximate search and expose the conditions behind linear or cubic decoding bounds.

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

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.

A chart parser reuses analyses of smaller spans instead of rebuilding them for every larger tree. We first make the grammar assumptions explicit, then examine that reuse.

We describe the continuous constituency grammars here using a context-free grammar:

[ G = (N, \Sigma, R, S) ]

where:

• $N$: a finite set of nonterminal symbols, the syntactic categories
• $\Sigma$: a finite set of terminal symbols, the words; $N$ and $\Sigma$ are disjoint
• $R$: a finite set of production rules of the form $A \to \alpha$ with $A \in N$ and $\alpha \in (N \cup \Sigma)^*$
• $S$: the designated start symbol for complete sentence derivations ($S \in N$)

A rule such as

[ NP \to Det\ N ]

says that a noun phrase can consist of a determiner followed by a noun. A parse tree records hierarchical rule applications. It does not fix the order of expanding independent branches: after applying (S\to A\ B), expanding (A) before (B), or (B) before (A), can give the same tree. Reading its leaves left to right recovers the sentence, and its internal categories describe the constituent structure.

For example, a small grammar might derive "the man saw the dog" with a tree like this:

S
├── NP
│   ├── Det: the
│   └── N: man
└── VP
    ├── V: saw
    └── NP
        ├── Det: the
        └── N: dog

The leaves are the tokens. Internal nodes carry syntactic categories, including phrase categories and preterminal part-of-speech categories. The root here is the sentence category S. Every internal node spans a contiguous run of leaves: "the man" and "saw the dog" are examples. This follows from the way ordered context-free rules combine adjacent yields and supplies the span decomposition used by CKY.

A context-free grammar can generate the same token sequence with more than one tree. That is syntactic ambiguity. A probabilistic context-free grammar, or PCFG, attaches a probability to each rule and defines the probability of a tree as the product of its rule probabilities:

[ P(T) = \prod_{r \in T} P(r) ]

where:

• $T$: a parse tree, understood as the multiset of rules applied in the derivation
• $r$: a rule occurrence in that derivation, drawn from the set $R$ of grammar rules
• $P(r)$: the probability the PCFG assigns to rule $r$. For each $A \in N$, $\sum_{r \in R:\operatorname{lhs}(r)=A} P(r) = 1$, where $\operatorname{lhs}(r)$ is the rule's left-hand side.

The product gives the probability of the rule choices generating that tree. Normalizing productions for each left-hand side specifies the local choices. A proper distribution over finite complete derivations additionally requires consistency: termination with probability one. Recursive PCFGs can violate this even when each local rule distribution sums to one. Each finite derivation still has a well-defined product weight, but a fixed sentence need not have finitely many derivations. For example, (S\to S) and (S\to a), each with probability (1/2), give a distinct parse of "a" at every unary-chain length (k\geq0). Its probability is (2^{-(k+1)}), and these infinitely many finite-derivation probabilities sum to one.

The most likely tree is the one that maximizes this product. In a bare, unlexicalized PCFG, a structural rule such as (PP \to P\ NP) has the same probability regardless of the head words involved. Its lexical productions still assign probabilities to words, but its structural rule choices do not directly condition on lexical heads. Lexicalized grammars add head words to the conditioning context. Latent-variable PCFGs instead refine coarse observed categories with hidden states. Neural chart parsers can score spans from contextual representations without requiring a PCFG rule-probability table. These approaches change what is scored while retaining a structured decoding problem.

The "ordered" part of the definition matters: the children of a node have a left-to-right order that matches the word order. This is what distinguishes a constituency tree from an unordered tree of categories, and it is what allows the tree to be read back as a sentence.

Chart parsing stores partial analyses in a chart. In the CKY setup here, a cell (\text{chart}[i,j]) stores the nonterminals that can derive the half-open span containing tokens (i, i+1, \ldots, j-1). A larger-span analysis combines shorter-span analyses. Keeping their results lets different larger analyses reuse the same subproblem values.

CKY uses grammars in Chomsky normal form. In the nonempty CNF convention here, every rule is either:

• A lexical rule (A \to w), where (w) is a terminal.
• A binary rule (A \to B\ C), where (B) and (C) are nonterminals.

For nonempty strings, a context-free grammar can be converted to an equivalent CNF grammar, though the conversion may introduce nonterminals and increase grammar size. A grammar that licenses the empty string needs a separate empty-string convention; unary productions also need treatment. A ternary production (A \to B\ C\ D) can be replaced by (A \to B\ X) and (X \to C\ D), with a fresh helper (X). In a PCFG, giving the first rule the original probability and the helper rule probability one preserves that rule occurrence's contribution to the derivation probability. Other transformations, especially eliminating unary cycles or empty productions, require their own probability accounting.

For a sentence with tokens indexed so that the span from $i$ to $j$ (half-open) contains tokens $i, i+1, \ldots, j-1$, the inside probability is the total probability of all subtrees rooted at nonterminal $A$ that derive that span. For a PCFG in CNF it is:

[ \alpha_{i,j}(A) = \sum_{A \to B C} P(A \to B C) \sum_{k=i+1}^{j-1} \alpha_{i,k}(B),\alpha_{k,j}(C) ]

where:

• $A, B, C$: nonterminal symbols, with $A$ the parent and $B, C$ its two children in a binary rule
• $\alpha_{i,j}(A)$: the inside probability that $A$ derives the span from token $i$ up to (but not including) token $j$
• $P(A \to B C)$: the probability assigned to the binary rule $A \to B C$ by the PCFG
• $k$: the split point; the left child $B$ spans $i$ to $k$ and the right child $C$ spans $k$ to $j$
• $\alpha_{i,k}(B)$ and $\alpha_{k,j}(C)$: the inside probabilities of the two children on their respective sub-spans

The base case is a lexical rule, where a preterminal $A$ derives a single token $w_i$:

[ \alpha_{i,i+1}(A) = P(A \to w_i) ]

where $P(A \to w_i)$ is the probability of the lexical rule that rewrites $A$ as the word $w_i$.

For Viterbi parsing, we want one highest-probability tree rather than the summed probability over all trees, so we replace the sum over splits with a max and keep backpointers:

[ \delta_{i,j}(A) = \max_{A \to B C} \max_{k=i+1}^{j-1} P(A \to B C),\delta_{i,k}(B),\delta_{k,j}(C) ]

where $\delta_{i,j}(A)$ is the maximum probability of any $A$-rooted subtree deriving the span $i$ to $j$, and the backpointer records the split point $k$ and rule $A \to B C$ that achieved the maximum.

The recurrence says something simple: a constituent spanning (i) to (j) can be split at some (k). The left child spans (i) to (k), the right child spans (k) to (j), and a binary rule combines them. Because every split uses smaller spans, the chart can be filled bottom-up. The algorithm starts with spans of length one, then length two, and so on, until the full sentence span is reached. At each step, the answers for the smaller spans are already available, so the larger span can be computed in a single pass over its possible split points. This is the same dynamic-programming pattern you see in sequence alignment and shortest-path problems: solve the small subproblems, memoize the answers, and combine them.

The chart's work can be viewed as a triangular table: each valid span owns one cell, and each cell scans the internal boundaries where a split could occur.

Unpruned compact CNF CKY takes (O(n^3 |R|)) time and (O(n^2 |N|)) memory with bounded scores and backpointers per state. The cubic factor comes from choosing a split point (k) for every span; grammar size also enters the bound. Pruning can reduce retained search space while losing the optimal tree. Neural span scoring changes the model but does not by itself remove the cubic bound of exact span decoding. Counting each span and each internal split once gives (n(n-1)(n+1)/6) span-split combinations: 4,495 at 30 tokens and 1,333,300 at 200 tokens, before checking grammar rules. This count separates the combinatorial work from a loose (n^3) upper bound.

Unpruned Viterbi CKY finds a highest-probability tree for its specified CNF PCFG. That guarantee concerns model optimization, not agreement with a reference analysis. A bare unlexicalized PCFG cannot directly condition a structural rule choice on lexical heads. An exact optimizer can therefore select a wrong analysis under its model, while an approximate search under a different model may select the reference tree. Comparing the resulting predictions requires an evaluation protocol.

CKY is simple, but it requires CNF. The Earley algorithm parses arbitrary context-free grammars, including left-recursive and unary rules, without converting to CNF. It maintains a set of dotted rules at each position. A dotted rule such as (NP \to Det \cdot N) means the parser has recognized a determiner and is waiting for a noun. The dot is a cursor that records how much of a rule's right-hand side has been matched so far.

Earley parsing proceeds by three operations. Prediction adds new dotted rules for the categories the parser expects next. Scanning advances the dot past a terminal when the next input token matches. Completion advances rules that were waiting on a nonterminal once that nonterminal has been fully recognized. The set of states at each position is called an Earley set, and the algorithm processes these sets left to right. Because it tracks the origin position of each dotted rule, it can handle the full generality of context-free grammars without the binary-branching restriction.

For a fixed grammar, the classical Earley bounds are (O(n^3)) in general, (O(n^2)) for unambiguous grammars, and (O(n)) for the bounded-state grammar class under the relevant algorithm conditions. Here bounded-state means that each Earley set contains at most a grammar-dependent constant number of states, including their distinct origin positions, independent of sentence length. Under the stated algorithm conditions, processing each input position then takes bounded work. Implementation details and grammar preprocessing matter to these bounds. Earley parsing is useful when the grammar should remain in its original, potentially nonbinary form. Weighted Earley algorithms also support probabilistic computation, so handling a general grammar does not exclude statistical training. Opedal et al. (2023) give a reference formulation and explain the grammar-size factors hidden by fixed-grammar notation.

Consider the sentence "the man saw the dog". A chart parser fills cells like this:

• Span [0,2] for "the man": NP; Det and N occupy [0,1] and [1,2].
• Span [2,3] for "saw": V.
• Span [3,5] for "the dog": NP; Det and N occupy [3,4] and [4,5].
• Span [2,5] for "saw the dog": VP, because VP (\to) V NP.
• Span [0,5] for the whole sentence: S, because S (\to) NP VP.

CKY builds larger analyses from smaller constituents, reusing each chart cell's results. This reuse does not imply streaming: the implementation below allocates its chart from the complete token sequence, and a contextual scorer may inspect the entire sentence. The span [0,2] for "the man" is a single NP cell in the chart, built from the Det cell at [0,1] and the N cell at [1,2]. This particular span has only one category under the tiny grammar. More generally, a chart can retain competing categories and derivations until a larger constituent uses them, rather than committing to one early attachment. The later eight-token telescope example exhibits two complete derivations.

Dependency decoders assemble word-to-word arcs under tree constraints. Transition and graph methods enforce those constraints through different search procedures.

A dependency tree represents syntax as a set of head-dependent relations. For a sentence with tokens (w_1, \ldots, w_n), we add an artificial root node (w_0). A dependency tree is a directed graph with:

• One node for the root and one node for each token.
• Exactly one head for every token.
• Exactly one token whose head is the root.
• No cycles.
• All nodes connected to the root.

Here, each arc carries a relation label. Examples from different treebank conventions include nsubj, dobj, det, amod and obl. The exact label set depends on the treebank. Universal Dependencies provides a cross-lingual inventory of labels and guidelines, but individual treebanks still differ in tokenization and annotation choices. Acyclicity, connectivity to ROOT and one incoming head arc per real token give a rooted arborescence. Requiring exactly one real token to attach directly to ROOT is an additional annotation convention; a general arborescence can have several ROOT children.

A dependency tree is projective when every node's subtree occupies a contiguous interval of token positions. With the artificial ROOT fixed outside the sentence at position zero, this is equivalent to drawing all arcs, including the ROOT arc, without crossings. Two arcs cross when their endpoint intervals interleave. Omitting the artificial ROOT arc can hide a nonprojective configuration, so the drawing convention matters. Projectivity belongs to a tree relative to word order; languages and treebanks differ in how frequently their analyses are nonprojective.

Ordinary projective transition systems cannot produce a nonprojective reference tree. Unrestricted arborescence decoding permits nonprojective trees directly. Czech and German treebanks include nonprojective constructions, so the permitted tree family affects coverage. Both the representation and inference procedure must permit the desired analysis; a SWAP extension is one way to extend a projective transition system.

Transition-based parsing builds a tree incrementally. The parser maintains a configuration with three parts:

• A stack of processed tokens.
• A buffer of unprocessed tokens.
• A set of arcs that have already been created.

The parser starts with the root on the stack and all tokens in the buffer. At each step, it applies a transition. In the arc-standard system, the transitions are:

The stack is ordered from left to right, with the top at the right end. A LEFT-ARC creates a head that is to the right of its dependent. A RIGHT-ARC creates a head that is to the left of its dependent. The asymmetry between the two arc actions is what lets the parser decide, at each step, whether the current pair of stack items should be linked with the top as head or the second item as head.

For "She saw him", a gold transition sequence is:

1. SHIFT "She".
2. SHIFT "saw".
3. LEFT-ARC(nsubj): "saw" is the head, "She" is the dependent.
4. SHIFT "him".
5. RIGHT-ARC(dobj): "saw" is the head, "him" is the dependent.
6. RIGHT-ARC(root): the artificial root is the head, "saw" is the dependent.

In this arc-standard convention, a complete parse of (n) tokens takes (n) SHIFT actions and (n) arc actions, including the final ROOT arc: (2n) transitions. With constant-time stack and buffer operations and fixed-cost action scoring, greedy decoding therefore takes (O(n)) time, excluding sentence encoding. A classifier scores the legal transitions at each configuration, and the parser chooses the highest-scoring action. Training uses an oracle that derives the gold action sequence from a gold tree. The oracle connects the gold tree to the action sequence the parser predicts. An oracle supplies local action targets from tree supervision; other structured training methods can use gold trees without committing to one canonical action sequence.

Greedy arc-standard decoding commits to its chosen action history. An incorrect arc changes the subsequent configuration and cannot be retracted within that history. Beam search keeps several configurations alive and can improve accuracy, but it is still approximate. Error propagation is especially dangerous because the parser's later decisions depend on the configuration it has built, so an early mistake changes the features the classifier sees and can cause further mistakes.

There is also spurious ambiguity: multiple transition sequences can produce the same tree. A static oracle that always follows one gold sequence can teach the parser to prefer an action even when another action would yield the same tree. A dynamic oracle identifies actions that preserve the minimum reachable loss relative to the gold tree. When the gold tree is still reachable, this includes all actions that preserve a gold derivation. After a mistake makes it unreachable, the oracle instead preserves the best achievable remaining outcome. This supports training on off-gold configurations as well as handling multiple correct action sequences.

The ordinary arc-standard and arc-eager systems both produce projective trees. In Nivre's (2009) stack-based nonprojective extension, a SWAP action removes the second-top stack item and returns it to the front of the buffer, subject to an ordering restriction that prevents repeated reversal. This changes the processing order and permits crossing arcs. Such a system can require quadratically many transitions in the worst case; the linear bound for ordinary arc-standard parsing does not carry over automatically.

Neural transition-based parsers use learned representations for scoring configurations. Chen and Manning (2014) used a feed-forward network over configuration features. Dyer et al. (2015) used a stack-LSTM to represent the configuration. Kiperwasser and Goldberg (2016) used BiLSTM features. These architectures change the inputs to action scoring; they do not guarantee that every decision improves. Within an ordinary arc-standard configuration, arc actions are irreversible. Greedy decoding commits to one history, while beam search can retain alternative histories and later select among them.

Graph-based parsing takes a different view. Instead of building a tree step by step, it scores candidate arcs and then finds an admissible tree that maximizes their total score:

[ \hat{y} = \arg\max_{y \in \mathcal{T}(w)} \sum_{(h,d,l) \in y} s(h,d,l) ]

where:

• $y$: a candidate dependency tree, a set of labeled arcs
• $\mathcal{T}(w)$: the set of valid dependency trees for the sentence $w$, each acyclic, connected to the root, and giving every token exactly one head
• $(h, d, l)$: one labeled arc, with $h$ the head token, $d$ the dependent token, and $l$ the relation label
• $s(h, d, l)$: the score assigned to that single arc

The score $s(h,d,l)$ contributes one arc term, while the decoder enforces the tree constraint. Each term may use contextual representations of the entire sentence; additive factorization does not require context-free features. It omits explicit interactions between selected arcs. For the projective and unrestricted arborescence families described below, this factorization permits polynomial-time exact decoding.

Without a projectivity restriction, arc-factored decoding is a maximum spanning arborescence problem. The Chu-Liu/Edmonds algorithm solves the rooted arborescence problem exactly. A standard arborescence decoder may give artificial ROOT several children, however. Enforcing exactly one ROOT attachment requires an additional constraint, for example by considering each possible sentence root while forbidding other ROOT arcs. A naive greedy approach fails because choosing the best incoming arc for each token can create a cycle. Chu-Liu/Edmonds handles cycles by contracting them into a supernode, adjusting arc weights, and recursing. When a cycle is expanded, one arc in the cycle is broken to restore a tree. The weight adjustment is the clever part: it encodes the cost of replacing one arc in the cycle with an arc from outside, so that the recursive call on the contracted graph makes the right global trade-off.

For projective arc-factored trees, Eisner-style dynamic programming gives (O(n^3)) decoding. Its ROOT constraints must match the tree convention, including the one-ROOT-child requirement here. Eisner's algorithm uses incomplete items that include an arc between the two boundary heads and complete items whose span is covered by a subtree headed at one boundary. It combines left and right dependents in a fixed order, which prevents crossing arcs. The result is an exact projective parser for arc-factored scores. These item states control which partial structures can combine while preserving a projective tree. A complete item is complete within its span; its head can still take dependents outside that span during later combinations.

For the arc-factored objectives described here, graph-based decoding is exact within the permitted tree family. The limitation is the factorization: sibling dependencies and grandparent relations are not explicit score factors. Higher-order graph-based models score larger fragments, and sufficiently rich nonprojective factorizations can make exact decoding NP-hard. Second-order models can score pairs of adjacent arcs or head-dependent-grandparent triples. Their tractability depends on the permitted structures and the specific pairs scored.

Two labeling arrangements are useful to distinguish. A pipeline first finds an unlabeled tree and then labels its arcs with a classifier. A joint model scores labeled arcs directly, so the best available label score can affect which head attachment is selected. A label-only second stage cannot repair an already fixed head attachment. For purely arc-factored labeled scores, maximize over the labels for each possible head-dependent pair first, then decode using those maximum arc scores and retain the winning labels. Label selection does not require a different structural search in that special case. Interactions involving labels on multiple arcs require additional modeling and decoding machinery.

Neural graph-based parsers learn token representations and score arcs with a neural network. Dozat and Manning (2017) use biaffine classifiers for arcs and labels. One general biaffine form, used for the illustrative computation below, is:

[ s(h,d) = \mathbf{h}_h^\top \mathbf{U} \mathbf{h}_d

• \mathbf{w}_h^\top \mathbf{h}_h
• \mathbf{w}_d^\top \mathbf{h}_d
• b ]

Here (\mathbf{h}_h\in\mathbb{R}^{d_h}) and (\mathbf{h}_d\in\mathbb{R}^{d_d}) represent the candidate head and dependent. The matrix (\mathbf U) has shape (d_h\times d_d); the weight vectors have the corresponding head or dependent dimension, and (b) is a scalar. The bilinear term combines features from both words, while the two linear terms contribute one-word preferences. The result is an unnormalized score, not a probability.

For labeled parsing, use a label-specific matrix (\mathbf{U}_l) and a label-specific bias:

[ s(h,d,l) = \mathbf{h}_h^\top \mathbf{U}_l \mathbf{h}_d

• \mathbf{w}_{h,l}^\top \mathbf{h}_h
• \mathbf{w}_{d,l}^\top \mathbf{h}_d
• b_l ]

where:

• $\mathbf{h}_h$: the representation of the head token $h$
• $\mathbf{h}_d$: the representation of the dependent token $d$
• $\mathbf{U}_l$: the learned bilinear matrix for label $l$, capturing head-dependent compatibility under that label
• $\mathbf{w}_{h,l}$ and $\mathbf{w}_{d,l}$: learned label-specific weight vectors applied to the head and dependent representations
• $b_l$: the learned scalar bias for label $l$
• $s(h,d,l)$: the resulting score for attaching dependent $d$ to head $h$ with label $l$

Using one parameter set gives one score per candidate arc. Using label-specific parameters gives a score for every candidate arc-label combination. An unlabeled scorer does not itself assign relation labels; a separate label classifier or a joint labeled objective supplies those decisions.

Token representations can come from a BiLSTM, a Transformer, or a pretrained language model. The scorer supplies arc scores to Chu-Liu/Edmonds or Eisner, with constraints matching the intended tree family. Training can use local head-selection cross-entropy, a structured margin, or a structured likelihood computed with the matrix-tree theorem. Contextual scores can use input information absent from the structural rule probabilities of a bare unlexicalized PCFG. Tree validity comes from the decoder and its constraints; it does not establish annotation accuracy.

The matrix-tree theorem connects arc-factored parsing to probabilistic modeling. With positive arc weights, which can be obtained by exponentiating scores, an appropriate reduced Laplacian determinant sums the products of arc weights over directed spanning trees rooted at a designated node. The full Laplacian is singular and is not the matrix whose determinant gives that rooted partition function. When the reduced matrix is nonsingular, arc marginals follow from derivatives of its log determinant and can be computed using its inverse. A standard rooted-arborescence partition can include several children of artificial ROOT; matching the single-ROOT-attachment convention in this chapter requires a compatible constrained construction, such as summing partitions with each possible sole ROOT child in turn. Computing a partition function does not replace maximum-score decoding.

Neural methods are not limited to transition-based or graph-based decoding. A span-based constituency parser can assign category scores to spans and use a CKY-style decoder to select a tree. This retains dynamic programming while changing the scoring model. Stern et al. (2017) use differences of contextual boundary vectors to represent spans; the scorer need not pool every token inside a span. Kitaev and Klein (2018) replace the recurrent sentence encoder with self-attention. The decoder is exact for its specified additive span objective, provided it does not prune candidates.

Sequence-to-sequence parsing takes a different route. It linearizes the tree as a string, such as a bracketed constituency tree or a sequence of dependency decisions, and trains a sequence-to-sequence model to generate that string. The decoder makes successive output-token decisions, for example using beam search. This can reuse a general sequence-generation architecture, but an unconstrained output vocabulary does not enforce balanced brackets, complete token coverage, or dependency-tree constraints. Constrained decoding or post-validation is needed when the output must be a well-formed tree. A high-scoring output string and a valid parse are separate requirements.

Large language models add another option: prompt the model to output a bracketed tree or a dependency list. This permits a parsing experiment without training a new task-specific model, but it establishes no accuracy guarantee for a language or annotation scheme. Prompt choices can affect the result. Report the prompt and requested output encoding when describing an experiment. Studies such as Tian et al. (2024) evaluate prompted constituency parsing and find difficulties with full trees. Keep the supplied syntactic-word sequence fixed, choose and report decoding settings, and validate token coverage and tree constraints before scoring against gold annotations.

Parsing decoding searches for an analysis under a model. Chart and graph decoders search tree structures directly. Sequence-to-sequence parsers instead generate an encoding of a tree through successive output-token decisions. Both perform inference, but their candidate spaces and structural guarantees differ.

The main trade-offs are:

• Exact versus approximate search. Unpruned Viterbi CKY and exact arborescence decoding optimize their specified objectives. Greedy transition decoding and finite beam search do not generally guarantee a global optimum.
• Projective versus non-projective. Arc-standard transition systems are projective. Eisner is projective. Chu-Liu/Edmonds handles non-projective trees. Swap-based transition systems extend the transition family but add complexity.
• Local versus global decisions. A transition parser makes local decisions that may be hard to revise. A graph-based parser makes local arc scores but enforces a global tree constraint at decode time. A chart parser combines local constituents into global spans.
• Time and memory. Ordinary greedy arc-standard decoding uses (2n) actions and is linear under the stated fixed-cost assumptions, excluding encoding. Compact CNF CKY has cubic sentence-length time and quadratic chart memory for a fixed grammar. Explicit tree enumeration has different storage costs. Unrestricted dense-graph arborescence decoding can use quadratic or cubic implementations; the single-ROOT constraint also needs accounting.
• Labeling. Joint arc-label scores can affect attachment selection. Labeling an already fixed tree cannot repair its heads. Cross-arc label interactions require a richer factorization.

These trade-offs interact. Exact search over a restricted scoring model and approximate search over a richer model can lead to different accuracy and latency results. Structural guarantees tell you which outputs are possible; they do not rank the models' linguistic accuracy. Compare that accuracy under the same annotation and evaluation protocol.

Table Table parsing-decoders summarizes decoder behavior. Sentence encoding is excluded; the transition row assumes fixed beam width and fixed-cost action scoring, and the chart rows hold the grammar or label inventory fixed. The MST row describes the base dense-graph solver: naively rerunning it for every possible sole ROOT child adds a factor of (n), whereas specialized single-root methods avoid that full repetition. Autoregressive sequence-model cost also depends on its architecture.

The table alone cannot choose a parser without application criteria. Measure encoding and decoding latency together for a latency budget. An unrestricted graph decoder is one option when nonprojective trees are required. For an explicit CFG, CKY after appropriate conversion or Earley on the general grammar are options. A neural scorer can also be combined with an exact decoder. Check the target annotations and permitted structures before comparing measured accuracy and resource cost.

Return to "the man saw the dog with a telescope". Ignore morphological details and use simplified labels.

Reading A attaches the prepositional phrase to the verb phrase. The man used a telescope to see the dog.

S
├── NP: the man
└── VP
    ├── VP
    │   ├── V: saw
    │   └── NP: the dog
    └── PP: with a telescope

Reading B attaches the prepositional phrase to the noun phrase "the dog". The dog had a telescope.

S
├── NP: the man
└── VP
    ├── V: saw
    └── NP
        ├── NP: the dog
        └── PP: with a telescope

In dependency form, the difference is one arc. Reading A makes "telescope" a dependent of "saw" through an oblique relation. Reading B makes "telescope" a dependent of "dog" through a nominal modifier relation. The rest of the tree can stay the same. This illustrates how much meaning can hinge on a single structural decision: the two trees differ in exactly one attachment, yet they describe different situations in the world.

The same words and part-of-speech tags permit different attachments. A scoring model ranks these relations using its available input. Surrounding discourse can favor one reading; a sentence-only input may leave that intended distinction unresolved even when the model assigns different scores to the two trees.

The code below is deliberately small. It is not a production parser. It is a set of executable models that show the core mechanisms: chart parsing, transition-based parsing, graph-based decoding, and neural arc scoring. The goal is to make the algorithms concrete, so that the prose above can be checked against running code.

We start with a small CNF grammar. The lexicon maps preterminal categories to words. The binary rules combine two constituents into a larger one.

Each row is a span and the categories that can derive it. The cell for "the dog" contains NP; Det and N occupy its one-token sub-spans. The cell for "saw the dog" contains VP. The cell for the whole sentence contains S. This is the chart that makes dynamic programming possible. The chart is also a useful debugging tool: for this exhaustive toy grammar, inspecting a missing category and the rules for its child spans can locate a failed derivation.

Now we implement the arc-standard transition system. The stack starts with the artificial root. The buffer starts with all token indices.

The final stack contains only the root. The buffer is empty. The arcs are exactly the dependency tree for the sentence. The parser created the subject arc when "saw" was on top of the stack and "She" was just below it. It created the object arc after shifting "him".

This example uses a hand-written transition sequence. In a trained transition parser, a classifier would score SHIFT, LEFT-ARC, and RIGHT-ARC at each step. The classifier would use the top stack words, their part-of-speech tags, the next buffer word, and possibly the already-built arcs. Greedy decoding picks the highest score. Beam search keeps several configurations.

For graph-based parsing, we need a way to find the best tree given arc scores. The brute-force decoder below is practical only for tiny sentences, but it makes the objective explicit.

The decoder recovers the gold tree because the gold arcs sum to 20 and every alternative includes at least one negative-scoring arc. The important point is not the hand-made scores. The important point is that the decoder enforces the tree constraint globally. A greedy per-token choice could create a cycle or two roots. The constrained toy decoder rejects both; an ordinary arborescence decoder can still allow multiple ROOT children.

A neural graph-based parser replaces the hand-made score table with learned representations. The code below uses random vectors, projections, and affine parameters. No encoder or scorer is trained, so these are illustrative scores rather than linguistic predictions. The computation follows the biaffine form above: encode tokens, project heads and dependents, compute a score matrix, then decode a tree.

The random parameters supply no learned linguistic preference. Replacing the random token vectors with contextual encoder outputs would give the scorer context-dependent inputs. Training aims to favor reference attachments; validity still depends on the decoder. Distinguish a model-ranking error from a search error: if an exact decoder optimizes its objective but the reference tree has a lower score, inspect the model, supervision and factorization. If the returned tree fails to optimize the specified objective, inspect the search approximation or decoder implementation.

Each method has a scope. Unpruned compact CNF Viterbi CKY is exact for its model and uses cubic sentence-length time and quadratic chart memory for a fixed grammar. Pruning can change exactness, and explicitly storing every tree can require much more memory. A bare PCFG's structural rule probabilities do not directly condition on lexical heads. Greedy arc-standard decisions are irreversible and can affect later configurations; beam search retains alternatives, while SWAP extensions have a different worst-case action count. Unrestricted graph decoding permits nonprojective trees, but arc-factored objectives omit explicit sibling and grandparent factors. Neural representations change the scores and features; decoder restrictions, domain shift, tokenization and annotation compatibility still matter.

The choice of formalism also has consequences. The continuous constituency trees used here group contiguous spans. Ordinary head-percolation conversion from such a tree yields projective dependencies; representing nonprojective analyses requires a different treatment, such as discontinuous constituents or an enriched representation. This is a restriction of the representation and conversion, not a claim that every constituency formalism is continuous. Dependency treebanks can directly annotate crossing arcs, but annotation conventions still matter: a parser trained with one label set or tokenization scheme may not transfer cleanly to another, even within one language.

Syntactic structure has been used in information and relation extraction, semantic role labeling, coreference resolution, machine translation, question answering, and knowledge graph construction. Whether a parse helps a particular system is an empirical question; a parser's errors can also propagate downstream. Pretrained parsers such as those in spaCy, Stanza, and SuPar let you obtain dependency analyses without training a parser from scratch. Throughput depends on the encoder, implementation, hardware and batching, so the decoder's asymptotic bound alone is not a capacity estimate. The next chapter takes up structured prediction and evaluation, including how to compare predicted trees with an annotation target.

Generating a parse string with an LLM does not remove the representation and evaluation requirements. Invalid or unfaithful trees have been observed in LLM constituency-parsing studies. Public test material can also create a contamination risk when pretraining data are unavailable for inspection; that risk is not proof that a particular model saw a particular treebank. Report the model and prompt, preserve the input units, and distinguish well-formedness from gold-annotation accuracy. A dedicated constrained decoder provides specified structural guarantees, while the quality of either approach still requires evaluation.

Parsing predicts syntactic structure over supplied input units. Constituency parsing builds nested phrase trees; dependency parsing builds labeled head-dependent trees. The candidate families counted here rapidly outgrow enumeration, although a restricted grammar can admit few analyses and a general cyclic grammar can admit infinitely many finite derivations of one sentence.

Unpruned Viterbi CKY is exact for its specified CNF PCFG and has cubic sentence-length time for a fixed grammar. Earley handles general CFGs with grammar-dependent bounds. Ordinary greedy arc-standard decoding builds projective trees in (2n) actions and is linear under fixed-cost scoring and operations, excluding encoding; SWAP extensions can require quadratically many actions. Chu-Liu/Edmonds exactly solves nonprojective arc-factored arborescence decoding, with an adaptation needed for our single-ROOT-child convention. Eisner-style decoding exactly optimizes the projective arc-factored family with matching ROOT constraints. Neural encoders and scorers supply learned representations and scores to these inference procedures, or generate encoded trees with a sequence model.

The central trade-offs are exact versus approximate search, projective versus non-projective structure, local versus global decisions, and speed versus accuracy. The best choice depends on the annotation scheme, the language, the latency budget, and the downstream task. In the next chapter we will connect these decoders to structured prediction and to the evaluation metrics used to compare their outputs with gold annotations.

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