Dependency Parsing

A constituency parse describes which words group together — it nests the sentence into phrases (an $\text{NP}$ inside a $\text{VP}$ inside an $\text{S}$) and reads the grammatical work off that nesting. A dependency parse instead describes which word governs which. It discards phrasal nodes entirely and records only directed, labeled relations between the words themselves — an arc from a head to each of its dependents.¹ The subject and object of a verb, which a phrase-structure tree buries under intervening $\text{NP}$ and $\text{VP}$ nodes, hang directly off the verb here.

Two arguments recur through the whole chapter. First, dependencies expose predicate-argument structure cheaply: the arcs prefer $\to$ I (nsubj) and prefer $\to$ flight (dobj) are the sentence's who did what almost verbatim, which is why coreference, question-answering, and information-extraction systems consume dependency parses directly. Second, dependencies handle free word order gracefully. A phrase-structure grammar needs a separate rule for each position an adverbial can occupy; a dependency grammar needs one labeled arc type, and the arc means the same thing wherever the word sits.¹ For morphologically rich languages — Czech, Hindi, Finnish — that abstraction away from position is the decisive advantage.

Dependency relations

Each arc carries a grammatical relation (also grammatical function): the role the dependent plays with respect to its head. The Universal Dependencies (UD) project standardizes this inventory across languages, so that nsubj means the same thing in an English tree and a Finnish one.² The core relations split into two groups: clausal relations, which name a word's syntactic role relative to a predicate, and modifier relations, which name how a word modifies its head.

Notice that case treats a preposition as a dependent of the noun it introduces, not as the head of a prepositional phrase. This is a deliberate UD choice: the content word (Houston) governs the function word (through), which keeps the relations lexical and comparable across languages that mark case with an affix rather than a separate word.

The formalism: rooted trees

Strip the labels and a dependency structure is a directed graph $G=(V,A)$: the vertices $V$ are the words (plus a special $\text{ROOT}$), and the arcs $A$ are the ordered head-dependent pairs. The parsing algorithms in this lesson all assume a particular restriction on that graph — a dependency tree.³

The single-head constraint is what distinguishes a dependency tree from a general semantic graph: each word has exactly one governor. The $\text{ROOT}$ node is a bookkeeping device — it gives the main verb of the sentence a head, so that every word (including the top predicate) sits at the end of exactly one arc.

Projectivity

One more property, projectivity, is defined by the linear order of the words, and it governs which algorithms can produce which trees.

Every tree drawn so far is projective. Non-projectivity appears when a dependent is separated from its head by words it does not dominate — common in flexible-word-order languages, and possible in English too. In the sentence below, the relative clause which was already late modifies flight, but this morning intervenes without being dominated by flight, so the arc flight $\to$ was must cross the arc morning $\to$ this.

Projectivity matters for two practical reasons.⁴ First, the English dependency treebanks were converted automatically from phrase-structure treebanks by head-finding rules, and that conversion always yields projective trees — so they never exhibit the phenomenon. Second, and more consequential for us: the transition-based parsers of the next section can produce only projective trees, so any non-projective sentence they meet is guaranteed at least one error. It is to escape that limitation that the graph-based approach exists.

Transition-based parsing

The first parser family borrows shift-reduce parsing from programming-language compilers.⁵ The machine has three parts: a stack on which the parse is assembled, a buffer holding the not-yet-read tokens, and a set of arcs accumulated so far. Together these three make up a configuration. A predictor called the oracle looks at the current configuration and chooses one of three transitions; applying it produces the next configuration. Parsing is a single left-to-right walk through configuration space.

The arc-standard transitions

The arc-standard system defines the three transitions over the top two stack elements. Write $s_1$ for the top of the stack and $s_2$ for the element beneath it.⁶

LEFT-ARC and RIGHT-ARC are the reduce operations — each consumes a stack element by attaching it to its head. Two preconditions keep the output a valid tree: both reduce operations require at least two elements on the stack, and LEFT-ARC may not apply when $s_2$ is $\text{ROOT}$ (since $\text{ROOT}$ can have no incoming arc). Because every word is shifted once and reduced once, the parse takes $2n$ transitions for a length-$n$ sentence — the algorithm is linear in sentence length, its defining strength.

The parser itself is a four-line loop around the oracle.

The initial configuration puts $\text{ROOT}$ on the stack, the whole sentence in the buffer, and no arcs. The final (goal) configuration has an empty buffer and only $\text{ROOT}$ left on the stack; the accumulated arc set is the parse. This is a pure greedy algorithm — the oracle commits to one transition per step, nothing is explored, nothing is undone. A wrong early choice propagates to a wrong parse.

