Algorithms for Deterministic Incremental Dependency Parsing

4.1 Arc-Standard Parsing

1. Give the transitions of the arc-standard parser.
   LEFT-ARC\(_l\): \((\sigma|i, j|\beta, A) \Rightarrow (\sigma, j|\beta, A \cup \{(j, l, i)\})\), if \(i \ne 0\) and \(i\) has no head. RIGHT-ARC\(_l\): \((\sigma|i, j|\beta, A) \Rightarrow (\sigma, i|\beta, A \cup \{(i, l, j)\})\), if \(j\) has no head; the head \(i\) goes back to the buffer. SHIFT: \((\sigma, i|\beta, A) \Rightarrow (\sigma|i, \beta, A)\).
   • Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics), §4.1, pp. 521–525
2. How does arc-standard parsing relate to shift-reduce parsing, and when can a right dependent be attached?
   It is the closest analogue of shift-reduce parsing for CFGs: LEFT-ARC and RIGHT-ARC are reduce actions replacing a head–dependent structure with its head. A right dependent can be attached only after it has collected all its own dependents, because it is removed when attached.
   • Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics), §4.1, pp. 521–525
3. Why are the stack-based algorithms linear time?
   Each SHIFT removes one node from the buffer, which never grows, so there are at most \(n\) shifts; each arc transition pops the stack, which only SHIFT pushes. So a transition sequence has at most \(2n\) transitions: \(O(n)\) time, and \(O(n)\) space for one configuration.
   • Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics), §4.1, pp. 521–525
4. For which class of graphs are the stack-based algorithms correct?
   Projective dependency forests: every transition preserves ROOT, SINGLE-HEAD, ACYCLICITY and PROJECTIVITY (soundness), and every projective forest has a transition sequence that builds it (completeness).
   • Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics), §4.1, pp. 521–525