Introduction

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 nn-word sentence in exactly 2n−12n - 1 steps — linear time.

Build the Tree

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.

<!-- Demo: arc-eager dependency parser for 'The dog chased the cat' -->
<div class="sentence-row" id="sentenceRow" aria-label="Sentence words"></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">Stack</div>
    <div class="state-val" id="stackVal"></div>
  </div>
  <div class="state-box">
    <div class="state-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">Shift</button>
  <button id="btnArcL" type="button">Arc-Left</button>
  <button id="btnArcR" type="button">Arc-Right</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
</div>
<div class="hint-para" id="hintPara">Click <b>Shift</b> to push the next word onto the stack, <b>Arc-Left</b> to make the buffer word the head of the stack-top, or <b>Arc-Right</b> to make the stack-top the head of the buffer word.</div>

/* Styles for the dependency parsing demo */
* { 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; }

// Arc-eager transition system (Nivre 2003) for 'The dog chased the cat'
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// Sentence words; index 0 is a virtual ROOT node
const WORDS = ['ROOT', 'The', 'dog', 'chased', 'the', 'cat'];
// Gold standard arcs (head index, dependent index, label)
// ROOT->chased(root), chased->dog(nsubj), chased->cat(dobj), dog->The(det), cat->the(det)
const GOLD = [
  { head: 0, dep: 3, label: 'root' },
  { head: 3, dep: 2, label: 'nsubj' },
  { head: 3, dep: 5, label: 'dobj' },
  { head: 2, dep: 1, label: 'det' },
  { head: 5, dep: 4, label: 'det' }
];

// Parser state: stack holds processed indices, buf holds remaining
let stack = [], buf = [], arcs = [], done = false;

function reset() {
  // Initialize parser: ROOT on stack, all real words in buffer
  stack = [0];
  buf = [1, 2, 3, 4, 5];
  arcs = [];
  done = false;
  setHint('Click <b>Shift</b> to push the next word onto the stack, <b>Arc-Left</b> to make the buffer word the head of the stack-top, or <b>Arc-Right</b> to make the stack-top the head of the buffer word.');
  setStatus('', '');
  render();
}

// Helper predicates for arc existence
function arcExists(h, d) { return arcs.some(a => a.head === h && a.dep === d); }
function hasHead(d) { return arcs.some(a => a.dep === d); }

function doShift() {
  if (buf.length === 0) return;
  stack.push(buf.shift());
  setHint('Shifted. The word is now on top of the stack.');
  setStatus('', '');
  render();
  checkDone();
}

function doArcLeft() {
  // Arc-Left: buffer[0] becomes head of stack-top; pop stack-top
  if (stack.length < 2 || buf.length === 0) return;
  const s = stack[stack.length - 1];
  const b = buf[0];
  arcs.push({ head: b, dep: s, label: guessLabel(b, s) });
  stack.pop();
  setHint('Arc-Left attached. The buffer word is now the head; the stack word was popped.');
  setStatus('', '');
  render();
  checkDone();
}

function doArcRight() {
  // Arc-Right: stack-top becomes head of buffer[0]; push buffer[0]
  if (stack.length === 0 || buf.length === 0) return;
  const s = stack[stack.length - 1];
  const b = buf[0];
  arcs.push({ head: s, dep: b, label: guessLabel(s, b) });
  buf.shift();
  stack.push(s === stack[stack.length - 1] ? b : b);
  // Push the new dependent onto the stack (arc-eager convention)
  stack[stack.length - 1] = b;
  setHint('Arc-Right attached. The stack word is now the head of the buffer word.');
  setStatus('', '');
  render();
  checkDone();
}

// Return the gold label for a (head,dep) pair, or '?' if not in gold
function guessLabel(h, d) {
  const match = GOLD.find(a => a.head === h && a.dep === d);
  return match ? match.label : '?';
}

function checkDone() {
  if (buf.length === 0 && stack.length === 1) {
    done = true;
    const correct = GOLD.every(g => arcs.some(a => a.head === g.head && a.dep === g.dep));
    if (correct) {
      setStatus('✓ Correct dependency tree!', 'ok');
      setHint('Perfect parse! All gold arcs are present.');
    } else {
      setStatus('✗ Tree has errors. Try resetting and using a different action sequence.', 'bad');
      setHint('Parse finished but some arcs are wrong. Press Reset to try again.');
    }
    updateButtons();
  }
}

