PaperlayerView exact revision on arXiv

Source-linked AI summary

DPH Parser: A Bottom-Up Grammar-Driven Parser for Joint Constituency and Dependency Analysis

Hussein Ghaly

arXiv:2609.06070v1cs.CL

TL;DR

Neural parsers can achieve strong benchmark performance but often leave syntactic structure implicit, limiting direct inspection of their structural decisions. This paper presents a bottom-up grammar-driven parser that builds phrase structures and derives dependencies using explicit heads. On English UD dev/test data, DPH has lower UAS than Stanza and is near spaCy; its rules and evaluation remain limited in scope.

  • Problem

    Neural systems often encode syntax implicitly, making structural decisions difficult to interpret, constrain, or modify, including in ambiguous sentences.

    Source: §1 · p. 1

  • Method

    The parser recursively projects phrases using syntactic rules and explicit head annotations, producing both constituency structure and dependency information.

    Source: §3.6 · p. 5, §5 · p. 7

  • Results

    DPH achieved UAS of 53.32% and 52.58% on UD Devset/Testset, compared with Stanza at 89.12% and 88.67%, and spaCy at 56.91% and 58.59%.

    Source: §5 · p. 6

  • Takeaways & Limitations

    The parser’s output supports inspection of both constituency and dependency structures, and the authors describe language-specific rule inventories as a possible direction for low-resource languages.

    Source: §5 · p. 7, §6 · p. 8

    The evaluation is limited to English UD dev/test corpora, with hand-crafted sample rules that are not a comprehensive listing of English syntax.

    Source: Limitations · p. 8

Abstract

from arXiv · show

This paper presents Dependency-Phrase Hierarchy Parser (DPH Parser), a grammar-driven bottom-up unsupervized parsing framework inspired by Generalized Phrase Structure Grammar (GPSG) and Head-driven Phrase Structure Grammar (HPSG). The parser incrementally constructs constituency structures using a compact inventory of feature-based syntactic rules while deriving dependency relations through explicit head annotations. The system combines probabilistic POS tagging, recursive phrase projection, and weighted parse hypotheses to process realistic and partially noisy text input. Unlike purely neural and data-driven parsers, the resulting syntactic derivations remain explicitly interpretable. We evaluated parser performance on English corpora from the Universal Dependencies (UD) project using Unlabeled Attachment Score (UAS) as the main parsing metric, comparing the outcomes against Stanza and spaCy parsers. For a small inventory of syntactic rules, DPH parser achieved UAS values of 53.32% & 52.58% (UD Devset/Testset respectively). For the same data, Stanza achieved 89.12% & 88.67% while spaCy achieved 56.91% and 58.59%. Although the current system does not yet approach the accuracy of modern neural parsers, the results demonstrate the feasibility of applying transparent rule-based bottom-up parsing to realistic treebank data while jointly producing constituency and dependency structures.

1 Introduction

Neural parsers can perform strongly while leaving syntactic structure implicit, making structural decisions difficult to inspect or modify. This work explores compact, linguistically motivated rules that construct interpretable phrase structures while preserving dependency information.

1 Introduction

  • Neural systems often encode syntax implicitly, making structural decisions difficult to interpret, constrain, or modify, especially in ambiguous sentences.The introduction illustrates ambiguity with whether hats modify both men and women or only women.Source: §1 · p. 1
  • The work investigates whether compact, linguistically motivated rules can incrementally build interpretable phrase structures while preserving dependency information.Source: §1 · p. 1
  • The formalism draws on GPSG and HPSG, using feature propagation and explicit head propagation to represent constraints and dependencies.GPSG slash features represent constituents with missing arguments; HPSG emphasizes typed feature structures and head propagation.Source: §1 · p. 1
  • A constituency-oriented strategy annotates heads in grammar rules so dependency relations can be derived from phrase structures in the same parsing process.The stated contributions include a rule and lexical-feature inventory, a bottom-up algorithm, and a hybrid output with derivations and parse hypotheses.Source: §1 · p. 2

2 Related Work

Prior work spans statistical and neural parsing as well as explicit grammar-based approaches. The paper situates its bottom-up GPSG- and HPSG-inspired parser among work combining symbolic grammatical structure with computational parsing.

2 Related Work

  • Modern parsing includes supervised statistical and neural dependency and constituency systems, alongside continued interest in grammar-constrained, interpretable parsing.The paper identifies formal syntax, semantic compositionality, and explainable language processing as areas of continued interest.Source: §2 · p. 2
  • GPSG and HPSG represent syntactic phenomena through explicit constraints and feature propagation, and earlier work explored their parsing methods and grammar engineering.Examples include GPSG parsing, HPSG parsing constraints, Japanese HPSG parsing, and hybrid constituent-dependency HPSG (Zhou and Zhao, 2019).Source: §2 · p. 2
  • Recent studies combine symbolic grammar and neural methods, including simplified-HPSG parsing, HPSG-inspired supertagging, and training HPSG parsers from annotated data.The cited examples are Nguyen et al. (2024), Zamaraeva and Gómez-Rodríguez (2024), and Li et al. (2021).Source: §2 · p. 2
  • The paper explores a bottom-up parsing approach inspired by GPSG and HPSG grammars.Source: §2 · p. 3

