page 1  (24 pages)
2to next section

VICTORIA UNIVERSITY OF WELLINGTON

VUW

Department of Computer Science

PO Box 600
Wellington
New Zealand

Tel: +64 4 471 5328
Fax: +64 4 495 5232
Internet: Tech.Reports@comp.vuw.ac.nz

The L? Parsing Algorithm

Eric K. Jones and Linton M. Miller

Technical Report CS-TR-93/9
December 1993

Abstract

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 strate-

gies 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.