編譯原理實驗報告

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

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

3、主要數據結構定義項目中主要數據結構定義本次實驗中我們使用了大多數STL中的數據結構，具體情況如下：stackqueuehash_sethash_mapsetmapvectlist1.LexLex中主要數據結構就是關于NFA和DFA圖的構造。實驗中我們采用自定義結點類Node來形成圖的結點。Node中有兩個數據域，一個是邊的權值，另一個邊所連向的點，而采用有向圖來表示NFA和DFA。具體如下：vectnfadfa2.YaccYacc中的主

4、要數據結構比較多。I.對于讀進的符號串，用兩張表，一張是終結符符號表，另一張是非終結符符號表，索引值為字符串，內容為對應的符號在程序中的內碼值，為int型。這種表采用hash_map類型實現。II.對于產生式，采用自定義結構Producer定義。具體如下：structProducerintleftvectright并在程序中用一個全局數據程序中用一個全局數據vectvectProducerSetProducerSet來存儲所有產生式，而

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

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

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

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