中南大學(xué)編譯原理實(shí)驗(yàn)報(bào)告

1、CENTRAL SOUTH UNIVERSITY 編 譯 原 理 實(shí) 驗(yàn) 報(bào) 告學(xué)生姓名 專業(yè)班級(jí) 學(xué) 號(hào) 學(xué) 院 信息科學(xué)與工程學(xué)院 指導(dǎo)教師 張修如 實(shí)驗(yàn)時(shí)間 2015年5月 實(shí)驗(yàn)一 計(jì)算FIRSTVT集一、實(shí)驗(yàn)?zāi)康倪M(jìn)一步培養(yǎng)學(xué)生編譯器設(shè)計(jì)的思想，加深對(duì)編譯原理和應(yīng)用程序的理解，針對(duì)編譯過(guò)程的重點(diǎn)和難點(diǎn)內(nèi)容進(jìn)行編程，獨(dú)立完成有一定工作量的程序設(shè)計(jì)任務(wù)，同時(shí)強(qiáng)調(diào)好的程序設(shè)計(jì)風(fēng)格，并綜合使用程序設(shè)計(jì)語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)和編譯原理的知識(shí)，熟悉使用開發(fā)工具VC /JAVA/C#/.NET 。二、實(shí)驗(yàn)內(nèi)容設(shè)計(jì)一個(gè)由正規(guī)文法生成FIRSTVT集的算法動(dòng)態(tài)模擬，實(shí)現(xiàn)以下功能：1輸入一個(gè)文法

2、G； 2輸出由文法G構(gòu)造FIRSTVT集的算法；3輸出FIRSTVT集。三、實(shí)驗(yàn)要求1思想的正確性，采用合適的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)等；2程序?qū)崿F(xiàn)的正確性，程序整體結(jié)構(gòu)合理、編程風(fēng)格規(guī)范等； 3程序功能的完善程度，包括功能的基本實(shí)現(xiàn)、基本完善、完全實(shí)現(xiàn)；    4工作認(rèn)真、獨(dú)立完成實(shí)驗(yàn)。四、實(shí)驗(yàn)步驟1問(wèn)題理解和分析：充分地分析和理解問(wèn)題本身，弄清要求做什么； 2確定解決問(wèn)題的方法：主要是找到解決問(wèn)題的主要思路，該怎么做；3詳細(xì)設(shè)計(jì)和編碼：確定算法的主要流程，再進(jìn)行編程；4程序調(diào)試和運(yùn)行：掌握程序調(diào)試和排錯(cuò)的基本方法，增加編程的感覺(jué)和解

3、決問(wèn)題的成就感；5完成實(shí)驗(yàn)報(bào)告。五、程序設(shè)計(jì)5.1基本算法 構(gòu)造集合FIRSTVT(P)的算法 按FIRSTVT(P)的定義，可以用如下兩條歸則來(lái)構(gòu)造： (1)若有產(chǎn)生式Pa或Qa，則aFIRSTVT(P) (2)若aFIRSTVT(Q)，且有產(chǎn)生式PQ，則aFIRSTVT(P) 構(gòu)造算法： 建立一個(gè)二維布爾數(shù)組FP,a，使得FP,a為真的條件適當(dāng)且僅當(dāng)aFIRSTVT(P)；再用一個(gè)棧STACK，把所有初值為真的數(shù)組元素FP,a的符號(hào)對(duì)(P,a)全都放到棧中；算法如下： (1)將布爾矩陣各元素置假；棧置空； (2

4、)按照歸則(1)查看產(chǎn)生式，對(duì)于Pa或PQa.，置相應(yīng)FP,a為真，符號(hào)對(duì)(P,a)入棧； (3)按規(guī)則(2)，對(duì)棧施加如下操作：彈出棧定符號(hào)對(duì)記作(Q,a)，查看所有產(chǎn)生式是否有形如PQ產(chǎn)生式，若有，且aFIRSTVT(P)，則將FP,a置為真，并把(P,a)入棧； (4)重復(fù)(3)，直到?？諡橹?。  5.2定義數(shù)據(jù)結(jié)構(gòu) 在程序中，用兩個(gè)字符數(shù)組vnM和vtN分別用來(lái)存儲(chǔ)所有的非終結(jié)字符集與終結(jié)字符集。為了記錄非終結(jié)符的FIRSTVT集，為此建立一個(gè)布爾數(shù)組FMN，記錄非終結(jié)符的FIRSTVT集。比如，F(xiàn)ij=true表示vtj屬于FIRST

