Efficient Bottom-Up Parsing

Efficient Bottom-Up Parsing Robert Moore and John Dowding SRI International 333 Ravenswood Avenue Menlo Park, CA 94025 Abstract This paper describes a series of experiments aimed at producing a bottom-up parser that will produce partial parses suitable for use in robust interpretation and still be reasonably efficient. In the course of these experi- ments, we improved parse times by a factor of 18 over our first attempt, ending with a system that was twice as fast as our previous parser, which relied on strong top-down constraints. The major algorithmic variations we tried are described along with the corresponding per- formance results. Introduction Elsewhere [1] we describe a change in our approach to NL processing to allow for more robust methods of in- terpretation. One consequence of this change is that it requires a different type of parsing algorithm from the one we have been using. In our previous SLS work, we have used a shift-reduce left-corner parser incorporating strong top-down constraints derived from the left con- text, to limit the structures built by the parser [2]. With this parser, no structure is built unless it can combine with structures already built to contribute to an analysis of the input as a single complete utterance. If we want to find grammatical fragments of the input that may be of use in robust interpretation, however, such strong use of top-down constraints is not appropriate. To address this issue, we have built and measured the performance of a number of bottom-up parsers. These parsers use the same unification grammar as our shift- reduce parser, but they do not impose the strong top- down constraints of the original. These experimental parsers fall into two groups: purely bottom-up parsers and bottom-up parsers that use limited top-down con- straints. The experiments were performed using a fixed grammar and lexicon for the Air Trave! Information Sys- tem (ATIS) domain, and an arbitrarily selected test cor- pus of 120 ATIS0 training sentences. The test grammar could produce complete parses for 79 of these 120 sen- tences. Pure Bottom-Up Parsing The first parser we implemented was a straightforward "naive" implementation of the CKY algorithm [3, 4] adapted to unification grammar. In this algorithm, a "chart" is maintained that contains records, or "edges," for each type of linguistic category that has been found between given start and end positions in a sentence. In context-free parsing, these categories are simply the non- terminal symbols of the grammar. In a unification gram- mar, they are complex structures that assign values to particular features of a more general category type. Our naive algorithm simply seeds the chart with edges for each possible category for all the words in the sen- tence, and then works left to right constructing addi- tional edges bottom-up. Each time an edge is added to the chart, the grammar is searched for rules whose last category on the right-hand side matches the edge just added to the chart, and the chart is scanned back to the left for a …

Content truncated to 500 words