Heuristic Conversion of Syntactic Trees

41 concepts33 papers1 proposal

Human language is rich and multi-layered, leading linguists to design various ways to represent its underlying structure. Constituency grammars focus on nested hierarchies, grouping words into phrases (like noun phrases or verb phrases). Dependency grammars ignore phrase boundaries entirely, focusing instead on word-to-word relationships (like subjects modifying verbs). Deep formalisms, such as Head-Driven Phrase Structure Grammar (HPSG) or Minimalist Grammars (MG), introduce intricate constraints to capture long-distance linguistic phenomena.

Building a "treebank"—a large corpus of sentences manually annotated with these structures—is incredibly expensive and requires years of expert labor. When NLP shifted its focus from phrase structures to dependency graphs, researchers faced a dilemma: abandon decades of legacy constituency treebanks, or manually re-annotate them from scratch.

The solution lies in heuristic conversion. Syntactic formalisms are not mutually exclusive; they are different geometric projections of the same underlying linguistic reality. By using deterministic, rule-based algorithms, we can translate sentences from one structural format to another, unlocking legacy data for modern models and bridging disparate theories of grammar.

To understand how a constituency tree can be transformed into a dependency tree, we must look at how phrases are organized. In any natural language phrase, there is a single word that acts as its structural core—the head. Every other word in that phrase serves to modify or complete the head. For example, in the noun phrase "the ancient scroll", the noun "scroll" is the head, while "the" and "ancient" are its dependents.

By formalizing this intuition into a prioritized list of rules for each phrase type (e.g., "in a Verb Phrase, look for the main verb first; if absent, look for an auxiliary"), we create a head-finding engine.

Constituency Tree:
       [Verb Phrase]
      /            \
 [Auxiliary]     [Main Verb]
    (will)         (write)

Step 1: Identify 'write' as the head of the Verb Phrase.
Step 2: Draw a dependency edge from the head 'write' to the dependent 'will'.

Dependency Graph:
    write
      |
   (aux)
      |
    will

When applied recursively from the bottom of a constituency tree to the top, this rule-based approach systematically flattens nested phrase boundaries. Once the head of every phrase is identified, direct word-to-word dependency edges are drawn between them.

This elegant mechanism allows researchers to instantly generate large-scale dependency data. For example, Dima Taji et al. built a highly reliable pipeline in Universal Dependencies for Arabic to convert the widely used Penn Arabic Treebank into a cross-linguistically consistent dependency format. Similarly, Yoav Goldberg et al. established the first dependency parsing results for Hebrew by migrating phrase-structure data via head-finding heuristics in Hebrew Dependency Parsing: Initial Results.

This strategy is highly adaptable across diverse domains and tasks:

Reversing the Pipeline: Projecting Phrases from Dependencies

The geometric relationship between formalisms is a two-way street. Sometimes, researchers possess dependency data but require phrase structures—either to leverage the global structural constraints of a parser or to perform shallow chunking tasks.

To convert dependencies back into phrases, heuristic algorithms operate in reverse using binarization and flattening. Because a dependency tree explicitly states which words modify which, an algorithm can project a synthetic phrase hierarchy around each head and its cluster of dependents.

Dependency Input:     [eat] ---> [apples]
Reverse Projection:   Project a Noun Phrase (NP) around 'apples', 
                      then project a Verb Phrase (VP) enclosing the head 'eat' and its child NP.
Synthetic Phrase:     [VP [V eat] [NP [N apples]]]

The authors of Data-driven, PCFG-based and Pseudo-PCFG-based Models for Chinese Dependency Parsing (Weiwei Sun et al.) demonstrated that converting dependency structures into synthetic phrase-structure trees allows grammar-based parsers to be trained on datasets that lack explicit constituency annotations.

In other scenarios, full hierarchical reconstruction isn't necessary; the goal is simply to find flat, shallow phrase boundaries (chunks). In On the Importance of Ezafe Construction in Persian Parsing, Alireza Nourian et al. used rule-based transformation algorithms to convert dependency tree representations into shallow phrase chunks, bootstrapping training data for chunking tasks in languages where only dependency corpora were available.

Graph Rewriting for Structural Enrichment

Transformations are not limited to moving between different formalisms; they can also occur within the same formalism to enrich its linguistic detail.

