Paper: A New Parallel Algorithm For Generalized LR Parsing

ACL ID C90-2053
Title A New Parallel Algorithm For Generalized LR Parsing
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1990

Tomita's parsing algorithm [~Ibmita 86], which adapted the LR parsing al- gorithm to context fl'ee grammars, makes use of a breadth-first strategy to handle LR table conflicts. As the breadth-first strategy is com- patible with parallel processing, we can easily develop a parallel generalized LR parser b~ed on Tomita's algorithm [Tanaka 89]. However, there is a problem in that this algorithm syn- chronizes parsing processes on each shift a,:- tion for the same input word to merge many st~ks :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 ...