# Head-driven Phrase Structure Parsing in O(n3) Time Complexity

arXiv: https://arxiv.org/abs/2105.09835 · HTML: https://mlsanity.com/paper/2105.09835/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 56 references that are in the map.
- First posted on arXiv 20 May 2021.

## Builds on (most cited first, 17 of 17)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019)
- [Deep Biaffine Attention for Neural Dependency Parsing](https://mlsanity.com/paper/1611.01734/) (2016)
- [Constituency Parsing with a Self-Attentive Encoder](https://mlsanity.com/paper/1805.01052/) (2018)
- [Multilingual Constituency Parsing with Self-Attention and Pre-Training](https://mlsanity.com/paper/1812.11760/) (2018)
- [75 Languages, 1 Model: Parsing Universal Dependencies Universally](https://mlsanity.com/paper/1904.02099/) (2019)
- [A Minimal Span-Based Neural Constituency Parser](https://mlsanity.com/paper/1705.03919/) (2017)
- [Head-Driven Phrase Structure Grammar Parsing on Penn Treebank](https://mlsanity.com/paper/1907.02684/) (2019)
- [In-Order Transition-based Constituent Parsing](https://mlsanity.com/paper/1707.05000/) (2017)
- [What's Going On in Neural Constituency Parsers? An Analysis](https://mlsanity.com/paper/1804.07853/) (2018)
- [Improving Constituency Parsing with Span Attention](https://mlsanity.com/paper/2010.07543/) (2020)
- [What Do Recurrent Neural Network Grammars Learn About Syntax?](https://mlsanity.com/paper/1611.05774/) (2016)
- [Evaluating Contextualized Embeddings on 54 Languages in POS Tagging, Lemmatization and Dependency Parsing](https://mlsanity.com/paper/1908.07448/) (2019)
- [Global Greedy Dependency Parsing](https://mlsanity.com/paper/1911.08673/) (2019)

## Built on by (most cited first, 2 of 2)

- [We can still parse using syntactic rules](https://mlsanity.com/paper/2602.14238/) (2026)
- [DPH Parser: A Bottom-Up Grammar-Driven Parser for Joint Constituency and Dependency Analysis](https://mlsanity.com/paper/2609.06070/) (2026)

## Abstract (arXiv)

Constituent and dependency parsing, the two classic forms of syntactic parsing, have been found to benefit from joint training and decoding under a uniform formalism, Head-driven Phrase Structure Grammar (HPSG). However, decoding this unified grammar has a higher time complexity (O(n5)) than decoding either form individually (O(n3)) since more factors have to be considered during decoding. We thus propose an improved head scorer that helps achieve a novel performance-preserved parser in O(n3) time complexity. Furthermore, on the basis of this proposed practical HPSG parser, we investigated the strengths of HPSG-based parsing and explored the general method of training an HPSG-based parser from only a constituent or dependency annotations in a multilingual scenario. We thus present a more effective, more in-depth, and general work on HPSG parsing.