L* Parsing: A General Framework for Syntactic Analysis of Natural Language

Natural Language Processing

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 12

Syntax

We describe a new algorithm for table-driven parsing with context-free grammars designed to support efficient syntactic analysis of natural language. The algorithm provides a general framework in which a variety of parser control strategies can be freely specified: bottom-up strategies, top-down strategies, and strategies that strike a balance between the two. The framework permits better sharing of parse forest substructure than other table-driven approaches, and facilitates the early termination of semantically ill-formed partial parses. The algorithm should thus find ready application to large-scale natural language processing.