Abbreviations

For more information about the lecture halls and seminar rooms, see our lecture room page. The names listed under "Technical Assistance" are student volunteers who will act as a contact person for technical questions of the lecturers and workshop speakers during the course or workshop.

Parsing beyond context-free grammars

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 different variants of Tree Adjoining Grammars, Linear Indexed 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 Earley and LR, automaton-based parsing algorithms and also graph-based parsing strategies. Besides concrete algorithms, the course will also introduce general specification methods for parsing algorithms.