A Parallel Version of Earley's Algorithm
Danilo Bruschi and Giovanni Pighizzini
Dipartimento di Scienze dell'Informazione
Università degli Studi di Milano
via Comelico 39 -- 20135 Milano, Italy
Abstract
In the world of sequential computation the most referenced
algorithms for recognizing context--free languages
are the CYK algorithm introduced in 1963
by Cocke, Younger and Kasami, and Earley's algorithm introduced in 1970.
The former only deals with grammars in Chomsky normal form while the
latter deals with every context--free grammar.
When in early 70's people started
investigating parallel algorithms, immediately it appeared that obtaining
efficient parallel parsers was not easy.
In fact in 1977 Jones et al. proved that
the construction of a context--free
recognizer is a P--complete problem.
However Ruzzo and Rytter
showed that when we restrict our attention to
context--free grammars in Chomsky normal form, the P--completeness
result just mentioned can be overcome.
In fact a parallel version of
CYK can be obtained using Ruzzo and Rytter results.
\smallbreak
On the other hand, Jones et al.\ result
seems to deny the possibility of
having a ``parallel equivalent'' of Earley's algorithm.
In this paper we show that this consideration is not true.
More precisely
we will show how to obtain
a parallel algorithm for recognizing a language specified by a
whatever context--free grammar. Using such an
algorithm we will further describe a parallel algorithm for the
parsing phase. To our knowledge
these are the first parallel algorithms which solve such problems.
Download
Compressed postscript
Compressed dvi