5、VT(vni)，值為false表示相應(yīng)的終結(jié)符不屬于非終結(jié)符的FIRSTVT集。 為了簡(jiǎn)便起見，程序中又構(gòu)造了一個(gè)兩維布爾數(shù)組firstMM+N來(lái)表示推導(dǎo)關(guān)系。數(shù)組第一維的M個(gè)字符代表非終結(jié)符；數(shù)組第二維的前M個(gè)字符代表非終結(jié)符，后N個(gè)字符代表終結(jié)符。以first數(shù)組為例，fistiM+j代表非終結(jié)符vni=P與非終結(jié)符vtj=a有推導(dǎo)關(guān)系P a；fistij代表非終結(jié)符vni=P與非終結(jié)符vtj=Q有推導(dǎo)關(guān)系或PQa.。  相關(guān)的數(shù)據(jù)結(jié)構(gòu)定義如下： char vnM,vtN;  /非終結(jié)字符與終結(jié)字符數(shù)組

6、0;bool firstMM+N,lastMM+N; /以布爾數(shù)組形式定義推導(dǎo)關(guān)系 char vnM,vtN;  /非終結(jié)字符與終結(jié)字符數(shù)組 int stp; /堆棧棧頂指針 符號(hào)棧的數(shù)據(jù)結(jié)構(gòu)： struct relation   int vn;   int vt;   /結(jié)構(gòu)體用來(lái)說(shuō)明終結(jié)符vt與非終結(jié)符vn之間的關(guān)系，若關(guān)系存在說(shuō)明vt屬于FIRSTVT(vn)&

7、#160;六、關(guān)鍵代碼#include<stdio.h>#include<iostream>#define N 10#define M 10using namespace std;/用于存儲(chǔ)FIRSTVT集char FIRSTVT0N,FIRSTVT1N,FIRSTVT2N,FIRSTVT3N,FIRSTVT4N;/接受輸入char INPUTNM; /存儲(chǔ)FIRSTVT集void setFIRSTVT(char X,int T)void FIRSTVT(char X,int S)void main() int i,j; printf("請(qǐng)輸入文法(按兩次回車

8、結(jié)束):n"); for(i=0;i<N;i+) for(j=0;j<M;j+) scanf("%c",&INPUTij); if(INPUTij='n') break; if(INPUTi0='n') break; /保存FIRSTVT集 for(i=0;INPUTi0!='n'i+) FIRSTVT(INPUTi0,i); printf("FIRSTVT SET:n"); for(i=0;INPUTi0!='n'i+) switch(i) case 0: p

9、rintf("FIRSTVT("); printf("%c",INPUT00); printf(")="); for(j=0;FIRSTVT0j!='0'j+) printf("%c",FIRSTVT0j); if(FIRSTVT0j+1!='0') printf(","); printf("n"); break; case 1: printf("FIRSTVT("); printf("%c",INPUT

10、10); printf(")="); for(j=0;FIRSTVT1j!='0'j+) printf("%c",FIRSTVT1j); if(FIRSTVT1j+1!='0') printf(","); printf("n"); break; case 2: printf("FIRSTVT("); printf("%c",INPUT20); printf(")="); for(j=0;FIRSTVT2j!='0&#

11、39;j+) printf("%c",FIRSTVT2j); if(FIRSTVT2j+1!='0') printf(","); printf("n"); break; case 3: printf("FIRSTVT("); printf("%c",INPUT30); printf(")="); for(j=0;FIRSTVT3j!='0'j+) printf("%c",FIRSTVT3j); if(FIRSTVT3j+1!

12、='0') printf(","); printf("n"); break; case 4: printf("FIRSTVT("); printf("%c",INPUT40); printf(")="); for(j=0;FIRSTVT4j!='0'j+) printf("%c",FIRSTVT4j); if(FIRSTVT4j+1!='0') printf(","); printf("n"

13、;); break; default :break; printf("n"); system("pause"); 七、實(shí)驗(yàn)結(jié)果與總結(jié)7.1實(shí)驗(yàn)結(jié)果上圖FIRSTVT集的關(guān)系矩陣中，內(nèi)的終結(jié)字符屬于對(duì)應(yīng)的非終結(jié)字符的FIRSTVT集，從上面兩個(gè)步驟可知用程序運(yùn)算的結(jié)果和分析得到的FIRSTVT集相符合。7.2實(shí)驗(yàn)總結(jié)通過(guò)此次實(shí)驗(yàn)，我復(fù)習(xí)鞏固了自下而上的分析方法，其中重點(diǎn)復(fù)習(xí)了算符優(yōu)先分析算法，對(duì)詞法、文法的判斷有了較深刻的認(rèn)識(shí)，對(duì)算符優(yōu)先分析算法的FirstVT集和LastVT集的構(gòu)造有了更加深刻的理解，對(duì)其中數(shù)據(jù)的流向和數(shù)據(jù)的輸出操作有了很清晰的認(rèn)識(shí)，對(duì)

