Richter: Computational Linguistics II, Parsing (WS 06/07)

General Information on the Course

Course Description in the Kommentierte Vorlesungsverzeichnis
Information Sheet (distributed in the first class meeting)
Classes: Our class meets Mondays and Wednesdays, 11ct-12.45 in Hörsaal 0.02 at the SfS. The course language is English.
Instructors: Frank Richter, Jan-Philipp Söhn
Office Hours: Tuesdays, 10.00-11.00, SfS, Room 2.17
Email: f.richter@em.uni-frankfurt.de, jp.soehn@uni-tuebingen.de

Slides, JFLAP Files, Handouts

Introductory meeting, Oct. 23rd: Slides on oral presentations
Oct. 25th: Formal language theory, DFAs
Oct. 30th: Formal language theory, regular languages II
Nov. 6th: Formal language theory, PDAs
Examples of PDAs (in JFLAP format): PDA-1, PDA-2, PDA-3, DPDA
Nov. 8th: PDAs, Properties of Type 2 and Type 3 languages
Example of a DPDA (in JFLAP format): DPDA
Nov. 13th: CFGs: Chomsky/Greibach Normal Form
Nov. 15th: CFGs, Type 0-3 Grammars: Derivations
Nov. 20th: Derivations, Complexity, CSGs
Nov. 22nd: CSGs, Turing Machines; Other Grammar Formalisms
Example of two CSGs and a Turing Machine (in JFLAP format):
CSG-1, CSG-2 (Kuroda Normal Form of CSG-1), Turing Machine
Nov. 27th: Introductory Overview: Parsing
Nov. 29th: Unger's Parser
Anne Brock's presentation: The Unger Parser
Dec. 4th: The CYK Parsing Method. Handout. Presentation:
Cornelia Kempa, Part 1
Carla Parra Escartín, Part 2
Dec. 6th: More on the CYK Parsing Method
Dec. 11th: Details of Chomsky Normal Form transformation
Dec. 18th/20th: Presentation by Aleksandar Dimitrov and Johannes Dellert: Top Down Parsing
Dec. 20th: Definite Clause Grammars
Jan. 8th: Overview, Eliminating Left-Recursion
Jan. 10th: Bottom-up Parsing
Presentation by Laura Kassner: Left-Corner Parsing
Jan. 15th: Left-Corner Parsing
Jan. 17th: Presentation by Christopher Millar and Ekaterina Volkova: The Earley Parsing Method
Jan. 22nd: Handout with illustration of the Earley parsing method
Jan. 24th: Presentation by Kilian Evang: LR Parsing
Jan. 29th: LR Parsing (Properties and variants)
JFLAP example used in class to illustrate SLR(1) parsing (automaton and chart)
Jan. 31st: Presentation by Tihomira Panayotova and Paolina Teneva: Tomita's Parser
Feb. 5th: Tomita's Paper (basis for our overview of Tomita's parsing method in this class meeting)

Electronically available Course Readings

Software

JFLAP: Software for experimenting with formal languages, including nondeterministic finite automata, nondeterministic pushdown automata, multi-tape Turing machines, several types of grammars, parsing, and L-systems.

A few links

on linguistics

at the SfS:
- Seminar für Sprachwissenschaft
- Fachschaft Allgemeine Sprachwissenschaft
at the Universität Tübingen:
- The Library Catalogue
- Sonderforschungsbereich 441 Linguistische Datenstrukturen
elsewhere in the world:
- The History of Mathematics Archive
- The linguist list

on computational resources

Frank Richter