[Mova](https://md.mova.elamur.ai/free/en/) · [this page in HTML](https://mova.elamur.ai/free/en/docs/papers/parsers-2003-nivre-efficient-algorithm-projective-dependency-parsing/)

[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/) / [English](https://md.mova.elamur.ai/free/en/docs/papers/en/) / An Efficient Algorithm for Projective Dependency Parsing

# An Efficient Algorithm for Projective Dependency Parsing

**Authors:** [Joakim Nivre](https://md.mova.elamur.ai/free/en/docs/papers/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

[**269** citations in our library](https://md.mova.elamur.ai/free/en/docs/papers/cited-by/parsers-2003-nivre-efficient-algorithm-projective-dependency-parsing/) of the 140673 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)

**Authors (1)**

1. Nivre, Joakim

Citations and author metrics from OpenAlex (); 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.

## Ideas

- 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.

## For Mova

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.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{nivre2003efficient,
  title = {{An Efficient Algorithm for Projective Dependency Parsing}},
  author = {Nivre, Joakim},
  booktitle = {Proceedings of the Eighth International Workshop on Parsing Technologies},
  year = {2003},
  url = {https://aclanthology.org/W03-3017/}
}
```

- [← previous On building a more efficient grammar by exploiting types](https://md.mova.elamur.ai/free/en/docs/papers/parsers-2000-flickinger-building-more-efficient-grammar/)
- [next → Statistical Dependency Analysis with Support Vector Machines](https://md.mova.elamur.ai/free/en/docs/papers/parsers-2003-yamada-statistical-dependency-analysis-support-vector/)
- [↑ back to English](https://md.mova.elamur.ai/free/en/docs/papers/en/)

## References

30 references, 1 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. [find](https://scholar.google.com/scholar?q=Michael+Collins%2E+Three+generative%2C+lexicalised+models+for+statistical+parsing%2E+In+Proceedings+of+the+35th+Annatual+Meeting+of+the+Association+for+Computational+Linguistics+%2C+pages+16%15+23%2C+Madrid%2C+Spai)
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. [find](https://scholar.google.com/scholar?q=Jason+M%2E+Eisner%2E+Three+new+probabilistic+models+for+dependency+parsing%3A+An+exploration%2E+In+Proceedings+of+COLING%2D96+%2C+Copenhagen%2C+1996%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/ast-1996-eisner-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)