Dependency Parsing

Why Does This Exist?

Parts of speech tell you "cat" is a noun and "chased" is a verb, but they never say who chased whom. "The cat chased a mouse" and "A mouse chased the cat" carry identical tags in a different order, yet mean opposite things. Part-of-speech tagging labels words. Dependency parsing connects them.

The connection is one arrow per word: each word points to its head, the word it modifies, with a label like nsubj (subject) or dobj (object). The main verb heads the whole sentence. That tree answers "who did what to whom" directly, which is why relation extraction and semantic role labeling both consume it. Without it, an extractor guessing from word order breaks on every passive or reordered sentence.

This page covers the tree and the two classic ways to build it. Tagging is the prerequisite: you cannot label relations well if you do not know nouns from verbs, so read the POS page first if tags like DET and NOUN feel new.

Think of It Like This

How It Actually Works

A dependency tree over words $w_1$ through $w_n$ plus an artificial ROOT $w_0$ is a directed graph $G = (V, A)$. Here $V$ is the word set including ROOT, and each arc $(h, d, r)$ runs from head $h$ to dependent $d$ with relation label $r$. A valid tree has three properties: every word except ROOT has exactly one incoming arc, every word is reachable from ROOT, and no cycles exist.

The worked sentence

"The cat chased a mouse" has $n = 5$ words, so a valid tree carries exactly $5$ arcs:

• chased heads the sentence (child of ROOT)
• cat points to chased with nsubj
• mouse points to chased with dobj
• The points to cat with det
• a points to mouse with det

That is the picture above: the focal spine from ROOT to the verb, two long argument arcs, two short article arcs. Five words, five arcs, one head each.

Two builders

Transition parsing reads left to right with a stack and a buffer, predicting Shift, Left-Arc, or Right-Arc at each step. It finishes in $2n$ steps for $n$ words, so our 5-word sentence takes $10$ transitions, which is why it runs in linear time. Graph parsing instead scores every possible arc and extracts the maximum spanning tree with the Chu-Liu-Edmonds algorithm in roughly $O(n^3)$. The first is fast and greedy, the second is slower and globally optimal, and on long sentences the global view wins.

Code

This checks the three tree properties on a head array where heads[i] is the index of the head of word i, with 0 meaning ROOT.

1def is_tree(heads: list[int]) -> tuple[bool, str]:2    n = len(heads) - 13    for d in range(1, n + 1):4        if heads[d] < 0 or heads[d] > n or heads[d] == d:5            return False, f"bad head for {d}"6    kids: dict[int, list[int]] = {i: [] for i in range(n + 1)}7    for d in range(1, n + 1):8        kids[heads[d]].append(d)9    seen = {0}10    stack = [0]11    while stack:12        node = stack.pop()13        for c in kids[node]:14            if c not in seen:15                seen.add(c)16                stack.append(c)17    ok = len(seen) == n + 118    return ok, "5 words, 5 arcs, one ROOT child" if ok else "not connected"19print(is_tree([0, 2, 3, 0, 5, 3]))  # -> (True, '5 words, 5 arcs, one ROOT child')

Watch Out For

The Quick Version

• Dependency parsing points every word at its head with a labeled relation, forming a tree headed by the main verb.
• The tree for "The cat chased a mouse" has 5 arcs: nsubj, dobj, two det labels, and the ROOT link to chased.
• Transition parsers build the tree in 2n greedy steps, so 5 words take 10 transitions; graph parsers score all arcs and decode the best tree globally.
• Subjects, objects and modifiers become explicit, which is what extraction and role labeling consume.
• Each word takes exactly one head, so shared modifiers and crossing arcs need deliberate handling.

What to Read Next

• Part-of-Speech Tagging
• Semantic Role Labeling
• Relation Extraction