Understanding Context-Free Parsing Algorithms
ETH Zürich: Spring 2025
Course Description
In the first part of the seminar, we study some of the most popular parsing algorithms, which are a fundamental tool both in natural language processing and in programming languages. Each week, a student will present a paper on parsing, including the papers that first described celebrated parsing algorithms like Earley’s and CKY. We will also put a lot of focus on weighted parsing, which is fundamental in applications to language modeling. In the second part, we’ll examine advanced NLP topics through analysis of pivotal (and often controversial) papers that are shaping the field’s future direction.
Time: Wednesday 12-14h
Location: CAB G 52
Course Structure and Schedule
The structure of this seminar is one of open-ended debate. Each week a group of students will present a paper in the list below (which is still being updated), followed by a class discussion. Grading is purely based on participation.
| Week |
Date |
Paper |
Author |
Presenter |
| 1 |
19.02.25 |
Intro |
|
|
| 2 |
26.02.25 |
An Efficient Probabilistic Context-Free Parsing Algorithm [...]
|
Stolcke et al., 1995
|
Clemente
|
| 3 |
5.03.25 |
Recognition and Parsing of Context Free Parsing Algorithms in Time n^3
|
Younger, 1965
|
Patrick and Pier
|
| 4 |
12.03.25 |
Top-Down Syntax Analysis |
Knuth, 1971
|
Florian and Jan
|
| 5 |
19.03.25 |
On the Translation of Languages from Left to Right |
Knuth, 1965
|
Nathan
|
| 6 |
26.03.25 |
Combinatory Grammars and Parasitic Gaps |
Steedman, 1986
|
Elias, Kai
|
| 7 |
2.04.25 |
The Probabilistic Chomsky-Shutzenberger Hierarchy |
Icard, 2020
|
Alex, Yannick
|
| 8 |
9.04.25 |
Fast, Practical GLL Parsing |
Afroozeh and Izmaylova, 2015
|
Finn
|
| 9 |
16.04.24 |
Exercise Session |
|
|
| 10 |
23.04.24 |
Easter Break |
|
|
| 11 |
30.04.24 |
Climbing Towards NLU: On Meaning, Form and Understanding [...] |
Bender and Koller, 2020
|
Kay |
| 12 |
7.05.24 |
GPT-3: Its Nature, Scope, Limits, and Consequences |
Floridi and Chiriatti, 2020
|
|
| 13 |
14.05.24 |
Language Models are Few Shot Learners |
Brown et al., 2020
|
Leon |
| 14 |
21.05.24 |
Deep Learning: a Critical Appraisal
|
Marcus, 2021
|
|
| 15 |
28.05.24 |
On the Dangers of Stochastic Parrots: can Language Models Be Too Big?
|
Bender et al., 2021
|
|
