Primordial Soup Algorithm: A Systematic Approach to the Specification and Designof Parallel Parsers

摘要

A general framework for parallel parsing is presented, which allows for aunified, systematic approach to parallel parsing. The Primordial Soup Algorithm (PSA) creates trees by allowing partial parse trees to combine arbitrarily. A large class of parallel parsing strategies can be defined by adding constraints to the general algorithm. This is exemplified by strategies for parsers based on the algorithms of Cocke-Younger-Kasami (CYK), Earley, de Vreught, and Honig and Rytter. From such a parsing strategy, algorithms for various machine architectures can be derived in a systematic way. As an example, the CYK case is treated in full detail. The PS framework can be used to derive sequential algorithms, and there is no fundamental difference between sequential and parallel processing. In an appendix, a prototype PROLOG implementation of the PSA is transformed into an Earley parser.