Hiroaki Numazaki


pdf bib
A New Parallel Algorithm for Generalized LR Parsing
Hiroaki Numazaki | Hozumi Tanaka
COLING 1990 Volume 2: Papers presented to the 13th International Conference on Computational Linguistics


pdf bib
Parallel Generalized LR Parsing based on Logic Programming
Hozumi Tanaka | Hiroaki Numazaki
Proceedings of the First International Workshop on Parsing Technologies

A generalized LR parsing algorithm, which has been developed by Tomita [Tomita 86], can treat a context free grammar. His algorithm makes use of breadth first strategy when a conflict occcurs in a LR parsing table. It is well known that the breadth first strategy is suitable for parallel processing. This paper presents an algorithm of a parallel parsing system (PLR) based on a generalized LR parsing. PLR is implemented in GHC [Ueda 85] that is a concurrent logic programming language developed by Japanese 5th generation computer project. The feature of PLR is as follows: Each entry of a LR parsing table is regarded as a process which handles shift and reduce operations. If a process discovers a conflict in a LR parsing table, it activates subprocesses which conduct shift and reduce operations. These subprocesses run in parallel and simulate breadth first strategy. There is no need to make some subprocesses synchronize during parsing. Stack information is sent to each subprocesses from their parent process. A simple experiment for parsing a sentence revealed the fact that PLR runs faster than PAX [Matsumoto 87][Matsumoto 89] that has been known as the best parallel parser.