編譯器-編譯原理課程設(shè)計(jì)

1、廣西大學(xué)編譯原理課程設(shè)計(jì) 專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 姓 名： 課 程： 編譯原理 指導(dǎo)教師： 目錄一程序簡介與分析-1二程序適用范圍-1三詞法分析-1四語法分析-3五語義分析和中間代碼生成-9六代碼生成-11七流程圖-12八實(shí)現(xiàn)-13九程序運(yùn)行結(jié)果-13十總結(jié)-18十一.附錄（源程序）-19 簡單的編譯程序設(shè)計(jì)一 程序簡介與分析 本程序由四個(gè)部分組成：詞法分析子程序，語法分析子程序，語義分析子程序，目標(biāo)代碼生成程序。本程序輸入一個(gè)叫haominjie.txt的c語言源程序，然后對(duì)它進(jìn)行詞法，語法，語義分析，并輸出匯編代碼。 詞法分析輸入的是c語言源程序，輸出的3是具有獨(dú)立語法意義的單詞符號(hào)。

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

3、我將源程序中的單詞符號(hào)分為：保留字，字母（標(biāo)識(shí)符）， 界符三類，統(tǒng)一用一張表表示如下：界符，保留字表單詞=+*:;()andifthenwhiledoint標(biāo)志符編碼1234567891031323335363725 程序從源程序文件haominjie.txt中一次讀入一個(gè)字符，并判斷它是不是字母，界符， 保留字，空格，換行，結(jié)束符號(hào)或者非法字符。 流程圖如下： 詞法分析流程圖四 語法分析源程序中涉及的文法GP定義如下表：說明語句表達(dá)式布爾表達(dá)式句法0、PP1、Pid () L;R2、LL;D3、LD4、Did:int5、EE+T6、ET7、TT*F8、TF9、F(E)10、Fid11、BB

4、and B12、Bidid13、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)目集部分如下：0. P.P 1. PP.2. P.id()L;R 3. Pi

5、d.()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.F 28. TF. 29. F (E) 30. F (.E) 31. F