Standard dependency structures are strictly trees: every word has exactly one incoming edge from a head. However, real language contains semantic overlaps, such as coordinated verbs ("She cooked and ate the pie") or relative clauses ("The pie that she ate"). In both cases, a single word logically belongs to multiple parents.

Graph rewriting solves this by using rule-based pattern matching to transform simple trees into enriched, multi-parent graphs. A graph rewriting engine searches for specific structural subgraphs (like a coordinated verb phrase) and applies a set of modifications (like copying the object relation to both verbs).

Standard Tree:
   [cooked] ---> (conj) ---> [ate] ---> (obj) ---> [pie]

Graph Rewriting Rule:
   If Verb_A has a conjunction Verb_B, and Verb_B has an object, 
   add an object edge from Verb_A to that same object.

Enhanced Graph:
   [cooked] ------------(obj)------------> [pie]
      |                                      ^
    (conj)                                   |
      v                                      |
    [ate] -------------(obj)-----------------+

Bruno Guillaume et al. developed the GREW system (Graph Rewriting for Enhanced Universal Dependencies), proving that explicit graph-pattern rules can systematically upgrade standard Universal Dependencies into Enhanced Universal Dependencies (EUD).

This two-step pipeline—parsing into a standard tree first, then applying rule-based graph transformations—allows systems to leverage highly optimized, robust standard parsers while still outputting rich semantic graphs, an architecture highlighted by Gosse Bouma et al. in the Overview of the IWPT 2020 Shared Task on Parsing into Enhanced Universal Dependencies.

Bootstrapping Deep Grammars and Downstream Tasks

Heuristic conversion also serves as a bridge to deep linguistic formalisms like HPSG and Minimalist Grammars. These formalisms require incredibly detailed lexical features and derivation trees that are nearly impossible to annotate manually at scale.

By designing sophisticated conversion pipelines, researchers can automatically extract deep grammars from existing treebanks. Kazuhiro Yoshida demonstrated this in Corpus-Oriented Development of Japanese HPSG Parsers, using heuristic rules to convert a general-purpose dependency corpus into an HPSG treebank, instantly achieving wide coverage. Similarly, John Torr utilized semi-automatic conversion of constituency treebanks to generate wide-coverage resources for Minimalist Grammars (Constraining MGbank: Agreement, L-Selection and Supertagging in Minimalist Grammars).

Furthermore, these structural transformations unlock powerful capabilities in downstream applications:

Why Heuristic Conversion Works

Why do these rule-based systems remain so effective, even in an era dominated by deep learning?

  1. Linguistic Invariance: The underlying semantic relationships in a sentence (who did what to whom) remain constant regardless of the formalism. Whether expressed as a nested phrase or a directed edge, the core information is identical. Rules simply change the coordinate system.
  2. Deterministic Logic: Unlike neural models, rule-based converters do not hallucinate, drop constraints, or require massive training data. When converting a corpus, a rule-based pipeline guarantees that identical structural patterns receive identical treatments, preserving the integrity of the gold-standard data.
  3. Neutralizing Annotation Bias: Different treebanks make arbitrary decisions on controversial structures (e.g., whether a prepositional phrase attaches to the noun or the verb). As Roy Schwartz et al. showed in Neutralizing Linguistically Problematic Annotations in Unsupervised Dependency Parsing Evaluation, heuristic conversion allows researchers to create multiple evaluation benchmarks from a single corpus by varying the head-identification rules. This neutralizes the annotation biases that often distort parser evaluation metrics (Ines Rehbein et al. in Evaluating Evaluation Measures).

By acting as a deterministic mathematical mapping between formalisms, heuristic tree conversion ensures that decades of linguistic annotation effort are never locked into a single format, allowing data to flow freely across paradigms.

Key Foundational Work

Methods for Obtaining Corresponding Phrase Structure and Dependency Grammars (1967) — contributed 3 concept elements to this direction.
Using Grammatical Relations to Compare Parsers (2003) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_constituency_to_dependency_transformatio_f6d78212,
  title = {constituency-to-dependency transformation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/constituency-to-dependency-transformation/rdr_f6d7821244be4f28a0f5b960800f64e6},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_constituency_to_dependency_transformatio_f6d78212_v1,
  title = {constituency-to-dependency transformation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/constituency-to-dependency-transformation/rdr_f6d7821244be4f28a0f5b960800f64e6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake