Parsing Discontinuous Constituents in Natural Language

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2120 papers182 conceptsfrozen 2026-10-04

Most syntactic parsers operate on a fundamental assumption: a phrase is a continuous block of words. In a sentence like "The quick brown fox jumps," the noun phrase "The quick brown fox" is a single, uninterrupted span. Mathematically, this allows us to represent the sentence as a "projective" tree where no branches cross.

However, many human languages—including German, Dutch, and Warlpiri—frequently violate this assumption. In these "non-configurational" languages, related words can be scattered across a sentence, separated by unrelated phrases. This creates discontinuous constituents. For example, in German, a verb and its arguments might be split across clause boundaries, a phenomenon Owen Rambow identifies as the "Third Construction" in A Linguistic and Computational Analysis of the German "Third Construction". When we try to draw a tree for such a sentence, the branches must cross, breaking the standard algorithms we use to understand language.

Redefining the Location of a Phrase

To handle these "tangled" structures, researchers first had to rethink how we define a constituent's "location." In Parsing with Discontinuous Constituents, Mark Johnson 0001 proposed generalizing the mathematical notion of a span. Instead of a single interval $[i, j]$, a constituent is represented as a set of non-adjacent intervals or bit-vectors. This allows a single grammatical unit to occupy multiple discontinuous slots in the input string.

This shift in representation requires moving beyond standard Context-Free Grammars (CFGs). Formalisms like Linear Context-Free Rewriting Systems (LCFRS) and Tree Adjoining Grammars (TAG) were developed to handle these non-local dependencies. As Thomas Ruprecht and Richard Mörbitz demonstrate in Supertagging-based Parsing with Linear Context-free Rewriting Systems, these systems can model crossing branches by allowing grammar rules to "rewrite" multiple spans at once.

The Complexity Bottleneck

The primary challenge with discontinuous parsing is computational cost. While standard continuous parsing can be done in $O(n^3)$ time, exact algorithms for discontinuous structures often explode to $O(n^6)$ or higher. Benoît Sagot and Giorgio Satta addressed this in Optimal Rank Reduction for Linear Context-Free Rewriting Systems with Fan-Out Two by finding ways to minimize the number of "fan-outs" (gaps) a grammar must track.

More recently, Caio Corro showed in Span-based discontinuous constituency parsing that it is possible to bridge this gap. By using a "grammarless" span-based approach, Corro developed a variant that runs in $O(n^3)$ while still covering 98% of observed linguistic structures, effectively making discontinuous parsing as efficient as its continuous counterpart.

Transition Systems and the Swap Operation

If chart-based parsing is too slow, another option is transition-based parsing, which builds the tree through a sequence of actions (like "Shift" and "Reduce"). To handle discontinuities, Wolfgang Maier 0001 introduced a clever Swap operation in Discontinuous Incremental Shift-reduce Parsing. This operation allows the parser to reorder words on the fly, moving a word out of its linear position so it can be combined with its true (but distant) syntactic partners.

Taking this further, María Grandury, Maximin Coavoux, and Shay B Cohen proposed a "stack-free" system in Discontinuous Constituency Parsing with a Stack-Free Transition System and a Dynamic Oracle. Instead of a linear stack, they use a random-access set, allowing the parser to pick any two constituents to combine, regardless of where they appear in the sentence.

Reorder and then Parse

A final, highly intuitive approach is to treat discontinuity as a pre-processing problem. If the words are in the "wrong" order for a standard parser, why not just move them?

In Reducing Discontinuous to Continuous Parsing with Pointer Network Reordering, Daniel Fernández-González and Carlos Gómez-Rodríguez use a neural Pointer Network to reorder the sentence into a continuous sequence before passing it to a standard parser. Similarly, Kailai Sun and Hai Zhao proposed the "Reorder and then Parse" framework in Reorder and then Parse, Fast and Accurate Discontinuous Constituency Parsing. By modeling word reordering as a graph of actions, they transform complex, crossing structures into simple, nested ones, achieving state-of-the-art speeds and accuracy.

By moving from rigid, contiguous spans to flexible sets, swaps, and reorderings, these researchers have turned the "tangled yarn" of free-word-order languages into a solvable computational problem.

Papers in this version

Showing 60 of 120 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 141 papers
  2. Version 1 · 2026-10-04 · 120 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_handling_discontinuous_constituents_b93893f2,
  title = {handling discontinuous constituents},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/handling-discontinuous-constituents/rdr_b93893f26b654bd7939ff7e691ceaa67},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_parsing_discontinuous_constituents_in_na_b93893f2_v1,
  title = {Parsing Discontinuous Constituents in Natural Language},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parsing-discontinuous-constituents-in-natural-language/rdr_b93893f26b654bd7939ff7e691ceaa67/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}