B. Pradeep et Csr. Murthy, PARALLEL RECOGNITION AND PARSING ON MESH-CONNECTED COMPUTERS WITH MULTIPLE BROADCASTING, Computer languages, 20(1), 1994, pp. 43-51
In this paper we present an optimal linear time algorithm for recognit
ion and parsing of context-free languages on n x n mesh connected comp
uters with multiple broadcasting, for an input string of length n. Our
algorithm is based on the well-known Cocke-Younger-Kasami (CYK) algor
ithm for the recognition and parsing of context-free languages, and is
faster than two recent algorithms available in the literature. The pa
rallel recognition of context-free languages is of particular importan
ce since parallel compilation is an increasingly important application
because of the availability of parallel hardware and the long running
times of optimizing and parallelizing compilers. Our algorithm is a c
ontribution towards this end.