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.