Parsing Discontinuous Constituents

223 concepts143 papers1 proposal

Standard constituency parsing operates on a elegant, intuitive assumption: natural language is built like Russian nesting dolls. Words group together into continuous phrases, which group into larger phrases, forming a clean hierarchical tree. In this traditional view, a phrase always occupies a single, unbroken interval of text.

But real-world language frequently breaks this assumption. In languages with flexible word order like German, or even in English sentences featuring extraposition or complex multiword expressions, syntactically related words are often split apart by intervening, unrelated text. This phenomenon creates discontinuous constituents—phrases whose internal components are separated, resulting in "crossing branches" in the syntactic tree.

Handling these non-contiguous structures is one of the most significant challenges in computational linguistics. To build parsers that truly understand the full layout of human speech, researchers have had to rethink how trees are represented, how search spaces are navigated, and how algorithms can bridge the gaps.

The Computational Explosion of Gaps

To understand why discontinuous parsing is difficult, we must look at the mechanics of standard chart parsing. A typical context-free grammar (CFG) parser uses dynamic programming to evaluate combinations of adjacent spans. It asks: Can span $[i, j]$ and span $[j, k]$ merge into a larger phrase $[i, k]$? Because the spans are strictly contiguous, an entire sentence can be parsed in $O(n^3)$ time.

As soon as you allow constituents to have gaps, this interval-based logic falls apart. If a phrase is split into two pieces, you can no longer define its location with just a start and an end point. Instead, you must track the boundaries of the first segment and the boundaries of the second segment.

Formalisms designed to handle these structures, such as Linear Context-Free Rewriting Systems (LCFRS) or Tree Adjoining Grammars, must maintain these fragmented states. However, tracking multiple disjoint spans causes a combinatorial explosion in the parser's search space. As noted by Benoît Sagot et al. in their work on optimal rank reduction, modeling these non-contiguous relationships traditionally pushes computational complexity up to $O(n^6)$ or worse, making exact parsing over large treebanks historically impractical.

Redefining the Representation: From Sets to Permutations

To bypass this computational bottleneck, researchers began experimenting with how discontinuous trees are represented. The foundational insight, introduced by Mark Johnson in Parsing with Discontinuous Constituents, was to generalize a constituent's location from a single continuous interval to a set of non-adjacent intervals or bit-vectors. This mathematical shift allowed formal grammars to map scattered words to a single grammatical unit, but the underlying search space remained vast.

Modern neural approaches solve this by transforming the input text so that standard, efficient parsing algorithms can be reused. Instead of changing the parser, they change the sentence.

One prominent strategy is the "Reorder and then Parse" framework proposed by Kailai Sun et al. in Reorder and then Parse, Fast and Accurate Discontinuous Constituency Parsing. The intuition here is simple: if a sentence contains a discontinuous phrase, there exists an alternative arrangement of those words where the phrase is continuous. By training a model to predict a graph of reordering actions, the system untangles the sentence first, transforming non-projective syntax into a standard projective sequence. Once the text is continuous, a fast $O(n^3)$ parser can process it without any specialized modifications.

Discontinuous: [The book] was written [by the professor] that I told you about.
                                 \_________________/ (Intervening clause)
Untangled:     [The book] [by the professor] was written that I told you about.

Taking this linearization strategy to its logical conclusion, David Vilares et al. demonstrated in Discontinuous Constituent Parsing as Sequence Labeling that tree discontinuities can be encoded directly as "nearly ordered permutations" of input words. This allows the entire parsing problem to be reduced to a fast, straightforward sequence labeling task, enabling general-purpose architectures like BERT to achieve high accuracy without any explicit tree-building logic at all.

Algorithmic Innovations: Stack-Free and Span-Based Parsers

For systems that parse the tree directly without reordering the input, the core challenge lies in the data structures used during derivation.

Traditional transition-based parsers use a linear stack and a buffer. They push words onto the stack from left to right and combine the top items. This structure inherently enforces contiguity; you cannot easily combine the top of the stack with an item buried deep underneath without disturbing the words in between.

To break this limitation, María Grandury et al. designed a novel transition system in Discontinuous Constituency Parsing with a Stack-Free Transition System and a Dynamic Oracle. They replaced the linear stack with a random-access set. Because the parser can query and manipulate any arbitrary subset of words in the set regardless of their original linear order, it can seamlessly jump across gaps and construct crossing branches in a linear number of steps.

On the chart-parsing side, Caio Corro tackled the problem by abandoning grammar-driven rules entirely in Span-based discontinuous constituency parsing. Instead of relying on rigid production rules that explode in complexity, the author developed a family of exact, grammarless chart algorithms. By observing that human languages only utilize a small fraction of theoretically possible gap configurations, the author designed a variant that restricts the search space to these naturally occurring structures. This achieved an exact chart-parsing complexity of $O(n^3)$—matching the speed of standard continuous parsers while still successfully capturing 98% of observed linguistic discontinuities.

Alternative Paradigms: Reduction and Unsupervised Induction

Beyond modifying constituency formalisms, researchers have found success by translating the problem into entirely different syntactic frameworks or inducing them without human labels.

Parsing as Reduction to Dependencies

Dependency parsing—which maps direct, word-to-word directed links rather than hierarchical phrase blocks—is naturally better suited for non-contiguous structures. A dependency edge can easily span across an arbitrary number of intervening words.

Leveraging this inherent flexibility, Andre Martins et al. introduced a method in Parsing as Reduction to convert phrase-structure trees into dependency graphs. By encoding the exact constituent attachment order directly into the dependency labels, they transformed the complex discontinuous constituency problem into a highly optimized dependency parsing task, achieving dramatic speedups.

Unsupervised Structural Awareness

The benefits of modeling discontinuities extend even to scenarios where no annotated treebanks exist. In Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammars, Songlin Yang et al. scaled up neuralized LCFRSs using low-rank tensor decompositions to induce trees without supervision.

Crucially, the authors discovered a fascinating global feedback loop: explicitly allowing the model the freedom to form discontinuous constituents actually improved its accuracy at identifying standard continuous phrases as well. By providing the grammar with the expressive power to handle non-linear, fragmented structures, the model gained a more robust global context, proving that accounting for the messy realities of language ultimately makes the entire syntactic model stronger.

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 2, frozen text):

@misc{lacuna_handling_discontinuous_constituents_b93893f2_v2,
  title = {handling discontinuous constituents},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/handling-discontinuous-constituents/rdr_b93893f26b654bd7939ff7e691ceaa67/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake