Parallel generalized LR parser based on logic programming

Tomita's algorithm [Tomita 85] which treats context free grammars makes use of the breadth-first strategy to handle conflicts occurring in a LR parsing table. Considering the compatibility of a breadth-first strategy with parallel processing, we developed a parallel generalized LR parser called PLR, whose algorithm is based on Tomita's algorithm. PLR is implemented in GIIC[Ueda 85] that is a concurrent logic programming language developed by the Japanese 5th generation computer project. We made two kinds of implementations of PLR. One implementation does not uses the Graph Structured Stacks (GSSs) developed by Tomita, and the other implementation uses them. In this paper, we describe two implementations of PLR. Then to evaluate the ability of PLR, we compare the parsing time of PLR with that of PAX[Matsumoto 87] which is an efficient parallel parser implemented in GHC. The experiment revealed that PLR with no GSSs runs faster than PAX.