14、數(shù)據(jù)在該實(shí)驗(yàn)中的存儲(chǔ)和運(yùn)算有了深刻的理解。同時(shí)，此次實(shí)驗(yàn)還增強(qiáng)了我的編碼能力。實(shí)驗(yàn)二 自上而下的語(yǔ)法分析-預(yù)測(cè)分析法設(shè)計(jì)與實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康募由顚?duì)語(yǔ)法分析器工作過(guò)程的理解；加強(qiáng)對(duì)預(yù)測(cè)分析法實(shí)現(xiàn)語(yǔ)法分析程序的掌握；能夠采用一種編程語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單的語(yǔ)法分析程序；能夠使用自己編寫的分析程序?qū)?jiǎn)單的程序段進(jìn)行語(yǔ)法翻譯。二、實(shí)驗(yàn)內(nèi)容用預(yù)測(cè)分析法編制語(yǔ)法分析程序，語(yǔ)法分析程序的實(shí)現(xiàn)可以采用任何一種編程語(yǔ)言和工具。三、實(shí)驗(yàn)要求1. 對(duì)語(yǔ)法規(guī)則有明確的定義；2. 編寫的分析程序能夠?qū)?shí)驗(yàn)一的結(jié)果進(jìn)行正確的語(yǔ)法分析；3. 對(duì)于遇到的語(yǔ)法錯(cuò)誤，能夠做出簡(jiǎn)單的錯(cuò)誤處理，給出簡(jiǎn)單的錯(cuò)誤提示，保證順利完成語(yǔ)法分析過(guò)程；4.

15、 實(shí)驗(yàn)報(bào)告要求用文法的形式對(duì)語(yǔ)法定義做出詳細(xì)說(shuō)明，說(shuō)明語(yǔ)法分析程序的工作過(guò)程，說(shuō)明錯(cuò)誤處理的實(shí)現(xiàn)。四、實(shí)驗(yàn)步驟1. 定義目標(biāo)語(yǔ)言的語(yǔ)法規(guī)則；2. 求解預(yù)測(cè)分析方法需要的符號(hào)集和分析表；3. 依次讀入符號(hào)串，根據(jù)預(yù)測(cè)分析的方法進(jìn)行語(yǔ)法分析，直到源程序結(jié)束；4. 對(duì)遇到的語(yǔ)法錯(cuò)誤做出錯(cuò)誤處理。五、程序設(shè)計(jì)所謂LL（1）分析法，就是指從左到右掃描輸入串（源程序），同時(shí)采用最左推導(dǎo)，且對(duì)每次直接推導(dǎo)只需向前看一個(gè)輸入符號(hào)，便可確定當(dāng)前所應(yīng)當(dāng)選擇的規(guī)則。實(shí)現(xiàn)LL（1）分析的程序又稱為L(zhǎng)L（1）分析程序或LL（1）分析器。我們知道一個(gè)文法要能進(jìn)行LL（1）分析，那么這個(gè)文法應(yīng)該滿足：無(wú)二義性，無(wú)左遞歸，無(wú)

