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.
Collapsing Phrases into Links: The Mechanics of Head-Finding
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:
- Simplifying Architectures: Instead of training separate models, toolkits like MSR SPLAT (Chris Quirk et al. in MSR SPLAT, a language analysis toolkit) derive dependencies directly from constituency outputs to maintain internal consistency.
- Evaluating Legacy Parsers: In Parsing Clinical Finnish: Experiments with Rule-Based and Statistical Dependency Parsers, Katri Haverinen et al. used hand-written transformation rules to convert phrase-structure outputs into dependencies, allowing legacy medical parsers to be evaluated against modern standards.
- Targeted Data Generation: Heuristic conversion can generate partially annotated datasets from phrase corpora (Daniel Flannery et al. in Training Dependency Parsers from Partially Annotated Corpora) or map synthetic context-free grammars to standardized dependency trees to test compositional generalization (Emily Goodwin et al. in Compositional Generalization in Dependency Parsing).
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:
- Question Generation: In Unsupervised multiple-choice question generation for out-of-domain Q&A fine-tuning, Guillaume Le Berre et al. combined dependency parsing and constituency tree transformations to rewrite declarative sentences into grammatically flawless interrogative forms, avoiding the hallucinations common in neural generation models.
- Textual Entailment: Roy Bar-Haim et al. formalized linguistic knowledge as transformation rules operating directly on dependency trees in Semantic Inference at the Lexical-Syntactic Level for Textual Entailment Recognition, mapping source propositions to target hypotheses to verify logical entailment.
- Framework Integration: Complex linguistic representations can be mapped into simplified dependency formats using specialized rewrite rules to ensure compatibility between different parsing frameworks, as shown by Lilja Øvrelid et al. in Improving data-driven dependency parsing using large-scale LFG grammars, and by Shiqi Li et al. in Combining Constituent and Dependency Syntactic Views for Chinese Semantic Role Labeling.
Why Heuristic Conversion Works
Why do these rule-based systems remain so effective, even in an era dominated by deep learning?
- 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.
- 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.
- 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.