Transition-Based Parsing

The algorithm operates on a triple: a stack (σ) holding partially processed tokens, a buffer (β) containing remaining input tokens, and a set of dependency arcs (A) representing the partially built tree. The initial state has an empty stack and the full sentence on the buffer, often with a ROOT node. Parsing terminates when the buffer is empty and the stack contains only the ROOT node, at which point A defines the complete dependency tree.

The parser selects from a small set of atomic actions at each step:

• SHIFT: Push the next buffer token onto the stack.
• LEFT-ARC(l): Pop the top two stack items (s1, s2), add an arc s1 → s2 with label l, and remove s2 from the stack.
• RIGHT-ARC(l): Pop the top two stack items (s1, s2), add an arc s2 → s1 with label l, and remove s1 from the stack.

Variants like the Arc-Eager strategy allow arcs to be built before the dependent is fully processed, reducing stack depth.

During training, a static oracle derives the gold-standard action sequence from an annotated treebank by simulating the parser's behavior. At each configuration, the oracle provides the correct action. A classifier—traditionally an SVM or a neural network—is trained on features extracted from the stack, buffer, and existing arcs to predict the next action. Dynamic oracles extend this by defining optimal actions even from error states, enabling exploration during learning and improving robustness to error propagation.

The simplest decoding strategy is greedy: at each step, select the single highest-probability action and commit to it. This yields O(n) linear-time complexity but suffers from error propagation—a single mistake can cascade into subsequent incorrect decisions. Beam search mitigates this by maintaining k candidate parser states simultaneously, expanding each with all valid actions, and pruning to the top-k highest-scoring partial sequences. This trades increased computational cost for higher accuracy, particularly on long sentences.

Classical transition-based parsers like MaltParser relied on hand-crafted feature templates encoding stack top tokens, their POS tags, and existing dependency relations. Modern neural approaches replace this with learned representations:

• Stack-LSTM parsers encode the stack and buffer as LSTMs, updating hidden states with each push/pop operation.
• Pointer-based architectures use attention to score head-dependent pairs directly.
• These neural models achieve state-of-the-art accuracy while eliminating the need for manual feature engineering, though at higher computational cost per step.

Standard transition-based parsers using LEFT-ARC and RIGHT-ARC actions can only produce projective dependency trees—those without crossing arcs. To handle non-projective structures common in languages like German or Czech, extensions are required:

• SWAP: Introduced by Nivre, this action moves the top stack item back to the buffer, enabling reordering.
• Arc-Hybrid and Arc-Eager variants offer different trade-offs between projectivity coverage and action complexity.
• Graph-based parsers using the Chu-Liu/Edmonds algorithm naturally handle non-projectivity but lose the linear-time efficiency of transition-based approaches.

The foundational algorithm for transition-based parsing that operates with a stack, a buffer, and a set of actions. The parser starts with the root on the stack and all input tokens in the buffer. At each step, it applies one of two primary actions:

• SHIFT: Pushes the next token from the buffer onto the stack.
• REDUCE: Pops the top two items from the stack and attaches them as a head-dependent pair, pushing the head back. This deterministic process builds the tree incrementally in linear time O(n), making it highly efficient for production systems like spaCy.

A specific transition strategy that builds dependency arcs as soon as the dependent has been fully processed, rather than waiting for the head to be complete. It defines four actions:

• SHIFT: Move word from buffer to stack.
• LEFT-ARC: Attach the top stack item as a dependent of the next buffer token with a leftward relation.
• RIGHT-ARC: Attach the next buffer token as a dependent of the top stack item with a rightward relation.
• REDUCE: Pop the stack when the top item has found its head. This eager approach allows the parser to resolve attachments immediately, reducing stack depth.

A critical training methodology that addresses the error propagation problem inherent in greedy transition-based parsers. Instead of only training on gold-standard parser states, a dynamic oracle defines the set of optimal actions from any valid state, even those reached after previous mistakes. This allows the parser to learn recovery behaviors during training by exploring non-gold states. The technique significantly improves robustness because the model learns to make the best possible decision given its current, potentially imperfect, context rather than assuming it always starts from a perfect state.

A non-deterministic extension to greedy parsing that mitigates error propagation by maintaining a fixed number (beam width) of the most probable partial parse states at each step. Instead of committing to a single action, the parser explores multiple hypotheses simultaneously, scoring each sequence of actions. At the end, the highest-scoring complete tree is selected. While this increases computational cost from O(n) to O(n * beam width), it provides a crucial accuracy boost by allowing the parser to recover from locally ambiguous decisions that a greedy strategy would lock in prematurely.

A seminal data-driven, transition-based dependency parsing system developed by Nivre et al. It uses history-based feature models that encode the current parser configuration—including stack tokens, buffer tokens, and already-built arcs—into a high-dimensional sparse feature vector. A Support Vector Machine (SVM) classifier then predicts the next transition action. MaltParser demonstrated that deterministic parsing could achieve competitive accuracy with graph-based methods while being significantly faster, establishing the viability of the transition-based paradigm for large-scale practical applications.

A structural limitation of classic transition-based parsers that can only build projective dependency trees—trees with no crossing arcs when drawn above the sentence. This is a direct consequence of the stack-based architecture, which processes words contiguously. While projective trees cover the majority of constructions in English, they fail to represent non-projective phenomena like wh-movement or the free word order in languages such as Czech or Dutch. Extensions like the swap-based transition system or pseudo-projective parsing with post-processing were developed to handle these cases.