編譯原理課程設(shè)計(jì)C語(yǔ)言編譯器的實(shí)現(xiàn)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上編譯原理課程設(shè)計(jì)C語(yǔ)言編譯器的實(shí)現(xiàn)專心-專注-專業(yè)揚(yáng)州大學(xué)編譯原理課程設(shè)計(jì) 學(xué) 號(hào)： 姓 名： 專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 課 程： 編譯原理 指導(dǎo)教師： 陳宏建 目錄一程序簡(jiǎn)介與分析-3二程序適用范圍-3三詞法分析-3四語(yǔ)法分析-4五語(yǔ)義分析和中間代碼生成-10六代碼生成-12七流程圖-13八實(shí)現(xiàn)-14九程序運(yùn)行結(jié)果-14十總結(jié)-18十一.附錄（源程序）-18 簡(jiǎn)單的編譯程序設(shè)計(jì)一 程序簡(jiǎn)介與分析本程序由四個(gè)部分組成：詞法分析子程序，語(yǔ)法分析子程序，語(yǔ)義分析子程序，目標(biāo)代碼生成程序。本程序輸入一個(gè)叫l(wèi)ibo.txt的c語(yǔ)言源程序，然后對(duì)它進(jìn)行詞法，語(yǔ)法，語(yǔ)義分析，并

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

3、及相應(yīng)的賦值語(yǔ)句，條件轉(zhuǎn)移語(yǔ)句和循環(huán)語(yǔ)句。三 詞法分析根據(jù)詞法分析的需要，我將源程序中的單詞符號(hào)分為：保留字，字母（標(biāo)識(shí)符），界符三類，統(tǒng)一用一張表表示如下：界符，保留字表單詞=+*>:;()andifthenwhiledoint標(biāo)志符編碼1234567891031323335363725程序從源程序文件libo.txt中一次讀入一個(gè)字符，并判斷它是不是字母，界符，保留字，空格，換行，結(jié)束符號(hào)或者非法字符。流程圖如下： 詞法分析流程圖四 語(yǔ)法分析源程序中涉及的文法GP定義如下表：說明語(yǔ)句表示式布爾表示式句法0、PP1、Pid () L;R2、LL;D3、LD4、Did:int5、EE+T

4、6、ET7、TT*F8、TF9、F(E)10、Fid11、BB and B12、Bid>id13、Mid=E14、Sif B then M15、Swhile B do M16、SM17、NN;S18、NS19、RN.上述文法的每個(gè)非終結(jié)符的FIRST 集和FOLLOW集如下表： FIRST 集 FOLLOW 集P id # L id ; D id ; E (,id ,;,+,),#T (,id ,;,+,),*,#F (,id ,;,+,),*,#B id then,do,andM id ,; S id,while,if ,; N id,while,if ,; R # .文法GP的項(xiàng)目集

5、部分如下：0. P.P 1. PP.2. P.id()L;R 3. Pid.()L;R 4. Pid(.)L;R 5. Pid().L;R 6. Pid()L.;R 7. Pid()L;.R 8. Pid()L;R. 9. L.L;D10.LL.;D 11. LL;.D 12. LL;D. 13.D.id:int 14. Did .:int 15. Did: .int 16. Did:int. 17.E.E+T 18. EE.+T 19. EE+.T 20. EE+T. 21. E.T 22. ET. 23. T.T*F 24. TT.*F 25. TT*.F 26. TT*F. 27. T.

