Parsing in Parallel

Parsing in Parallel Xiuming Huang ~ Louise Guthrie Computing Research Laboratory New Mexico State University Las Cruces, NMI USA 88003 ABSTRACT The paper is a description of a parallel model for natural language parsing, and a design for its imple- mentation on the Hype,'eube multiproeessor. The pm'allel model is based on the Semantic Definite Clause Grammar formalism and integrates syntax and semantics through the commmfication of processes. The main proeessess, of which there are six, contain either purely syntactic or purely semantic information, giving the advantage of simple, transparent algorithms dedicated to only one aspect of parsing. Communica- tion between processes is used to hnpose semantic eon- st,'aints on the syntactic processes. 1. Introduction This paper describes parallel model for natural language parsing and gives a design for its implementa- tion. With the advent of parallel machines, it may be possible to view the relation of syntax and semantics in natural language parsing in a wholly new way. The approach is moving towards an application environ- meat which is similar to the heterarchical sytem pro- posed by Winograd [Winograd 721. Processes which control the syntactic aspects can be separated from those which control the semantic aspects in that the syntactic processes contain no semantic information themselves, but receive it by communication with the semantic processes, and vice versa. The advantage of this approach is that transparent algorithms can be written that are dedicated to only one aspect of pars- ing, while the desirable effects of integrating syntax and semantics can be achieved through the communication of processes. In our model we use this communication to enforce semantic constraints on the syntactic proces- sors in order to avoid the combinatorial explosion of producing all legal syntactic possibilities. Communication between the two components is then our focus in designing a parallel parser. There seem to be three obvious levels at which communica- tion between syntax and semantics can take place: the word level, tim phrase level, and the sentence level. We have chosen to consider communication at the phrase level rather than at either of the other two because it would be too early for the syntactic and semantic components to communicate at the word level (too lit- tle information is available at this level to help the parsing), and too late for them to communicate at the sentence level (too many syntactic parses might have already been "produced). How the communication between the syntactic and semantic components takes place at the phrase level will be described in Section 3. In Section 4, we design an hnplementation of this pa,'allel model for a 6-Hypereube lintel 85] multlpro- cessing system, which we will have available shortly. The 6-Hypercube has sixty-four identical processors (Intel 80286's with 512K bytes of memory) and no shared memory. Although each node in the Hypereube can eventually communicate with any other node, each processor can directly communicate with only six immediately neighboring nodes. We therefore intend to limit our message passing among processors to immedi- ate neighbors whenever possible. …

Content truncated to 500 words