---
title: "Shift-Reduce Dependency DAG Parsing — Sagae 2008"
description: "Most data-driven dependency parsers assume a tree, in which every word has exactly… 89.0 precision. 22 references, cited by 44 papers here."
authors: ["Kenji Sagae", "Jun'ichi Tsujii"]
year: 2008
venue: "Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008)"
source: "https://aclanthology.org/C08-1095/"
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/sagae-2008-shift-reduce-dependency-dag-parsing/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/sagae-2008-shift-reduce-dependency-dag-parsing/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2008](https://md.research.elamur.ai/free/en/papers/2008/) / Shift-Reduce Dependency DAG Parsing

# Shift-Reduce Dependency DAG Parsing

**Authors:** [Kenji Sagae](https://md.research.elamur.ai/free/en/authors/kenji-sagae/) and [Jun'ichi Tsujii](https://md.research.elamur.ai/free/en/authors/jun-ichi-tsujii/) · **Year:** 2008 · **Venue:** [Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008)](https://md.research.elamur.ai/free/en/venues/coling/) ([COLING 2008](https://md.research.elamur.ai/free/en/venues/coling/2008/)) · **Publisher:** [International Committee on Computational Linguistics (ICCL)](https://md.research.elamur.ai/free/en/publishers/international-committee-on-computational-linguistics-iccl/) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/C08-1095/) · [PDF](https://aclanthology.org/C08-1095.pdf) · [OpenAlex](https://openalex.org/W2125225769)

**Citations:** 80 citations (OpenAlex, 2026-10-14) · [44](https://md.research.elamur.ai/free/en/papers/sagae-2008-shift-reduce-dependency-dag-parsing/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## Summary
Most data-driven dependency parsers assume a tree, in which every word has exactly one head. Many phenomena need words with several heads, which gives a directed acyclic graph (DAG). Examples are control, relative clauses, long-distance dependencies, anaphora and semantic predicate-argument relations. Sagae and Tsujii extend transition-based shift-reduce parsing to cover these cases, using both Nivre's basic bottom-up algorithm and its arc-eager variant. They add two actions, left-attach and right-attach, which create an arc but keep the dependent available for further heads. The core algorithm outputs projective DAGs. Pseudo-projective transformations and an extra arc-reversing transform recover non-projective arcs. Decisions come from maximum entropy classifiers with beam search. The authors test the approach on English HPSG predicate-argument dependencies from the HPSG Treebank and on the Danish Dependency Treebank. It outperforms tree-only baselines and earlier systems, including McDonald et al.'s graph-based approximate inference and HPSG-based parsers. The method costs about as much as tree parsing. This shows that deeper, graph-shaped analyses can be produced without a full lexicalized grammar formalism.

## Key points
- **English HPSG predicate-argument data (labeled):** DAG-beam reaches 89.0 precision, 88.5 recall and 88.7 F-score. The comparison systems score lower:
  - a tree-only parser that keeps only each word's closest head: F 87.0, recall 84.3;
  - Sagae et al.: F 88.2;
  - Miyao & Tsujii: F 84.6.
- **Danish Dependency Treebank (unlabeled):** DAG-beam scores F 87.2, against 85.0 for tree-only and 85.6 for McDonald et al. Labeled DAG F-score is 82.4.
- **Danish arc types:**
  - long-distance dependencies: 83.2 precision, 82.0 recall;
  - anaphoric reference links: 84.9 precision, 84.4 recall.
- **Danish pseudo-projective round trip:** transformation followed by detransformation is accurate to 99.4% precision and 98.8% recall. Reducing the beam width to 1 costs only about 1.5 points.
- **Danish data split:** the split follows McDonald et al. (2006), and graphs containing cycles were discarded so results are directly comparable.

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

## Institutions

- [University of Southern California](https://md.research.elamur.ai/free/en/universities/university-of-southern-california/) — University, Los Angeles, United States · 162 works · 35,836 citations
- [The University of Tokyo](https://md.research.elamur.ai/free/en/universities/the-university-of-tokyo/) — University, Tokyo, Japan · 90 works · 9,156 citations
- [University of Manchester](https://md.research.elamur.ai/free/en/universities/university-of-manchester/) — University, Manchester, United Kingdom · 87 works · 44,938 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 16,667 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 16,194 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 16,039 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 15,891 works

## Cite

Cite as: Kenji Sagae and Jun'ichi Tsujii. 2008. Shift-Reduce Dependency DAG Parsing. Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008).

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

```bibtex
@inproceedings{sagae2008shift,
  title = {{Shift-Reduce Dependency DAG Parsing}},
  author = {Kenji Sagae and Jun'ichi Tsujii},
  booktitle = {Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008)},
  year = {2008},
  doi = {10.3115/1599081.1599176},
  url = {https://doi.org/10.3115/1599081.1599176}
}
```

- [← previous Dependency Parsing of Turkish](https://md.research.elamur.ai/free/en/papers/eryigit-2008-dependency-parsing-turkish/)
- [next → MASC: the Manually Annotated Sub-Corpus of American English](https://md.research.elamur.ai/free/en/papers/ide-2008-masc-manually-annotated-sub-corpus/)
- [↑ back to papers of 2008](https://md.research.elamur.ai/free/en/papers/2008/)

## References

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

1. Briscoe, T., Carroll, J. and Watson, R. 2006. [The second release of the RASP system](https://md.research.elamur.ai/free/en/papers/briscoe-2006-second-release-rasp-system/). In Proceedings of the COLING/ACL-06 Demo Session.
2. Buchholz, Sabine and Erwin Marsi. 2006. [CoNLL-X Shared Task on Multilingual Dependency Parsing](https://md.research.elamur.ai/free/en/papers/buchholz-2006-conll-x-shared-task-multilingual/). In Proceedings of the 10th Conference on Computational Natural Language Learning (CoNLL-X) Shared Task session.
3. Clark, Stephen, Julia Hockenmaier, and Mark Steedman. 2002. Building Deep Dependency Structures using a Wide-Coverage CCG Parser. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics (ACL). [find](https://scholar.google.com/scholar?q=Clark%2C+Stephen%2C+Julia+Hockenmaier%2C+and+Mark+Steedman%2E+2002%2E+Building+Deep+Dependency+Structures+using+a+Wide%2DCoverage+CCG+Parser%2E+In+Proceedings+of+the+40th+Annual+Meeting+of+the+Association+for+Compu)
4. Covington, Michael A. 2001. A fundamental algorithm for dependency parsing. In Proceedings of the Annual ACM Southeast Conference, 95-102. [find](https://scholar.google.com/scholar?q=Covington%2C+Michael+A%2E+2001%2E+A+fundamental+algorithm+for+dependency+parsing%2E+In+Proceedings+of+the+Annual+ACM+Southeast+Conference%2C+95%2D102%2E)
5. Erkan, Gunes, Arzucan Ozgur, and Dragomir R. Radev. 2007. Semisupervised classification for extracting protein interaction sentences using dependency parsing. In Proceedings of CoNLL-EMNLP. [find](https://scholar.google.com/scholar?q=Erkan%2C+Gunes%2C+Arzucan+Ozgur%2C+and+Dragomir+R%2E+Radev%2E+2007%2E+Semisupervised+classification+for+extracting+protein+interaction+sentences+using+dependency+parsing%2E+In+Proceedings+of+CoNLL%2DEMNLP%2E)
6. Hudson, Richard. 1984. Word Grammar. Oxford: Blackwell. [find](https://scholar.google.com/scholar?q=Hudson%2C+Richard%2E+1984%2E+Word+Grammar%2E+Oxford%3A+Blackwell%2E)
7. Hudson, Richard. 2005. Word Grammar. In K. Brown (Ed.), Encyclopedia of Language and Linguistics (second ed., pp 633-642). Elsevier. [find](https://scholar.google.com/scholar?q=Hudson%2C+Richard%2E+2005%2E+Word+Grammar%2E+In+K%2E+Brown+%28Ed%2E%29%2C+Encyclopedia+of+Language+and+Linguistics+%28second+ed%2E%2C+pp+633%2D642%29%2E+Elsevier%2E)
8. Hockenmaier, Julia and Mark Steedman. 2007. [CCGbank: a corpus of CCG derivations and dependency structures extracted from the Penn Treebank](https://md.research.elamur.ai/free/en/papers/hockenmaier-2007-ccgbank-corpus-ccg-derivations-dependency/). In Computational Linguistics 33(3), pp 355-396, MIT press.
9. Kromann, Matthias T. 2003. The Danish dependency treebank and the underlying linguistic theory. In Proceedings of the Second Workshop on Treebanks and Linguistic Theories (TLT). [find](https://scholar.google.com/scholar?q=Kromann%2C+Matthias+T%2E+2003%2E+The+Danish+dependency+treebank+and+the+underlying+linguistic+theory%2E+In+Proceedings+of+the+Second+Workshop+on+Treebanks+and+Linguistic+Theories+%28TLT%29%2E)
10. McDonald, Ryan and Fernando Pereira. 2006. [Online learning of approximate dependency parsing algorithms](https://md.research.elamur.ai/free/en/papers/mcdonald-2006-online-learning-approximate-dependency-parsing/). In Proceedings of the 11th Conference of the European Chapter of the Association for Computational Linguistics (EACL).
11. McDonald, Ryan, Fernando Pereira, Kiril Ribarov and Jan Hajic. 2005. [Non-projective Dependency Parsing using Spanning Tree Algorithms](https://md.research.elamur.ai/free/en/papers/mcdonald-2005-non-projective-dependency-parsing-spanning/). In Proceedings of the Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT-EMNLP).
12. Miyao, Yusuke, Takashi Ninomiya, and Jun’ichi Tsujii. 2004. Corpus-oriented grammar development for acquiring a Head-driven Phrase Structure Grammar from the Penn Treebank. In Proceedings of the International Joint Conference on Natural Language Processing (IJCNLP). [find](https://scholar.google.com/scholar?q=Miyao%2C+Yusuke%2C+Takashi+Ninomiya%2C+and+Jun%E2%80%99ichi+Tsujii%2E+2004%2E+Corpus%2Doriented+grammar+development+for+acquiring+a+Head%2Ddriven+Phrase+Structure+Grammar+from+the+Penn+Treebank%2E+In+Proceedings+of+the+Inter)
13. Miyao Yusuke and Jun'ichi Tsujii. 2005. [Probabilistic disambiguation models for wide-coverage HPSG parsing](https://md.research.elamur.ai/free/en/papers/miyao-2005-probabilistic-disambiguation-models-wide-coverage/). In Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics.
14. Nivre, Joakim. 2004. [Incrementality in Deterministic Dependency Parsing](https://md.research.elamur.ai/free/en/papers/nivre-2004-incrementality-deterministic-dependency-parsing/). In Incremental Parsing: Bringing Engineering and Cognition Together (Workshop at ACL-2004).
15. Nivre, Joakim, Johan Hall, Sandra Kübler, Ryan McDonald, Jens Nilsson, Sebastian Riedel, Deniz Yuret. 2007. In Proceedings of the CoNLL 2007 Shared Task in the Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning. [find](https://scholar.google.com/scholar?q=Nivre%2C+Joakim%2C+Johan+Hall%2C+Sandra+K%C3%BCbler%2C+Ryan+McDonald%2C+Jens+Nilsson%2C+Sebastian+Riedel%2C+Deniz+Yuret%2E+2007%2E+In+Proceedings+of+the+CoNLL+2007+Shared+Task+in+the+Joint+Conference+on+Empirical+Methods+in)
16. Nivre, Joakim. and Jens Nilsson. 2005. [Pseudo-Projective Dependency Parsing](https://md.research.elamur.ai/free/en/papers/nivre-2005-pseudo-projective-dependency-parsing/). In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL), pp. 99-106.
17. Nivre, Joakim. 2007. Incremental non-projective dependency parsing. In Proceedings of Human Language Technologies: The Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL-HLT’07). [find](https://scholar.google.com/scholar?q=Nivre%2C+Joakim%2E+2007%2E+Incremental+non%2Dprojective+dependency+parsing%2E+In+Proceedings+of+Human+Language+Technologies%3A+The+Annual+Conference+of+the+North+American+Chapter+of+the+Association+for+Computatio)
18. Saetre, R., Sagae, K., and Tsujii, J. 2007. Syntactic features for protein-protein interaction extraction. In Proceedings of the International Symposium on Languages in Biology and Medicine (LBM short oral presentations). [find](https://scholar.google.com/scholar?q=Saetre%2C+R%2E%2C+Sagae%2C+K%2E%2C+and+Tsujii%2C+J%2E+2007%2E+Syntactic+features+for+protein%2Dprotein+interaction+extraction%2E+In+Proceedings+of+the+International+Symposium+on+Languages+in+Biology+and+Medicine+%28LBM+short)
19. Sagae, Kenji., Yusuke Miyao Jun’ichi and Tsujii. 2007. HPSG Parsing with shallow dependency constraints. In Proceedings of the 44th Meeting of the Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Sagae%2C+Kenji%2E%2C+Yusuke+Miyao+Jun%E2%80%99ichi+and+Tsujii%2E+2007%2E+HPSG+Parsing+with+shallow+dependency+constraints%2E+In+Proceedings+of+the+44th+Meeting+of+the+Association+for+Computational+Linguistics%2E)
20. Sagae, K., Tsujii, J. 2007. [Dependency parsing and domain adaptation with LR models and parser ensembles](https://md.research.elamur.ai/free/en/papers/sagae-2007-dependency-parsing-domain-adaptation-lr/). In Proceedings of the CoNLL 2007 Shared Task. in EMNLP-CoNLL.
21. Tsuruoka, Yoshimasa and Tsujii, Jun’ichi. 2005. [Bidirectional inference with the easiest-first strategy for tagging sequence data](https://md.research.elamur.ai/free/en/papers/tsuruoka-2005-bidirectional-inference-easiest-first-strategy/). In Proceedings of the Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT-EMNLP), pp. 523-530.
22. Wang, Mengqiu, Noah A. Smith, and Teruko Mitamura. 2007. [What is the Jeopardy Model? A Quasi-Synchronous Grammar for QA](https://md.research.elamur.ai/free/en/papers/wang-2007-what-is-jeopardy-model-quasi/). In Proceedings of the Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL).

*Updated 29 October 2026*