1、并行語法分析是并行編譯技術、并行系統(tǒng)程序設計等研究領域的關鍵技術。是目前計算機科學研究領域中倍受關注的熱點之一。這一問題的研究涉及自動機理論、并行計算模型、并行存儲結構、算法復雜度、并行算法設計、數(shù)據(jù)結構、多處理機任務分配、優(yōu)化技術等。這些關鍵技術問題的研究和關鍵算法的設計策略對完善并行編譯技術、擴大其應用范圍、增強其通用和實用性都有著重要的理論和實踐意義。 本文主要對基于改進的CYK算法的字-格語法分析方法、線性陣列LA(Li

2、nearArray)連接狀態(tài)中上下文無關文法(CFG)的并行語法分析算法、擴增式LL語法分析算法的并行化、PRAM模型上的上下文無關文法的并行識別和并行語法分析方法、并行環(huán)境下非確定有限自動機和確定有限自動機之間等價性轉(zhuǎn)換、有限自動機模型最小化等問題進行研究。具體內(nèi)容如下： 對并行語法分析技術做了較系統(tǒng)的分類和綜述；提出一種基于改進的CYK算法的字-格語法分析方法：將字-格的CYK初始化表與CYK算法對常規(guī)句子的語法分析相比較，

3、以字-格變形后的時間序列跨度為屬性改進CYK算法，在字-格的CYK初始化表結構基礎上做語法分析而不需改動CYK表結構或數(shù)據(jù)；指出環(huán)型結構網(wǎng)絡連接狀態(tài)中，并行語法分析項目表的存儲結構中形如[i，j，B→η·]的項目的傳遞可能產(chǎn)生冗余的情況，對其產(chǎn)生的原因做了仔細分析；提出線性陣列LA(LinearArray)連接狀態(tài)中上下文無關文法(CFG)的并行語法分析算法的設計思想，減少這種傳遞中的冗余，并以實例詳細描述了線性陣列連接結構中分析信息的

4、存儲演變過程；對PRAM模型上的上下文無關文法的并行識別和并行語法分析方法-金字塔結構進行分析、修改和補充，使其適用于非Chomsky范式；在對擴增式語法分析算法和線索化LL語法分析樹進行分析的基礎上，對其中的語法分析樹的重用、d距離函數(shù)的計算和結點分離等關鍵問題的并行性做了詳細討論，給出一個改進的并行化擴增式LL語法分析算法；提出一種多處理機環(huán)境中FIRST和FOLLOW集合求解的并行處理方法，并對這類集合的并行算法設計思想和它的實現(xiàn)

5、策略做了詳細論述。由于文法中終結符和非終結符個數(shù)很多，因此這種并行處理方法對并行編譯和提高效率有其理論和現(xiàn)實意義；對并行環(huán)境下非確定有限自動機和確定有限自動機之間等價性轉(zhuǎn)換、有限自動機模型最小化等問題進行研究，提出并詳細分析了非確定有限自動機到確定有限自動機的并行轉(zhuǎn)換方法及算法和基于可區(qū)分狀態(tài)表結構的并行最小化算法，并以實例描述了并行轉(zhuǎn)化的過程和并行最小化算法的并行處理過程，并驗證其算法的可行性和與理論分析值的一致性。 本課題的