編譯器編譯原理課程設(shè)計(jì)[共63頁(yè)][共62頁(yè)]

《編譯器編譯原理課程設(shè)計(jì)[共63頁(yè)][共62頁(yè)]》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《編譯器編譯原理課程設(shè)計(jì)[共63頁(yè)][共62頁(yè)]（63頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 廣西大學(xué) 編譯原理課程設(shè)計(jì) 專(zhuān) 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 姓 名： 課 程： 編譯原理 指導(dǎo)教師： 目錄 一．程序簡(jiǎn)介與分析---------------------------------------------------------1 二．程序適用范圍-------------------------------

2、----------------------------1 三．詞法分析---------------------------------------------------------------1 四．語(yǔ)法分析---------------------------------------------------------------3 五．語(yǔ)義分析和中間代碼生成------------------------------------------------9 六．代碼生成-----------------------------------------------

3、---------------11 七．流程圖----------------------------------------------------------------12 八．實(shí)現(xiàn)------------------------------------------------------------------13 九．程序運(yùn)行結(jié)果----------------------------------------------------------13 十．總結(jié)----------------------------------------------------

4、--------------18 十一.附錄（源程序）--------------------------------------------------------19 簡(jiǎn)單的編譯程序設(shè)計(jì) 一． 程序簡(jiǎn)介與分析 本程序由四個(gè)部分組成：詞法分析子程序，語(yǔ)法分析子程序，語(yǔ)義分析子程序，目標(biāo)代碼生成程序。本程序輸入一個(gè)叫haominjie.txt的c語(yǔ)言源程序，然后對(duì)它進(jìn)行詞法，語(yǔ)法，語(yǔ)義分析，并輸出匯編代碼。 詞法分析輸入的是c語(yǔ)言源程序，輸出的3是具有獨(dú)立語(yǔ)法意義的單詞符號(hào)。 語(yǔ)法分析以詞法分析產(chǎn)生的編碼流為輸入，

5、按照SLR(1)分析方法進(jìn)行語(yǔ)法分析，產(chǎn)生語(yǔ)法樹(shù)，輸出移進(jìn)和歸約的動(dòng)作，如果源程序不符合文法，則有“語(yǔ)法分析出錯(cuò)”的提示。 語(yǔ)義分析階段，在語(yǔ)法分析的同時(shí)，在歸約的時(shí)候，給出相應(yīng)的語(yǔ)義動(dòng)作，最后輸出中間代碼四元式和新的符號(hào)表，如果有未聲明的變量出現(xiàn)，則會(huì)提示出出錯(cuò)，并顯示出此變量的名稱(chēng)。 代碼生成階段，將語(yǔ)義分析得到的中間代碼四元式轉(zhuǎn)化為匯編語(yǔ)言的目標(biāo)代碼并輸出。 二． 程序適用范圍 本程序的使用范圍為：整型常量，四則運(yùn)算（為了簡(jiǎn)化問(wèn)題，本程序只考慮加法運(yùn)算和乘法運(yùn)算）和布爾表達(dá)式以及相應(yīng)的賦值語(yǔ)句，條件轉(zhuǎn)移語(yǔ)句和循環(huán)語(yǔ)句。 三． 詞法分析 根據(jù)詞法分析的

6、需要，我將源程序中的單詞符號(hào)分為：保留字，字母（標(biāo)識(shí)符）， 界符三類(lèi)，統(tǒng)一用一張表表示如下： 界符，保留字表 單詞 = + * > : ; { } ( ) and if then while do int 標(biāo)志符 編碼 1 2 3 4 5 6 7 8 9 10 31 32 33 35 36 37 25 程序從源程序文件haominjie.txt中一次讀入一個(gè)字符，并判斷它是不是字母，界符， 保留字，空格，換行，結(jié)束符號(hào)或者非法字符。 流程圖如下：

