---
title: "An Efficient Algorithm for Projective Dependency Parsing — Nivre 2003"
description: "Nivre defines a deterministic shift-reduce parser for projective dependency grammar. 30 references, cited by 269 papers here."
authors: ["Joakim Nivre"]
year: 2003
venue: "Proceedings of the Eighth International Workshop on Parsing Technologies"
source: "https://aclanthology.org/W03-3017/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/nivre-2003-efficient-algorithm-projective-dependency-parsing/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/nivre-2003-efficient-algorithm-projective-dependency-parsing/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2003](https://md.research.elamur.ai/free/en/papers/2003/) / An Efficient Algorithm for Projective Dependency Parsing

# An Efficient Algorithm for Projective Dependency Parsing

**Authors:** [Joakim Nivre](https://md.research.elamur.ai/free/en/authors/joakim-nivre/) · **Year:** 2003 · **Venue:** Proceedings of the Eighth International Workshop on Parsing Technologies **Link:** [aclanthology.org/W03-3017](https://aclanthology.org/W03-3017/) · **Licence:** [CC BY-NC-SA 3.0](https://creativecommons.org/licenses/by-nc-sa/3.0/) — summary only

[**475** citations](https://openalex.org/works?filter=cites:W81000870) OpenAlex, 2026-10-14 · [**269** citations in our library](https://md.research.elamur.ai/free/en/papers/nivre-2003-efficient-algorithm-projective-dependency-parsing/cited-by/) of the 140,884 papers whose bibliographies we read · [Proceedings of the Eighth International Workshop on Parsing Technologies](https://aclanthology.org/volumes/W03-30/) · [licence](https://creativecommons.org/licenses/by-nc-sa/3.0/)

- [Publisher's page](https://aclanthology.org/W03-3017/)
- [PDF](https://aclanthology.org/W03-3017.pdf)
- [OpenAlex](https://openalex.org/W81000870)

**Authors (1)**

1. [Nivre, Joakim](https://openalex.org/A5077063699) [Semantic Scholar](https://www.semanticscholar.org/author/1720988) · h 60 · 16,139 citations · 333 works

Citations and author metrics: OpenAlex, 2026-10-14; authors with the same name are not always told apart.

## What it is about

Nivre defines a deterministic shift-reduce parser for projective dependency grammar. It runs in time linear in the sentence length and always returns a graph that is projective and acyclic. Its transitions are Left-Arc, Right-Arc, Reduce and Shift, and a scheduling policy decides between them. In a pilot on about 4,000 words (257 sentences) of hand-annotated Swedish, parsed with a hand-written grammar of 126 rules, the mean attachment score is 80.0 with a fixed priority order, 87.8 with a rule that shifts when the stack top can still head the next token, and 89.0 with a further lookahead for shift/right-arc conflicts. The author gives a 95% interval of 85–93% and calls the evidence small.

## For Mova

- I1. en/src/parse.rs: in the static oracle, add the shift-or-reduce rule of the paper (shift when the stack top can still take the next word as a dependent, from the UD grammar of the `en` tables); measure cv LAS on the train folds, EWT test once per release.
- I2. en/src/parse.rs: the lookahead for shift against right-arc: when the stack top is a verb and the next word could be its post-modifier or the pre-modifier of the word after it, prefer shift; measure the share of such conflicts in EWT train and the cv LAS with and without the rule.
- I3. `en beam-curve`: measure parse time per sentence for greedy arc-standard against beam 8 on EWT test, to see how much time the beam costs against the LAS it buys, using the linear-time claim as the baseline.

The shift/reduce conflict rules are the part that transfers to `en/src/parse.rs`, which is arc-standard with a static oracle. The relevant chapters are 20-syntax-overview and 21-clause-structure, where the verb-modifier ambiguity is discussed. Measure first: how often the conflict in idea I2 occurs in EWT train, since the paper's pilot is too small to show a gain on its own.

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

## Cite

Cite as Joakim Nivre. 2003. An Efficient Algorithm for Projective Dependency Parsing. Proceedings of the Eighth International Workshop on Parsing Technologies.

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

```bibtex
@inproceedings{nivre2003efficient,
  title = {{An Efficient Algorithm for Projective Dependency Parsing}},
  author = {Joakim Nivre},
  booktitle = {Proceedings of the Eighth International Workshop on Parsing Technologies},
  year = {2003},
  url = {https://aclanthology.org/W03-3017/}
}
```

- [← previous Extended Gloss Overlaps as a Measure of Semantic Relatedness](https://md.research.elamur.ai/free/en/papers/banerjee-2003-extended-gloss-overlaps-as-measure/)
- [next → The Web as a Parallel Corpus](https://md.research.elamur.ai/free/en/papers/resnik-2003-web-as-parallel-corpus/)
- [↑ back to papers of 2003](https://md.research.elamur.ai/free/en/papers/2003/)

## References

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

1. Alfred V. Aho, Ravi Sethi, and Jerey D. Ullman. Compilers: Principles Techniques, and Tools . Addison Wesley, 1986. [find](https://scholar.google.com/scholar?q=Alfred+V%2E+Aho%2C+Ravi+Sethi%2C+and+Je%1Brey+D%2E+Ullman%2E+Compilers%3A+Principles+Techniques%2C+and+Tools+%2E+Addison+Wesley%2C+1986%2E)
2. Cristina Barbero, Leonardo Lesmo, Vincenzo Lombardo, and Paola Merlo. Integration of syntactic and lexical information in a hierarchical dependency grammar. In Sylvain Kahane and Alain Polguère, editors, Proceedings of the Workshop on Processing of Dependency-Based Grammars , pages 5867, Université… [find](https://scholar.google.com/scholar?q=Cristina+Barbero%2C+Leonardo+Lesmo%2C+Vincenzo+Lombardo%2C+and+Paola+Merlo%2E+Integration+of+syntactic+and+lexical+information+in+a+hierarchical+dependency+grammar%2E+In+Sylvain+Kahane+and+Alain+Polgu%C3%A8re%2C+edito)
3. Glenn Carroll and Eugene Charniak. Two experiments on learning probabilistic dependency grammars from corpora. Technical Report TR-92, Department of Computer Science, Brown University, 1992. [find](https://scholar.google.com/scholar?q=Glenn+Carroll+and+Eugene+Charniak%2E+Two+experiments+on+learning+probabilistic+dependency+grammars+from+corpora%2E+Technical+Report+TR%2D92%2C+Department+of+Computer+Science%2C+Brown+University%2C+1992%2E)
4. Michael Collins. A new statistical parser based on bigram lexical dependencies. In Proceedings of the 34th Annatual Meeting of the Association for Computational Linguistics , pages 184191, Santa Cruz, CA, 1996. [find](https://scholar.google.com/scholar?q=Michael+Collins%2E+A+new+statistical+parser+based+on+bigram+lexical+dependencies%2E+In+Proceedings+of+the+34th+Annatual+Meeting+of+the+Association+for+Computational+Linguistics+%2C+pages+184%15191%2C+Santa+Cruz)
5. Michael Collins. Three generative, lexicalised models for statistical parsing. In Proceedings of the 35th Annatual Meeting of the Association for Computational Linguistics , pages 16 23, Madrid, Spain, 1997. [our card](https://md.research.elamur.ai/free/en/papers/collins-1997-three-generative-lexicalised-models-statistical/)
6. Michael Collins. Head-Driven Statistical Models for Natural Language Parsing . PhD thesis, University of Pennsylvania, 1999. [find](https://scholar.google.com/scholar?q=Michael+Collins%2E+Head%2DDriven+Statistical+Models+for+Natural+Language+Parsing+%2E+PhD+thesis%2C+University+of+Pennsylvania%2C+1999%2E)
7. Michael Collins, Jan Haji£, Eric Brill, Lance Ramshaw, and Christoph Tillmann. A Statistical Parser of Czech. In Proceedings of 37th ACL Conference , pages 505512, University of Maryland, College Park, USA, 1999. [find](https://scholar.google.com/scholar?q=Michael+Collins%2C+Jan+Haji%C2%A3%2C+Eric+Brill%2C+Lance+Ramshaw%2C+and+Christoph+Tillmann%2E+A+Statistical+Parser+of+Czech%2E+In+Proceedings+of+37th+ACL+Conference+%2C+pages+505%15512%2C+University+of+Maryland%2C+College+Par)
8. Jacques Courtin and Damien Genthial. parsing. In Sylvain Kahane and Alain Polguère, editors, Proceedings of the Workshop on Processing of Dependency-Based Grammars , pages 95101, Université de Montréal, Quebec, Canada, August 1998. [find](https://scholar.google.com/scholar?q=Jacques+Courtin+and+Damien+Genthial%2E+parsing%2E+In+Sylvain+Kahane+and+Alain+Polgu%C3%A8re%2C+editors%2C+Proceedings+of+the+Workshop+on+Processing+of+Dependency%2DBased+Grammars+%2C+pages+95%15101%2C+Universit%C3%A9+de+Montr%C3%A9)
9. Michael A. Covington. A dependency parser for variable-word-order languages. Technical Report AI-1990-01, University of Georgia, Athens, GA, 1990. [find](https://scholar.google.com/scholar?q=Michael+A%2E+Covington%2E+A+dependency+parser+for+variable%2Dword%2Dorder+languages%2E+Technical+Report+AI%2D1990%2D01%2C+University+of+Georgia%2C+Athens%2C+GA%2C+1990%2E)
10. Michael A. Covington. Discontinuous dependency parsing of free and xed word order: Work in progress. Technical Report AI-1994-02, University of Georgia, Athens, GA, 1994. [find](https://scholar.google.com/scholar?q=Michael+A%2E+Covington%2E+Discontinuous+dependency+parsing+of+free+and+%1Cxed+word+order%3A+Work+in+progress%2E+Technical+Report+AI%2D1994%2D02%2C+University+of+Georgia%2C+Athens%2C+GA%2C+1994%2E)
11. Ralph Debusmann. A declarative grammar formalism for dependency grammar. Master's thesis, Computational Linguistics, Universität des Saarlandes, November 2001. [find](https://scholar.google.com/scholar?q=Ralph+Debusmann%2E+A+declarative+grammar+formalism+for+dependency+grammar%2E+Master%27s+thesis%2C+Computational+Linguistics%2C+Universit%C3%A4t+des+Saarlandes%2C+November+2001%2E)
12. Denys Duchier. Axiomatizing dependency parsing using set constraints. In Sixth Meeting on Mathematics of Language , pages 115126, Orlando, Florida, July 1999. [find](https://scholar.google.com/scholar?q=Denys+Duchier%2E+Axiomatizing+dependency+parsing+using+set+constraints%2E+In+Sixth+Meeting+on+Mathematics+of+Language+%2C+pages+115%15126%2C+Orlando%2C+Florida%2C+July+1999%2E)
13. Denys Duchier. Lexicalized syntax and topology for non-projective dependency grammar. In Joint Conference on Formal Grammars and Mathematics of Language FGMOL'01 , Helsinki, August 2001. [find](https://scholar.google.com/scholar?q=Denys+Duchier%2E+Lexicalized+syntax+and+topology+for+non%2Dprojective+dependency+grammar%2E+In+Joint+Conference+on+Formal+Grammars+and+Mathematics+of+Language+FGMOL%2701+%2C+Helsinki%2C+August+2001%2E)
14. Denys Duchier. Conguration of labeled trees under lexicalized constraints and principles. Journal of Language and Computation , 1, 2002. [find](https://scholar.google.com/scholar?q=Denys+Duchier%2E+Con%1Cguration+of+labeled+trees+under+lexicalized+constraints+and+principles%2E+Journal+of+Language+and+Computation+%2C+1%2C+2002%2E)
15. Jason M. Eisner. An empirical comparison of probability models for dependency grammar. Technical Report IRCS-96-11, Institute for Research in Cognitive Science, University of Pennsylvania, 1996. [find](https://scholar.google.com/scholar?q=Jason+M%2E+Eisner%2E+An+empirical+comparison+of+probability+models+for+dependency+grammar%2E+Technical+Report+IRCS%2D96%2D11%2C+Institute+for+Research+in+Cognitive+Science%2C+University+of+Pennsylvania%2C+1996%2E)
16. Jason M. Eisner. Three new probabilistic models for dependency parsing: An exploration. In Proceedings of COLING-96 , Copenhagen, 1996. [our card](https://md.research.elamur.ai/free/en/papers/eisner-1996-three-new-probabilistic-models-dependency/)
17. Jason M. Eisner. Bilexical grammars and their cubic-time parsing algorithms. In Harry Bunt and Anton Nijholt, editors, Advances in Probabilistic and Other Parsing Technologies . Kluwer, 2000. [find](https://scholar.google.com/scholar?q=Jason+M%2E+Eisner%2E+Bilexical+grammars+and+their+cubic%2Dtime+parsing+algorithms%2E+In+Harry+Bunt+and+Anton+Nijholt%2C+editors%2C+Advances+in+Probabilistic+and+Other+Parsing+Technologies+%2E+Kluwer%2C+2000%2E)
18. Haim Gaifman. Dependency systems and phrase-structure systems. Information and Control , 8:304337, 1965. [find](https://scholar.google.com/scholar?q=Haim+Gaifman%2E+Dependency+systems+and+phrase%2Dstructure+systems%2E+Information+and+Control+%2C+8%3A304%15337%2C+1965%2E)
19. David G. Hays. Dependency theory: 40:511525, 1964. [find](https://scholar.google.com/scholar?q=David+G%2E+Hays%2E+Dependency+theory%3A+40%3A511%15525%2C+1964%2E)
20. Richard A. Hudson. English Word Grammar . Blackwell, 1990. [find](https://scholar.google.com/scholar?q=Richard+A%2E+Hudson%2E+English+Word+Grammar+%2E+Blackwell%2C+1990%2E)
21. Mitchell P. Marcus. A Theory of Syntactic Recognition for Natural Language . MIT Press, 1980. [find](https://scholar.google.com/scholar?q=Mitchell+P%2E+Marcus%2E+A+Theory+of+Syntactic+Recognition+for+Natural+Language+%2E+MIT+Press%2C+1980%2E)
22. Hiroshi Maruyama. Structural disambiguation with constraint propagation. In Proceedings of the 28th ACL , pages 3138, Pittsburgh, PA, 1990. [find](https://scholar.google.com/scholar?q=Hiroshi+Maruyama%2E+Structural+disambiguation+with+constraint+propagation%2E+In+Proceedings+of+the+28th+ACL+%2C+pages+31%1538%2C+Pittsburgh%2C+PA%2C+1990%2E)
23. Igor Mel'cuk. Dependency Syntax: Theory and Practice . Press, 1988. Parsing with dependency relations and robust A formalism and some observations. Language , State University of New York [find](https://scholar.google.com/scholar?q=Igor+Mel%27cuk%2E+Dependency+Syntax%3A+Theory+and+Practice+%2E+Press%2C+1988%2E+Parsing+with+dependency+relations+and+robust+A+formalism+and+some+observations%2E+Language+%2C+State+University+of+New+York)
24. Wolfgang Menzel and Ingo Schröder. ing graded constraints. In Sylvain Kahane and Alain Polguère, editors, Proceedings of the Workshop on Processing of Dependency-Based Grammars , pages 7887, Université de Montréal, Quebec, Canada, August 1998. [find](https://scholar.google.com/scholar?q=Wolfgang+Menzel+and+Ingo+Schr%C3%B6der%2E+ing+graded+constraints%2E+In+Sylvain+Kahane+and+Alain+Polgu%C3%A8re%2C+editors%2C+Proceedings+of+the+Workshop+on+Processing+of+Dependency%2DBased+Grammars+%2C+pages+78%1587%2C+Universi)
25. Christer Samuelsson. A statistical theory of dependency syntax. In Proceedings COLING-2000 . Morgan Kaufmann, 2000. [find](https://scholar.google.com/scholar?q=Christer+Samuelsson%2E+A+statistical+theory+of+dependency+syntax%2E+In+Proceedings+COLING%2D2000+%2E+Morgan+Kaufmann%2C+2000%2E)
26. Petr Sgall, Eva Hajicova, and Jarmila Panevova. Pragmatic Aspects . Reidel, 1986. [find](https://scholar.google.com/scholar?q=Petr+Sgall%2C+Eva+Hajicova%2C+and+Jarmila+Panevova%2E+Pragmatic+Aspects+%2E+Reidel%2C+1986%2E)
27. Daniel Sleator and Davy Temperley. Report CMU-CS-91-196, Carnegie Mellon University, Computer Science, 1991. [find](https://scholar.google.com/scholar?q=Daniel+Sleator+and+Davy+Temperley%2E+Report+CMU%2DCS%2D91%2D196%2C+Carnegie+Mellon+University%2C+Computer+Science%2C+1991%2E)
28. Daniel Sleator and Davy Temperley. International Workshop on Parsing Technologies , 1993. [find](https://scholar.google.com/scholar?q=Daniel+Sleator+and+Davy+Temperley%2E+International+Workshop+on+Parsing+Technologies+%2C+1993%2E)
29. Stockholm Umeå Corpus. Version 1.0. University and Department of Linguistics, Stockholm University. ISBN 91-7191-348-3., August 1997. [find](https://scholar.google.com/scholar?q=Stockholm+Ume%C3%A5+Corpus%2E+Version+1%2E0%2E+University+and+Department+of+Linguistics%2C+Stockholm+University%2E+ISBN+91%2D7191%2D348%2D3%2E%2C+August+1997%2E)
30. Lucien Tesnière. Éléments de syntaxe structurale . Editions Klincksieck, 1959. Decision procedures for dependency parsing us-The Meaning of the Sentence in Its Parsing English with a link grammar. Technical Parsing English with a link grammar. In Third Produced by Department of Linguistics, Umeå [find](https://scholar.google.com/scholar?q=Lucien+Tesni%C3%A8re%2E+%C3%89l%C3%A9ments+de+syntaxe+structurale+%2E+Editions+Klincksieck%2C+1959%2E+Decision+procedures+for+dependency+parsing+us%2DThe+Meaning+of+the+Sentence+in+Its+Parsing+English+with+a+link+grammar%2E+Tec)