# Discontinuous Constituency Parsing with a Stack-Free Transition System and a Dynamic Oracle

arXiv: https://arxiv.org/abs/1904.00615 · HTML: https://mlsanity.com/paper/1904.00615/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Apr 2019.

## Built on by (most cited first, 3 of 3)

- [Reducing Discontinuous to Continuous Parsing with Pointer Network Reordering](https://mlsanity.com/paper/2104.06239/) (2021)
- [Discontinuous Grammar as a Foreign Language](https://mlsanity.com/paper/2110.10431/) (2021)
- [Exploiting Pre-trained Encoder-Decoder Transformers for Sequence-to-Sequence Constituent Parsing](https://mlsanity.com/paper/2605.13373/) (2026)

## Abstract (arXiv)

We introduce a novel transition system for discontinuous constituency parsing. Instead of storing subtrees in a stack --i.e. a data structure with linear-time sequential access-- the proposed system uses a set of parsing items, with constant-time random access. This change makes it possible to construct any discontinuous constituency tree in exactly 4n - 2 transitions for a sentence of length n. At each parsing step, the parser considers every item in the set to be combined with a focus item and to construct a new constituent in a bottom-up fashion. The parsing strategy is based on the assumption that most syntactic structures can be parsed incrementally and that the set --the memory of the parser-- remains reasonably small on average. Moreover, we introduce a provably correct dynamic oracle for the new transition system, and present the first experiments in discontinuous constituency parsing using a dynamic oracle. Our parser obtains state-of-the-art results on three English and German discontinuous treebanks.