AN EFFICIENT PARALLEL PARSING ALGORITHM FOR CONTEXT-FREE LANGUAGES BASED ON EARLEYS METHOD

Authors
ATSUMI K MASUYAMA S
Citation
K. Atsumi et S. Masuyama, AN EFFICIENT PARALLEL PARSING ALGORITHM FOR CONTEXT-FREE LANGUAGES BASED ON EARLEYS METHOD, IEICE transactions on fundamentals of electronics, communications and computer science, E79A(4), 1996, pp. 547-552
Citations number
9
Categorie Soggetti
Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture","Computer Science Information Systems
Journal title
IEICE transactions on fundamentals of electronics, communications and computer science → ACNP
ISSN journal
09168508
Volume
E79A
Issue
4
Year of publication
1996
Pages
547 - 552
Database
ISI
SICI code
0916-8508(1996)E79A:4<547:AEPPAF>2.0.ZU;2-D
Abstract
We propose a parallel parsing algorithm based on Earley's method, whic h works in O(log(2)n) time using O(n(4.752)) processors on CREW PRAM. This algorithm runs with less number of processors compared with previ ously proposed W. Rytter's algorithm.