function setStatus(t, cls) {
  const el = document.getElementById('status');
  el.textContent = t; el.className = 'status ' + cls;
}
function setHint(t) { document.getElementById('hintPara').innerHTML = t; }

// Re-render words, arcs, and state display
function render() {
  renderWords();
  renderArcs();
  renderState();
  updateButtons();
}

function renderWords() {
  const row = document.getElementById('sentenceRow');
  row.innerHTML = '';
  WORDS.forEach((w, i) => {
    if (i === 0) return; // Don't render the virtual ROOT chip
    const chip = document.createElement('span');
    chip.className = 'word-chip';
    chip.dataset.idx = i;
    chip.textContent = w;
    if (stack.includes(i)) chip.classList.add('on-stack');
    else if (arcs.some(a => a.dep === i)) chip.classList.add('attached');
    row.appendChild(chip);
  });
}

// Draw dependency arcs as bezier curves above the sentence
function renderArcs() {
  const canvas = document.getElementById('arcCanvas');
  const wrap = canvas.parentElement;
  const chips = [...document.querySelectorAll('.word-chip')];
  if (chips.length === 0) { canvas.width = 0; canvas.height = 0; return; }

  const H = 54;
  canvas.width = wrap.clientWidth || 400;
  canvas.height = H;
  const ctx = canvas.getContext('2d');
  ctx.clearRect(0, 0, canvas.width, canvas.height);

  // Compute horizontal center of each word chip in canvas coordinates
  const pos = {};
  chips.forEach(ch => {
    const idx = parseInt(ch.dataset.idx);
    const r = ch.getBoundingClientRect();
    const wr = wrap.getBoundingClientRect();
    pos[idx] = r.left - wr.left + r.width / 2;
  });

  arcs.forEach(({ head, dep }) => {
    const hIdx = head === 0 ? null : head;
    if (hIdx === null) return;
    const x1 = pos[hIdx], x2 = pos[dep];
    if (x1 === undefined || x2 === undefined) return;
    const mid = (x1 + x2) / 2;
    const span = Math.abs(x2 - x1);
    const cy = H - span * 0.28 - 4;
    ctx.beginPath();
    ctx.moveTo(x1, H);
    ctx.bezierCurveTo(x1, cy, x2, cy, x2, H);
    ctx.strokeStyle = '#1d7a5f';
    ctx.lineWidth = 1.6;
    ctx.stroke();
    // Draw arrowhead pointing toward the dependent
    const angle = x2 > x1 ? Math.PI / 2 : -Math.PI / 2;
    const ax = x2, ay = H - 1;
    ctx.beginPath();
    ctx.moveTo(ax, ay);
    ctx.lineTo(ax - 5 * Math.cos(angle - 0.4), ay - 5 * Math.sin(angle - 0.4));
    ctx.moveTo(ax, ay);
    ctx.lineTo(ax - 5 * Math.cos(angle + 0.4), ay - 5 * Math.sin(angle + 0.4));
    ctx.stroke();
  });
}

function renderState() {
  document.getElementById('stackVal').textContent =
    stack.map(i => WORDS[i]).join(' | ') || '—';
  document.getElementById('bufferVal').textContent =
    buf.map(i => WORDS[i]).join(' ') || '—';
}

function updateButtons() {
  const canShift = !done && buf.length > 0;
  const canArcL = !done && stack.length >= 2 && buf.length > 0;
  const canArcR = !done && stack.length >= 1 && buf.length > 0;
  document.getElementById('btnShift').disabled = !canShift;
  document.getElementById('btnArcL').disabled = !canArcL;
  document.getElementById('btnArcR').disabled = !canArcR;
}

document.getElementById('btnShift').addEventListener('click', doShift);
document.getElementById('btnArcL').addEventListener('click', doArcLeft);
document.getElementById('btnArcR').addEventListener('click', doArcRight);
document.getElementById('btnReset').addEventListener('click', reset);
reset();
Result
Console

Notice that each step commits immediately — no backtracking. That is what makes the algorithm linear. A correct sequence of 2n−12n - 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 Real Complexity

The transition system itself is deceptively cheap:

  • O(n)O(n) steps. An nn-word sentence requires exactly 2n−12n - 1 transitions (each word is shifted once and attached once). The stack never grows beyond nn entries.
  • O(n2)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(n2)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)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(n2)O(n^2) Eisner algorithm or the O(n3)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.

Where It Matters

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.

Conclusion

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−12n - 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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/dependency-parsing-arc/Content licensed under CC BY-NC 4.0.