Seminar (Laura Kallmeyer)
Tuesday 12.30-12.00 and Thursday 08.30-10.00, room 24.21.03.26
Start: 02.04.2019. Last session: 11.07.2019.
Course description:
Parsing is a central task in natural language processing. Its goal is to compute the syntactic structures of sentences. Such a syntactic structure could either be a constituency structure or a dependency structure. The former is in many cases taken to be generated by a context-free grammar (CFG). Consequently, constituency parsing amounts to a) implementing/inducing a context-free grammar and b) using this grammar for parsing. Dependency parsing, in contrast to this, is mostly grammar-less parsing using machine-learning techniques.
In this course, we will mainly concentrate on step b) of CFG-based constituency parsing. We will revise various symbolic parsing algorithms that yield, given a CFG and an input sentence, the set of all parse trees for this sentence. In the second half of the course, we will move on to probabilistic parsing, covering Viterbi parsing and weighted deductive parsing with A* estimates.
For references see the slides of the individual sessions.
Schedule and Slides
(The slides are from WS 17/18.)
- 02.04.19 Introduction
- 04.04.19 Context-free grammars (CFG)
- 09.04.19 CFG II
- 11.04.19 Push-Down Automata (PDA)
- 16.04.19 Unger’s Parser
- 18.04.19 Unger’s Parser II. Example
An implementation of Unger’s Parser (by Simon Petitjean) can be found here. - 23.04.19 Top-down Parsing (LL-Parsing)
- 25.04.19 Parsing as Deduction. An example of agenda-based parsing can be found here.
- 30.04.19 CYK Parsing
- 02.05.19 CYK Parsing II
- 07.05.19 Shift Reduce Parsing
- 09.05.19 LL(1) Parsing
- 14.05.19 LL(1) Parsing II
- 16.05.19 Left Corner Parsing
- 21.05.19 Preparation mid term exam. Sample exercises can be found here, and the mid term exam from 2016 is here, and the one from 2017 can be found here. Any non-electronic material (course slides etc.) is allowed. .
- 23.05.19 Mid term exam, room 2421.U1.24.
- 28.05.19 Earley Parsing
- 30.05.19 entfällt (Christi Himmelfahrt)
- 04.06.19 Earley Parsing II
- 06.06.19 LR Parsing
- 11.06.19 LR Parsing II
- 13.06.19Tomita
- 18.06.19 PCFG, Inside and outside, Viterbi
- 20.06.19 entfällt (Fronleichnam)
- 25.06.19 Treebank grammars
- 27.06.19 Weighted deductive parsing
- 02.07.19 Weighted deductive parsing II
- 04.07.19 A* parsing
- 09.07.19 Preparation final exam. For preparation, here is the final exam from 2013, and here the one from 2016.
- 11.07.19 Final exam. Any non-electronic material (course slides etc.) is allowed.
The exam takes place in room 2521.HS 5F!
Exercises
There are weekly exercises for the course. These exercises are not mandatory but working on them is a good way to prepare for the exams. The solutions of the exercises will be discussed in the course.
The collection of homework exercises can be found here: Parsing-exercises
Leistungsnachweise
Sowohl für einen BN als auch für eine AP muss in einer Gruppe von zwei Studierenden ein Beispiel zu einem der Themen erklärt und als Handout ausgearbeitet werden. Daneben ist die Teilnahme an beiden Klausuren obligatorisch. Für einen BN müssen mindestens 50% der Aufgaben sinnvoll bearbeitet werden. Für eine AP setzt sich die Gesamtnote zu gleichen Teilen aus den beiden Klausurnoten zusammen.