An Efficient Algorithm for Projective Dependency Parsing

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.

Library summary

The Research library's own summary of the paper, in our words — not the paper's text.

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/W03-3017.pdf

Summary

Nivre addresses the cost of dependency parsing. Dynamic programming and constraint-based methods are expensive, and the paper asks whether a deterministic, shift-reduce-style procedure could work instead. The parser uses a stack, the remaining input, and a growing set of arcs. It has four actions: Left-Arc, Right-Arc, Reduce and Shift. Each action is licensed by a very simple grammar of "directed D-rules," which state only whether one word (or tag) may head another to its left or right. The paper proves two properties. The parser runs in linear time in sentence length, and its output is always projective and acyclic. When a sentence cannot be fully connected, the result is a set of well-formed fragments rather than a failure.

The experiment used a small hand-annotated sample of the Stockholm-Umeå Corpus (SUC), parsed with a 126-rule hand-written grammar. The best scheduling policy reached an attachment score of about 89%, which the paper conservatively reports as above 85%. This matters because it shows that fast, greedy, robust dependency parsing can be reasonably accurate.

Key points

Transition system: The parser state is a triple (stack, input, arcs) with four transitions. Arc-creating actions immediately pop or push the dependent, which rules out 2-cycles. A Reduce is allowed only when the top node already has a head.
Formal guarantees:
- Worst-case running time is linear in input length.
- Every output graph is projective and acyclic.
- A rejected string still yields connected components, each a valid analysis of a substring.
Data: About 4000 words from SUC, drawn as 16 connected segments totalling 257 sentences. The author annotated the dependencies by hand. Gold part-of-speech tags were used as input.
Grammar: 126 hand-crafted rules, of which 90 are left-headed and 36 right-headed. Most rules refer only to POS tags.
Results:
- Three scheduling policies were compared: baseline, S/R and S/RA. Accuracy rose with each more refined policy, and all differences were significant under a paired t-test at α = .05.
- The best parser scored a mean of 89.0 with a standard deviation of 10.6, and its 95% confidence interval is roughly 85–93%.
- For reference, the paper cites roughly 90–91% for English and 80% for Czech from Eisner and Collins et al.

Interesting ideas

Separate the transition system from the decision policy. The same four actions yield different parsers depending on how conflicts are resolved. This makes it easy to swap a hand rule for a statistical classifier later, a direction the paper itself suggests, without touching the correctness proofs.
Build well-formedness into the actions. Popping or pushing the dependent at the moment an arc is created means cycles and non-projective arcs can never appear. No post-hoc validation is needed. This is a useful pattern for any incremental structure builder.
Treat partial output as a robustness feature. Instead of failing on ungrammatical or unusual input, the parser returns well-formed fragments. Downstream tasks such as information retrieval can still use these, which suits noisy web text or under-resourced languages.
Use cheap, linguistically motivated tie-breakers. The S/R rule shifts only if the stack top could transitively head the next token. The S/RA rule prefers to read a word after a verb as a pre-modifier of the following word. Small heuristics like these gave measurable gains, a good first step before training data exists.
Report uncertainty honestly for small test sets. The paper gives per-sentence mean scores with standard deviation, uses paired significance tests, and states a confidence interval. It frames the headline claim at the interval's lower bound, which is a sensible habit for small hand-annotated evaluation sets, such as new Ukrainian treebank samples.

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/}
}

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.

Alfred V. Aho, Ravi Sethi, and Jerey D. Ullman. Compilers: Principles Techniques, and Tools . Addison Wesley, 1986. find
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
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
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
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
Michael Collins. Head-Driven Statistical Models for Natural Language Parsing . PhD thesis, University of Pennsylvania, 1999. find
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
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
Michael A. Covington. A dependency parser for variable-word-order languages. Technical Report AI-1990-01, University of Georgia, Athens, GA, 1990. find
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
Ralph Debusmann. A declarative grammar formalism for dependency grammar. Master's thesis, Computational Linguistics, Universität des Saarlandes, November 2001. find
Denys Duchier. Axiomatizing dependency parsing using set constraints. In Sixth Meeting on Mathematics of Language , pages 115126, Orlando, Florida, July 1999. find
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
Denys Duchier. Conguration of labeled trees under lexicalized constraints and principles. Journal of Language and Computation , 1, 2002. find
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
Jason M. Eisner. Three new probabilistic models for dependency parsing: An exploration. In Proceedings of COLING-96 , Copenhagen, 1996. find our card
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
Haim Gaifman. Dependency systems and phrase-structure systems. Information and Control , 8:304337, 1965. find
David G. Hays. Dependency theory: 40:511525, 1964. find
Richard A. Hudson. English Word Grammar . Blackwell, 1990. find
Mitchell P. Marcus. A Theory of Syntactic Recognition for Natural Language . MIT Press, 1980. find
Hiroshi Maruyama. Structural disambiguation with constraint propagation. In Proceedings of the 28th ACL , pages 3138, Pittsburgh, PA, 1990. find
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
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
Christer Samuelsson. A statistical theory of dependency syntax. In Proceedings COLING-2000 . Morgan Kaufmann, 2000. find
Petr Sgall, Eva Hajicova, and Jarmila Panevova. Pragmatic Aspects . Reidel, 1986. find
Daniel Sleator and Davy Temperley. Report CMU-CS-91-196, Carnegie Mellon University, Computer Science, 1991. find
Daniel Sleator and Davy Temperley. International Workshop on Parsing Technologies , 1993. find
Stockholm Umeå Corpus. Version 1.0. University and Department of Linguistics, Stockholm University. ISBN 91-7191-348-3., August 1997. find
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