Parallel Generalized LR Parsing based on Logic Programming

Hozumi Tanaka, Hiroaki Numazaki


Abstract
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.
Anthology ID:
W89-0234
Volume:
Proceedings of the First International Workshop on Parsing Technologies
Month:
August
Year:
1989
Address:
Pittsburgh, Pennsylvania, USA
Venues:
IWPT | WS
SIG:
SIGPARSE
Publisher:
Carnegy Mellon University
Note:
Pages:
329–338
Language:
URL:
https://www.aclweb.org/anthology/W89-0234
DOI:
Bib Export formats:
BibTeX MODS XML EndNote
PDF:
http://aclanthology.lst.uni-saarland.de/W89-0234.pdf