Dependency parsing represents the syntactic structure of a sentence as a set of directed binary relations between words. Each relation, called a dependency, connects a head (governor) word to a dependent (modifier) word and is labeled with a grammatical relation such as nsubj (nominal subject), obj (direct object), or amod (adjectival modifier). The resulting structure is a dependency tree: a rooted, directed tree in which every word except the root has exactly one head, and there are no cycles.
Dependency Trees
V = {0, 1, ..., n} (0 = artificial root node)
A ⊆ V × V (set of arcs/dependencies)
Constraints:
1. Single head: each wi (i ≥ 1) has exactly one head
2. Acyclicity: no directed cycles
3. Connectedness: every word is reachable from root
Together ⇒ A forms a directed tree rooted at node 0
Dependency representations have several advantages over constituency representations. They directly encode predicate-argument structure and head-modifier relations, making them closer to the semantic interpretation. They are more suitable for languages with free word order (such as Czech, Turkish, or Hindi), where constituency trees require many discontinuous or crossing branches. They also produce more compact representations — every tree has exactly n arcs for a sentence of n words.
Approaches to Dependency Parsing
The two dominant algorithmic paradigms are transition-based parsing, which constructs the tree incrementally through a sequence of shift-reduce actions, and graph-based parsing, which scores all possible arcs and finds the highest-scoring tree using maximum spanning tree algorithms. Transition-based parsers are faster (typically linear time) but may propagate errors; graph-based parsers are globally optimal but slower (typically quadratic or cubic time).
Modern dependency parsers achieve labeled attachment scores (LAS) above 95% for English and above 90% for many other languages. The Universal Dependencies project has standardized annotation across more than 100 languages, enabling large-scale multilingual dependency parsing research. Neural network models, particularly those based on BiLSTMs and Transformers, have achieved the highest accuracy across most languages.