Parsing Beyond CFG

Since the 80s, we know that natural languages are not context-free. Starting from this insight, the notion of mild context-sensitivity has been developed, which is oftentimes assumed to constitute a good characterization of the complexity of natural languages.

In this course, we will look at some mildly context-sensitive grammar formalisms, more specifically at tree-rewriting formalisms such as Tree Adjoining Grammars (TAG) and at Linear Context-Free Rewriting Systems (LCFRS). We will investigate their formal properties, learn about symbolic parsing algorithms that have been proposed for them and also give an overview of data-driven approaches to using these formalisms in the context of probabilistic parsing. Finally, we will also cover recent approaches to grammar-less transition-based parsing that aim at generating structures that are beyond the structures context-free grammars can describe.

Textbook: Laura Kallmeyer (2010): Parsing Beyond Context-Free Grammars. Springer.