A new parallel algorithm for generalized LR parsing
Hiroaki Numazaki, Hozumi Tanaka · 1990
Tomita's parsing algorithm [Tomita 86], which adapted the LR parsing algorithm to context free grammars, makes use of a breadth-first strategy to handl LR table conflicts. As the breadth-first strategy is compatible with parallel processing, we can easily develop a parallel generalized LR parser based on Tomita's algorithm [Tanaka 89]. However, there is a problem in that this algorithm synchronizes parsing processes on each shift action for the same input word to merge many stacks into Graph Structured Stacks (GSS). In other words, a process that has completed a shift action must wait until all other processes have ended theirs --- a strategy that reduces parallel performance. We have developed a new parallel parsing algorithm that does not need to wait for shift actions before merging many stacks, using stream communication of a concurrent logic programming language called GHC [Ueda 85]. Thus we obtain a parallel generalized LR parser implemented in GHC.