A worked trace

Trace Book the flight through Houston step by step. Read the action column as the transition the oracle chooses in each configuration, and the last column as the arc it produces.

Steps 0-2 just shift; the first reduce comes at step 3, where flight is the head of the determiner the (LEFT-ARC). Notice that book and flight sit adjacent on the stack as early as step 4, yet their arc book $\to$ flight is not asserted until step 8. Arc-standard must wait: attaching flight to book at step 4 would pop flight off the stack, and then flight could never become the head of Houston. Every dependent must collect all its dependents before it is itself reduced. To produce labeled trees, parameterize the reduce operators with a relation — LEFT-ARC(det), RIGHT-ARC(dobj) — expanding the three transitions to two per relation plus SHIFT.

Arc-eager: attaching right dependents early

Arc-standard's collect all your dependents before you are reduced rule forces a peculiar delay: a head cannot attach a right dependent the moment it is seen, because attaching it would immediately pop something the head still needs. The arc-eager system removes that delay by defining its transitions over the top of the stack $s_1$ and the front of the buffer $b_1$, instead of over the top two stack elements.⁷ It has four transitions.

The payoff is that RIGHT-ARC attaches a right dependent as soon as the head and dependent are adjacent, then leaves the dependent on the stack to grow its own subtree — the eager in the name. The cost is the extra REDUCE, whose sole job is to clear a fully-attached word off the stack so its head can move on. Both systems still take a linear number of transitions and still produce only projective trees; they differ only in when an arc is committed, which changes the error profile a greedy oracle exhibits. Arc-standard tends to over-postpone; arc-eager can attach a right dependent to the wrong head early and then be unable to revise it. Trace Book the flight under arc-eager to see the earlier commitment.

At step 2 the determiner the is attached to flight while flight still sits in the buffer (LEFT-ARC fires on $s_1$ = the, $b_1$ = flight). At step 3 flight is attached to book by RIGHT-ARC — immediately, not eight steps later — and shifted so it stays available. Compare this with the arc-standard trace, where the same book $\to$ flight arc waited until step 8. The two REDUCE steps at the end pop the now-complete flight and book so the buffer-empty, stack-[root] goal is reached. (Assume a final implicit root $\to$ book link, which some formulations add as an explicit closing transition.)

Training the oracle

The oracle is a classifier from configuration to transition, trained by supervised learning. But a treebank pairs whole sentences with whole trees, not configurations with transitions — so we manufacture the training pairs. Run the parser over each training sentence with its gold tree in hand, and at each configuration let a training oracle read off the correct transition by consulting the reference parse.⁸

The extra condition on RIGHT-ARC is the formal version of the wait we saw at step 4: never pop a word until all of its own dependents are attached, or they are lost. Simulating the parser this way turns one gold tree into a sequence of (configuration, transition) training pairs.

A feature-based classifier extracts the same kinds of features used for POS tagging: word forms, lemmas, and parts of speech of the top stack elements and the front buffer words, plus the relations already attached to them. Denote a feature by location.property — $s_1.w$ is the word form on top of the stack, $b_1.t$ the part of speech at the front of the buffer, and combinations like $s_1.t\circ s_2.t$ concatenate the tags of the top two stack words. Feature templates instantiate thousands of such features, and any linear classifier (multinomial logistic regression, an SVM) predicts the action from them.

A neural classifier replaces the hand-built features with learned representations.⁹ Run the sentence through an encoder once, then take the contextual embeddings of the top two stack words and the front buffer word, concatenate them, and feed a feedforward network that emits a softmax over the transitions.

Both classifiers train the same way: cross-entropy against the oracle's action at each configuration. The parser's linear-time greedy walk is unchanged; only the oracle's internals differ.

Where this continues

Dependency parsing replaces the constituency tree's phrasal nodes with directed, labeled arcs from heads to dependents, so a verb's arguments sit on the surface. We fixed the formalism — rooted trees, the typed Universal-Dependency relations, and projectivity — and built the first parser family: the transition-based stack-and-buffer machine, its arc-standard and arc-eager action sets, and the oracle that trains it to a linear-time greedy walk.

Greedy transition parsing commits locally. The second family scores whole trees instead — every candidate edge, then a maximum spanning tree — and the modern biaffine neural scorer that powers it, along with attachment-score evaluation, continues in graph-based and neural dependency parsing.