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 Peer
4 12.03.25 Top-Down Syntax Analysis Knuth, 1971
5 19.03.25 On the Translation of Languages from Left to Right Knuth, 1965
6 26.03.25 Combinatory Grammars and Parasitic Gaps Steedman, 1986
7 2.04.25 The Probabilistic Chomsky-Shutzenberger Hierarchy Icard, 2020
8 9.04.25
9 16.04.24
10 23.04.24 Easter Break
11 30.04.24 Climbing Towards NLU: On Meaning, Form and Understanding [...] Bender and Koller, 2020
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
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

Lecturer

Avatar

Ryan Cotterell

Assistant Professor of Computer Science

ETH Zürich

Teaching Assistant ‘Understanding Context-Free Parsing Algorithms’