Seminar (Laura Kallmeyer)

Monday 10.30-12.00 and Tuesday 10.30-12.00 both room 24.21.01.82 Start: 04.04.2022. Last session: 12.07.2022. The course will be taught in person, at the university. Further information on the course can be found here on the Moodle course page.

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. A useful tool for trying out different parsing alorithms can be found here.

Schedule and Slides

(under construction. Some of the slides are from previous years.)

• • 04.04.22 Introduction 
  • 05.04.22 Context-free grammars (CFG)
  • 11.04.22 CFG continued
  • 12.04.22 Push-Down Automata (PDA)
  • 18.04.22 fällt aus (Ostermontag)
  • 19.04.22 Unger’s Parser. Example of a trace for Unger’s parser. An implementation of Unger’s Parser (by Simon Petitjean) can be found here.
  • 25.04.22 Top-down Parsing (LL-Parsing). You can try out top-down parsing with example grammars using the CL Taskbox here (Samya Daleh).
  • 26.04.22 Parsing as Deduction. An example of agenda-based parsing can be found here. Furthermore, see CL Taskbox for a variety of deduction-based parsing algorithms.
  • 02.05.22 Parsing as Deduction continued.
  • 03.05.22 CYK Parsing
  • 09.05.22 CYK continued
  • 10.05.22 CYK continued
  • 16.05.22 Shift reduce parsing
  • 17.05.22 Shift reduce continued
  • 23.05.22 LL(1) Parsing
  • 24.05.22 Left Corner Parsing
  • 30.05.22 Left Corner continued
  • 31.05.22 Earley Parsing
  • 06.06.22 fällt aus (Pfingsten)
  • 07.06.22 Earley continued
  • 13.06.22 Earley continued
  • 14.06.22 LR Parsing
  • 20.06.22 LR continued
  • 21.06.22 Tomita
  • 27.06.22 PCFG, Inside and outside, Viterbi (already known from intro to CL), Treebank grammars 
  • 28.06.22 Weighted deductive parsing
  • 04.07.22 Weighted deductive parsing continued. See here for an exercise from last year that extends the Earley deduction rules with weights.
  • 05.07.22 A* parsing
  • 11.07.22 A* parsing continued. Example for k-best parsing. And a second example for k-best parsing. a second example for k-best parsing
  • 12.07.22 tba

 

Homework

There are weekly exercises for the course. These exercises are obligatory, they have to be handed in via Moodle. The solutions of the exercises will be discussed in the course.

• Homework 1 (CFG), due 12.04.22 at 10.30 am. Mit Lösung.
• Homework 2 (CFG, PDA), due 19.04.22 at 10.30 am. Mit Lösung.
• Homework 3 (PDA), due 26.04.22, 10.30 am. Mit Lösung.
• Homework 4 (Unger, top-down), due 03.05.22, 10.30 am
• Homework 5 (Parsing as deduction), due 10.05.22, 10.30 am
• Homework 6 (CYK parsing), due 17.05.22, 10.30 am
• Homework 7 (Shift-reduce), due 24.05.22. 10.30 am
• Homework 8 (LL(1)), due 31.05.22, 10.30 am.
• Homework 9 (Left Corner), due 07.06.22, 10.30 am.
• Homework 10 (Earley), due 21.06.22, 10.30 am
• Homework 11 (LR), due 28.06.22, 10.30 am.
• Homework 12 (weighted deductive parsing), due 12.07.22, 10.30 am

Leistungsnachweise

Sowohl für einen BN als auch für eine AP müssen mindestens 9 der 12 Hausaufgabenblätter bearbeitet und sinnvoll gelöst werden. Gruppenarbeit (max. Gruppengröße ist 3) ist erlaubt, bitte alle Namen auf die Abgabe. Eventuell muss auch noch ein Kurzreferat für einen BN gemacht werden. Für eine AP kann zusätzlich eine individuelle Prüfung vereinbart werden, zum Beispiel eine mündliche Prüfung. (Für Studierende des BA Computerlinguistik integrativ ist Parsing eine Grundveranstaltung in CL5, hier ist keine AP vorgesehen.)