Sommersemester 2009
Parsing Beyond Context-Free Grammar
Pro-/Hauptseminar, 2 hours, credit points: 3 (BA), 5 (MA).
Mittwochs, 8.30 Uhr, Seminarraum 1.13

Course description

The use of context-free grammars (CFGs) as a description device for natural language is well explored, especially when focusing on parsing: Robust and fast parsing techniques are available. However, the expressive power of CFG is too limited to adequately capture all natural language phenomena. Therefore extensions of CFG are of interest for computational linguistics. This course investigates efficient parsing algorithms for more general classes of grammar formalisms that go beyond CFGs. Examples are Tree Adjoining Grammars, Linear Indexed Grammars, Multiple Context-Free Grammars and Range Concatenation Grammars. These grammars have in common that they allow polynomial parsing and that CFG is a special simple instantiation of these formalisms. We will treat classical parsing algorithms for these formalisms such as CYK and Earley, making use of the paradigm of parsing as deduction, and also automaton-based parsing strategies. Besides symbolic parsing algorithms we will cover probabilistic extensions of these strategies, focusing in particular on recent proposals for exploiting search strategies on weighted hypergraphs for statistical parsing.

The topic of this course is closely related to our current research that deals with probabilistic parsing of mildly context-sensitive languages.


The course syllabus is available here: [pdf]

29.4. General Introduction: Grammar formalisms and parsing as deduction. Slides [pdf].
6.5. TAG 1: Introduction to the formalism, CYK parsing for TAG. Slides [pdf]. Example [pdf].
13.5. TAG 2: Earley parsing. Slides [pdf]. Example [pdf]. Deduction rules and example for prefix-valid Earley parsing [pdf].
20.5. TAG 3: LR parsing. Slides [pdf]. Example [pdf].
27.5. MCFG/LCFRS/Simple RCG 1: Introduction to the formalism. Slides [pdf].
10.6. Midterm exam: Solutions [pdf].
17.6. Discussion of midterm exam
24.6. MCFG/LCFRS/Simple RCG 2: CYK parsing. Slides [pdf]. Example [pdf].
1.7. MCFG/LCFRS/Simple RCG 3: Transformations. Slides [pdf].
8.7. MCFG/LCFRS/Simple RCG 4: Earley Parsing. Slides [pdf]. Example [pdf].
15.7. RCG: Introduction to the formalism, CYK and Earley parsing. Slides [pdf]. Example [pdf].
22.7. Exam [pdf]

All exercises and solutions are available in a single file: [pdf].

Last modified: Tue Nov 10 12:56:19 CET 2009 /