Fast systolic parsing of context free languages

Abstract

In this paper a new method for parallel parsing is developed. The method is based on partial computation of the tables of the well known Coke, Younger, Kasamy (CYC) algorithm. The method is shown to be more appropriate for systolization than other similar approaches. The complexity results are O(n ²) working time using O(n ²) processors. It is proved that O(n) working time can be obtained doing some improvements at the level of processing elements. However the algorithm is faster in the average case than other algorithms from the literature, due to the new technique of partial computation.

Keywords:

• Parallel algorithms
• Context-free languages
• Parsing
• Systolic arrays

C.R.Categories:

• C.1.3
• D.3.4