并行語法分析中幾類算法的設(shè)計(jì)與研究.pdf

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

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

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

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

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