Paper: A Tabulation-Based Parsing Method That Reduces Copying

ACL ID P03-1026
Title A Tabulation-Based Parsing Method That Reduces Copying
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2003

This paper presents a new bottom-up chart parsing algorithm for Prolog along with a compilation procedure that reduces the amount of copying at run-time to a con- stant number (2) per edge. It has ap- plications to unification-based grammars with very large partially ordered cate- gories, in which copying is expensive, and can facilitate the use of more so- phisticated indexing strategies for retriev- ing such categories that may otherwise be overwhelmed by the cost of such copy- ing. It also provides a new perspective on “quick-checking” and related heuris- tics, which seems to confirm that forcing an early failure (as opposed to seeking an early guarantee of success) is in fact the best approach to use. A preliminary empirical evaluation of its performance is also provided.