For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
An Efficient Parallel Parsing Algorithm for Context-Free Languages Based on Earley's Method
Kiyotaka ATSUMI Shigeru MASUYAMA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1996/04/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
parallel parsing, context-free grammar, theoretically efficient parallel algorithm, Earley's method,
Full Text: PDF(522.2KB)>>
We propose a parallel parsing algorithm based on Earley's method, which works in O(log2n) time using O(n4.752) processors on CREW PRAM. This algorithm runs with less number of precessors compared with previously proposed W. Rytter's algorithm.