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

Compressed postscript
Compressed dvi