[Mova](https://md.mova.elamur.ai/free/en/) · [this page in HTML](https://mova.elamur.ai/free/en/docs/papers/zhang-2008-tale-two-parsers-investigating-combining/)

[home](https://md.mova.elamur.ai/free/en/) / [docs](https://md.mova.elamur.ai/free/en/docs/) / [papers](https://md.mova.elamur.ai/free/en/docs/papers/) / A Tale of Two Parsers: Investigating and Combining Graph-based and Transition-based Dependency Parsing

# A Tale of Two Parsers: Investigating and Combining Graph-based and Transition-based Dependency Parsing

**Authors:** [Yue Zhang](https://md.mova.elamur.ai/free/en/docs/papers/authors/yue-zhang/), [Stephen Clark](https://md.mova.elamur.ai/free/en/docs/papers/authors/stephen-clark/) · **Year:** 2008 · **Venue:** Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing (EMNLP) **Link:** [aclanthology.org/D08-1059](https://aclanthology.org/D08-1059/) (ACL Anthology D08-1059) **License of the paper:** [CC BY-NC-SA 3.0](https://creativecommons.org/licenses/by-nc-sa/3.0/) (ACL Anthology, before 2016) — [creativecommons.org/licenses/by-nc-sa/3.0](https://creativecommons.org/licenses/by-nc-sa/3.0/)

[**187** citations](https://openalex.org/works?filter=cites:W1598566484) openalex-snapshot · 2026-10-14[**163** citations in our library](https://md.mova.elamur.ai/free/en/docs/papers/cited-by/zhang-2008-tale-two-parsers-investigating-combining/) of the 140673 papers whose bibliographies we read[Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing](https://aclanthology.org/volumes/D08-1/)[licence](https://creativecommons.org/licenses/by-nc-sa/3.0/)

- [Publisher's page](https://aclanthology.org/D08-1059/)
- [PDF](https://aclanthology.org/D08-1059.pdf)
- [OpenAlex](https://openalex.org/W1598566484)

**Authors (2)**

1. [Yue Zhang](https://openalex.org/A5100333729) [ORCID](https://orcid.org/0000-0002-5214-2268) · h 59 · 13916 citations · 343 works
2. [Stephen Clark](https://openalex.org/A5057392864) [ORCID](https://orcid.org/0000-0002-2193-4705) · h 64 · 17686 citations · 441 works

Citations and author metrics from openalex-snapshot (2026-10-14); authors with the same name are not always told apart.

## Summary

The paper compares graph-based and transition-based dependency parsing within one framework based on beam search and a discriminatively trained perceptron. It shows that a transition-based parser does not have to be greedy: decoding with a beam of partial action sequences, combined with perceptron training with early update (stop and update as soon as the gold sequence falls out of the beam), gives a strong transition-based parser. A graph-based parser is formulated with the same beam-search decoder. Because the two approaches use different kinds of features, the authors combine them into a single model whose score sums both feature sets, and report that the combination improves over each parser alone on English and Chinese.

## How Mova uses it

- `en/src/parse.rs`: the English UD parser is an arc-standard transition system (SHIFT / LEFT(label) / RIGHT(label)) with weight tables trained by an averaged perceptron. Decoding uses a beam of 8 hypotheses, and training uses beam search with early update, as in this paper.
- Only the transition-based half is used; the graph-based parser and the combined model are not implemented.

## Effectiveness in Mova

Measured (beam with early update vs greedy, same features): EWT test LAS 79.00 → 79.77, dev 77.33 → 79.17, PUD 74.48 → 76.33. In the `en` crate summary with Mova's own tags: EWT UAS/LAS 84.2/79.8 with the beam vs 83.4/79.0 greedy.

---

👨‍🔬💥

## More ideas (a second reading)

- I1. `en/src/parse.rs`: add a second scorer over whole trees, with sibling and grandparent features on the arc set, and add its score to the beam ranking of the transition parser. Measure LAS on EWT test against the current arc-standard parser and on the two-fold check.
- I2. Beam curve: report dev LAS for beam sizes 1, 2, 4, 8 and 16 with the `en parse-eval` command, as the paper does for its curves. Pick the beam at the knee of the curve, not the largest one, to keep the parser fast.
- I3. Complete-match rate: add the share of sentences with a fully correct tree to `en parse-eval`. The paper reports it next to head accuracy, and it shows whether a parser is usable without repair.

Topics: [Dependency parsing](https://md.mova.elamur.ai/free/en/docs/papers/topics/dependency-parsing/)

## Cite

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

```
@inproceedings{zhang2008tale,
  title = {{A Tale of Two Parsers: Investigating and Combining Graph-based and Transition-based Dependency Parsing}},
  author = {Zhang, Yue and Clark, Stephen},
  booktitle = {Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing},
  year = {2008},
  url = {https://aclanthology.org/D08-1059/}
}
```

- [← previous STaR: Bootstrapping Reasoning With Reasoning](https://md.mova.elamur.ai/free/en/docs/papers/zelikman-2022-star-bootstrapping-reasoning-reasoning/)
- [next → Encoding Logical Relations of Chinese Complex Sentences within the Universal Dependencies Framework](https://md.mova.elamur.ai/free/en/docs/papers/zhu-2026-encoding-logical-relations-chinese-complex/)
- [↑ back to papers](https://md.mova.elamur.ai/free/en/docs/papers/)

## References

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

1. Sabine Buchholz and Erwin Marsi. 2006. CoNLL-X shared task on multilingual dependency parsing. In Proceedings of CoNLL, pages 149–164, New York City, USA, June. [find](https://scholar.google.com/scholar?q=Sabine+Buchholz+and+Erwin+Marsi%2E+2006%2E+CoNLL%2DX+shared+task+on+multilingual+dependency+parsing%2E+In+Proceedings+of+CoNLL%2C+pages+149%E2%80%93164%2C+New+York+City%2C+USA%2C+June%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/parsers-2006-buchholz-conll-x-shared-task-multilingual/)
2. Xavier Carreras, Mihai Surdeanu, and Lluis Marquez. 2006. Projective dependency parsing with perceptron. In Proceedings of CoNLL, New York City, USA, June. [find](https://scholar.google.com/scholar?q=Xavier+Carreras%2C+Mihai+Surdeanu%2C+and+Lluis+Marquez%2E+2006%2E+Projective+dependency+parsing+with+perceptron%2E+In+Proceedings+of+CoNLL%2C+New+York+City%2C+USA%2C+June%2E)
3. Xavier Carreras. 2007. Experiments with a higher-order projective dependency parser. In Proceedings of the CoNLL Shared Task Session of EMNLP/CoNLL, pages 957–961, Prague, Czech Republic, June. [find](https://scholar.google.com/scholar?q=Xavier+Carreras%2E+2007%2E+Experiments+with+a+higher%2Dorder+projective+dependency+parser%2E+In+Proceedings+of+the+CoNLL+Shared+Task+Session+of+EMNLP%2FCoNLL%2C+pages+957%E2%80%93961%2C+Prague%2C+Czech+Republic%2C+June%2E)
4. Michael Collins and Brian Roark. 2004. Incremental parsing with the perceptron algorithm. In Proceedings of ACL, pages 111–118, Barcelona, Spain, July. [find](https://scholar.google.com/scholar?q=Michael+Collins+and+Brian+Roark%2E+2004%2E+Incremental+parsing+with+the+perceptron+algorithm%2E+In+Proceedings+of+ACL%2C+pages+111%E2%80%93118%2C+Barcelona%2C+Spain%2C+July%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/collins-2004-incremental-parsing-perceptron-algorithm/)
5. Michael Collins. 2002. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. In Proceedings of EMNLP, pages 1–8, Philadelphia, USA, July. [find](https://scholar.google.com/scholar?q=Michael+Collins%2E+2002%2E+Discriminative+training+methods+for+hidden+markov+models%3A+Theory+and+experiments+with+perceptron+algorithms%2E+In+Proceedings+of+EMNLP%2C+pages+1%E2%80%938%2C+Philadelphia%2C+USA%2C+July%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/collins-2002-discriminative-training-methods-hidden-markov/)
6. Michael A. Covington. 2001. A fundamental algorithm for dependency parsing. In Proceedings of the ACM Southeast Conference, Athens, Georgia, March. [find](https://scholar.google.com/scholar?q=Michael+A%2E+Covington%2E+2001%2E+A+fundamental+algorithm+for+dependency+parsing%2E+In+Proceedings+of+the+ACM+Southeast+Conference%2C+Athens%2C+Georgia%2C+March%2E)
7. Xiangyu Duan, Jun Zhao, and Bo Xu. 2007. Probabilistic models for action-based chinese dependency parsing. In Proceedings of ECML/ECPPKDD, Warsaw, Poland, September. [find](https://scholar.google.com/scholar?q=Xiangyu+Duan%2C+Jun+Zhao%2C+and+Bo+Xu%2E+2007%2E+Probabilistic+models+for+action%2Dbased+chinese+dependency+parsing%2E+In+Proceedings+of+ECML%2FECPPKDD%2C+Warsaw%2C+Poland%2C+September%2E)
8. Jason Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proceedings of COLING, pages 340–345, Copenhagen, Denmark, August. [find](https://scholar.google.com/scholar?q=Jason+Eisner%2E+1996%2E+Three+new+probabilistic+models+for+dependency+parsing%3A+An+exploration%2E+In+Proceedings+of+COLING%2C+pages+340%E2%80%93345%2C+Copenhagen%2C+Denmark%2C+August%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/ast-1996-eisner-three-new-probabilistic-models-dependency/)
9. Johan Hall, Jens Nilsson, Joakim Nivre, Gülsen Eryigit, Beáta Megyesi, Mattias Nilsson, and Markus Saers. 2007. Single malt or blended? a study in multilingual parser optimization. In Proceedings of the CoNLL Shared Task Session of EMNLP/CoNLL, pages 933– 939, Prague, Czech Republic, June. [find](https://scholar.google.com/scholar?q=Johan+Hall%2C+Jens+Nilsson%2C+Joakim+Nivre%2C+Gu%CC%88lsen+Eryigit%2C+Bea%CC%81ta+Megyesi%2C+Mattias+Nilsson%2C+and+Markus+Saers%2E+2007%2E+Single+malt+or+blended%3F+a+study+in+multilingual+parser+optimization%2E+In+Proceedings+of)
10. Keith Hall. 2007. K-best spanning tree parsing. In Proceedings of ACL, Prague, Czech Republic, June. [find](https://scholar.google.com/scholar?q=Keith+Hall%2E+2007%2E+K%2Dbest+spanning+tree+parsing%2E+In+Proceedings+of+ACL%2C+Prague%2C+Czech+Republic%2C+June%2E)
11. Richard Johansson and Pierre Nugues. 2006. Investigating multilingual dependency parsing. In Proceedings of CoNLL, pages 206–210, New York City, USA, June. [find](https://scholar.google.com/scholar?q=Richard+Johansson+and+Pierre+Nugues%2E+2006%2E+Investigating+multilingual+dependency+parsing%2E+In+Proceedings+of+CoNLL%2C+pages+206%E2%80%93210%2C+New+York+City%2C+USA%2C+June%2E)
12. Richard Johansson and Pierre Nugues. 2007. Incremental dependency parsing using online learning. In Proceedings of the CoNLL/EMNLP, pages 1134–1138, Prague, Czech Republic. [find](https://scholar.google.com/scholar?q=Richard+Johansson+and+Pierre+Nugues%2E+2007%2E+Incremental+dependency+parsing+using+online+learning%2E+In+Proceedings+of+the+CoNLL%2FEMNLP%2C+pages+1134%E2%80%931138%2C+Prague%2C+Czech+Republic%2E)
13. Philip Koehn, Franz Och, and Daniel Marcu. 2003. Statistical phrase-based translation. In Proceedings of NAACL/HLT, Edmonton, Canada, May. [find](https://scholar.google.com/scholar?q=Philip+Koehn%2C+Franz+Och%2C+and+Daniel+Marcu%2E+2003%2E+Statistical+phrase%2Dbased+translation%2E+In+Proceedings+of+NAACL%2FHLT%2C+Edmonton%2C+Canada%2C+May%2E)
14. Terry Koo, Xavier Carreras, and Michael Collins. 2008. Simple semi-supervised dependency parsing. In Proceedings of ACL/HLT, pages 595–603, Columbus, Ohio, June. [find](https://scholar.google.com/scholar?q=Terry+Koo%2C+Xavier+Carreras%2C+and+Michael+Collins%2E+2008%2E+Simple+semi%2Dsupervised+dependency+parsing%2E+In+Proceedings+of+ACL%2FHLT%2C+pages+595%E2%80%93603%2C+Columbus%2C+Ohio%2C+June%2E)
15. Ryan McDonald and Joakim Nivre. 2007. Characterizing the errors of data-driven dependency parsing models. In Proceedings of EMNLP/CoNLL, pages 122– 131, Prague, Czech Republic, June. [find](https://scholar.google.com/scholar?q=Ryan+McDonald+and+Joakim+Nivre%2E+2007%2E+Characterizing+the+errors+of+data%2Ddriven+dependency+parsing+models%2E+In+Proceedings+of+EMNLP%2FCoNLL%2C+pages+122%E2%80%93+131%2C+Prague%2C+Czech+Republic%2C+June%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/missing4-2007-mcdonald-characterizing-errors-data-driven-dependency/)
16. R McDonald and F Pereira. 2006. Online learning of approximate dependency parsing algorithms. In In Proc. of EACL, pages 81–88, Trento, Italy, April. [find](https://scholar.google.com/scholar?q=R+McDonald+and+F+Pereira%2E+2006%2E+Online+learning+of+approximate+dependency+parsing+algorithms%2E+In+In+Proc%2E+of+EACL%2C+pages+81%E2%80%9388%2C+Trento%2C+Italy%2C+April%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/continual-2006-mcdonald-online-learning-approximate-dependency-parsing/)
17. Ryan McDonald, Koby Crammer, and Fernando Pereira. 2005. Online large-margin training of dependency parsers. In Proceedings of ACL, pages 91–98, Ann Arbor, Michigan, June. [find](https://scholar.google.com/scholar?q=Ryan+McDonald%2C+Koby+Crammer%2C+and+Fernando+Pereira%2E+2005%2E+Online+large%2Dmargin+training+of+dependency+parsers%2E+In+Proceedings+of+ACL%2C+pages+91%E2%80%9398%2C+Ann+Arbor%2C+Michigan%2C+June%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/narrative-2005-mcdonald-online-large-margin-training-dependency/)
18. Tetsuji Nakagawa. 2007. Multilingual dependency parsing using global features. In Proceedings of the CoNLL Shared Task Session of EMNLP/CoNLL, pages 952–956, Prague, Czech Republic, June. [find](https://scholar.google.com/scholar?q=Tetsuji+Nakagawa%2E+2007%2E+Multilingual+dependency+parsing+using+global+features%2E+In+Proceedings+of+the+CoNLL+Shared+Task+Session+of+EMNLP%2FCoNLL%2C+pages+952%E2%80%93956%2C+Prague%2C+Czech+Republic%2C+June%2E)
19. Joakim Nivre and Ryan McDonald. 2008. Integrating graph-based and transition-based dependency parsers. In Proceedings of ACL/HLT, pages 950–958, Columbus, Ohio, June. [find](https://scholar.google.com/scholar?q=Joakim+Nivre+and+Ryan+McDonald%2E+2008%2E+Integrating+graph%2Dbased+and+transition%2Dbased+dependency+parsers%2E+In+Proceedings+of+ACL%2FHLT%2C+pages+950%E2%80%93958%2C+Columbus%2C+Ohio%2C+June%2E)
20. Joakim Nivre, Johan Hall, Jens Nilsson, Gülşen Eryiǧit, and Svetoslav Marinov. 2006. Labeled pseudo-projective dependency parsing with support vector machines. In Proceedings of CoNLL, pages 221–225, New York City, USA, June. [find](https://scholar.google.com/scholar?q=Joakim+Nivre%2C+Johan+Hall%2C+Jens+Nilsson%2C+Gu%CC%88ls%CC%A7en+Eryig%CC%8Cit%2C+and+Svetoslav+Marinov%2E+2006%2E+Labeled+pseudo%2Dprojective+dependency+parsing+with+support+vector+machines%2E+In+Proceedings+of+CoNLL%2C+pages+221%E2%80%9322)
21. K Sagae and A Lavie. 2006a. Parser combination by reparsing. In In Proc. HLT/NAACL, pages 129–132, New York City, USA, June. [find](https://scholar.google.com/scholar?q=K+Sagae+and+A+Lavie%2E+2006a%2E+Parser+combination+by+reparsing%2E+In+In+Proc%2E+HLT%2FNAACL%2C+pages+129%E2%80%93132%2C+New+York+City%2C+USA%2C+June%2E)
22. Kenji Sagae and Alon Lavie. 2006b. A best-first probabilistic shift-reduce parser. In Proceedings of COL-ING/ACL (poster), pages 691–698, Sydney, Australia, July. [find](https://scholar.google.com/scholar?q=Kenji+Sagae+and+Alon+Lavie%2E+2006b%2E+A+best%2Dfirst+probabilistic+shift%2Dreduce+parser%2E+In+Proceedings+of+COL%2DING%2FACL+%28poster%29%2C+pages+691%E2%80%93698%2C+Sydney%2C+Australia%2C+July%2E)
23. Honglin Sun and Daniel Jurafsky. 2004. Shallow semantic parsing of Chinese. In Proceedings of NAACL/HLT, Boston, USA, May. [find](https://scholar.google.com/scholar?q=Honglin+Sun+and+Daniel+Jurafsky%2E+2004%2E+Shallow+semantic+parsing+of+Chinese%2E+In+Proceedings+of+NAACL%2FHLT%2C+Boston%2C+USA%2C+May%2E)
24. H Yamada and Y Matsumoto. 2003. Statistical dependency analysis using support vector machines. In Proceedings of IWPT, Nancy, France, April. [find](https://scholar.google.com/scholar?q=H+Yamada+and+Y+Matsumoto%2E+2003%2E+Statistical+dependency+analysis+using+support+vector+machines%2E+In+Proceedings+of+IWPT%2C+Nancy%2C+France%2C+April%2E)