Derivation of a Parallel Bottom-Up Parser from a Sequential Parser


IEICE TRANSACTIONS on Information and Systems   Vol.E75-D   No.6   pp.852-860
Publication Date: 1992/11/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Software Theory
parallel logic programming,  AND/OR-parallelism,  nondeterminacy,  program transformation,  bottom-up parsing,  

Full Text: PDF>>
Buy this Article

This paper describes the derivation of a parallel program from a nondeterministic sequential program using a bottom-up parser as an example. The derivation procedure consists of two stages: exploitation of AND-parallelism and exploitation of OR-parallelism. An interpreter of the sequential parser BUP is first transformed so that processes for the nodes in a parsing tree can run in parallel. Then, the resultant program is transformed so that a nondeterministic search of a parsing tree can be done in parallel. The former stage is performed by hand-simulation, and the latter is accomplished by the compiler of ANDOR-, which is an AND/OR parallel logic programming language. The program finally derived, written in KL1 (Kernel Language of the FGCS Project), achieves an all-solution search without side effects. The program generated corresponds to an interpreter of PAX, a revised parallel version of BUP. This correspondence shows that the derivation method proposed in this paper is effective for creating efficient parallel programs.