The L* Parsing Algorithm


Authors: Eric K. Jones, Linton Miller
Pages: 24
Source: GZipped PostScript (72kb); Adobe PDF (353kb)

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.

[Up to Computer Science Technical Report Archive: Home Page]