---
title: Dependency Parsing
module: Linguistic Structure
moduleNumber: 6
lessonNumber: 3
order: 603
summary: >
  A dependency parse throws away phrases and keeps only directed, labeled arcs
  from heads to their dependents, so the subject and object of a verb hang off the
  verb directly. We fix the formalism (rooted trees, typed Universal-Dependency
  relations, projectivity), then build the first parser family: transition-based
  arc-standard and arc-eager parsing, a greedy stack-and-buffer machine trained
  from an oracle. Graph-based and neural dependency parsing follow in the companion
  lesson.
topics: [Structure]
sources:
  - book: Jurafsky
    ref: "Ch. 14 — Dependency Parsing; §14.1 Dependency Relations; §14.2 Dependency Formalisms"
  - book: Jurafsky
    ref: "§14.4 Transition-Based Dependency Parsing"
---

A [constituency parse](/natural-language-processing/linguistic-structure/constituency-parsing)
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**.[^jm-intro] 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.

$$
% caption: A typed dependency parse of "I prefer the morning flight through
% Denver": every arc runs from a head to a dependent and carries a grammatical
% relation, with a single root arc into the main verb.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  w/.style={font=\small, inner sep=1.5pt},
  a/.style={->, thick, shorten <=2pt, shorten >=2pt},
  rel/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  \node[w] (I)     at (0,0)    {I};
  \node[w] (prefer) at (1.7,0) {prefer};
  \node[w] (the)   at (3.9,0)  {the};
  \node[w] (mor)   at (5.3,0)  {morning};
  \node[w] (fl)    at (7.4,0)  {f\/light};
  \node[w] (thr)   at (9.2,0)  {through};
  \node[w] (den)   at (11.2,0) {Denver};
  % root: short arrow stopping well above the word
  \draw[a, acc] (1.7,2.0) -- (1.7,0.45);
  \node[rel, text=acc] at (1.7,2.2) {root};
  % arcs above, labels centered high above each arc
  \draw[a] (prefer.north) to[bend left=45] (I.north);
  \node[rel] at (0.85,1.0) {nsubj};
  \draw[a] (prefer.north) to[bend left=32] (fl.north);
  \node[rel] at (4.55,1.75) {dobj};
  \draw[a] (fl.north) to[bend left=55] (the.north);
  \node[rel] at (5.35,0.75) {det};
  \draw[a] (fl.north) to[bend left=52] (mor.north);
  \node[rel] at (6.55,1.15) {nmod};
  \draw[a] (fl.north) to[bend left=32] (den.north);
  \node[rel] at (9.3,1.35) {nmod};
  \draw[a] (den.north) to[bend left=50] (thr.north);
  \node[rel] at (10.2,0.85) {case};
