Arc-Eager Parsing

Unlike Arc-Standard parsing, which delays attachment until the head is complete, Arc-Eager performs Left-Arc and Right-Arc actions immediately when the dependent is on top of the stack. This means a word can receive its head before all of its own dependents are attached, reducing the number of items that must remain on the stack and enabling earlier commitment to syntactic structure.

The parser operates with exactly four atomic actions:

• SHIFT: Pushes the next input token from the buffer onto the stack
• LEFT-ARC(l): Attaches the stack top as a dependent of the next buffer token with label l, then pops the stack
• RIGHT-ARC(l): Attaches the next buffer token as a dependent of the stack top with label l, then pushes the buffer token onto the stack
• REDUCE: Pops the stack top, indicating it is fully processed and will receive no more dependents

Each action has strict preconditions to ensure valid tree construction:

• LEFT-ARC requires the stack top to not already have a head (no multiple heads)
• RIGHT-ARC can only be applied when the dependent has no head assigned
• REDUCE requires the stack top to already have a head, preventing orphaned tokens
• These constraints guarantee the output is a well-formed, single-root dependency tree without cycles

Arc-Eager parsing runs in O(n) time for a sentence of length n, as each token is shifted once and reduced at most once. This makes it significantly faster than graph-based alternatives like the Chu-Liu/Edmonds algorithm, which require O(n²) or O(n³) operations. The deterministic, greedy nature eliminates the need for global optimization passes, making it ideal for production NLP pipelines like spaCy.

The standard Arc-Eager algorithm can only produce projective dependency trees — structures without crossing arcs. This is because the stack-buffer architecture processes words in linear order and cannot create arcs that cross previously established dependencies. For languages with frequent non-projective constructions, such as Czech or Dutch, extensions like swap-based parsing or pseudo-projective transformations are required.

As a greedy, deterministic algorithm, Arc-Eager makes irreversible decisions at each step. An incorrect attachment early in the sentence cascades into subsequent errors because the parser cannot backtrack. This is mitigated by:

• Dynamic oracles that allow training on non-gold states
• Beam search that maintains multiple hypotheses in parallel
• Deep neural feature extractors that improve individual action prediction accuracy

The canonical lazy transition system where both the head and dependent must be on the stack before an arc is formed. This constraint means right-arc actions can only occur when the dependent has been fully reduced, creating a strict bottom-up derivation.

• Forms dependencies only after the entire subtree of the dependent is complete
• Produces projective trees exclusively
• Simpler state space than Arc-Eager but requires more SHIFT operations
• Often used as the baseline transition system in academic comparisons

A training methodology that defines the set of optimal actions from any valid parser state—even states reached after previous errors. This allows the parser to explore non-gold states during learning and learn recovery strategies.

• Critical for Arc-Eager parsers where early attachment decisions can cascade
• Defines a loss function that measures the cost of each action from the current state
• Enables exploration-based training rather than strict teacher forcing
• Significantly improves robustness to error propagation in greedy decoding

A non-deterministic search strategy that maintains a fixed number of the most probable partial parse states at each step. Instead of committing to a single greedy action, the parser explores k parallel hypotheses simultaneously.

• Mitigates the error propagation inherent in greedy Arc-Eager parsing
• Beam width of 8–32 typically balances accuracy and speed
• Each state tracks its cumulative log-probability score
• Allows the parser to recover from locally ambiguous attachment decisions by considering global context

Arc-Eager parsing naturally produces projective trees, but many languages exhibit crossing arcs due to free word order or long-distance dependencies. Extensions like the Swap transition or pseudo-projective parsing add mechanisms to handle non-projectivity.

• SWAP action: Moves the top stack item back to the buffer to reorder processing
• Pseudo-projective parsing: Converts non-projective training data into projective trees with encoded arc labels, then restores crossings post-hoc
• Languages like Czech, Dutch, and German frequently require non-projective handling
• Adds complexity to the transition system but preserves Arc-Eager's efficiency