---
title: "Span-Based Constituency Parsing with a Structure-Label System and Provably Optimal — Cross 2016"
description: "They propose a shift-reduce variant in which stack elements are plain sentence spans, not partial trees. 38 references, cited by 77 papers here."
authors: ["James Cross", "Liang Huang"]
year: 2016
venue: "arXiv:1612.06475"
source: "https://arxiv.org/abs/1612.06475"
doi: "10.48550/arxiv.1612.06475"
arxiv: "1612.06475"
licence: "arXiv — non-exclusive license to distribute"
licence_url: "http://arxiv.org/licenses/nonexclusive-distrib/1.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/cross-2016-span-based-constituency-parsing-structure/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/cross-2016-span-based-constituency-parsing-structure/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2016](https://md.research.elamur.ai/free/en/papers/2016/page/2/) / Span-Based Constituency Parsing with a Structure-Label System and Provably Optimal Dynamic Oracles

# Span-Based Constituency Parsing with a Structure-Label System and Provably Optimal Dynamic Oracles

**Authors:** [James Cross](https://md.research.elamur.ai/free/en/authors/james-cross/) and [Liang Huang](https://md.research.elamur.ai/free/en/authors/liang-huang/) · **Year:** 2016 · **Venue:** arXiv:1612.06475 · **Licence:** [arXiv — non-exclusive license to distribute](http://arxiv.org/licenses/nonexclusive-distrib/1.0/)

**Links:** [Publisher's page](https://arxiv.org/abs/1612.06475) · [PDF](https://arxiv.org/pdf/1612.06475) · [DOI 10.48550/arxiv.1612.06475](https://doi.org/10.48550/arxiv.1612.06475) · [arXiv 1612.06475](https://arxiv.org/abs/1612.06475) · [OpenAlex](https://openalex.org/W2563495010)

**Citations:** 114 citations (OpenAlex, 2026-10-14) · [77](https://md.research.elamur.ai/free/en/papers/cross-2016-span-based-constituency-parsing-structure/cited-by/) in our library, of the 140,884 papers whose bibliographies we read

## Summary
Cross and Huang address the gap between neural greedy parsers, which lead in dependency parsing, and the best constituency parsers. They propose a shift-reduce variant in which stack elements are plain sentence spans, not partial trees. The parser alternates between structural moves (shift, or a non-directional combine of the top two spans) and label moves (assign a nonterminal or a unary chain to the top span, or skip it). Because of this design, n-ary productions need no binarization, and every sentence takes exactly 4n−2 steps. Each span is encoded as the difference of forward and backward outputs from a two-layer bi-directional LSTM, extending LSTM-Minus. The authors also derive a dynamic oracle that is provably optimal for F1, precision and recall and runs in amortized O(1) time. Training uses this oracle together with exploration. With strictly greedy, linear-time decoding, the parser obtains the best results among single-model, closed-data parsers without reranking on both the Penn Treebank and the French Treebank. The work shows that a simple span-centric design can match far more complex parsers.

## Key points
- Very few features are needed: structural decisions rely on 4 span features, while label decisions rely on 3. No pre-trained embeddings are used.
- Results on the Penn Treebank (WSJ section 23):
  - The dynamic oracle with exploration reaches F1 91.3, compared with 91.0 for the static oracle.
  - POS tags come from the Stanford tagger with 10-way jackknifing.
- Results on the PTB development set:
  - The static and dynamic oracles alone both give F1 91.38.
  - Adding exploration with α=1.0 raises F1 to 91.64, gaining precision at some cost to recall.
- Results on the French Treebank (SPMRL 2014 data, with predicted morphology and lemmas): F1 83.31 with dynamic training versus 83.18 with static training. This exceeds Björkelund et al. (2014) at 82.53, a system that used reranking and external data.
- Code is available at github.com/jhcross/span-parser. The authors list beam search and dynamic programming as future extensions.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

Fields: [Other](https://md.research.elamur.ai/free/en/shelves/other/)

Topics: [📐 Syntax & grammar formalisms](https://md.research.elamur.ai/free/en/topics/syntax-grammar/)

## Institutions

- [Oregon State University](https://md.research.elamur.ai/free/en/universities/oregon-state-university/) — University, Corvallis, United States · 4 works · 618 citations

## Cite

Cite as: James Cross and Liang Huang. 2016. Span-Based Constituency Parsing with a Structure-Label System and Provably Optimal Dynamic Oracles. arXiv:1612.06475.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@misc{cross2016span,
  title = {{Span-Based Constituency Parsing with a Structure-Label System and Provably Optimal Dynamic Oracles}},
  author = {James Cross and Liang Huang},
  year = {2016},
  doi = {10.48550/arxiv.1612.06475},
  eprint = {1612.06475},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1612.06475}
}
```

- [← previous Multilingual Projection for Parsing Truly Low-Resource Languages](https://md.research.elamur.ai/free/en/papers/agic-2016-multilingual-projection-parsing-truly-low/)
- [next → Tweet Sarcasm Detection Using Deep Neural Network](https://md.research.elamur.ai/free/en/papers/zhang-2016-tweet-sarcasm-detection-deep-neural/)
- [↑ back to papers of 2016](https://md.research.elamur.ai/free/en/papers/2016/page/2/)

## References

38 references, 10 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Anne Abeillé, Lionel Clément, and François Toussenel. 2003. Building a treebank for french. In Treebanks, pages 165–187. Springer. [find](https://scholar.google.com/scholar?q=Anne+Abeille%CC%81%2C+Lionel+Cle%CC%81ment%2C+and+Franc%CC%A7ois+Toussenel%2E+2003%2E+Building+a+treebank+for+french%2E+In+Treebanks%2C+pages+165%E2%80%93187%2E+Springer%2E)
2. Daniel Andor, Chris Alberti, David Weiss, Aliaksei Severyn, Alessandro Presta, Kuzman Ganchev, Slav Petrov, and Michael Collins. 2016. Globally normalized transition-based neural networks. Proceedings of ACL. [our card](https://md.research.elamur.ai/free/en/papers/andor-2016-globally-normalized-transition-based-neural/)
3. Miguel Ballesteros, Chris Dyer, and Noah A Smith. 2015. Improved transition-based parsing by modeling characters instead of words with lstms. arXiv preprint arXiv:1508.00657. [our card](https://md.research.elamur.ai/free/en/papers/ballesteros-2015-improved-transition-based-parsing-modeling/)
4. Miguel Ballesteros, Yoav Goldberg, Chris Dyer, and Noah A Smith. 2016. Training with exploration improves a greedy stack-lstm parser. arXiv preprint arXiv:1603.03793. [find](https://scholar.google.com/scholar?q=Miguel+Ballesteros%2C+Yoav+Goldberg%2C+Chris+Dyer%2C+and+Noah+A+Smith%2E+2016%2E+Training+with+exploration+improves+a+greedy+stack%2Dlstm+parser%2E+arXiv+preprint+arXiv%3A1603%2E03793%2E)
5. Anders Björkelund, Ozlem Cetinoglu, Agnieszka Falenska, Richárd Farkas, Thomas Mueller, Wolfgang Seeker, and Zsolt Szántó. 2014. Introducing the ims-wrocław-szeged-cis entry at the spmrl 2014 shared task: Reranking and morpho-syntax meet unlabeled data. In Proceedings of the First Joint Workshop… [find](https://scholar.google.com/scholar?q=Anders+Bjo%CC%88rkelund%2C+Ozlem+Cetinoglu%2C+Agnieszka+Falenska%2C+Richa%CC%81rd+Farkas%2C+Thomas+Mueller%2C+Wolfgang+Seeker%2C+and+Zsolt+Sza%CC%81nto%CC%81%2E+2014%2E+Introducing+the+ims%2Dwroc%C5%82aw%2Dszeged%2Dcis+entry+at+the+spmrl+2014+shar)
6. Xavier Carreras, Michael Collins, and Terry Koo. 2008. Tag, dynamic programming, and the perceptron for efficient, feature-rich parsing. In Proceedings of the Twelfth Conference on Computational Natural Language Learning, pages 9–16. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Xavier+Carreras%2C+Michael+Collins%2C+and+Terry+Koo%2E+2008%2E+Tag%2C+dynamic+programming%2C+and+the+perceptron+for+efficient%2C+feature%2Drich+parsing%2E+In+Proceedings+of+the+Twelfth+Conference+on+Computational+Natur)
7. Danqi Chen and Christopher D Manning. 2014. A fast and accurate dependency parser using neural networks. In Empirical Methods in Natural Language Processing (EMNLP). [our card](https://md.research.elamur.ai/free/en/papers/chen-2014-fast-accurate-dependency-parser-neural/)
8. Maximin Coavoux and Benoı̂t Crabbé. 2016. Neural greedy constituent parsing with dynamic oracles. Proceedings of ACL. [find](https://scholar.google.com/scholar?q=Maximin+Coavoux+and+Beno%C4%B1%CC%82t+Crabbe%CC%81%2E+2016%2E+Neural+greedy+constituent+parsing+with+dynamic+oracles%2E+Proceedings+of+ACL%2E)
9. James Cross and Liang Huang. 2016. Incremental parsing with minimal features using bi-directional lstm. Proceedings of ACL. [find](https://scholar.google.com/scholar?q=James+Cross+and+Liang+Huang%2E+2016%2E+Incremental+parsing+with+minimal+features+using+bi%2Ddirectional+lstm%2E+Proceedings+of+ACL%2E)
10. Greg Durrett and Dan Klein. 2015. Neural crf parsing. Proceedings of ACL. [find](https://scholar.google.com/scholar?q=Greg+Durrett+and+Dan+Klein%2E+2015%2E+Neural+crf+parsing%2E+Proceedings+of+ACL%2E)
11. Chris Dyer, Miguel Ballesteros, Wang Ling, Austin Matthews, and Noah A Smith. 2015. Transition-based dependency parsing with stack long short-term memory. Empirical Methods in Natural Language Processing (EMNLP). [our card](https://md.research.elamur.ai/free/en/papers/dyer-2015-transition-based-dependency-parsing-stack/)
12. Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah A Smith. 2016. Recurrent neural network grammars. Proceedings of HLT-NAACL. [find](https://scholar.google.com/scholar?q=Chris+Dyer%2C+Adhiguna+Kuncoro%2C+Miguel+Ballesteros%2C+and+Noah+A+Smith%2E+2016%2E+Recurrent+neural+network+grammars%2E+Proceedings+of+HLT%2DNAACL%2E)
13. Yoav Goldberg and Joakim Nivre. 2013. Training deterministic parsers with non-deterministic oracles. Transactions of the association for Computational Linguistics, 1:403–414. [find](https://scholar.google.com/scholar?q=Yoav+Goldberg+and+Joakim+Nivre%2E+2013%2E+Training+deterministic+parsers+with+non%2Ddeterministic+oracles%2E+Transactions+of+the+association+for+Computational+Linguistics%2C+1%3A403%E2%80%93414%2E)
14. Yoav Goldberg, Francesco Sartorio, and Giorgio Satta. 2014. A tabular method for dynamic oracles in transition-based parsing. Trans. of ACL. [find](https://scholar.google.com/scholar?q=Yoav+Goldberg%2C+Francesco+Sartorio%2C+and+Giorgio+Satta%2E+2014%2E+A+tabular+method+for+dynamic+oracles+in+transition%2Dbased+parsing%2E+Trans%2E+of+ACL%2E)
15. James Henderson. 2004. Discriminative training of a neural network statistical parser. In Proceedings of ACL. [find](https://scholar.google.com/scholar?q=James+Henderson%2E+2004%2E+Discriminative+training+of+a+neural+network+statistical+parser%2E+In+Proceedings+of+ACL%2E)
16. Geoffrey E. Hinton, Nitish Srivastava, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. 2012. Improving neural networks by preventing co-adaptation of feature detectors. CoRR, abs/1207.0580. [find](https://scholar.google.com/scholar?q=Geoffrey+E%2E+Hinton%2C+Nitish+Srivastava%2C+Alex+Krizhevsky%2C+Ilya+Sutskever%2C+and+Ruslan+Salakhutdinov%2E+2012%2E+Improving+neural+networks+by+preventing+co%2Dadaptation+of+feature+detectors%2E+CoRR%2C+abs%2F1207%2E0580%2E)
17. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural computation, 9(8):1735–1780. [find](https://scholar.google.com/scholar?q=Sepp+Hochreiter+and+Ju%CC%88rgen+Schmidhuber%2E+1997%2E+Long+short%2Dterm+memory%2E+Neural+computation%2C+9%288%29%3A1735%E2%80%931780%2E)
18. Liang Huang and Kenji Sagae. 2010. Dynamic programming for linear-time incremental parsing. In Proceedings of ACL 2010. [find](https://scholar.google.com/scholar?q=Liang+Huang+and+Kenji+Sagae%2E+2010%2E+Dynamic+programming+for+linear%2Dtime+incremental+parsing%2E+In+Proceedings+of+ACL+2010%2E)
19. Liang Huang. 2008. Forest reranking: Discriminative parsing with non-local features. In Proceedings of the ACL: HLT, Columbus, OH, June. [find](https://scholar.google.com/scholar?q=Liang+Huang%2E+2008%2E+Forest+reranking%3A+Discriminative+parsing+with+non%2Dlocal+features%2E+In+Proceedings+of+the+ACL%3A+HLT%2C+Columbus%2C+OH%2C+June%2E)
20. Eliyahu Kiperwasser and Yoav Goldberg. 2016a. Easy-first dependency parsing with hierarchical tree lstms. arXiv preprint arXiv:1603.00375. [find](https://scholar.google.com/scholar?q=Eliyahu+Kiperwasser+and+Yoav+Goldberg%2E+2016a%2E+Easy%2Dfirst+dependency+parsing+with+hierarchical+tree+lstms%2E+arXiv+preprint+arXiv%3A1603%2E00375%2E)
21. Eliyahu Kiperwasser and Yoav Goldberg. 2016b. Simple and accurate dependency parsing using bidirectional LSTM feature representations. CoRR, abs/1603.04351. [our card](https://md.research.elamur.ai/free/en/papers/kiperwasser-2016-simple-accurate-dependency-parsing-bidirectional/)
22. Mitchell P Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. 1993. Building a large annotated corpus of english: The penn treebank. Computational linguistics, 19(2):313–330. [our card](https://md.research.elamur.ai/free/en/papers/marcus-1993-building-large-annotated-corpus-english/)
23. David McClosky, Eugene Charniak, and Mark Johnson. 2006. Reranking and self-training for parser adaptation. In Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, pages 337–344. Association for Co… [our card](https://md.research.elamur.ai/free/en/papers/mcclosky-2006-reranking-self-training-parser-adaptation/)
24. Haitao Mi and Liang Huang. 2015. Shift-reduce constituency parsing with dynamic programming and pos tag lattice. In Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. [find](https://scholar.google.com/scholar?q=Haitao+Mi+and+Liang+Huang%2E+2015%2E+Shift%2Dreduce+constituency+parsing+with+dynamic+programming+and+pos+tag+lattice%2E+In+Proceedings+of+the+2015+Conference+of+the+North+American+Chapter+of+the+Association+)
25. Slav Petrov and Dan Klein. 2007. Improved inference for unlexicalized parsing. In Proceedings of HLT-NAACL. [our card](https://md.research.elamur.ai/free/en/papers/petrov-2007-improved-inference-unlexicalized-parsing/)
26. Kenji Sagae and Alon Lavie. 2006. A best-first probabilistic shift-reduce parser. In Proceedings of the COLING/ACL on Main conference poster sessions, pages 691–698. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Kenji+Sagae+and+Alon+Lavie%2E+2006%2E+A+best%2Dfirst+probabilistic+shift%2Dreduce+parser%2E+In+Proceedings+of+the+COLING%2FACL+on+Main+conference+poster+sessions%2C+pages+691%E2%80%93698%2E+Association+for+Computational+Ling)
27. Djamé Seddah, Sandra Kübler, and Reut Tsarfaty. 2014. Introducing the spmrl 2014 shared task on parsing morphologically-rich languages. In Proceedings of the First Joint Workshop on Statistical Parsing of Morphologically Rich Languages and Syntactic Analysis of Non-Canonical Languages, pages 103–1… [find](https://scholar.google.com/scholar?q=Djame%CC%81+Seddah%2C+Sandra+Ku%CC%88bler%2C+and+Reut+Tsarfaty%2E+2014%2E+Introducing+the+spmrl+2014+shared+task+on+parsing+morphologically%2Drich+languages%2E+In+Proceedings+of+the+First+Joint+Workshop+on+Statistical+Pars)
28. Hiroyuki Shindo, Yusuke Miyao, Akinori Fujino, and Masaaki Nagata. 2012. Bayesian symbol-refined tree substitution grammars for syntactic parsing. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics: Long Papers-Volume 1, pages 440–448. Association for Computat… [find](https://scholar.google.com/scholar?q=Hiroyuki+Shindo%2C+Yusuke+Miyao%2C+Akinori+Fujino%2C+and+Masaaki+Nagata%2E+2012%2E+Bayesian+symbol%2Drefined+tree+substitution+grammars+for+syntactic+parsing%2E+In+Proceedings+of+the+50th+Annual+Meeting+of+the+Asso)
29. Richard Socher, John Bauer, Christopher D Manning, and Andrew Y Ng. 2013. Parsing with compositional vector grammars. In ACL (1), pages 455–465. [find](https://scholar.google.com/scholar?q=Richard+Socher%2C+John+Bauer%2C+Christopher+D+Manning%2C+and+Andrew+Y+Ng%2E+2013%2E+Parsing+with+compositional+vector+grammars%2E+In+ACL+%281%29%2C+pages+455%E2%80%93465%2E)
30. Martin Sundermeyer, Ralf Schlüter, and Hermann Ney. 2012. Lstm neural networks for language modeling. In INTERSPEECH, pages 194–197. [find](https://scholar.google.com/scholar?q=Martin+Sundermeyer%2C+Ralf+Schlu%CC%88ter%2C+and+Hermann+Ney%2E+2012%2E+Lstm+neural+networks+for+language+modeling%2E+In+INTERSPEECH%2C+pages+194%E2%80%93197%2E)
31. Ilya Sutskever, Oriol Vinyals, and Quoc V Le. 2014. Sequence to sequence learning with neural networks. In Advances in neural information processing systems, pages 3104–3112. [find](https://scholar.google.com/scholar?q=Ilya+Sutskever%2C+Oriol+Vinyals%2C+and+Quoc+V+Le%2E+2014%2E+Sequence+to+sequence+learning+with+neural+networks%2E+In+Advances+in+neural+information+processing+systems%2C+pages+3104%E2%80%933112%2E)
32. Le Quang Thang, Hiroshi Noji, and Yusuke Miyao. 2015. Optimal shift-reduce constituent parsing with structured perceptron. [find](https://scholar.google.com/scholar?q=Le+Quang+Thang%2C+Hiroshi+Noji%2C+and+Yusuke+Miyao%2E+2015%2E+Optimal+shift%2Dreduce+constituent+parsing+with+structured+perceptron%2E)
33. Oriol Vinyals, Łukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, and Geoffrey Hinton. 2015. Grammar as a foreign language. In Advances in Neural Information Processing Systems, pages 2755– 2763. [find](https://scholar.google.com/scholar?q=Oriol+Vinyals%2C+%C5%81ukasz+Kaiser%2C+Terry+Koo%2C+Slav+Petrov%2C+Ilya+Sutskever%2C+and+Geoffrey+Hinton%2E+2015%2E+Grammar+as+a+foreign+language%2E+In+Advances+in+Neural+Information+Processing+Systems%2C+pages+2755%E2%80%93+2763%2E)
34. Wenhui Wang and Baobao Chang. 2016. Graph-based dependency parsing with bidirectional lstm. In Proceedings of ACL. [find](https://scholar.google.com/scholar?q=Wenhui+Wang+and+Baobao+Chang%2E+2016%2E+Graph%2Dbased+dependency+parsing+with+bidirectional+lstm%2E+In+Proceedings+of+ACL%2E)
35. Taro Watanabe and Eiichiro Sumita. 2015. Transition-based neural constituent parsing. Proceedings of ACL-IJCNLP. [find](https://scholar.google.com/scholar?q=Taro+Watanabe+and+Eiichiro+Sumita%2E+2015%2E+Transition%2Dbased+neural+constituent+parsing%2E+Proceedings+of+ACL%2DIJCNLP%2E)
36. David Weiss, Chris Alberti, Michael Collins, and Slav Petrov. 2015. Structured training for neural network transition-based parsing. In Proceedings of ACL. [find](https://scholar.google.com/scholar?q=David+Weiss%2C+Chris+Alberti%2C+Michael+Collins%2C+and+Slav+Petrov%2E+2015%2E+Structured+training+for+neural+network+transition%2Dbased+parsing%2E+In+Proceedings+of+ACL%2E)
37. Matthew D. Zeiler. 2012. ADADELTA: an adaptive learning rate method. CoRR, abs/1212.5701. [our card](https://md.research.elamur.ai/free/en/papers/zeiler-2012-adadelta-adaptive-learning-rate-method/)
38. Muhua Zhu, Yue Zhang, Wenliang Chen, Min Zhang, and Jingbo Zhu. 2013. Fast and accurate shift-reduce constituent parsing. In ACL (1), pages 434–443. [our card](https://md.research.elamur.ai/free/en/papers/zhu-2013-fast-accurate-shift-reduce-constituent/)