Shift-Reduce Parsing

The parser maintains two fundamental data structures that define its state at any point during processing:

• Buffer: Contains the remaining input tokens to be processed, initially holding the entire sentence in order
• Stack: Holds partially processed tokens that are awaiting head-dependent attachment
• The initial state places the entire sentence on the buffer with an empty stack; the terminal state empties the buffer and leaves a single root node on the stack
• This dual-structure design enables efficient left-to-right processing without requiring random access to the entire sentence

The SHIFT operation moves the next token from the front of the buffer onto the top of the stack:

• Does not create any dependency relations—it simply advances the parser's reading head
• Enables the parser to delay attachment decisions until sufficient right context has been observed
• In Arc-Standard parsing, SHIFT is the only way to introduce new tokens into the stack for potential reduction
• The decision to SHIFT versus REDUCE is the fundamental choice at each parsing step, learned from annotated treebank data

The REDUCE operation pops the top two items from the stack and attaches them as a head-dependent pair, pushing the head back onto the stack:

• Left-Arc: Attaches the top stack item as a dependent of the second item, removing the dependent from the stack
• Right-Arc: Attaches the second stack item as a dependent of the top item, removing the dependent from the stack
• Each reduction assigns a typed dependency relation such as nsubj, dobj, or amod
• The specific arc direction and label are predicted by a classifier trained on gold-standard treebank annotations

Shift-Reduce parsers typically employ a greedy decoding strategy that selects the single most probable action at each step:

• A classifier—historically an SVM or perceptron, now typically a neural network—scores possible actions based on features extracted from the current parser state
• Features include the top tokens on the stack, the next buffer token, their part-of-speech tags, and existing dependency relations
• Greedy decoding achieves linear O(n) time complexity, making it suitable for production environments
• The primary weakness is error propagation: an incorrect early decision cannot be corrected and may cascade into subsequent errors

Two primary transition strategies define when dependencies can be created:

• Arc-Standard: Requires both the head and dependent to be on the stack before reduction; produces only projective trees but simplifies the action space
• Arc-Eager: Creates dependencies as soon as the dependent is fully processed, even if the head has not yet found all its dependents; supports a limited class of non-projective structures
• Arc-Eager introduces additional actions like REDUCE (pop stack without attachment) and requires more complex oracle derivation
• The choice of strategy affects the parser's ability to handle free word order and long-distance dependencies

Shift-Reduce parsers are trained by converting gold-standard dependency trees into action sequences using an oracle:

• A static oracle deterministically derives the correct action sequence from a gold parse tree by simulating the parser's state
• At each step, the oracle compares the current stack and buffer to the gold tree and outputs the required SHIFT or REDUCE action
• The parser learns to predict these oracle actions from state features, effectively learning to replicate the treebank annotations
• Static oracles assume the parser is always in a gold state, which does not reflect real-world error conditions during inference

A structural property of dependency trees where there are no crossing arcs when the sentence is drawn linearly with words in order. Shift-reduce parsers in their basic form produce only projective trees.

• Crossing Dependencies: Common in languages with free word order (Czech, Dutch, German).
• Non-Projective Extensions: Techniques like swap-based parsing or pseudo-projective transformations allow shift-reduce to handle non-projective structures.
• Evaluation Impact: Non-projective arcs account for 1-5% of dependencies in most treebanks.