基于內(nèi)存自動(dòng)機(jī)與模式的動(dòng)態(tài)引擎構(gòu)造技術(shù)研究.pdf

1、解釋是軟件系統(tǒng)開發(fā)與構(gòu)造過程中反復(fù)出現(xiàn)的一個(gè)主題。一個(gè)應(yīng)用系統(tǒng)自身可被理解為針對(duì)數(shù)據(jù)的變換和解釋。系統(tǒng)開發(fā)者為實(shí)現(xiàn)軟件系統(tǒng)的適應(yīng)性與擴(kuò)展性，利用解釋系統(tǒng)將開發(fā)時(shí)尚不能確定的狀態(tài)留待運(yùn)行時(shí)解釋并執(zhí)行特定動(dòng)作。語言的翻譯或解釋引擎是各種引擎中最為復(fù)雜的一種，本文以腳本語言的定義和引擎構(gòu)造為核心，總結(jié)語言中各種語法和語義現(xiàn)象，重點(diǎn)研究在內(nèi)存自動(dòng)機(jī)基礎(chǔ)上的SLL(*)計(jì)算、回溯計(jì)算、LookAhead DFA構(gòu)造以及文法與語義模式。 論

2、文在構(gòu)造內(nèi)存自動(dòng)機(jī)的基礎(chǔ)上，將SLL(*)計(jì)算、回溯計(jì)算、以及動(dòng)態(tài)引擎的結(jié)構(gòu)分析統(tǒng)一為自動(dòng)機(jī)上的狀態(tài)遷移操作。這些算法都已在動(dòng)態(tài)解析引擎XDSLL(*) Parser中實(shí)現(xiàn)。為了驗(yàn)證算法的正確性、有效性以及相關(guān)綜合性能，本文還對(duì)其進(jìn)行了系統(tǒng)的實(shí)驗(yàn)研究。作者研究工作的具體內(nèi)容包括： (1)定義基本正則表達(dá)式的元語言并構(gòu)造正則元語言識(shí)別引擎 正則元語言用于描述待解析目標(biāo)的詞法結(jié)構(gòu)，而正則元語言識(shí)別引擎將元語言描述的正則表達(dá)式

3、轉(zhuǎn)化為等價(jià)語法樹，在語法樹基礎(chǔ)之上構(gòu)造相應(yīng)的內(nèi)存有限狀態(tài)自動(dòng)機(jī)，并在構(gòu)造過程中進(jìn)行沖突檢測(cè)以及沖突消解，最終實(shí)現(xiàn)在內(nèi)存有限狀態(tài)自動(dòng)機(jī)上的輸入流匹配，為后續(xù)的文法結(jié)構(gòu)分析提供輸入。 (2)提出了一種增強(qiáng)的SLL(*)分析計(jì)算方法 動(dòng)態(tài)分析引擎自身是基于下推自動(dòng)機(jī)PDA進(jìn)行狀態(tài)遷移的，可以為結(jié)構(gòu)分析提供運(yùn)行時(shí)的棧信息。增強(qiáng)的SLL(*)分析算法以終結(jié)符號(hào)和運(yùn)行時(shí)棧信息為計(jì)算依據(jù)，減少了僅采用終結(jié)符號(hào)進(jìn)行預(yù)測(cè)分析時(shí)所產(chǎn)生的狀態(tài)

4、爆炸問題，從而加快了在內(nèi)存自動(dòng)機(jī)上選擇下一遷移狀態(tài)時(shí)的速度。 (3)提出了一種SLL(*)分析與回溯分析相結(jié)合的分析方法 SLL(*)分析不保證對(duì)所有LL文法都能夠進(jìn)行結(jié)構(gòu)分析，回溯分析可保證對(duì)所有LL文法甚至二義文法進(jìn)行分析，但其單次分析不具有完備性。當(dāng)SLL(*)分析失效時(shí)，啟用回溯分析以保證動(dòng)態(tài)解析引擎對(duì)語法分析的完備性，同時(shí)將SLL(*)計(jì)算結(jié)果與回溯分析結(jié)果進(jìn)行融合并構(gòu)造LookAhead DFA以加快引擎分

5、析速度。 (4)實(shí)現(xiàn)了基于PDA的結(jié)構(gòu)分析引擎與語義動(dòng)作掛接機(jī)制 結(jié)構(gòu)分析等價(jià)于PDA中的狀態(tài)遷移，直接在PDA上進(jìn)行狀態(tài)遷移即可完成結(jié)構(gòu)分析；在進(jìn)行狀態(tài)遷移的同時(shí)，執(zhí)行特定結(jié)構(gòu)所附加的語義動(dòng)作，可完成相應(yīng)語義計(jì)算，同時(shí)提供基于語法樹上語義動(dòng)作的前置計(jì)算與后置計(jì)算，便于開發(fā)者改變語法樹上的缺省計(jì)算順序。 (5)實(shí)現(xiàn)了常用的文法模式與相應(yīng)的語義動(dòng)作 作者對(duì)語言中頻繁出現(xiàn)的部分文法模式進(jìn)行了分析，并將相應(yīng)的語