The CYK-Approach to Serial and Parallel Parsing

Abstract

Traditional parsing methods for general context-free grammars have been re-investigated in order to see whether they can be adapted to a parallel processing view. In this paper we discuss sequential and parallel versions of the Cocke-Younger-Kasami (CYK) parsing algorithm. The algorithms that are considered turn out to be suitable for implementations ranging from environments with a small number of asynchronous processors to environments consisting of a large array of highly synchronized processors.