An Efficient Parallel Parsing Algorithm for Context-Free Languages Based on Earley's Method

Kiyotaka ATSUMI  Shigeru MASUYAMA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E79-A   No.4   pp.547-552
Publication Date: 1996/04/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
parallel parsing,  context-free grammar,  theoretically efficient parallel algorithm,  Earley's method,  

Full Text: PDF(522.2KB)>>
Buy this Article




Summary: 
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.