3 Methodology

The parser incrementally projects weighted POS-tag hypotheses into phrase structures, with head annotations enabling dependency derivation. Its extensible GPSG- and HPSG-inspired rules use categories and features to constrain syntactic combinations.

3.1 Parsing Algorithm Overview

  • The left-to-right parser starts from multiple weighted POS-tag hypotheses and recursively projects phrases through unary and binary rules, enforcing category and feature compatibility.For binary projections, it searches preceding phrases for a compatible first child; explicit head-child annotations support dependency derivation.Source: §3.1 · p. 3
  • The parser uses explicit grammatical constraints rather than transition-based parser actions or global arc optimization, with weighted ambiguity resolution and fallbacks for partially parseable input.It has limited tolerance for disfluencies and extra-textual elements.Source: §3.1 · p. 3

3.2 Syntactic Rules

  • Rules resemble CFG productions but add features and head annotations; exactly one child of each binary rule is designated as head for recovering dependencies.Categories can carry positive or negative features that constrain grammatical combinations.Source: §3.2 · p. 3
  • Refined noun-phrase categories such as NP-U and NP-DT constrain recursive combinations that a naive NP → NP NP rule would allow too freely.The examples distinguish noun phrases lacking determiners from those containing determiners.Source: §3.2 · p. 3
  • The grammar also encodes auxiliary sequences and agreement, permits valid sequences such as “would have been,” and includes limited slash features for syntactic gaps.HPSG-inspired head information and feature percolation let parent categories inherit features from head children.Source: §3.2 · p. 4
  • The rule inventory is designed to be extensible and maintainable, and combines phrase-structure rules, terminal mappings, and lexical tags.The authors describe the rules as a practical way to integrate linguistic theory, not as a comprehensive account of English grammar.Source: §3.2 · p. 4

3.3 POS Tagging

The parser relies on probabilistic POS tagging that supplies multiple tag hypotheses and confidence scores. Its RNN-based tagger uses fine-grained UD tags and provides the weighted terminal phrases from which parsing begins.

3.3 POS Tagging

  • The parser requires POS tagging aligned with its rule categories, confidence scores, and multiple tag hypotheses for each token.The most probable tag for a token need not yield the best global parse.Source: §3.3 · p. 4
  • The RNN tagger outputs probabilities over UPOS and language-specific XPOS tags, with XPOS preferred for distinctions needed by syntactic rules.The distinctions include gerunds, infinitives, participles, and finite verbs.Source: §3.3 · pp. 4–5
  • The tagger is the study’s supervised component: it is trained on UD treebank data using token character, capitalization, and orthographic features.The described model is a three-layer LSTM with hidden size 64, trained with Adam and cross-entropy loss.Source: §3.3 · p. 5
  • POS-tagging output forms the initial weighted terminal phrase objects used by the parser.Source: §3.3 · p. 5

3.4 Lexical Tags

The parser augments POS tags with custom lexical categories and features, represents constituents as phrase objects, and recursively projects them through syntactic rules. Binary rules combine compatible phrases into larger constituents while preserving head information.

3.4 Lexical Tags

  • Custom lexical tags add categories and features for grammatical distinctions that standard POS tags may not capture.The category BE is assigned to forms of “to be,” with similar treatment for “to have” and “to do.”Source: §3.4 · p. 5

3.5 Phrase Representation

  • Phrase objects represent terminal lexical categories or non-terminal constituents and store spans, categories, features, child identifiers, head information, weights, and dependency information.These objects form the basis for subsequent parsing operations.Source: §3.5 · p. 5

3.6 Parsing and Phrase Projection

  • Projection matches phrases to unary or binary rules; binary rules search preceding phrases for a compatible first child and combine the pair into a parent phrase.The parent carries the combined span and weight plus the selected head child, then is indexed and projected recursively.Source: §3.6 · p. 5

3.7 Parser Indexing and Optimization

The parser indexes phrase hypotheses and rules to reduce search, accommodates some noisy or incomplete input with fallback parsing, and emits constituency and dependency outputs for qualitative and quantitative evaluation.

3.7 Parser Indexing and Optimization

  • Span- and category-based phrase indexing, alongside indexes for rule categories and features, reduces the search space and improves parsing efficiency.These structures support rapid lookup amid many overlapping phrase hypotheses.Source: §3.7 · p. 5

3.8 Noise Handling and Fallback Parsing

  • Limited skipping lets adjacent phrases combine across small amounts of noise; when irregularities or missing rules prevent a full parse, a shortest-path-inspired fallback connects parseable chunks.The fallback selects a likely sequence of chunks rather than forcing a convergent parse.Source: §3.8 · pp. 5–6

