Algorithm partition and parallel recognition of general context-free languages using fixed-size VLSI architecture

摘要

Recognition of general context-free languages has been very important in language processing and syntactic pattern recognition. Many researchers have attempted to speed-up the recognition procedure. Recently, several VLSI implementations of context-free language recognition have been proposed. The main disadvantage of these proposed VLSI systems is that the size of the processor array is critical to the performance. That is, an n × n upper triangular array can only process strings with length not longer than n. In this paper we propose two algorithms which can recognize general context-free languages without restriction on the length of input string. The first one has time complexity O(n4k2) using k × k processing elements to recognize n input symbols; if k = n, its time complexity will be O(n2). The second one, if using k × k processing elements to recognize n input symbols, has time complexity O(n3k2); if k = n, the time complexity will be O(n). If there are several such modules, we can perform parallel recognition of general context-free languages. Since these algorithms essentially speed-up the dynamic programming procedure by using highly pipelining and parallelism of VLSI architecture, the proposed algorithms may also be useful for other problems solvable by dynamic programming.