Compose-Reduce Parsing

COMPOSE-REWUCE PARSING Henry S. Thompson1 Mike Dixon2 John Lamping2 1: Human Communication Research Centre University of Edinburgh 2 Buccleuch Place Edinburgh EH8 9LW SCOTLAND 2: Xerox Palo Alto Research Center 3333 Coyote Hill Road Palo Alto, CA 94304 ABSTRACT Two new parsing algorithms for context-free phrase structure gram- mars are presented which perform a bounded amount of processing per word per analysis path, independently of sentence length. They are thus ca- pable of parsing in real-time in a par- allel implementation which forks pro- cessors in response to non-determinis- tic choice points. 0. INTRODUCTION The work reported here grew out of our attempt to improve on the o (n 2) performance of the SIMD parallel parser described in (Thompson 1991). Rather than start with a commitment to a specific SIMD architecture, as that work had, we agreed that the best place to start was with a more abstract architecture-independent considera- tion of the CF-PSG parsing problem-- given arbitrary resources, what algo- rithms could one envisage which could recognise and/or parse atomic category phrase-structure grammars in o (n) ? In the end, two quite differ- ent approaches emerged. One took as its starting point non-deterministic shift-reduce parsing, and sought to achieve linear (indeed real-time) com- plexity by performing a constant-time step per word of the input. The other took as its starting point tabular pars- ing (Earley, C KY), and sought to achieve linear complexity by perform- ing a constant-time step for the identi- fication/construction of constituents of each length from 0 to n. The latter route has been widely canvassed, although to our knowledge has not yet been implemented--see (Nijholt 1989, 90) for extensive references. The former route, whereby real-time pars- ing is achieved by processor forking at non-deterministic choice points in an extended shill-reduce parser, is to our knowledge new. In this paper we pre- sent outlines of two such parsers, which we call compose-reduce parsers. L COMPOSE-Rk~nUCE PARSING Why couldn't a simple breadth- first chart parser achieve linear per- formance on an appropriate parallel system? If you provided enough pro- cessors to immediately process all agenda entries as they were created, would not this give the desired result? No, because the processing of a single word might require many serialised 87 steps. Consider processing the word "park" in the sentence "The people who ran in the park got wet." Given a simple traditional sort of grammar, that word completes an sP, which in turn completes a P P, which in turn completes a vP, which in turn com- pletes an s, which in turn completes a REL, which in turn completes an NP. The construction/recognition of these constituents is necessarily serialised, so regardless of the number of proces- sors available a constant-time step is impossible. (Note that this only pre- cludes a real-time parse by this route, but not necessarily a linear one.) In the shift-reduce approach to parsing, all this means is that for non-linear grammars, a single shift step may be followed by many reduce steps. …

Content truncated to 500 words