Paper: Object-Oriented Parallel Parsing For Context-Free Grammars

ACL ID C88-2158
Title Object-Oriented Parallel Parsing For Context-Free Grammars
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1988

This paper describes a new parallel parsing scheme for context-free grammars and our experience of implementing this scheme, and it also reports the result of our simula- tion for running the parsing program on a massive parallel processor. In our basic parsing scheme, a set of context free- grammar :,:ules is represented by a network of processor- like computing agents each having its local memory. Each computing agent in the network corresponds to an occur- fence of a non-terminal or terminal symbol appearing in the grammar rules. Computing agents in the network work concurrently and communicate with one another by passing messages which are partial parse trees. This scheme is shown to he fast (0(n,h) time for the first complete parse tree, where n is the length of an input sentence and ...