An Efficient Parallel Parsing Algorithm for Context-Free Languages Based on Earley's Method
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E79-A No.4 pp.547-552
- Publication Date
- 1996/04/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kiyotaka ATSUMI, Shigeru MASUYAMA, "An Efficient Parallel Parsing Algorithm for Context-Free Languages Based on Earley's Method" in IEICE TRANSACTIONS on Fundamentals,
vol. E79-A, no. 4, pp. 547-552, April 1996, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e79-a_4_547/_p
Copy
@ARTICLE{e79-a_4_547,
author={Kiyotaka ATSUMI, Shigeru MASUYAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Efficient Parallel Parsing Algorithm for Context-Free Languages Based on Earley's Method},
year={1996},
volume={E79-A},
number={4},
pages={547-552},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={April},}
Copy
TY - JOUR
TI - An Efficient Parallel Parsing Algorithm for Context-Free Languages Based on Earley's Method
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 547
EP - 552
AU - Kiyotaka ATSUMI
AU - Shigeru MASUYAMA
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E79-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 1996
AB - 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.
ER -
English
