A PARALLEL AUGMENTED CONTEXT-FREE PARSING SYSTEM FOR NATURAL LANGUAGE ANALYSIS

Parsing efficiency is one of the important issues in building practical natural language processing systems. This paper proposes a design and an implementation of a parallel augmented context-free parsing system for natural language analysis. Natural language grammars are more than context-free, so that unification formalisms are adopted to enforce the linguistic constraints and to transfer the linguistic information. Lexical and structural ambiguities are the famous problems in parsing natural language sentences. Traditional LR approaches to deal with these problems are pseudo parallelism or blind parallelism. They fork many processes to take care of parsing. Apparently, it results in the scheduling problem in shared-memory model or the communication problem in distributed-memory model. This paper presents a merge mechanism to compose the same jobs into one. It can not only eliminate the duplications, but aIso reduce the number of forked processes to the great extent. The gapping problems are also treated in this parallel parsing system. Currently, it is implemented in Prolog and in Strand, and running on Sun-series workstations.