編譯原理實(shí)驗(yàn)報告

1、編譯原理實(shí)驗(yàn)報告編譯原理實(shí)驗(yàn)報告一項目目的項目目的1.鞏固大三上學(xué)期編譯原理理論課程的學(xué)習(xí)成果，加深對編譯原理及程序構(gòu)造過程的理解。2.增強(qiáng)程序設(shè)計能力。二項目內(nèi)容要求項目內(nèi)容要求本次實(shí)驗(yàn)分為兩部分，第一部分是詞法分析生成器Lex的構(gòu)造，第二部分是語法分析生成器Yacc的構(gòu)造。另外，根據(jù)自己開發(fā)的工具，生成C語言子集的詞法分析器和語法分析器。具體內(nèi)容要求如下：1.Lex（1）Lex輸入文件的解析（2）正規(guī)表達(dá)式的解析（3）一個正規(guī)表達(dá)式

2、到NFA的轉(zhuǎn)換算法實(shí)現(xiàn)（4）多個NFA的合并（5）NFA的確定化和最小化算法實(shí)現(xiàn)（6）返回狀態(tài)與返回內(nèi)容的對應(yīng)2.Yacc（1）Yacc輸入文件的解析（2）上下文無關(guān)文法到對應(yīng)LR(1)文法的下推自動機(jī)的構(gòu)造（3）LR(1)文法的下推自動機(jī)到相應(yīng)分析表的構(gòu)造（4）LR(1)總控程序的構(gòu)造（查表程序）（5）LR(1)到LALR(1)的映射（）（6）符號表的構(gòu)建與相應(yīng)管理程序（7）語義動作程序的加入其中()表示是我們未能完成的功能。三項目中

3、主要數(shù)據(jù)結(jié)構(gòu)定義項目中主要數(shù)據(jù)結(jié)構(gòu)定義本次實(shí)驗(yàn)中我們使用了大多數(shù)STL中的數(shù)據(jù)結(jié)構(gòu)，具體情況如下：stackqueuehash_sethash_mapsetmapvectlist1.LexLex中主要數(shù)據(jù)結(jié)構(gòu)就是關(guān)于NFA和DFA圖的構(gòu)造。實(shí)驗(yàn)中我們采用自定義結(jié)點(diǎn)類Node來形成圖的結(jié)點(diǎn)。Node中有兩個數(shù)據(jù)域，一個是邊的權(quán)值，另一個邊所連向的點(diǎn)，而采用有向圖來表示NFA和DFA。具體如下：vectnfadfa2.YaccYacc中的主

4、要數(shù)據(jù)結(jié)構(gòu)比較多。I.對于讀進(jìn)的符號串，用兩張表，一張是終結(jié)符符號表，另一張是非終結(jié)符符號表，索引值為字符串，內(nèi)容為對應(yīng)的符號在程序中的內(nèi)碼值，為int型。這種表采用hash_map類型實(shí)現(xiàn)。II.對于產(chǎn)生式，采用自定義結(jié)構(gòu)Producer定義。具體如下：structProducerintleftvectright并在程序中用一個全局?jǐn)?shù)據(jù)程序中用一個全局?jǐn)?shù)據(jù)vectvectProducerSetProducerSet來存儲所有產(chǎn)生式，而

5、在其它來存儲所有產(chǎn)生式，而在其它器的代碼。形成一個函數(shù)analysis(yytextintn)，其參數(shù)中前者表示符號串，后者表示符號串長。２Yacc部分Yacc的主要思想同Lex一樣，都是采取教材上的算法來實(shí)現(xiàn)。①Yacc輸入文件的解析過程由于Yacc的輸入文件格式較為復(fù)雜，所以此處采用了狀態(tài)跳轉(zhuǎn)的方法來進(jìn)行控制輸入。此部分具體所做的工作如下：i.讀取定義段，存儲語義值類型定義，存儲終結(jié)符和非終結(jié)符語義值類型，算符優(yōu)先級定義，左右結(jié)合性

6、定義。ii.讀取規(guī)則段，完成產(chǎn)生式集合的生成。如有語義動作，完成語義動作的解析及存儲。iii.讀取用戶自定義段，沒什么解析，直接輸出到文件。②依據(jù)第一步生成的各種數(shù)據(jù)結(jié)構(gòu)，開始內(nèi)部處理過程。利用LR(1)分析法，依據(jù)產(chǎn)生式集合，進(jìn)行項目集算法的計算。在計算的過程中，完成語法分析表的構(gòu)造。③完成符號表的構(gòu)造，并存儲好以備輸出。④利用自己寫好的語法分析器的模板程序，以及語法分析表的構(gòu)造完成，最終生成語法分析器的結(jié)果代碼。同時，生成符號表文件

7、signal_table.txt以及可供詞法分析引用的符號串定義頭文件yytab.h。五項目開發(fā)過程中的問題項目開發(fā)過程中的問題1.對于文件輸入流的分析。一種思路是純粹依靠條件控制語句進(jìn)行控制分析，此種方法的缺點(diǎn)是邏輯容易產(chǎn)生混亂，且出錯不易檢查，健壯性也不強(qiáng)。另一種思路是把它當(dāng)成一種語法，用語法分析的思想進(jìn)行處理。這種方法處理起來比較穩(wěn)妥，易于查錯，只是工作量太大。由于時間關(guān)系，最終我們采用第一種思路，導(dǎo)致的后果是輸入文件一定要符合我

8、們的要求，否則很有可能導(dǎo)致非正常運(yùn)行。２對于Yacc中LALR(1)分析表的構(gòu)造。由于起初我們的估計不足，并沒有真正生成項目集之間的關(guān)系表，而只是在生成項目集的過程中就構(gòu)造出了LR(1)分析表。故在這種情況下，無法采用教材上所說的第一種思路，即很耗空間的算法，將項目集按同心合并后再輸出。而對于算法二，即利用搜索符的推導(dǎo)關(guān)系直接導(dǎo)出LALR(1)分析表的算法，由于我們時間不足，故也來不及完成。所以最終我們只做到了LR(1)分析表。六項目總