Richter:
Computational Linguistics II, Parsing (WS 06/07)
General Information on the Course
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:
- at the Universität Tübingen:
- elsewhere in the world:
on computational resources
Frank Richter