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

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

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

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

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

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

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

6、需要，我將源程序中的單詞符號分為：保留字，字母（標(biāo)識符）， 界符三類，統(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é)束符號或者非法字符。 流程圖如下：

7、 詞法分析流程圖 四． 語法分析 ．源程序中涉及的文法G[P]定義如下表： 說明語句 表達(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é)符。對于有規(guī)約動作和接受的狀態(tài)，將其特別標(biāo)明。文法G[P]的DFA圖如下： 有歸約動作 8 12 7 6 5 : int 說明語句 接受狀態(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 五． 語義分析和中間代碼生成 　 載語法分析過程中，隨著分析的步步進(jìn)展，根據(jù)每個(gè)產(chǎn)生式所對應(yīng)的語義子程序（或語義規(guī)則描述的語義動作）進(jìn)行翻譯的辦法稱作語法制導(dǎo)翻譯。 語法制導(dǎo)翻譯 歸約動作 翻譯方案 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} 語法翻譯生成的四元式如下： 六． 代碼生成 目標(biāo)代碼生成階段的任務(wù)是把中間代碼變換成特定機(jī)器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼。這是編譯的最后階段，它的工作與硬件系統(tǒng)結(jié)構(gòu)和指令含義有關(guān)，這個(gè)階段的工作很復(fù)雜，涉及到硬件系統(tǒng)功能部件的運(yùn)用、機(jī)器指令的選擇、各種數(shù)據(jù)類型變量的存儲空間分配以及寄存器和后緩寄存器的調(diào)度等。本程序生成的目標(biāo)代碼與0x8086微處理器兼容

35、。 下面列舉幾個(gè)簡單的四元式與匯編代碼的轉(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．輸出符號表的內(nèi)容 5． 輸出語法分析的結(jié)

37、果（本程序采用自下而上的LR語法分析） 6．輸出中間代碼 7．輸出目標(biāo)代碼 十． 總結(jié) 通過本次實(shí)驗(yàn)，對編譯程序各階段有了更深刻更深入的了解，也糾正了自己在某些方面的的錯(cuò)誤，豐富了自己關(guān)于編譯原理方面的知識。同時(shí)也培養(yǎng)了自己熱愛思考，勤查資料的習(xí)慣。由于水平本次實(shí)驗(yàn)涉及面并不是很全面，我只考慮了c語言的一個(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;//遞增編號 token *next; }; tok

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

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

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

42、}; symb *symb_head,*symb_tail;//語義符號鏈表 ////////////////////////////////詞法分析有關(guān)函數(shù)聲明 void outdaima() ; void scan();//按字符讀取源文件 void cifa_main();//詞法分析主程序 int judge(char ch);//判斷輸入字符的類型 void out1(char ch);//寫入token.txt void out3(char ch,string word);//寫入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)文件中 ////////////////////////////////語法分析有關(guān)函數(shù)聲明 void yufa_main();//語法分析主程序 void yufa_initialize();//初始化語法分析數(shù)據(jù)結(jié)構(gòu) int yufa_SLR1(int a);//語法分析主體部分 int ID1(int a);//給輸入字符編號，轉(zhuǎn)化成action表列編號

44、string ID10(int i);//給輸入字符反編號 int ID2(char ch);//給非終結(jié)狀態(tài)編號，轉(zhuǎn)化成go_to表列編號 int ID20(char ch);//給非終結(jié)狀態(tài)編號 char ID21(int j);//給非終結(jié)狀態(tài)反編號 void add(ike *temp);//給ike分析棧鏈表增加一個(gè)結(jié)點(diǎn) void del();//給ike分析棧鏈表刪除一個(gè)結(jié)點(diǎn) /////////////////////////////////語義分析相關(guān)函數(shù)的聲明 void yuyi_main(int m);//語義分析主程序 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);//向語義符號表鏈中加一個(gè)結(jié)點(diǎn) void output_yuyi();//輸出中間代碼四元式和最后符號表 string newop(int m);//把數(shù)字變成字符串 string id_numtoname(int num);//把編號轉(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;//語義臨時(shí)變量 string E_name,T_name,F_name,M_name,id_name,id1_name,id2_name,errword;//用于歸約時(shí)名稱傳遞和未聲明變量的輸出 int id_num,id1_num,id2_num,id_left,id_while,id_then,id_do;//用

47、于記錄一些特殊的字符位置信息 ////////////////////////////////主程序開始 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<<"請輸入源文件路徑及名稱:"; 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<<"符號表內(nèi)容如下："<next; while(temp3!=NULL) { cout<num<<" "<word<

64、mp3=temp3->next; } } void outfile() { ofstream fout1("token.txt");//寫文件 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; } } /////////////////////////////////////////語法分析子程序 void yufa_main() { if(err==0) { system("pause"

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