6、 (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 說明語句接受狀態(tài) D id D id3021491011R ; L ) ( id P26252423 if B then M271430292028191718222113 id and id 句法S id = if idM N ; S id M while while B do M id and353

7、431 id B 布爾表達(dá)式 and3233 id1536 T id38 id ( F E3716 * (403941 F ( id F id + E ( 表達(dá)式4342 + ) T4445 *GP：SLR（1）分析表Actiongotoid();:*+=intandifthenwhiledo$PDRETFBMSLN012345678910111213141516170123456789100s211acc2s33s44s5895s66s77r48r39s1010s5s13121111r112r213s14s23s2722211714s1515s36s4116383716r13s43r1317

8、s19s1818r1919s14s23s272220GP：SLR（1）分析表Actiongotoid();:*+=intandifthenwhiledo$PDRETFBMSLN0123456789101112131415161701234567891020r17r1721r18r1822r16r1623s312424s34s2525s142626r14r1427s312828s3429s14s293030r15r1531s3232s3333r12r12r1234s313535r11r11r1136r10r10r10r10r1037r8r8r8r8r838r6r6s39r6r639s36s414

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

10、ce:=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 pnil then F.place:=p else error;BB and BBB1 and A B2backpatch(B1.truelist,A.quad);B.truelist:=B2.truelist;B.falselist:=m

11、erge(B1.falselist,B2.falselist);AA.quad:=nextquadBididBid1id2B.truelist:=makelist(nextquad); B.falselist:=makelist(nextquad+1); emit(if id1.placeid2.placegoto_ _); emit(goto_ _);Mid=EMid=E p:=lookup(); if pnil then emit(p:=E.place) else error;Sif B then MSif B then A Mbackpatch(B.truelist,A.q

12、uad) 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語法翻譯生成的四元式如下：六 代碼生成目標(biāo)代碼生成階段的任務(wù)是把中間代碼變換成特定機(jī)器上的絕對(duì)指令代碼或可重定位的指令代碼或匯編指令代碼。這是編譯的最后階段，它的工作與硬件系統(tǒng)結(jié)構(gòu)和指令含義

13、有關(guān)，這個(gè)階段的工作很復(fù)雜，涉及到硬件系統(tǒng)功能部件的運(yùn)用、機(jī)器指令的選擇、各種數(shù)據(jù)類型變量的存儲(chǔ)空間分配以及寄存器和后緩寄存器的調(diào)度等。本程序生成的目標(biāo)代碼與0x8086微處理器兼容。下面列舉幾個(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

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

15、地方也還存在一些缺陷。十一 附錄（源程序）本程序輸入的c源代碼如下：haominjie()a:int;b:int;ccc:int;d:int; if cccb and ccca then a=b+a; while cccd do a=d; a=(b+ccc)*a+d本程序的完整源代碼如下：#include#include#include#include#include#includeusing namespace std;struct token/詞法 token結(jié)構(gòu)體int code;/編碼int num;/遞增編號(hào)token *next;token *token_head,*token_t

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

17、o4611;/語法 go_to表struct ike/語法 分析棧結(jié)構(gòu)體，雙鏈ike *pre;int num;/狀態(tài)int word;/符號(hào)編碼ike *next;ike *stack_head,*stack_tail;/分析棧首尾指針struct L/語義四元式的數(shù)據(jù)結(jié)構(gòu)int k;string op;/操作符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_t

18、rue_head,*L_false_head;/*四元式鏈，true鏈，false鏈*/struct symb/語義輸入時(shí)符號(hào)表string word;/變量名稱int addr;/變量地址symb *next;symb *symb_head,*symb_tail;/語義符號(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 w

19、ord);/寫入string.txtvoid input1(token *temp);/插入結(jié)點(diǎn)到隊(duì)列tokenvoid input3(str *temp);/插入結(jié)點(diǎn)到隊(duì)列stringvoid 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);/給輸入字符編號(hào)，轉(zhuǎn)化成action表列編號(hào)string ID10(in

20、t 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)/語義分析相關(guān)函數(shù)的聲明void yuyi_main(int m);/語義分析主程序void add_L_four(L *temp);/向四元式鏈中加一個(gè)結(jié)點(diǎn)void add_L_true(L *temp);/向true鏈中加一個(gè)結(jié)點(diǎn)void add_L_fa

21、lse(L *temp);/向false鏈中加一個(gè)結(jié)點(diǎn)void add_symb(symb *temp);/向語義符號(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);/變量聲明檢查/全局變量的聲明FILE *fp;/文件指針int wordcount;/標(biāo)志符計(jì)數(shù)int err;/標(biāo)志詞法分析結(jié)果正確或錯(cuò)誤int nl;/讀取行數(shù)int yuyi_linshi;/語義臨時(shí)變量

22、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;/用于記錄一些特殊的字符位置信息/主程序開始int main()cout*endl;cout* 說明： *endl;cout* 第一部分：詞法分析 *endl;cout* 第二部分：語法分析 *endl;cout* 第三部分：語義分析 *endl;cout* 第四部分：目標(biāo)代碼生成 *endl;cout*e

23、ndl;cifa_main();/詞法yufa_main();/語法output_yuyi();/語義 outdaima(); /代碼生成coutnext=NULL;token_tail=new token;token_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_fo

24、ur_tail-next=NULL;L_true_head=new L;L_true_head-Ltrue=NULL;L_false_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詞法分析正確完

25、成!endlendlm;coutendl;if(m=y)outfile();cout結(jié)果成功保存在token.txt和sting.txt兩個(gè)文件中，請(qǐng)打開查看endl;coutendl;void scan()coutendl;system(pause);coutendl;char ch;string word;char document50;int flag=0;coutdocument;coutendl;cout*endl;cout* 第一部分：詞法分析 *endl;cout*endl;if(fp=fopen(document,rt)=NULL)err=1;cout無法找到該文件!endl;

26、return;while(!feof(fp)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;elsecoutnl行 錯(cuò)誤:非法字符! ch | ch=: | ch=; | ch= | ch= | ch=( | ch=)flag=1;/界符else if(a=ch & ch=z) | (A=ch & ch : id=4;break;case : : id=5;break;case ; : id=6;b

27、reak;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 token;temp-code=-1;temp-num=-1;temp-next=NULL;str *temp1;tem

28、p1=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 | 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 i

29、f(word=while)temp-code=35;else if(word=do)temp-code=36;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 | flag=6)wordcount+;temp-code=25;temp-num=wordcount;input1(temp);temp1-num=wordcount;temp1-word=word;input3(temp1);return;else