Dependency Parsing

Every sentence you speak is secretly a tree. The verb is usually the root; every other word depends on exactly one head. In "The dog chased the cat," chased is the root, dog and cat are its dependents, and each the depends on its noun. Dependency parsing is the problem of finding that tree automatically.

Why does this matter? Knowing who did what to whom — the dependency structure — is the first step for question answering, machine translation, information extraction, and virtually every task in natural language processing. Without it, a computer sees "dog bites man" and "man bites dog" as nearly identical bags of words.

The classic solution is a transition system: a tiny state machine that scans the sentence left to right and fires one of three actions at each step — Shift a word onto a stack, attach an Arc-Left (the top of the stack depends on the next word), or attach an Arc-Right (the next word depends on the top of the stack). Joakim Nivre formalized this arc-eager algorithm in 2003, and it parses an $n$-word sentence in exactly $2n - 1$ steps — linear time.

The sentence "The dog chased the cat" is loaded below. Use the three buttons to run the arc-eager transition system step by step. The stack grows on the left; the input buffer shrinks from the right; arcs appear above the words as you attach them.

<!-- {{c_html_intro}} -->
<div class="sentence-row" id="sentenceRow" aria-label="{{aria_sentence}}"></div>
<div class="arc-canvas-wrap">
  <canvas id="arcCanvas" aria-hidden="true"></canvas>
</div>
<div class="state-row">
  <div class="state-box">
    <div class="state-label">{{label_stack}}</div>
    <div class="state-val" id="stackVal"></div>
  </div>
  <div class="state-box">
    <div class="state-label">{{label_buffer}}</div>
    <div class="state-val" id="bufferVal"></div>
  </div>
</div>
<div class="status" id="status"></div>
<div class="btns">
  <button id="btnShift" type="button">{{btn_shift}}</button>
  <button id="btnArcL" type="button">{{btn_arc_left}}</button>
  <button id="btnArcR" type="button">{{btn_arc_right}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="hint-para" id="hintPara">{{hint_initial}}</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px; }
.sentence-row { display: flex; gap: 6px; flex-wrap: wrap; margin-bottom: 4px; min-height: 36px; }
.word-chip { padding: 4px 10px; border-radius: 20px; font-size: .9rem; font-weight: 600;
             background: #e8eef3; border: 1.5px solid #cdd9e3; color: #1d3557; white-space: nowrap; }
.word-chip.on-stack { background: #1d3557; color: #fff; border-color: #1d3557; }
.word-chip.attached { background: #d0f0d8; border-color: #6cbb88; color: #145227; }
.arc-canvas-wrap { width: 100%; overflow: hidden; margin-bottom: 4px; }
canvas { display: block; width: 100%; }
.state-row { display: flex; gap: 10px; margin: 6px 0; }
.state-box { flex: 1; background: #f4f6f8; border-radius: 8px; padding: 6px 10px; min-height: 36px; }
.state-label { font-size: .72rem; font-weight: 700; color: #5a7088; text-transform: uppercase;
               letter-spacing: .04em; margin-bottom: 2px; }
.state-val { font-size: .85rem; color: #1d3557; font-family: ui-monospace, monospace; word-break: break-all; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin: 4px 0; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: 6px; flex-wrap: wrap; margin-bottom: 8px; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem; border: 1.5px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .38; cursor: not-allowed; }
.hint-para { font-size: .82rem; color: #555; line-height: 1.45; }

// Code not found

Notice that each step commits immediately — no backtracking. That is what makes the algorithm linear. A correct sequence of $2n - 1$ actions produces the full dependency tree. Wrong actions accumulate and the tree breaks; press Reset to start over and try a different strategy.

The transition system itself is deceptively cheap:

• $O(n)$ steps. An $n$-word sentence requires exactly $2n - 1$ transitions (each word is shifted once and attached once). The stack never grows beyond $n$ entries.
• $O(n^2)$ feature space (classical). A greedy classifier picks the action at each step using features of the current configuration — top of stack, next word in buffer, their part-of-speech tags, and the arcs already built. With hand-crafted features, this blows up combinatorially.
• Neural parsers collapse the feature cost. Chen & Manning (2014) replaced the feature templates with a small feed-forward network over dense word embeddings, cutting $O(n^2)$ feature extraction to a cheap matrix multiply. Modern transformer-based parsers (like those built on BERT) push accuracy above 95 % on standard benchmarks — but the $O(n)$ transition count stays the same.
• Projective vs. non-projective. The arc-eager system produces only projective trees — arcs cannot cross. Most English sentences are projective, but languages with freer word order (Czech, Dutch, German) need more powerful algorithms, such as the $O(n^2)$ Eisner algorithm or the $O(n^3)$ CYK-style chart parser for dependency grammars.

Choosing the right transition at each step is, technically, a search problem. Greedy parsers are fast but make errors they cannot undo. Beam search keeps several hypotheses alive simultaneously, trading speed for accuracy — a classic pattern-matching vs. efficiency tradeoff.

Once you can turn a sentence into a tree, a remarkable number of downstream tasks become straightforward:

• Question answering: "Who founded Microsoft?" is almost trivially answered once you know founded is the root and Microsoft is its object.
• Machine translation: word order differs across languages, but dependency structure is often shared — a parser on the source side helps the model restructure the output correctly.
• Information extraction: extracting "company acquired company for price" from news requires knowing which noun is the subject, which is the object, and which is an instrument.
• Search and semantic search: query understanding — "hotels near the Eiffel Tower open on Sundays" — leans heavily on parsing to separate the location constraint from the time constraint.
• Clinical NLP: mining patient records for "patient has no history of diabetes" vs. "patient has history of diabetes" requires the negation arc, not just the keyword.

The field traces its roots to Lucien Tesnière's 1959 Éléments de syntaxe structurale. Today every major NLP library (spaCy, Stanford CoreNLP, Stanza) ships a pretrained dependency parser that runs in milliseconds per sentence.

Dependency parsing is a quiet triumph of algorithm design: a three-action state machine — Shift, Arc-Left, Arc-Right — is all it takes to turn any sentence into a tree, and it does so in exactly $2n - 1$ steps.

The clever part was never the transitions themselves. It was realizing that the hard question — which action to fire next? — could be handed off to a learned classifier, first hand-crafted features, then neural networks, now transformers. The algorithm stayed linear; the intelligence moved into the model.

Next time an autocomplete rewrites your sentence, or a chatbot correctly understands "book a table for two near the museum that closes at nine," dependency parsing is almost certainly somewhere in the pipeline, silently turning your words into a tree.