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

Abstract

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. Introduction Natural language grammars are highly ambiguous. Systems for natural language understanding must therefore be carefully designed to prune out undesirable partial parses as soon as possible using semantic and pragmatic information. The need to rapidly prune a large number of unpromising parses yields two desiderata for parser design: 1. Flexible c...