3.9 Output Representation and Evaluation

  • The selected full-sentence or largest parseable span yields a PTB constituency tree and CoNLL dependency relations, which are evaluated qualitatively and quantitatively against spaCy and Stanza.Qualitative evaluation inspects outputs against predefined rules; quantitative evaluation compares performance across corpora.Source: §3.9 · p. 6

4 Experimental Setup

The evaluation measures head-selection accuracy on English Universal Dependencies dev/test data and benchmarks the parser against standard spaCy and Stanza models. The experimental code and associated materials are provided in a GitHub repository.

4.1 Metrics

  • Unlabelled Attachment Score (UAS) measures the proportion of dataset tokens whose heads the parser identifies correctly.The metric focuses on which words depend on which.Source: §4.1 · p. 6

4.2 Data

  • Evaluation uses tokenized English UD dev/test datasets, comprising seven dev files and thirteen test files; spaCy and Stanza standard models are run without training or fine-tuning.UD evaluation tools compare CoNLL-format parses with gold-standard parses; the passage also reports eight train files.Source: §4.2 · p. 6

4.3 Code

  • Experiment code, notebooks, POS models, rule spreadsheets, and other materials are included in a GitHub repository with usage instructions.Source: §4.3 · p. 6

5 Results and Discussion

The DPH parser’s UAS trails Stanza’s on the reported UD dev/test data, while its ATIS results are close to spaCy’s. Qualitative examples show joint constituency and dependency output, including a derivation for a missing-object gap; the parser uses only a small subset of English rules.

5 Results and Discussion

  • DPH achieved UAS of 53.32% and 52.58% on UD Devset/Testset, versus Stanza’s 89.12% and 88.67% and spaCy’s 56.91% and 58.59%.The comparison is reported in Figure 3; the evaluation averages UAS across devset/testset weighted by dataset token counts.Source: §5 · p. 6, Figure 3 · p. 7
  • On ATIS, DPH scored 55.89%/54.35% UAS, below Stanza’s 75.50%/76.90% but near spaCy’s 41.66%/39.89%.The values are devset/testset respectively; the paper also reports DPH surpassing spaCy on multiple datasets.Source: §5 · p. 7
  • The proof-of-concept parser has 148 English rules, which do not cover the full grammar; the effect of wider coverage on parsing outcomes remains to be measured.The paper says the current rule subset can parse various datasets, but further investigation is needed to assess wider coverage.Source: §5 · p. 7
  • The parser output combines dependency information, including token IDs, heads, and tags, with a hierarchy of phrases, levels, and spans.Figure 4 is cited as an example of the hierarchical phrase listing.Source: §5 · p. 7
  • For “the man my friend saw X,” the derivation applies a VP-O/NP rule for a missing direct object, projects to S/NP, and then fills the gap.Figure 4 illustrates the slash-representation derivation.Source: §5 · p. 7, Figure 4 · p. 8

6 Conclusions

The study reports UAS outcomes as a baseline for future implementations, not as competitive parsing. Qualitative testing found expected derivations for syntactic gaps, while the approach also produces inspectable hypotheses and identifies requirements for expansion to other languages.

6 Conclusions

  • The pipeline parses real-world data, but its UAS outcomes are reported as a baseline for future implementations rather than competitive parsing.The authors describe the reported outcomes as a starting point for future implementations.Source: §6 · p. 8
  • The parser produced expected derivations for GPSG slash-notation syntactic gaps, though accuracy on these constructions in real-world data needs further quantitative study.The authors tested sentences exhibiting specific syntactic phenomena as part of a qualitative evaluation.Source: §6 · p. 8
  • The parser exposes full grammatical derivations and multiple whole-sentence and chunk-level hypotheses, enabling ambiguity detection and re-ranking of candidate parses.The approach also combines dependency and constituency structures.Source: §6 · p. 8
  • Expansion to another language requires language-specific POS tags, lexical categories, features, grammatical rules, and POS prediction; rich morphology also requires sub-tokenization prediction.The paper identifies these resources as requirements for applying the approach to a new language.Source: §6 · p. 8
  • The work links linguistic formalisms with empirical computational modeling and supports language-specific rule inventories for low-resource and understudied languages.The authors describe the approach as a way to leverage theoretical syntactic knowledge in those settings.Source: §6 · p. 8

Limitations

The reported results are limited to English UD dev/test corpora, using a handcrafted sample of rules and features tuned on UD training data.

Limitations

  • The results cover English only and only the corpora included in the UD dev/test datasets.The paper's stated result scope is limited to these datasets.Source: Limitations · p. 8
  • The handcrafted rules and features are a sample, not a comprehensive inventory of English syntax.Source: Limitations · p. 8
  • The POS tagger was trained on Universal Dependencies training data, and rule and algorithm tuning also used UD training data.Source: Limitations · p. 8
Loading 2609.06070v1…