Dependency Parsing (Summer 2021)

General Information

Instructors: Kilian Evang
Jakub Waszczuk
Lectures: Tuesday, 14:30 – 16:00, online
Labs: Friday, 10:30 – 12:00, online
Course web page:
(This web page, which will be updated throughout the course.)
Office hours: by appointment
Languages: English and German

Course Description

The task of syntactic parsing consists in finding the structure of a natural language sentence. Just as there are two main approaches of representing such structures – namely, constituency- and dependency-based structures – there are also two main approaches of syntactic parsing, adapted to handle constituency trees and dependency graphs, respectively. Since dependency parsing adopts a different view on how structure of languages should be represented, the methods used for dependency parsing are often different from those used for constituency parsing.

Dependency parsing can be performed either using linguistic descriptions (grammars) or using machine learning (data driven). This course presents the methods used in data-driven dependency parsing. These methods fall in two main families, the first one being based on transition systems, the second one on graph theory.


  • BN: homework exercises (> 50% correct); possibly in groups (up to 3 members)
  • AP: written exam


Week 1 Introduction and overview
Week 2 Basics of dependency parsing
Week 3 Grammar-based approaches to dependency parsing
Week 4 Introduction to data-driven dependency parsing
Week 5

Transition-based dependency parsing (part 1)

Projective shift-reduce (a.k.a. arc-standard) parsing
Week 6

Transition-based dependency parsing (part 2)

Arc-eager parsing, non-projective parsing
Week 7

Transition-based dependency parsing (part 3)

Dynamic oracles

Week 8 Implementation of a transition-based parser (part 1)
Week 9 Implementation of a transition-based parser (part 2)
Week 10 Implementation of a transition-based parser (part 3)
Week 11

Graph-based dependency parsing (part 1)

Chu-Liu-Edmonds’ algorithm
Week 12

Graph-based dependency parsing (part 2)

Eisner algorithm
Week 13

Graph-based dependency parsing (part 3)

Beyond arc-factored models
Week 14 Revision for the exam
Week 15 Exam


Thanks to Simon Petitjean, Andreas van Cranenburgh, and Rafael Ehren for providing their teaching materials, as well as to Sandra Kübler, Ryan McDonald, and Joakim Nivre, authors of the various tutorials (ACL 2006, ESSLLI 2007, EACL 2014) on which this course is based.