The L* Parsing Algorithm

This report describes a new algorithm for table-driven parsing with arbitrary context-free grammars. The algorithm provides a 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 algorithm thus combines the flexibility of chart parsing with the low overhead of table-driven approaches, and should find ready application to natural language processing. Publishing Information A shorter version of this report has been accepted for the 17th Annual Computer Science Conference to be held in Christchurch, New Zealand, January 1994. Author Information Eric Jones is on the academic staff of the Department of Computer Science at Victoria University of Wellington and a member of the department's artificial intelligence group. Linton Miller is a Masters student with the Department of Computer Science at Victoria University of Wellington. 1 Introduction Parsers fo..