7、 詞法分析流程圖 四． 語(yǔ)法分析 ．源程序中涉及的文法G[P]定義如下表： 說(shuō)明語(yǔ)句 表達(dá)式 布爾表達(dá)式 句法 0、P’→P 1、P→id () L;R 2、L→L;D 3、L→D 4、D→id:int 5、E→E+T 6、E→T 7、T→T*F 8、T→F 9、F→(E) 10、F→id 11、B→B and B 12、B→id>id 13、M→id=E 14、S→if B then M 15、S→while

8、 B do M 16、S→M 17、N→N;S 18、N→S 19、R→{N} .上述文法的每個(gè)非終結(jié)符的FIRST 集和FOLLOW集如下表： FIRST 集 FOLLOW 集 P { id } { # } L { id } { ; } D { id } { ; } E {(,id } { },;,+,),#} T {(,id } { },;,+,),*,#} F

9、 {(,id } { },;,+,),*,#} B { id } {then,do,and} M { id } { },;} S {id,while,if} { },;} N {id,while,if} { },;} R { { } { # } .文法G[P]的項(xiàng)目集部分如下： 0. P’→.P 1. P’→P. 2. P→.id()L;R 3. P→id.()L;R

10、 4. P→id(.)L;R 5. P→id().L;R 6. P→id()L.;R 7. P→id()L;.R 8. P→id()L;R. 9. L→.L;D 10.L→L.;D 11. L→L;.D 12. L→L;D. 13.D→.id:int 14. D→id .:int 15. D→id: .int 16. D→id:int. 17.E→.E+T 18. E→E.+T 19. E→E+.T 20. E→E

11、+T. 21. E→.T 22. E→T. 23. T→.T*F 24. T→T.*F 25. T→T*.F 26. T→T*F. 27. T→.F 28. T→F. 29. F→ (E) 30. F→ (.E) 31. F→ (E.) 32. F→ (E). 33. F→.id 34. F→id. .再由項(xiàng)目集構(gòu)造文法的DFA活前綴。為了方便，省去了項(xiàng)目

12、族集的每個(gè)狀態(tài)的項(xiàng)目，直接在狀態(tài)轉(zhuǎn)換的箭頭上標(biāo)明終結(jié)符或非終結(jié)符。對(duì)于有規(guī)約動(dòng)作和接受的狀態(tài)，將其特別標(biāo)明。文法G[P]的DFA圖如下： 有歸約動(dòng)作 8 12 7 6 5 : int 說(shuō)明語(yǔ)句 接受狀態(tài) D id D id 3 0 2 1 4 9 10 11

13、 R ; L ) ( id P 26 25 24 23 { if B then M 27 14 30 29 20 28 19 17 18 22 21 13 id and id 句法 S

14、 id = } if id M N ; S id M while while B do M

15、 id and 35 34 31 id B 布爾表達(dá)式 > and 32 33 id 15 36 T id 38

16、 id ( F E 37 16 * ( 40 39 41 F ( id F id + E ( 表達(dá)式 43

17、 42 + ) T 44 45 * G[P]：SLR（1）分析表 Action goto id ( ) ; : * + > = { } int and if then while do $ P D R

18、E T F B M S L N 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 0 1 2 3 4 5 6 7 8 9 10 0 s2 1 1 acc 2 s3

19、 3 s4 4 s5 8 9 5 s6 6 s7 7 r4

20、 8 r3 9 s10 10 s5 s13 12 11 11 r1 12

21、 r2 13 s14 s23 s27 22 21 17 14 s15 15 s36 s41 16 38 37 16 r13 s43

22、 r13 17 s19 s18 18 r19 19 s14 s23 s27 22 20 G[P]：SLR（1）分析表 Action goto id ( ) ; :

23、 * + > = { } int and if then while do $ P D R E T F B M S L N 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 0 1 2 3 4 5 6 7 8 9 10 20 r17 r17 21 r18 r18

24、 22 r16 r16 23 s31 24 24 s34 s25 25 s14 26 26

25、r14 r14 27 s31 28 28 s34 29 s14 s29 30 30 r15 r15

26、 31 s32 32 s33 33 r12 r12 r12 34 s31 35 35

27、 r11 r11 r11 36 r10 r10 r10 r10 r10 37 r8 r8 r8 r8 r8 38 r6 r6 s39 r6 r6 39 s36 s4

28、1 40 G[P]：SLR（1）分析表 action goto id ( ) ; : * + > = { } int and if then while do $ P D R E T F B M S L N 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 0 1 2 3 4 5 6 7 8 9 10 40

29、r7 r7 r7 r7 r7 41 s36 s41 42 38 37 42 s45 s43 43 s36 s41 44 37 44 r5 r5 s39

30、 r5 r5 45 r9 r9 r9 r9 r9 五． 語(yǔ)義分析和中間代碼生成 　 載語(yǔ)法分析過(guò)程中，隨著分析的步步進(jìn)展，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義子程序（或語(yǔ)義規(guī)則描述的語(yǔ)義動(dòng)作）進(jìn)行翻譯的辦法稱(chēng)作語(yǔ)法制導(dǎo)翻譯。 語(yǔ)法制導(dǎo)翻譯 歸約動(dòng)作 翻譯方案 E→E+T E→E1+T {E.place=newtemp; Emit(E.place’:=’E1.place’+’T.

31、place);} E→T E→T { E.place:=T.place;} T→T*F T→T1*F {T.place=newtemp; Emit(T.place’:=’ T1.place’+’F.place);} T→F T→F {T.place:=F.place;} F→(E) F→(E) {F.place:=E.place;} F→id F→id {p:=lookup(id.name); if p<>nil then F.place:=p else error;} B→B and B B→B1 and A B2

32、{backpatch(B1.truelist,A.quad); B.truelist:=B2.truelist; B.falselist:=merge(B1.falselist,B2.falselist);} A→∈{A.quad:=nextquad} B→id>id B→id1>id2 {B.truelist:=makelist(nextquad); B.falselist:=makelist(nextquad+1); emit(if id1.place’>’id2.place’goto_ _’); emit(’goto_ _’);} M→id=E M→id=

33、E { p:=lookup(id.name); if p<>nil then emit(p’:=’E.place) else error;} S→if B then M S→if B then A M {backpatch(B.truelist,A.quad) backpatch(B.falselist,nextquad)} A→∈{A.quad:=nextquad} S→while B do M S→while A1 B do A2 M { backpatch(B.truelist,A2.quad) backpatch(B.falselist,ne

34、xtquad+1) emit(’goto’A1.quad)} A1→∈{A1.quad:=nextquad} A2→∈{A2.quad:=nextquad} 語(yǔ)法翻譯生成的四元式如下： 六． 代碼生成 目標(biāo)代碼生成階段的任務(wù)是把中間代碼變換成特定機(jī)器上的絕對(duì)指令代碼或可重定位的指令代碼或匯編指令代碼。這是編譯的最后階段，它的工作與硬件系統(tǒng)結(jié)構(gòu)和指令含義有關(guān)，這個(gè)階段的工作很復(fù)雜，涉及到硬件系統(tǒng)功能部件的運(yùn)用、機(jī)器指令的選擇、各種數(shù)據(jù)類(lèi)型變量的存儲(chǔ)空間分配以及寄存器和后緩寄存器的調(diào)度等。本程序生成的目標(biāo)代碼與0x8086微處理器兼容

35、。 下面列舉幾個(gè)簡(jiǎn)單的四元式與匯編代碼的轉(zhuǎn)化列子： ．（+，A，B，T）→ MOV R ，A ； ADD R ，B ; ST R , T . ( *, A , B , T ) → MOV R ，A ； MUL R ，B ; ST R , T . ( J, _ , _ , L) → JMP L . ( J> , A , B , L ) → MOV R , A CMP R , B JB L . ( =,A , _ ,T ) → LD R , A ST R , T

36、本程序生成的目標(biāo)代碼如下： 七． 程序流程圖 編譯程序流程圖 八． 實(shí)現(xiàn) 本程序運(yùn)行的硬件環(huán)境為CPU 2GHZ ,內(nèi)存為4G .軟件環(huán)境為windows 8.1 系統(tǒng)，Visual C++環(huán)境。 九． 程序運(yùn)行結(jié)果 1． 輸入源文件路徑： 2． 輸出保留字 3．輸出符號(hào)表的內(nèi)容 5． 輸出語(yǔ)法分析的結(jié)

37、果（本程序采用自下而上的LR語(yǔ)法分析） 6．輸出中間代碼 7．輸出目標(biāo)代碼 十． 總結(jié) 通過(guò)本次實(shí)驗(yàn)，對(duì)編譯程序各階段有了更深刻更深入的了解，也糾正了自己在某些方面的的錯(cuò)誤，豐富了自己關(guān)于編譯原理方面的知識(shí)。同時(shí)也培養(yǎng)了自己熱愛(ài)思考，勤查資料的習(xí)慣。由于水平本次實(shí)驗(yàn)涉及面并不是很全面，我只考慮了c語(yǔ)言的一個(gè)子集。當(dāng)然本程序的算法在某些地方也還存在一些缺陷。 十一． 附錄（源程序） 本程序輸入的c源代碼如下： haominjie() a:int; b:int; ccc:int; d:int; { if ccc>b

38、and ccc>a then a=b+a; while ccc>d do a=d; a=(b+ccc)*a+d } 本程序的完整源代碼如下： #include #include #include #include #include #include using namespace std; struct token//詞法 token結(jié)構(gòu)體 { int code;//編碼 int num;//遞增編號(hào) token *next; }; tok

39、en *token_head,*token_tail;//token隊(duì)列 struct str//詞法 string結(jié)構(gòu)體 { int num;//編號(hào) string word;//字符串內(nèi)容 str *next; }; str *string_head,*string_tail;//string隊(duì)列 struct ivan//語(yǔ)法 產(chǎn)生式結(jié)構(gòu)體 { char left;//產(chǎn)生式的左部 string right;//產(chǎn)生式的右部 int len;//產(chǎn)生式右部的長(zhǎng)度 }; ivan css[20];//語(yǔ)法 20個(gè)產(chǎn)生式 struct pank//

40、語(yǔ)法 action表結(jié)構(gòu)體 { char sr;//移進(jìn)或歸約 int state;//轉(zhuǎn)到的狀態(tài)編號(hào) }; pank action[46][18];//action表 int go_to[46][11];//語(yǔ)法 go_to表 struct ike//語(yǔ)法 分析棧結(jié)構(gòu)體，雙鏈 { ike *pre; int num;//狀態(tài) int word;//符號(hào)編碼 ike *next; }; ike *stack_head,*stack_tail;//分析棧首尾指針 struct L//語(yǔ)義四元式的數(shù)據(jù)結(jié)構(gòu) { int k; string op;/

41、/操作符 string op1;//操作數(shù) string op2;//操作數(shù) string result;//結(jié)果 L *next;//語(yǔ)義四元式向后指針 L *Ltrue;//回填true鏈向前指針 L *Lfalse;//回填false鏈向前指針 }; L *L_four_head,*L_four_tail,*L_true_head,*L_false_head;/*四元式鏈，true鏈，false鏈*/ struct symb//語(yǔ)義輸入時(shí)符號(hào)表 { string word;//變量名稱(chēng) int addr;//變量地址 symb *next;

42、}; symb *symb_head,*symb_tail;//語(yǔ)義符號(hào)鏈表 ////////////////////////////////詞法分析有關(guān)函數(shù)聲明 void outdaima() ; void scan();//按字符讀取源文件 void cifa_main();//詞法分析主程序 int judge(char ch);//判斷輸入字符的類(lèi)型 void out1(char ch);//寫(xiě)入token.txt void out3(char ch,string word);//寫(xiě)入string.txt void input1(token *temp);//插入

43、結(jié)點(diǎn)到隊(duì)列token void input3(str *temp);//插入結(jié)點(diǎn)到隊(duì)列string void output();//輸出三個(gè)隊(duì)列的內(nèi)容 void outfile();//輸出三個(gè)隊(duì)列的內(nèi)容到相應(yīng)文件中 ////////////////////////////////語(yǔ)法分析有關(guān)函數(shù)聲明 void yufa_main();//語(yǔ)法分析主程序 void yufa_initialize();//初始化語(yǔ)法分析數(shù)據(jù)結(jié)構(gòu) int yufa_SLR1(int a);//語(yǔ)法分析主體部分 int ID1(int a);//給輸入字符編號(hào)，轉(zhuǎn)化成action表列編號(hào)

44、string ID10(int i);//給輸入字符反編號(hào) int ID2(char ch);//給非終結(jié)狀態(tài)編號(hào)，轉(zhuǎn)化成go_to表列編號(hào) int ID20(char ch);//給非終結(jié)狀態(tài)編號(hào) char ID21(int j);//給非終結(jié)狀態(tài)反編號(hào) void add(ike *temp);//給ike分析棧鏈表增加一個(gè)結(jié)點(diǎn) void del();//給ike分析棧鏈表刪除一個(gè)結(jié)點(diǎn) /////////////////////////////////語(yǔ)義分析相關(guān)函數(shù)的聲明 void yuyi_main(int m);//語(yǔ)義分析主程序 void add_L_four

45、(L *temp);//向四元式鏈中加一個(gè)結(jié)點(diǎn) void add_L_true(L *temp);//向true鏈中加一個(gè)結(jié)點(diǎn) void add_L_false(L *temp);//向false鏈中加一個(gè)結(jié)點(diǎn) void add_symb(symb *temp);//向語(yǔ)義符號(hào)表鏈中加一個(gè)結(jié)點(diǎn) void output_yuyi();//輸出中間代碼四元式和最后符號(hào)表 string newop(int m);//把數(shù)字變成字符串 string id_numtoname(int num);//把編號(hào)轉(zhuǎn)換成相應(yīng)的變量名 int lookup(string m);//變量聲明檢查

46、/////////////////////////////////全局變量的聲明 FILE *fp;//文件指針 int wordcount;//標(biāo)志符計(jì)數(shù) int err;//標(biāo)志詞法分析結(jié)果正確或錯(cuò)誤 int nl;//讀取行數(shù) int yuyi_linshi;//語(yǔ)義臨時(shí)變量 string E_name,T_name,F_name,M_name,id_name,id1_name,id2_name,errword;//用于歸約時(shí)名稱(chēng)傳遞和未聲明變量的輸出 int id_num,id1_num,id2_num,id_left,id_while,id_then,id_do;//用

47、于記錄一些特殊的字符位置信息 ////////////////////////////////主程序開(kāi)始 int main() { cout<<"************************"<

48、*****************"<next=NULL; token_tail=new token; tok

49、en_tail->next=NULL; string_head=new str; string_head->next=NULL; string_tail=new str; string_tail->next=NULL;//初始化三個(gè)隊(duì)列的首尾指針 L_four_head=new L; L_four_head->next=NULL; L_four_tail=new L; L_four_tail->k=0; L_four_tail->next=NULL; L_true_head=new L; L_true_head->Ltrue=NULL; L_fa

50、lse_head=new L; L_false_head->Lfalse=NULL; symb_head=new symb; symb_head->next=NULL; symb_tail=new symb; symb_tail->next=NULL; yuyi_linshi=-1; id_num=0; wordcount=0;//初始化字符計(jì)數(shù)器 err=0;//初始化詞法分析錯(cuò)誤標(biāo)志 nl=1;//初始化讀取行數(shù) scan(); if(err==0) { char m; output(); cout<<"詞法分析正確完成

51、!"<>m; cout<

52、]; int flag=0; cout<<"請(qǐng)輸入源文件路徑及名稱(chēng):"; cin>>document; cout<

53、) { word=""; ch=fgetc(fp); flag=judge(ch); if(flag==1) out1(ch); else if(flag==3) out3(ch,word); else if(flag==4 || flag==5 ||flag==6) continue; else { cout<

54、 flag=0; if(ch=='=' || ch=='+' || ch=='*' || ch=='>' || ch==':' || ch==';' || ch=='{' || ch=='}' || ch=='(' || ch==')') flag=1;//界符 else if(('a'<=ch && ch<='z') || ('A'<=ch && ch<='Z')) flag=3;//字母 else if(ch==' ') flag=4;//空格 else if(feof(fp)) flag=5;//結(jié)束 else if(ch=='\n') {

55、 flag=6;//換行 nl++; } else flag=0;//非法字符 return(flag); } void out1(char ch) { int id; switch(ch) { case '=' : id=1;break; case '+' : id=2;break; case '*' : id=3;break; case '>' : id=4;break; case ':' : id=5;break; case ';' : id=6;break; case '{' : id=7;break; c

56、ase '}' : id=8;break; case '(' : id=9;break; case ')' : id=10;break;//界符編碼 default : id=0; } token *temp; temp=new token; temp->code=id; temp->num=-1; temp->next=NULL; input1(temp); return; } void out3(char ch,string word) { token *temp; temp=new token; temp->code=-1;

57、 temp->num=-1; temp->next=NULL; str *temp1; temp1=new str; temp1->num=-1; temp1->word=""; temp1->next=NULL; int flag=0; word=word+ch; ch=fgetc(fp); flag=judge(ch); if(flag==1 || flag==4 || flag==5 || flag==6) { if(word=="and" || word=="if" || word=="then" || word=="while"

58、 || word=="do" || word=="int") { if(word=="and") temp->code=31; else if(word=="if") temp->code=32; else if(word=="then") temp->code=33; else if(word=="while") temp->code=35; else if(word=="do") temp->code=36; else if(word=="int") temp->code=37

59、;//關(guān)鍵字編碼 input1(temp); if(flag==1) out1(ch); else if(flag==4 || flag==5 || flag==6) return; } else if(flag==1) { wordcount++; temp->code=25; temp->num=wordcount; input1(temp); temp1->num=wordcount; temp1->word=word; input3(temp1); out1(c

60、h); } else if(flag==4 || flag==5 || flag==6) { wordcount++; temp->code=25; temp->num=wordcount; input1(temp); temp1->num=wordcount; temp1->word=word; input3(temp1); } return; } else if(flag==2 || flag==3) out3(ch,word);//形成字符串 else { err=1;

61、 cout<next == NULL) { token_head->next=temp; token_tail->next=temp; } else { token_tail->next->next=temp; token_tail->next=temp; } } void input3(str *temp) { if(string_head-

62、>next == NULL) { string_head->next=temp; string_tail->next=temp; } else { string_tail->next->next=temp; string_tail->next=temp; } } void output() { cout<<"token表內(nèi)容如下："<next; while(temp1!=NULL) { cout<

63、p1->code; if(temp1->num == -1) { cout<num<next; } cout<<"符號(hào)表內(nèi)容如下："<next; while(temp3!=NULL) { cout<num<<" "<word<

64、mp3=temp3->next; } } void outfile() { ofstream fout1("token.txt");//寫(xiě)文件 ofstream fout3("string.txt"); token *temp1; temp1=new token; temp1=token_head->next; while(temp1!=NULL) { fout1<code; if(temp1->num == -1) fout1<num<

65、ndl; temp1=temp1->next; } str *temp3; temp3=new str; temp3=string_head->next; while(temp3!=NULL) { fout3<num<<" "<word<next; } } /////////////////////////////////////////語(yǔ)法分析子程序 void yufa_main() { if(err==0) { system("pause"

66、); cout<next; int p,q; p=0; q=0; cout<<"語(yǔ)法分析過(guò)程如下："<code); p=yufa_SLR1(w); if(p==1) break; if(p==0) temp=temp->next; if(temp==NULL) q=1; }//語(yǔ)法分析 if(q==1) while(1) { p=yu