16、左公因子。當(dāng)文法滿足條件后，再分別構(gòu)造文法每個(gè)非終結(jié)符的FIRST和FOLLOW集合，然后根據(jù)FIRST和FOLLOW集合構(gòu)造LL（1）分析表，最后利用分析表，根據(jù)LL(1)語(yǔ)法分析構(gòu)造一個(gè)分析器。LL（1）的語(yǔ)法分析程序包含了三個(gè)部分，總控程序，預(yù)測(cè)分析表函數(shù)，先進(jìn)先出的語(yǔ)法分析棧，本程序也是采用了同樣的方法進(jìn)行語(yǔ)法分析，該程序是采用了JAVA語(yǔ)言來(lái)編寫，其邏輯結(jié)構(gòu)圖如下：STACK分析棧輸出a1 a2 a3 aian#輸入串（源程序）總控程序預(yù)測(cè)分析表MX1Xn-1Xn#LL（1）預(yù)測(cè)分析程序的總控程序在任何時(shí)候都是按STACK棧頂符號(hào)X和當(dāng)前的輸入符號(hào)a做哪種過(guò)程的。對(duì)于任何（X，a），

17、總控程序每次都執(zhí)行下述三種可能的動(dòng)作之一：（）若X = a =#，則宣布分析成功，停止分析過(guò)程。（）若X = a#，則把X從STACK棧頂彈出，讓a指向下一個(gè)輸入符號(hào)。（）若X是一個(gè)非終結(jié)符，則查看預(yù)測(cè)分析表M。若MA，a中存放著關(guān)于X的一個(gè)產(chǎn)生式，那么，首先把X彈出STACK棧頂，然后，把產(chǎn)生式的右部符號(hào)串按反序一一彈出STACK棧（若右部符號(hào)為，則不推什么東西進(jìn)STACK棧）。若MA，a中存放著“出錯(cuò)標(biāo)志”，則調(diào)用出錯(cuò)診斷程序ERROR。事實(shí)上，LL（1）的分析是根據(jù)文法構(gòu)造的，它反映了相應(yīng)文法所定義的語(yǔ)言的固定特征，因此在LL（1）分析器中，實(shí)際上是以LL（1）分析表代替相應(yīng)方法來(lái)進(jìn)行分

18、析的。六、關(guān)鍵代碼LL1_Analysis.javapackage analyse;import java.io.*;import java.util.Stack;public class LL1_Analysis String terminator;/ 終結(jié)符 String nonTerminator;/ 非終結(jié)符 String analysisTable;/ 分析表 public Stack<String> stack = null; StringBuffer strArray; / 字符數(shù)組 int index = 0;/ 字符數(shù)組索引值 / 匹配結(jié)果：無(wú)效輸入，成功（均為#

19、）， 兩字符相等（且不等于#）， 彈棧（產(chǎn)生式為）， 壓棧（將產(chǎn)生式反序入棧）， 錯(cuò)誤（棧值為null） enum Type INVALID_STR, SUCCESS, EQUAL, POP_STACK, PUSH_STR, ERROR FileWriter writer = null; void temp() /* * 執(zhí)行預(yù)測(cè)分析法 */ public void run() initialization(); analysis(); public String find (String str1, String str2) void analysis()/ 從輸入串?dāng)?shù)組讀一個(gè)StringS

20、tring readFromStrArray(StringBuffer strArray) / 輸入串指針前移void indexForward() / 返回當(dāng)前輸入串索引int getIndex() / 判斷輸入串指針是否在合理范圍boolean isIndexInStrArray() / 當(dāng)前字符與棧頂元素匹配public Type match(String pop, String str) boolean isTerminator(String str) boolean isNonTerminator(String str) boolean isValidStr(String str)

21、void printState(String production) String printStrArray() String printStack() /* * 全局初始化 */public void initialization() / 初始化終結(jié)符void initTerminator() / 初始化非終結(jié)符void initNonTerminator() / 初始化分析表void initAnalysisTable() / 初始化棧void initStack() /* * 從命令行讀取輸入串 * throws IOException */String readFromConsole

22、() throws IOException 七、實(shí)驗(yàn)結(jié)果與總結(jié)7.1實(shí)驗(yàn)結(jié)果正確輸入下的結(jié)果：非法輸入下的結(jié)果：7.2實(shí)驗(yàn)總結(jié)通過(guò)此次實(shí)驗(yàn)，我學(xué)習(xí)并了解了如何設(shè)計(jì)、編寫和調(diào)試預(yù)測(cè)分析程序，加深了對(duì)自上而下分析原理的理解；熟悉了預(yù)測(cè)分析程序的工作過(guò)程以及構(gòu)造預(yù)測(cè)分析表的相關(guān)原理，并使用JAVA語(yǔ)言直接編寫了此語(yǔ)法分析程序。另外，此次實(shí)驗(yàn)也讓我重新熟悉了JAVA語(yǔ)言的相關(guān)內(nèi)容，加深了對(duì)JAVA語(yǔ)言功能的理解。實(shí)驗(yàn)三 中間代碼生成一、實(shí)驗(yàn)?zāi)康氖煜に阈g(shù)表達(dá)式的語(yǔ)法分析與中間代碼生成原理。二、實(shí)驗(yàn)內(nèi)容完成以下描述賦值語(yǔ)句和算術(shù)表達(dá)式文法的語(yǔ)法制導(dǎo)生成中間代碼四元式的過(guò)程。GA:AV:=EEE+TE-TT

