PARALLEL RECOGNITION AND PARSING ON MESH-CONNECTED COMPUTERS WITH MULTIPLE BROADCASTING

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.