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

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

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

3、主要數(shù)據(jù)結(jié)構(gòu)定義項(xiàng)目中主要數(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來(lái)形成圖的結(jié)點(diǎn)。Node中有兩個(gè)數(shù)據(jù)域，一個(gè)是邊的權(quán)值，另一個(gè)邊所連向的點(diǎn)，而采用有向圖來(lái)表示NFA和DFA。具體如下：vectnfadfa2.YaccYacc中的主

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

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

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

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

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