Parallel parsing on a transputer network

Parsing is a commonly used operation in many applications requiring language analysis. In most areas, such as translation of programming languages, linear time parsers can be built given that the underlying grammars are unambiguous, and that a limited amount of look-ahead is required to recognize productions. These prove too limiting, and more general parsing algorithms, such as the CYK algorithm or Early's algorithm, are necessary when parsing inputs in areas such as image processing, pattern recognition and natural language processing. These algorithms generally require O(n3) time. Several attempts have been made to parallelize general CFL parsers in order to improve their time complexity. Some of these have utilized synchronously operating custom VLSI. This paper describes a parallel algorithm for parsing CFLs based on Early's algorithm implemented on a network of INMOS transputers, a currently available, off-the-shelf processor.