Content area
Two types of parallel natural language processing are studied in this work: (1) the parallelism between syntactic and non-syntactic processing and, (2) the parallelism within syntactic processing. It is recognized that a syntactic category can potentially be attached to more than one node in the syntactic tree of a sentence. Even if all the attachments are syntactically well-formed, non-syntactic factors such as semantic and pragmatic consideration may require one particular attachment. Syntactic processing must synchronize and communicate with non-syntactic processing. Two syntactic processing algorithms are proposed for use in a parallel environment: Early's algorithm and the LR(k) algorithm. Conditions are identified to detect the syntactic ambiguity and the algorithms are augmented accordingly. It is shown that by using non-syntactic information during syntactic processing, backtracking can be reduced, and the performance of the syntactic processor is improved.
For the second type of parallelism, it is recognized that one portion of a grammar can be isolated from the rest of the grammar and be processed by a separate processor. A partial grammar of a larger grammar is defined. Parallel syntactic processing is achieved by using two processors concurrently: the main processor (mp) and the auxiliary processor (ap). The auxiliary processor processes/accepts a substring in the input that is generated by the partial grammar. The main processor is responsible for processing the rest of the input and for interprocessor communication. The LR(k) algorithm is augmented to the effect that the main processor can take advantage of the processing result of the auxiliary processor. It is shown that the performance of the proposed parallel processing is supported by many of the syntactic constraints in natural languages. In addition, by recognizing the divisibility of the grammar, parallel parsing supports partial semantic interpretation during the course of the processing and is useful for constructing fault-tolerant NLP.