Algorithms for Deterministic Incremental Dependency Parsing

4.2 Arc-Eager Parsing

1. Give the transitions of the arc-eager parser.
   LEFT-ARC\(_l\): as in arc-standard (pop \(i\), add \((j, l, i)\)). RIGHT-ARC\(_l\): \((\sigma|i, j|\beta, A) \Rightarrow (\sigma|i|j, \beta, A \cup \{(i, l, j)\})\), pushing the dependent. REDUCE: pop the stack, if the top already has a head. SHIFT: push the first buffer node.
   • Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics), §4.2, pp. 525–529
2. How does arc-eager differ from arc-standard parsing?
   Arc-eager attaches right dependents as soon as possible, before they have found their own right dependents, so both head and dependent stay on the stack; REDUCE pops the dependent later. It is more incremental: a word is attached as soon as its head is available.
   • Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics), §4.2, pp. 525–529
3. Trace arc-eager parsing of “John saw Mary” (saw is the root; John and Mary depend on saw).
   SHIFT, LEFT-ARC_SBJ, RIGHT-ARC_ROOT, RIGHT-ARC_OBJ; the buffer is then empty, so parsing ends (LA/RA = LEFT-/RIGHT-ARC):

   transition	stack	buffer	arc
   –	[0]	[1,2,3]
   SHIFT	[0, 1]	[2, 3]
   LASBJ	[0]	[2, 3]	2 → 1
   RAROOT	[0, 2]	[3]	0 → 2
   RAOBJ	[0,2,3]	[ ]	2 → 3

   • Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics), §4.2, pp. 525–529