A Tabulation-Based Parsing Method that Reduces Copying

A Tabulation-Based Parsing Method that Reduces Copying Gerald Penn and Cosmin Munteanu Department of Computer Science University of Toronto Toronto M5S 3G4, Canada � gpenn,mcosmin � @cs.toronto.edu Abstract 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. 1 Introduction This paper addresses the cost of copying edges in memoization-based, all-paths parsers for phrase- structure grammars. While there have been great ad- vances in probabilistic parsing methods in the last five years, which find one or a few most probable parses for a string relative to some grammar, all- paths parsing is still widely used in grammar devel- opment, and as a means of verifying the accuracy of syntactically more precise grammars, given a corpus or test suite. Most if not all efficient all-paths phrase-structure- based parsers for natural language are chart-based because of the inherent ambiguity that exists in large-scale natural language grammars. Within WAM-based Prolog, memoization can be a fairly costly operation because, in addition to the cost of copying an edge into the memoization table, there is the additional cost of copying an edge out of the table onto the heap in order to be used as a premise in further deductions (phrase structure rule applica- tions). All textbook bottom-up Prolog parsers copy edges out: once for every attempt to match an edge to a daughter category, based on a matching end- point node, which is usually the first-argument on which the memoization predicate is indexed. De- pending on the grammar and the empirical distri- bution of matching mother/lexical and daughter de- scriptions, this number could approach ��� copies for an edge added early to the chart, where � is the length of the input to be parsed. For classical context-free grammars, the category information that must be copied is normally quite small in size. For feature-structure-based grammars and other highly lexicalized grammars with large categories, however, which have become consider- ably more popular since the advent of the standard parsing algorithms, it becomes quite significant. The ALE system (Carpenter and Penn, 1996) attempts to reduce this by using an algorithm due to Carpen- ter that traverses the string breadth-first, right-to-left, but matches rule daughters rule depth-first, left-to- right in a failure-driven loop, which eliminates the need for active edges and keeps the sizes of the heap and call stack …

Content truncated to 500 words