\end{tikzpicture}
$$

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](/natural-language-processing/linguistic-structure/semantic-roles-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.[^jm-intro] 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.[^jm-relations] 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.

| Group | Relation | Meaning | Example (head $\to$ dependent) |
| --- | --- | --- | --- |
| Clausal | `nsubj` | nominal subject | _United_ canceled $\to$ _United_ |
| Clausal | `dobj` | direct object | canceled the _flight_ $\to$ _flight_ |
| Clausal | `iobj` | indirect object | booked _her_ the flight $\to$ _her_ |
| Clausal | `ccomp` | clausal complement | said _that it left_ |
| Modifier | `nmod` | nominal modifier | the _morning_ flight $\to$ _morning_ |
| Modifier | `amod` | adjectival modifier | the _cheapest_ flight $\to$ _cheapest_ |
| Modifier | `det` | determiner | _the_ flight $\to$ _the_ |
| Modifier | `case` | preposition / case marker | flight _through_ Houston $\to$ _through_ |

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.

$$
% caption: The same relation set applied to "United canceled the morning flights
% to Houston": clausal arcs (nsubj, dobj) attach arguments to the verb; modifier
% arcs (nmod, det, case) attach modifiers to their nouns.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  w/.style={font=\small, inner sep=1.5pt},
  a/.style={->, thick, shorten <=2pt, shorten >=2pt},
  rel/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  \node[w] (U)   at (0,0)   {United};
  \node[w] (can) at (2.0,0) {canceled};
  \node[w] (the) at (4.3,0) {the};
  \node[w] (mor) at (5.7,0) {morning};
  \node[w] (fl)  at (7.8,0) {f\/lights};
  \node[w] (to)  at (9.5,0) {to};
  \node[w] (hou) at (10.9,0) {Houston};
  \draw[a, acc] (2.0,2.0) -- (2.0,0.45);
  \node[rel, text=acc] at (2.0,2.2) {root};
  \draw[a] (can.north) to[bend left=45] (U.north);
  \node[rel] at (1.0,1.0) {nsubj};
  \draw[a] (can.north) to[bend left=32] (fl.north);
  \node[rel] at (5.0,1.75) {dobj};
  \draw[a] (fl.north) to[bend left=55] (the.north);
  \node[rel] at (5.65,0.75) {det};
  \draw[a] (fl.north) to[bend left=52] (mor.north);
  \node[rel] at (6.95,1.15) {nmod};
  \draw[a] (fl.north) to[bend left=32] (hou.north);
  \node[rel] at (9.6,1.35) {nmod};
  \draw[a] (hou.north) to[bend left=50] (to.north);
  \node[rel] at (10.0,0.85) {case};
\end{tikzpicture}
$$

## 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**.[^jm-formal]

> **Definition (Dependency tree).** A directed graph over the words of a sentence
> (plus $\text{ROOT}$) satisfying three constraints: (1) a single $\text{ROOT}$
> node with no incoming arc; (2) every other vertex has _exactly one_ incoming arc,
> i.e. exactly one head; (3) there is a unique directed path from $\text{ROOT}$ to
> each vertex. Together these force each word to have a single head and the whole
> structure to be connected and acyclic.

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.

> **Definition (Projective arc).** An arc from head $h$ to dependent $d$ is
> projective if there is a path from $h$ to every word lying _between_ $h$ and $d$
> in the sentence. A tree is **projective** if all of its arcs are projective —
> equivalently, if it can be drawn above the sentence with no two arcs crossing.

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`.

$$
% caption: A non-projective parse of "JetBlue canceled our flight this morning
% which was already late": the arc from flight to its relative-clause head was
% (drawn in red) crosses the morning arc, so no crossing-free drawing exists.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  w/.style={font=\small, inner sep=1.5pt},
  a/.style={->, thick, shorten <=2pt, shorten >=2pt},
  rel/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[w] (jb)  at (0,0)     {JetBlue};
  \node[w] (can) at (2.0,0)   {canceled};
  \node[w] (our) at (4.0,0)   {our};
  \node[w] (fl)  at (5.3,0)   {f\/light};
  \node[w] (this) at (6.9,0)  {this};
  \node[w] (mor) at (8.3,0)   {morning};
  \node[w] (wh)  at (10.2,0)  {which};
  \node[w] (was) at (11.8,0)  {was};
  \node[w] (late) at (13.2,0) {late};
  \draw[a, acc] (2.0,2.6) -- (2.0,0.45);
  \node[rel, text=acc] at (2.0,2.8) {root};
  \draw[a] (can.north) to[bend left=45] (jb.north);
  \node[rel] at (1.0,1.0) {nsubj};
  \draw[a] (can.north) to[bend left=28] (fl.north);
  \node[rel] at (3.6,1.35) {dobj};
  \draw[a] (fl.north) to[bend left=52] (our.north);
  \node[rel] at (4.65,0.75) {det};
  \draw[a] (can.north) to[bend left=40] (mor.north);
  \node[rel] at (5.15,2.05) {nmod};
  \draw[a] (mor.north) to[bend left=52] (this.north);
  \node[rel] at (7.6,0.8) {det};
  % the crossing (non-projective) arc, drawn in red
  \draw[a, red] (fl.north) to[bend left=30] (was.north);
  \node[rel, text=red] at (8.9,1.75) {mod};
  \draw[a] (was.north) to[bend left=52] (wh.north);
  \node[rel] at (11.0,0.85) {nsubj};
  \draw[a] (was.north) to[bend left=48] (late.north);
  \node[rel] at (12.5,0.9) {adv};
\end{tikzpicture}
$$

Projectivity matters for two practical reasons.[^jm-proj] 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.[^jm-trans] 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.

$$
% caption: The transition-based architecture: an oracle inspects the top of the
% stack and the front of the buffer, picks one of SHIFT / LEFT-ARC / RIGHT-ARC,
% and the chosen action updates the stack, buffer, and set of arcs.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=27mm, minimum height=13mm, align=center},
  small/.style={font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (stack) at (0,0) {Stack\\[2pt]\texttt{[root, w2, w1]}};
  \node[box] (buf)   at (0,-2.1) {Bu\/f\/f\/er\\[2pt]\texttt{[w3, ...]}};
  \node[box, draw=acc, text=acc, thick] (par) at (4.6,-1.05) {Oracle};
  \node[box] (arcs)  at (9.4,-1.05) {Arcs\\[2pt](dependency\\relations)};
  \draw[->, thick] (stack.east) -- (par.north west);
  \draw[->, thick] (buf.east) -- (par.south west);
  \draw[->, acc, thick] (par.east) -- node[small, above]{action} (arcs.west);
  \node[small, align=center] at (4.6,-3.2) {picks one of\\ \texttt{SHIFT},\ \ \texttt{LEFT-ARC},\ \ \texttt{RIGHT-ARC}};
\end{tikzpicture}
$$

### 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.[^jm-arcstd]

> **Definition (Arc-standard transitions).**
> **`LEFT-ARC`** asserts a head-dependent relation $s_1 \to s_2$ (the top word is
> the head of the one beneath it) and removes $s_2$ from the stack.
> **`RIGHT-ARC`** asserts $s_2 \to s_1$ (the second word is the head of the top)
> and removes $s_1$ from the stack.
> **`SHIFT`** moves the front word of the buffer onto the stack.

`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.

```algorithm
caption: $\textsc{Dependency-Parse}(words)$ — greedy transition-based parsing
$state \gets \{[\text{root}],\ words,\ \{\}\}$ // stack, buffer, arcs
while $state$ is not final do
  $t \gets \textsc{Oracle}(state)$ // pick a transition
  $state \gets \textsc{Apply}(t, state)$ // stack/buffer/arcs update
return $state$
```

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.

$$
% caption: A full arc-standard trace of "Book the flight through Houston". Each row
% is a configuration; SHIFT loads the stack until a reduce is possible, then
% LEFT-ARC / RIGHT-ARC attach words to their heads bottom-up until only root
% remains.
\begin{tikzpicture}[>=stealth, font=\scriptsize]
  \definecolor{acc}{HTML}{2348F2}
  \def\rh{0.52}
  % header
  \node[anchor=west, font=\scriptsize\bfseries] at (0,0)     {Step};
  \node[anchor=west, font=\scriptsize\bfseries] at (1.0,0)   {Stack};
  \node[anchor=west, font=\scriptsize\bfseries] at (7.4,0)   {Bu\/f\/f\/er};
  \node[anchor=west, font=\scriptsize\bfseries] at (13.4,0)  {Action};
  \node[anchor=west, font=\scriptsize\bfseries] at (15.8,0)  {Arc added};
  \draw[black] (-0.1,-0.25) -- (19.6,-0.25);
  \foreach \i/\stk/\buf/\act/\arc in {
    0/{[root]}/{[book, the, f\/light, through, houston]}/{SHIFT}/{},
    1/{[root, book]}/{[the, f\/light, through, houston]}/{SHIFT}/{},
    2/{[root, book, the]}/{[f\/light, through, houston]}/{SHIFT}/{},
    3/{[root, book, the, f\/light]}/{[through, houston]}/{LEFT-ARC}/{the $\gets$ f\/light},
    4/{[root, book, f\/light]}/{[through, houston]}/{SHIFT}/{},
    5/{[root, book, f\/light, through]}/{[houston]}/{SHIFT}/{},
    6/{[root, book, f\/light, through, houston]}/{[ ]}/{LEFT-ARC}/{through $\gets$ houston},
    7/{[root, book, f\/light, houston]}/{[ ]}/{RIGHT-ARC}/{f\/light $\to$ houston},
    8/{[root, book, f\/light]}/{[ ]}/{RIGHT-ARC}/{book $\to$ f\/light},
    9/{[root, book]}/{[ ]}/{RIGHT-ARC}/{root $\to$ book},
    10/{[root]}/{[ ]}/{Done}/{}
  }{
    \node[anchor=west] at (0,{-0.55-\i*\rh})    {\i};
    \node[anchor=west, font=\footnotesize\ttfamily] at (1.0,{-0.55-\i*\rh})  {\stk};
    \node[anchor=west, font=\footnotesize\ttfamily] at (7.4,{-0.55-\i*\rh})  {\buf};
    \node[anchor=west, font=\footnotesize\ttfamily] at (13.4,{-0.55-\i*\rh}) {\act};
    \node[anchor=west, font=\footnotesize\ttfamily] at (15.8,{-0.55-\i*\rh}) {\arc};
  }
\end{tikzpicture}
$$

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.[^jm-arceager] It has four transitions.

> **Definition (Arc-eager transitions).**
> **`LEFT-ARC`** asserts $b_1 \to s_1$ (the buffer front is the head of the stack
> top) and pops $s_1$; it requires $s_1$ to have no head yet and not be $\text{ROOT}$.
> **`RIGHT-ARC`** asserts $s_1 \to b_1$ (the stack top is the head of the buffer
> front) and _shifts_ $b_1$ onto the stack — the dependent is attached but kept,
> so it can collect its own dependents later.
> **`REDUCE`** pops $s_1$, but only once $s_1$ already has a head.
> **`SHIFT`** moves $b_1$ onto the stack.

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.

$$
% caption: An arc-eager trace of "Book the flight". RIGHT-ARC at step 4 attaches
% flight to book immediately (unlike arc-standard, which waits), keeping flight on
% the stack; the later REDUCE clears attached words so the parse can finish.
\begin{tikzpicture}[>=stealth, font=\scriptsize]
  \definecolor{acc}{HTML}{2348F2}
  \def\rh{0.52}
  \node[anchor=west, font=\scriptsize\bfseries] at (0,0)     {Step};
  \node[anchor=west, font=\scriptsize\bfseries] at (1.0,0)   {Stack};
  \node[anchor=west, font=\scriptsize\bfseries] at (6.2,0)   {Bu\/f\/f\/er};
  \node[anchor=west, font=\scriptsize\bfseries] at (10.4,0)  {Action};
  \node[anchor=west, font=\scriptsize\bfseries] at (13.0,0)  {Arc added};
  \draw[black] (-0.1,-0.25) -- (17.0,-0.25);
  \foreach \i/\stk/\buf/\act/\arc in {
    0/{[root]}/{[book, the, f\/light]}/{SHIFT}/{},
    1/{[root, book]}/{[the, f\/light]}/{SHIFT}/{},
    2/{[root, book, the]}/{[f\/light]}/{LEFT-ARC}/{the $\gets$ f\/light},
    3/{[root, book]}/{[f\/light]}/{RIGHT-ARC}/{book $\to$ f\/light},
    4/{[root, book, f\/light]}/{[ ]}/{REDUCE}/{},
    5/{[root, book]}/{[ ]}/{REDUCE}/{},
    6/{[root]}/{[ ]}/{Done}/{root $\to$ book}
  }{
    \node[anchor=west] at (0,{-0.55-\i*\rh})    {\i};
    \node[anchor=west, font=\footnotesize\ttfamily] at (1.0,{-0.55-\i*\rh})  {\stk};
    \node[anchor=west, font=\footnotesize\ttfamily] at (6.2,{-0.55-\i*\rh})  {\buf};
    \node[anchor=west, font=\footnotesize\ttfamily] at (10.4,{-0.55-\i*\rh}) {\act};
    \node[anchor=west, font=\footnotesize\ttfamily] at (13.0,{-0.55-\i*\rh}) {\arc};
  }
\end{tikzpicture}
$$

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.[^jm-oracle]

> **Definition (Training oracle).** Given the current configuration and the
> reference (gold) parse with relation set $R_p$, choose:
> **`LEFT-ARC(r)`** if $(s_1\, r\, s_2) \in R_p$;
> otherwise **`RIGHT-ARC(r)`** if $(s_2\, r\, s_1) \in R_p$ _and_ every dependent
> of $s_1$ has already been attached;
> otherwise **`SHIFT`**.

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.

$$
% caption: Turning a gold tree into oracle training data: simulate the parse with
% the reference parse in hand, and each configuration paired with the transition
% the training oracle dictates becomes one supervised (features, action) example.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=26mm, minimum height=12mm, align=center},
  small/.style={font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (tree) at (0,0) {gold tree\\(from treebank)};
  \node[box] (sim)  at (4.0,0) {simulate\\the parser};
  \node[box, draw=acc, text=acc, thick] (pairs) at (9.0,0) {(conf\/ig, action)\\training pairs};
  \node[box] (clf)  at (13.2,0) {trained\\classif\/ier};
  \draw[->, thick] (tree) -- (sim);
  \draw[->, acc, thick] (sim) -- node[small, above]{training oracle} (pairs);
  \draw[->, thick] (pairs) -- (clf);
\end{tikzpicture}
$$

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.[^jm-neural] 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.

$$
% caption: The neural oracle. An encoder embeds every word once; the head of the
% classifier reads the embeddings of the top two stack words s1, s2 and the front
% buffer word b1, concatenates them, and a feedforward network with a softmax
% predicts the next transition.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  tok/.style={draw, minimum width=9mm, minimum height=6mm, font=\scriptsize},
  box/.style={draw, minimum width=20mm, minimum height=8mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  % encoder row
  \foreach \i/\x in {1/0, 2/1.2, 3/2.4, 4/3.6, 5/4.8}
    \node[tok] (t\i) at (\x,0) {w\i};
  \node[box, minimum width=58mm] (enc) at (2.4,1.2) {ENCODER};
  \foreach \i in {1,...,5} \draw[->] (t\i.north) -- (enc.south -| t\i.north);
  % pick three embeddings
  \node[box, draw=acc, text=acc] (sel) at (2.4,2.7) {concat  e(s2), e(s1), e(b1)};
  \draw[->, acc, thick] (enc.north) -- (sel.south);
  \node[box] (ffn) at (2.4,4.0) {FFN + softmax};
  \draw[->, thick] (sel.north) -- (ffn.south);
  \node[font=\footnotesize\ttfamily, anchor=west, align=left] at (5.1,4.0) {SHIFT / LEFT-ARC\\/ RIGHT-ARC};
  \draw[->, acc, thick] (ffn.east) -- (5.0,4.0);
\end{tikzpicture}
$$

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](/natural-language-processing/linguistic-structure/graph-based-and-neural-dependency-parsing).

[^jm-intro]: **Jurafsky & Martin**, _Speech and Language Processing_ (3rd ed.), Ch. 14 — Dependency Parsing: dependency grammar describes syntax with directed binary grammatical relations from heads to dependents, with no phrasal constituents, and its abstraction from word order suits free-word-order and morphologically rich languages.
[^jm-relations]: **Jurafsky & Martin**, §14.1 — Dependency Relations: grammatical relations as head-dependent pairs typed by grammatical function, and the Universal Dependencies inventory split into clausal-argument and nominal-modifier relations.
[^jm-formal]: **Jurafsky & Martin**, §14.2 — Dependency Formalisms: a dependency structure as a directed graph $G=(V,A)$, and the rooted-tree restriction (single root, single head per word, unique root-to-vertex path).
[^jm-proj]: **Jurafsky & Martin**, §14.2.1 — Projectivity: an arc is projective if the head reaches every word between it and its dependent; projective trees have no crossing arcs; treebanks converted from phrase structure are projective, and transition-based parsers produce only projective trees.
[^jm-trans]: **Jurafsky & Martin**, §14.4 — Transition-Based Dependency Parsing: the shift-reduce architecture with a stack, buffer, and oracle, configurations as parser state, and parsing as a greedy linear-time walk through configuration space.
[^jm-arcstd]: **Jurafsky & Martin**, §14.4 — the arc-standard transition system: the LEFT-ARC, RIGHT-ARC, and SHIFT operators over the top two stack elements, their preconditions, and labeled parsing by parameterizing the arc operators with relations.
[^jm-arceager]: **Jurafsky & Martin**, §14.4 — the arc-eager transition system as an alternative to arc-standard: transitions defined over the stack top and buffer front, with LEFT-ARC / RIGHT-ARC / REDUCE / SHIFT, so a head may attach a right dependent as soon as they are adjacent rather than waiting.
[^jm-oracle]: **Jurafsky & Martin**, §14.4.1 — Creating an Oracle: generating configuration-transition training pairs by simulating the parser against a reference parse, with the training oracle's LEFT-ARC / RIGHT-ARC / SHIFT rule and the precondition that all of a word's dependents be attached before it is reduced.
[^jm-neural]: **Jurafsky & Martin**, §14.4.2–§14.4.3 — feature-based and neural classifiers for the oracle: hand-designed location.property feature templates versus an encoder plus a feedforward network over the top two stack words and the front buffer word, trained with cross-entropy.