Design And Study Of A Few Parallel Parsing Algorithms

Parallel parsing is key technology in the research fields of parallel compiler technology and programming of parallel system, and is one of the hot spots in computer science field currently. The study involved in automata theory, parallel computing model, parallel storage structure, algorithm complexity, parallel algorithm design, data structure, multi-task processor and optimize technology. These key technology research and key algorithm design strategy have great theoretical and practical significance of improving parallel compiler technology, expanding the scope of application and enhancing the practicality.The thesis makes research on Word—Lattice parsing method based on improved CYK algorithm, parallel parsing context-free grammar in linear array connecting state, improved increment parallel LL parsing algorithm, method of context-free grammar parallel recognition and parallel parsing on PRAM model, Parallel conversion method and algorithm from NFA to DFA and parallel algorithm of minimization based on distinguishable state table. As follows:Parallel parsing technology is classified and summarized systemically in the thesis. Word—Lattice parsing method based on improved CYK algorithm is proposed, which improves on CYK algorithm according time sequence span attribute after Word—Lattice distortion, makes parsing without changing structure and data of CYK table. Instance feasibility of producing useless in passing item of the form [i , j , B?η·] in parallel parsing table memory structure in circle structure and design idea of parallel parsing context-free grammar in linear array connecting state after analyzing carefully the reason to reduce this kind of useless is illustrated, and storage evolvement progress of linear array connection state is described in detail by examples. Method of context-free grammar parallel recognition and parallel parsing on PRAM model, pyramid structure, are parsed, mended and supplemented, in order to make it apply to Chomsky Normal Form. An improved increment parallel LL parsing algorithm is improved after analysis of increment parsing algorithm and parsing tree of indexed LL and discussing the parallel of using grammar parsing, calculating of d space function and node separating. A kind of parallel processing method to compute the FIRST and FOLLOW sets under multi-process environment is proposed, which discuss this kind of sets'parallel design idea and implement method. The parallel process method has great significance both in theory and practice for so many terminators and non-terminators in grammar. Parallel conversion method and algorithm from NFA to DFA and parallel algorithm of minimization based on distinguishable state table are proposed after study in perfect conversion between NFA and DFA under parallel environment and DFA model minimization, and parallel conversion process together with parallel process of parallel minimization algorithm are described with examples, in order to prove feasibility of algorithm and consistency of the value of theory parsing.The follow research of the subject include: study and discuss the design and operation norms of parallel parsing from the view of system theory, verify and derive the design and improved algorithm on papers. The next is to consider the technique of algorithm realization.