Algorithms for Deterministic Incremental Dependency Parsing

4 Stack-Based Algorithms

1. What is a stack-based parser configuration?
   A triple \((\sigma, \beta, A)\): a stack \(\sigma\) of partially processed tokens still candidates for arcs, a buffer \(\beta\) of remaining input tokens, and an arc set \(A\). Parsing starts with \(([0], [1, \ldots, n], \emptyset)\) and ends when the buffer is empty.
   • Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics), §4, pp. 520–521