ON CKY-PARSING OF CONTEXT-FREE ORAmARS IN PARALLEL
M Chanwani · 1992
A parallel version of CKY-parsing algorithm for context-free grammar is presented. The algorithm uses PRAM model of computation and parses a string (or sentence) of length n in parallel time O(n.logn) employing O(n2) processors. The proposed algorithm adopts a very simple procedure and also provides the multiple parses for ambiguous languages. I. INTROWCTION Parsing is an essential component In any natural language processing system and other systems employlng context-f ree grammars 1 i ke language compilers, interpreters etc. A large number of good algorithms have been developed for sequential parsing of context-free languages. The popular algorithms are CKY-parsing [l], Earley’s parsing 121 and Tomita’s parsing [31. Parslng times, in general, for these algorithms are O(4) where n is the length of input string (or sentence). Although this parslng time may be acceptable In the most of the applications having small sized inputs, there exists a desire to exploit parallelism in the parsing phenomenon to improve speed of computation. Parallel techniques have been Introduced in the area of formal language theory and computational llngulstlcs. Some of the parallel techniques have been evolved from cognitive viewpoints [41 and other have been investigated from computational linguistic viewpoints 151. Gibbons and Rytter [6] have proposed a parallel parsing algorithin with O(log2n) parallel time requlring a large number of processors (O(n6)). Chu and Fu 171 have presented a parallel version of CKY-algorithm taking O(n) time using O($) processors but with concurrent writes. The concurrent writes in the algorithm, which lead to abstract WRAM model, pose difficulty for its implementation on many parallel machine. PRAM model resolves this problem. However, it takes more time. According to Gibbons and Rytter [61, let C(A,n,m) be the parallel time complexity of algorithm A (with problem size n) within a model of parallel computation denoted by m, we have the following relation: C(A’,n,PRAM) = C(A,n,WRAM).logn where A’ Is an algorithm designed for PRAM model. In this paper, we present a Parallel version of CKY-algorithm for parsing on context-free gramnars which takes O(n. logn) time using O($) processors. We also show that how concurrent write conflicts can be resolved in our a1 gorl thm.