Process Grammar Processor: An Architecture for a Parallel Parser

A parallel architecture of a parser for Natural Language is described. A serial architecture has been already realized and is currently used in a system for the design and testing of Natural Language grammars and the generation of the corresponding parsers. This system works using a Process Grammar Processor running a model of grammar suited for the generation of Natural Language applications. The grammar model, named Process Grammar (PG), is an extension of an augmented context-free phrase-structure grammar, and the parser is designed to use such a grammar model. A PG is a set of rules that are treated by the processor as descriptors of processes that are scheduled and applied if the conditions for their execution hold: from this the name Process Grammar. In this report the PG model is extended in order to allow a more structured and modular construction of grammars, even of big dimensions, keeping separated parsing control, and syntactic and semantic specifications, partitioning a PG in clusters of rules, completely independent one from each other, carrying on their own dedicated recognition of specific parts of speech. The parallel architecture is composed by parallel processes cooperating and communicating by means of a message passing protocol. This allows the realization of some parsing strategies and the implementation of parsing mechanisms extending the recognition capacity of the parser that could not be possible in a standard and serial context-free parsing environment. Both serial and parallel versions of the parser are introduced and described, looking in greater detail the mechanisms of process scheduling and how they can be used and extended for implementing various cases of parsing strategies.

ICSI Technical Report TR-92-054

Technical Report