6、F 28. TF. 29. F (E) 30. F (.E) 31. F (E.) 32. F (E). 33. F.id 34. Fid. .再由項(xiàng)目集構(gòu)造文法的DFA活前綴。為了方便，省去了項(xiàng)目族集的每個(gè)狀態(tài)的項(xiàng)目，直接在狀態(tài)轉(zhuǎn)換的箭頭上標(biāo)明終結(jié)符或非終結(jié)符。對(duì)于有規(guī)約動(dòng)作和接受的狀態(tài)，將其特別標(biāo)明。文法GP的DFA圖如下： 有歸約動(dòng)作812765 : int 說明語(yǔ)句接受狀態(tài) D id D id3021491011R ; L ) ( id P26252423 if B then M271430292028191718222113 id and id 句法S id = if idM N ;

7、 S id M while while B do M id and353431 id B 布爾表示式 > and3233 id1536 T id38 id ( F E3716 * (403941 F ( id F id + E ( 表示式4342 + ) T4445 *GP：SLR（1）分析表Actiongotoid();:*+>=intandifthenwhiledo$PDRETFBMSLN012345678910111213141516170123456789100s211acc2s33s44s5895s66s77r48r39s1010s5s13121111r112r213s1

8、4s23s2722211714s1515s36s4116383716r13s43r1317s19s1818r1919s14s23s272220GP：SLR（1）分析表Actiongotoid();:*+>=intandifthenwhiledo$PDRETFBMSLN0123456789101112131415161701234567891020r17r1721r18r1822r16r1623s312424s34s2525s142626r14r1427s312828s3429s14s293030r15r1531s3232s3333r12r12r1234s313535r11r11r1136

9、r10r10r10r10r1037r8r8r8r8r838r6r6s39r6r639s36s4140GP：SLR（1）分析表actiongotoid();:*+>=intandifthenwhiledo$PDRETFBMSLN0123456789101112131415161701234567891040r7r7r7r7r741s36s4142383742s45s4343s36s41443744r5r5s39r5r545r9r9r9r9r9五 語(yǔ)義分析和中間代碼生成載語(yǔ)法分析過程中，隨著分析的步步進(jìn)展，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義子程序（或語(yǔ)義規(guī)則描述的語(yǔ)義動(dòng)作）進(jìn)行翻譯的辦法稱作語(yǔ)法制導(dǎo)

10、翻譯。語(yǔ)法制導(dǎo)翻譯歸約動(dòng)作翻譯方案EE+TEE1+TE.place=newtemp;Emit(E.place:=E1.place+T.place);ETET E.place:=T.place;TT*FTT1*FT.place=newtemp; Emit(T.place:= T1.place+F.place);TFTF T.place:=F.place;F(E)F(E)F.place:=E.place;FidFid p:=lookup(); if p<>nil then F.place:=p else error;BB and BBB1 and A B2backpatc

11、h(B1.truelist,A.quad);B.truelist:=B2.truelist;B.falselist:=merge(B1.falselist,B2.falselist);AA.quad:=nextquadBid>idBid1>id2B.truelist:=makelist(nextquad); B.falselist:=makelist(nextquad+1); emit(if id1.place>id2.placegoto_ _); emit(goto_ _);Mid=EMid=E p:=lookup(); if p<>nil the

12、n emit(p:=E.place) else error;Sif B then MSif B then A Mbackpatch(B.truelist,A.quad) backpatch(B.falselist,nextquad)AA.quad:=nextquadSwhile B do MSwhile A1 B do A2 M backpatch(B.truelist,A2.quad) backpatch(B.falselist,nextquad+1) emit(gotoA1.quad)A1A1.quad:=nextquadA2A2.quad:=nextquad語(yǔ)法翻譯生成的四元式如下：六

13、代碼生成目標(biāo)代碼生成階段的任務(wù)是把中間代碼變換成特定機(jī)器上的絕對(duì)指令代碼或可重定位的指令代碼或匯編指令代碼。這是編譯的最后階段，它的工作與硬件系統(tǒng)結(jié)構(gòu)和指令含義有關(guān)，這個(gè)階段的工作很復(fù)雜，涉及到硬件系統(tǒng)功能部件的運(yùn)用、機(jī)器指令的選擇、各種數(shù)據(jù)類型變量的存儲(chǔ)空間分配以及寄存器和后緩寄存器的調(diào)度等。本程序生成的目標(biāo)代碼與0x8086微處理器兼容。下面列舉幾個(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

14、 L. ( J> , A , B , L ) MOV R , A CMP R , B JB L. ( =,A , _ ,T ) LD R , A ST R , T 本程序生成的目標(biāo)代碼如下： 七 程序流程圖 編譯程序流程圖 八 實(shí)現(xiàn)本程序運(yùn)行的硬件環(huán)境為CPU1.66HZ ,內(nèi)存為768M .軟件環(huán)境為windows xp系統(tǒng)，Visual C+環(huán)境。九 程序運(yùn)行結(jié)果1 輸入源文件路徑：2 輸出保留字 3輸出符號(hào)表的內(nèi)容5輸出語(yǔ)法分析的結(jié)果（本程序采用自下而上的LR語(yǔ)法分析）6輸出中間代碼7輸出目標(biāo)代碼十 總結(jié)經(jīng)過本次實(shí)驗(yàn)，我對(duì)編譯程序各階段有了更深刻更深入的了解，也糾正了自己在某些方面

15、的的錯(cuò)誤，豐富了自己關(guān)于編譯原理方面的知識(shí)。同時(shí)也培養(yǎng)了自己熱愛思考，勤查資料的習(xí)慣。由于水平本次實(shí)驗(yàn)涉及面并不是很全面，我只考慮了c語(yǔ)言的一個(gè)子集。當(dāng)然本程序的算法在某些地方也還存在一些缺陷。十一 附錄（源程序）本程序輸入的c源代碼如下：libo()a:int;b:int;ccc:int;d:int;if ccc>b and ccc>a then a=b+a;while ccc>d do a=d;a=(b+ccc)*a+d本程序的完整源代碼如下：#include<cstdio>#include<iostream>#include<cstdlib

16、>#include<fstream>#include<string>#include<cmath>using namespace std;struct token/詞法 token結(jié)構(gòu)體int code;/編碼int num;/遞增編號(hào)token *next;token *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 iva

17、n/語(yǔ)法 產(chǎn)生式結(jié)構(gòu)體char left;/產(chǎn)生式的左部string right;/產(chǎn)生式的右部int len;/產(chǎn)生式右部的長(zhǎng)度;ivan css20;/語(yǔ)法 20個(gè)產(chǎn)生式struct pank/語(yǔ)法 action表結(jié)構(gòu)體char sr;/移進(jìn)或歸約int state;/轉(zhuǎn)到的狀態(tài)編號(hào);pank action4618;/action表int go_to4611;/語(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;/分析棧首尾指針stru

18、ct L/語(yǔ)義四元式的數(shù)據(jù)結(jié)構(gòu)int k;string op;/操作符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;/變量名稱int addr;/變量地址symb *next;symb *symb_head,*

19、symb_tail;/語(yǔ)義符號(hào)鏈表/詞法分析有關(guān)函數(shù)聲明void outdaima() ;void scan();/按字符讀取源文件void cifa_main();/詞法分析主程序int judge(char ch);/判斷輸入字符的類型void out1(char ch);/寫入token.txtvoid out3(char ch,string word);/寫入string.txtvoid input1(token *temp);/插入結(jié)點(diǎn)到隊(duì)列tokenvoid input3(str *temp);/插入結(jié)點(diǎn)到隊(duì)列stringvoid output();/輸出三個(gè)隊(duì)列的內(nèi)容void o

20、utfile();/輸出三個(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)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 *te

21、mp);/給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(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);/

22、把數(shù)字變成字符串string id_numtoname(int num);/把編號(hào)轉(zhuǎn)換成相應(yīng)的變量名int lookup(string m);/變量聲明檢查/全局變量的聲明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í)名稱傳遞和未聲明變量的輸出int id_num,id1_num,id2_num,id_left,

23、id_while,id_then,id_do;/用于記錄一些特殊的字符位置信息/主程序開始int main()cout<<"*"<<endl;cout<<"* 說明： *"<<endl;cout<<"* 第一部分：詞法分析 *"<<endl;cout<<"* 第二部分：語(yǔ)法分析 *"<<endl;cout<<"* 第三部分：語(yǔ)義分析 *"<<endl;cout<<&

24、quot;* 第四部分：目標(biāo)代碼生成 *"<<endl;cout<<"*"<<endl;cifa_main();/詞法yufa_main();/語(yǔ)法output_yuyi();/語(yǔ)義 outdaima(); /代碼生成cout<<endl;system("pause");return(0);/詞法分析子程序void cifa_main()token_head=new token;token_head->next=NULL;token_tail=new token;token_tail->

25、;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_false_head=new L;L_false_head

26、->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<<"詞法分析正確完成!"<<endl<<endl<<"如果將結(jié)果保存到文件中請(qǐng)輸入 y ，

27、否則請(qǐng)輸入其它字母："cin>>m;cout<<endl;if(m='y')outfile();cout<<"結(jié)果成功保存在token.txt和sting.txt兩個(gè)文件中，請(qǐng)打開查看"<<endl;cout<<endl;void scan()cout<<endl;system("pause");cout<<endl;char ch;string word;char document50;int flag=0;cout<<"

28、請(qǐng)輸入源文件路徑及名稱:"cin>>document;cout<<endl;cout<<"*"<<endl;cout<<"* 第一部分：詞法分析 *"<<endl;cout<<"*"<<endl;if(fp=fopen(document,"rt")=NULL)err=1;cout<<"無法找到該文件!"<<endl;return;while(!feof(fp)word

29、=""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;elsecout<<nl<<"行 "<<"錯(cuò)誤:非法字符! "<<ch<<endl;err=1;fclose(fp);int judge(char ch)int flag=0;if(ch='=' | ch='+

30、9; | 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;/

31、空格else if(feof(fp)flag=5;/結(jié)束else if(ch='n')flag=6;/換行nl+;elseflag=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 '' :

32、id=6;break;case '' : id=7;break;case '' : 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

33、token;temp->code=-1;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&

34、quot; | word="while" | 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=3

35、6;else if(word="int")temp->code=37;/關(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(ch);else if(flag=4 | flag=5 | fl

36、ag=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);/形成字符串elseerr=1;cout<<nl<<"行 "<<"錯(cuò)誤:非法字符! "<<ch<<endl;return;void input1(token

37、 *temp)if(token_head->next = NULL)token_head->next=temp;token_tail->next=temp;elsetoken_tail->next->next=temp;token_tail->next=temp;void input3(str *temp)if(string_head->next = NULL)string_head->next=temp;string_tail->next=temp;elsestring_tail->next->next=temp;string_tail->next=temp;void output()cout<<"token表內(nèi)容如下："<<endl;token *temp1;temp1=new token;temp1=token_head->next;while(temp1!=NULL)cout<<temp1->code;if(temp1->num = -1)cout<<endl;elsecout<<" "<<temp1->num<<