23、T*FT/FFF(E)iVi說(shuō)明：終結(jié)符號(hào)i 為用戶定義的簡(jiǎn)單變量,即標(biāo)識(shí)符的定義。三、實(shí)驗(yàn)要求1給出每一產(chǎn)生式對(duì)應(yīng)的語(yǔ)義動(dòng)作；2設(shè)計(jì)中間代碼四元式的結(jié)構(gòu)（暫不與符號(hào)表有關(guān)）；3. 輸入串應(yīng)是詞法分析的輸出二元式序列，即某算術(shù)表達(dá)式“實(shí)驗(yàn)項(xiàng)目一”的輸出結(jié)果。輸出為輸入串的四元式序列中間文件；4設(shè)計(jì)兩個(gè)測(cè)試用例（盡可能完備），并給出程序執(zhí)行結(jié)果四元式序列。四、實(shí)驗(yàn)步驟1問(wèn)題理解和分析：充分地分析和理解問(wèn)題本身，弄清要求做什么； 2確定解決問(wèn)題的方法：主要是找到解決問(wèn)題的主要思路，該怎么做；3詳細(xì)設(shè)計(jì)和編碼：確定算法的主要流程，再進(jìn)行編程；4程序調(diào)試和運(yùn)行：掌握程序調(diào)試和排錯(cuò)的基本方法，

24、增加編程的感覺(jué)和解決問(wèn)題的成就感；5完成實(shí)驗(yàn)報(bào)告。五、程序設(shè)計(jì)5.1 數(shù)據(jù)結(jié)構(gòu)描述本程序采用的是算符優(yōu)先文法，文法以及算符優(yōu)先矩陣是根據(jù)第一次實(shí)驗(yàn)來(lái)修改的，所以主要的數(shù)據(jù)結(jié)構(gòu)也跟第一次差不多，主要為文法的表示，F(xiàn)irstVT集和LastVT集以及算符優(yōu)先矩陣：struct infochar left;vector<string> right;vector<char> first;vector<char> last;算符優(yōu)先矩陣采用二維字符數(shù)組表示的：char mtr99; /算符優(yōu)先矩陣5.2程序結(jié)構(gòu)描述：本程序一共有10個(gè)功能函數(shù)：void get();

25、/獲取文法void print(); /打印文法void fun(); /求FirstVT 和 LastVTvoid fun_show(); /打印FirstVT 和 LastVTvoid matrix(); /求算符優(yōu)先矩陣void matrix_show(); /打印算符優(yōu)先矩陣void test(); /測(cè)試文法int cmp(char a,char b); /比較兩個(gè)運(yùn)算符的優(yōu)先級(jí) 1 0 -1void out(char now,int avg1,int avg2); /打印四元式int ope(char op,int a,int b); /定義四元式計(jì)算方法六、關(guān)鍵代碼#includ

26、e <iostream>#include <string>#include <VECTOR>#include <stack>using namespace std;struct infochar left;vector<string> right;vector<char> first;vector<char> last;vector<info> lang;char mtr99; /算符優(yōu)先矩陣stack<char> sta;void get(); /獲取文法void print(); /

27、打印文法void fun(); /求FirstVT 和 LastVTvoid fun_show(); /打印FirstVT 和 LastVTvoid matrix(); /求算符優(yōu)先矩陣void matrix_show(); /打印算符優(yōu)先矩陣void test(); /測(cè)試文法int cmp(char a,char b); /比較兩個(gè)運(yùn)算符的優(yōu)先級(jí) 1 0 -1void out(char now,int avg1,int avg2); /打印四元式int ope(char op,int a,int b); /定義四元式計(jì)算方法int main()int choose;get();fun();matrix();while(1)cout << "*" << endl;cout << " 打印文法請(qǐng)按 1" << endl;cout << " 查看FirstV