編譯原理課程設計報告-編譯器(共33頁)

1、精選優(yōu)質文檔-傾情為你奉上 目錄課設要求用C語言對下述文法和單詞表定義的語言設計編制一個編譯器。（1）單詞符號及種別表單詞符號種別編碼單詞值main1int 2float3double4char5if 6else 7do8while9l(l|d)*10內部字符串 ( +|-| ) d*(.dd* | )( e ( +|-| ) dd*|) 20二進制數(shù)值表示=21+22- 23* 24/ 25(26)272829,30;31>32>=33<34<=35=36!=37（2）語法結構定義<程序> := main()<語句塊> <語句塊>

2、:= <語句串> /程序用括號括起來<語句串>:=<語句><語句><語句>:=<賦值語句>|<條件語句>|<循環(huán)語句><賦值語句>:=ID=<表達式> /賦值語句用”=”號<條件語句>:=if<條件><語句塊> /條件怎么沒有括號，囧（自己加1個）<循環(huán)語句>:=do <語句塊>while <條件><條件>:=<表達式><關系運算符><表達式> /沒有布爾運

3、算，還算簡單<表達式> := <項> +<項>|-<項><項> := <因子>*<因子>|/<因子><因子> :=ID|num|(<表達式>)num:= ( +|-| ) 數(shù)字*(.數(shù)字數(shù)字* | )( e ( +|-| ) 數(shù)字數(shù)字*|)ID:=字母(字母|d數(shù)字)*字母:=a|b|c|z|A|B|C|Z數(shù)字:=0|1|2|9<關系運算符> := <|<=|>|>=|=|!=一、 總體設計思想采用遞歸下降（自上而下）的語法制導翻譯法。二、

4、 詳細算法設計在前兩次試驗的基礎上改進。詞法分析程序 à 語法分析程序 à 語義分析程序 à編譯器。不斷完善，不斷改進。漸變的過程。三、 流程框圖圖 I 主函數(shù)示意圖圖 II 遞歸下降分析程序示意圖是否為main？調用scanner是否為（？調用scanner是否為）？調用scanner調用語句塊分析函數(shù)staBlock出錯處理否否否圖 III 語句塊分析示意圖是否為 ？調用scanner調用語句串分析函數(shù)staString調用scanner是否為 ？出錯處理否否圖 IV 語句串分析示意圖調用語句分析函數(shù)sta回溯，調用backpatch是否為 ; ？調用scan

5、ner調用語句分析函數(shù)sta否出錯處理圖 V 語句分析示意圖調用賦值語句分析函數(shù)fuzhi是否為 字符串？是否為 if ？調用條件語句分析函數(shù)tiaojian是否為 do ？調用循環(huán)語句分析函數(shù)xunhuan四、 函數(shù)相關說明1. 所有函數(shù)一覽void scanner(); /掃描void lrparser(); void staBlock(int *nChain); /語句塊void staString(int *nChain); /語句串void sta(int *nChain); /語句void fuzhi(); /賦值語句void tiaojian(int *nChain); /條件語

6、句void xunhuan(); /循環(huán)語句char* E(); /Expresiion表達式char* T(); /Term項char* F(); /Factor因子char *newTemp(); /自動生成臨時變量void backpatch(int p,int t); /回填int merge(int p1,int p2); /合并p1和p2void emit(char *res,char *num1,char *op,char *num2); /生成四元式2. void emit(char *res,char *num1,char *op,char *num2)該函數(shù)的功能是生成一個

7、三地址語句送到四元式表中。void emit(char *res,char *num1,char *op,char *num2)strcpy(fourComq.result,res);strcpy(fourComq.arg1,num1);strcpy(fourComq.opera,op);strcpy(fourComq.arg2,num2);q+;四元式表中的結構如下：structchar result10; /字符串（字符數(shù)組）char arg110; /操作數(shù)1char opera10; /運算符char arg210; /操作數(shù)2fourCom20; /結構體數(shù)組3. char *new

8、Temp()該函數(shù)的功能是會動一個新的臨時變量，臨時變量名產生的順序是T1,T2,T3,.char *newTemp()char *p;char varTemp10;p=(char *)malloc(10);kk+;itoa(kk,varTemp,10); /整數(shù)轉換為字符串strcpy(p+1,varTemp);p0='T' /字符串前加T，便于識別return p;4. int merge(int p1,int p2)該函數(shù)的功能是將以P1,P2為鏈首的兩條鏈合并成一條鏈，返回時的函數(shù)值作為合并后的鏈首。int merge(int p1,int p2) /合并p1和p2ch

9、ar circle,nResult;if(p2=0)nResult=p1;elsenResult=circle=p2;while(atoi(fourComcircle.result) /四元式第四個分量不為0circle=atoi(fourComcircle.result); /strcpy(fourComcircle.result,p1);sprintf(fourComcircle.result,"%s",p1);/目的是用p1的值覆蓋0return nResult; /p2是頭，p1覆蓋0，接在p2后邊5. void backpatch(int p,int t)該函數(shù)的

10、功能是把P所鏈接的每個四元式的第四區(qū)段（result段）都回填t。void backpatch(int p,int t) int w,circle=p;while(circle) /circle不為0的時候w=atoi(fourComcircle.result); /四元式circle第四分量內容/strcpy(fourComcircle.result,t); /把t填進四元式circle的第四分量sprintf(fourComcircle.result,"%d",t);circle=w; /w記錄的是鏈條上下一個四元式，移動！return;6. void fuzhi()該

11、函數(shù)的功能是對賦值語句進行分析。void fuzhi() /賦值語句只有1個操作數(shù)char res10,num10; /num操作數(shù)if(syn=10) /字符串strcpy(res,token); /結果scanner();if(syn=21) /=scanner();strcpy(num,E();emit(res,num,"=","");elseprintf("缺少=號n");7. void tiaojian(int *nChain)該函數(shù)的功能是對條件語句進行分析。/<條件語句>->if(<條件>)

12、<語句塊>void tiaojian(int *nChain)char res10,num110,num210,op10;int nChainTemp;/<條件>-><表達式><關系運算符><表達式>if(syn=6) /ifscanner();/strcpy(num1,E();if(syn=26) /(scanner();strcpy(num1,E();if(syn<=37)&&(syn>=32) switch(syn)case 32:strcpy(op,">");brea

13、k;case 33:strcpy(op,">=");break;case 34:strcpy(op,"<");break;case 35:strcpy(op,"<=");break;case 36:strcpy(op,"=");break;case 37:strcpy(op,"!=");break;default:printf("error");scanner();strcpy(num2,E();strcat(num1,op);strcat(num1,num

14、2);/nfc=nextq+1;ntc=nextq; /記住if語句位置emit("0","if",num1,"goto"); nfc=nextq; /if中表達式為假emit("0","","","goto");/第一個0已回填backpatch(ntc,nextq); /ntc鏈接的所有四元式都回填nextqif(syn=27) /)scanner();staBlock(&nChainTemp); /語句塊*nChain=merge(nChai

15、nTemp,nfc);8. void xunhuan()該函數(shù)的功能是對循環(huán)語句進行分析。/<循環(huán)語句>:=do <語句塊>while <條件>void xunhuan()char res10,num110,num210,op10;int nChainTemp;if(syn=8) /donnc=nextq; /記住if語句位置，emit之后nextq就變了/emit("0","if",num1,"goto"); scanner();staBlock(&nChainTemp); /語句塊if(

16、syn=9) /whilescanner();if(syn=26) /(scanner();strcpy(num1,E();if(syn<=37)&&(syn>=32) switch(syn)case 32:strcpy(op,">");break;case 33:strcpy(op,">=");break;case 34:strcpy(op,"<");break;case 35:strcpy(op,"<=");break;case 36:strcpy(op,&q

17、uot;=");break;case 37:strcpy(op,"!=");break;default:printf("error");scanner();strcpy(num2,E();strcat(num1,op);strcat(num1,num2);nnb=nextq;emit("0","if",num1,"goto"); backpatch(nnb,nnc);nna=nextq;emit("0","","","

18、;goto");backpatch(nna,nextq);if(syn=27) /)scanner();五、 程序運行結果圖 VI 賦值語句的分析圖 VII 條件語句的分析圖 VIII 循環(huán)語句的分析圖 IX 綜合六、 編譯器使用說明程序提示用戶輸入字符串“Please input your source string:”，用戶輸入字符串并以“#”號結束?；剀嚭螅绦蝻@示運行結果。七、 心得與體會剛拿到課設題目的時候，感覺很難，沒有頭緒。雖然之前實驗時候，詞法分析程序和語法分析程序的代碼都是自己一個一個敲的。但是記得那時的語法分析程序用的是遞歸下降分析法，而且只判斷輸入串是否是文法的

19、句子（輸出只有簡單的success或者error）。課設的要求呢？要加上語義分析，而且要輸出四元式。好像語義分析的部分，我一點印象也沒有了，老師那一部分上得有點快。運動會3天假，時間全用來啃課本了。“語義分析與中間代碼生成”，我又一點一點的看。3天時間，終于可以寫出語義程序了。這是課設的第1個里程碑。采用遞歸下降的語法制導翻譯法，實現(xiàn)了對賦值表達式的語義分析，并生成四元式。但是后來發(fā)現(xiàn)，更難的東西在后邊。程序語句有3種：賦值語句，條件語句，循環(huán)語句。而賦值語句的翻譯，恰恰是最簡單的。對于賦值語句的翻譯，課本上有詳細的講解，有代碼的簡單舉例。而對于條件語句（ifelse）和循環(huán)語句（dowhil

20、e），課本講解不那么詳細，沒有代碼舉例，上課時候我也沒太理解老師所講解的。特別是其中鏈nChain的概念，一直看不懂。因為這個困難，課設被我擱置了3天。再后來利用上機的時間，請教了一下老師和另外一個同學，發(fā)現(xiàn)課本后給的樣例程序是錯的，而且錯得一塌糊涂。只好自己寫，寫，寫。然后就是課設的第2個里程碑。實現(xiàn)了對條件語句（if語句）的分析，并生成四元式。接下來又是開發(fā)停滯的一段時間，直到11月18日。熟悉了一下原先寫的代碼，然后開始繼續(xù)后邊的部分。迎來了課設的第3個里程碑。實現(xiàn)了對循環(huán)語句（while語句）的分析，并生成四元式。而且好像沒有預期中困難，可能是有條件語句的鋪墊吧。他們的處理方法其實很類

21、似，也是emit+backpatch+merge。而且由于老師給的語法中沒有布爾表達式，所以很多merge的工作也可以省略了，嘿嘿。最后一步就是整合，系統(tǒng)測試，書寫文檔了。個人認為這次課設的機會非常寶貴，加深了我對編譯器處理語言的過程的理解。我想，作為學軟件的學生，不應該只會用Java，或者C+，或者C#。一門高級語言其實學起來是很容易的，而在校期間，這些計算機基礎課程一定要學好！才能為將來打好基礎。八、 源程序清單/*編譯器*/*Erin*/*軟件工程0801班*/*HUST*/*#include<stdio.h>#include<string.h>#include&

22、lt;math.h>#include<stdlib.h>char prog80; /存放所有輸入字符 char token8; /存放詞組 char ch; /單個字符 int syn,p,m,n,i; /syn:種別編碼 double sum; int count; int isSignal; /是否帶正負號(0不帶，1負號，2正號）int isError;int isDecimal; /是否是小數(shù) double decimal; /小數(shù) int isExp; /是否是指數(shù) int index; /指數(shù)冪 int isNegative; /是否帶負號 double temp

23、; int temp2;int repeat; /是否連續(xù)出現(xiàn)+,-int nextq;int kk; /臨時變量的標號int ntc,nfc,nnc,nnb,nna;char *rwtab9="main","int","float","double","char","if","else","do","while" structchar result10; /字符串（字符數(shù)組）char arg110;char ope

24、ra10;char arg210;fourCom20; /結構體數(shù)組void scanner(); /掃描void lrparser(); void staBlock(int *nChain); /語句塊void staString(int *nChain); /語句串void sta(int *nChain); /語句void fuzhi(); /賦值語句void tiaojian(int *nChain); /條件語句void xunhuan(); /循環(huán)語句char* E(); /Expresiion表達式char* T(); /Term項char* F(); /Factor因子char

25、 *newTemp(); /自動生成臨時變量void backpatch(int p,int t); /回填int merge(int p1,int p2); /合并p1和p2void emit(char *res,char *num1,char *op,char *num2); /生成四元式void main()p=0;count=0;isDecimal=0;index=0;repeat=0;kk=0;printf("nPlease input your source string:n");doch=getchar();progp+=ch;while(ch!='#

26、');p=0;isError=0;scanner();lrparser();for(i=1;i<nextq;i+) /循環(huán)輸出四元式printf("n%dt",i);printf("(%5s %5s %5s t%5s )n",fourComi.arg1,fourComi.opera,fourComi.arg2,fourComi.result);void lrparser()int nChain;nfc=ntc=1;nextq=1;if(syn=1) /mainscanner();if(syn=26) /(scanner();if(syn=2

27、7) /)scanner();staBlock(&nChain);elseprintf("缺少右括號n");else printf("缺少左括號n");elseprintf("缺少mainn");/<語句塊> := ''<語句串>''void staBlock(int *nChain) /語句塊if(syn=28) /scanner();staString(nChain);/backpatch(*nChain,nextq);if(syn=29) /scanner(); /

28、讀下一個elseprintf("缺少號n");elseprintf("缺少號n");/<語句串>:=<語句><語句>void staString(int *nChain) /語句串sta(nChain);backpatch(*nChain,nextq);while(syn=31) /;scanner();sta(nChain);/backpatch(*nChain,nextq-1);void sta(int *nChain) /語句if(syn=10)fuzhi();/*nChain=0;else if(syn=6)

29、/iftiaojian(nChain);else if(syn=8) /doxunhuan();/<條件語句>->if(<條件>)<語句塊>void tiaojian(int *nChain)char res10,num110,num210,op10;int nChainTemp;/<條件>-><表達式><關系運算符><表達式>if(syn=6) /ifscanner();/strcpy(num1,E();if(syn=26) /(scanner();strcpy(num1,E();if(syn&l

30、t;=37)&&(syn>=32) switch(syn)case 32:strcpy(op,">");break;case 33:strcpy(op,">=");break;case 34:strcpy(op,"<");break;case 35:strcpy(op,"<=");break;case 36:strcpy(op,"=");break;case 37:strcpy(op,"!=");break;default:pri

31、ntf("error");scanner();strcpy(num2,E();strcat(num1,op);strcat(num1,num2);/nfc=nextq+1;ntc=nextq; /記住if語句位置emit("0","if",num1,"goto"); nfc=nextq; /if中表達式為假emit("0","","","goto");/第一個0已回填backpatch(ntc,nextq); /ntc鏈接的所有四元式都

32、回填nextqif(syn=27) /)scanner();staBlock(&nChainTemp); /語句塊*nChain=merge(nChainTemp,nfc);/<循環(huán)語句>:=do <語句塊>while <條件>void xunhuan()char res10,num110,num210,op10;int nChainTemp;if(syn=8) /donnc=nextq; /記住if語句位置，emit之后nextq就變了/emit("0","if",num1,"goto")

33、; scanner();staBlock(&nChainTemp); /語句塊if(syn=9) /whilescanner();if(syn=26) /(scanner();strcpy(num1,E();if(syn<=37)&&(syn>=32) switch(syn)case 32:strcpy(op,">");break;case 33:strcpy(op,">=");break;case 34:strcpy(op,"<");break;case 35:strcpy(op

34、,"<=");break;case 36:strcpy(op,"=");break;case 37:strcpy(op,"!=");break;default:printf("error");scanner();strcpy(num2,E();strcat(num1,op);strcat(num1,num2);nnb=nextq;emit("0","if",num1,"goto"); backpatch(nnb,nnc);nna=nextq;emit

35、("0","","","goto");backpatch(nna,nextq);if(syn=27) /)scanner();void fuzhi() /賦值語句只有1個操作數(shù)char res10,num10; /num操作數(shù)if(syn=10) /字符串strcpy(res,token); /結果scanner();if(syn=21) /=scanner();strcpy(num,E();emit(res,num,"=","");elseprintf("缺少=號

36、n");char* E() /Expression表達式char *res,*num1,*op,*num2;res=(char *)malloc(10);num1=(char *)malloc(10);op=(char *)malloc(10);num2=(char *)malloc(10);strcpy(num1,T();while(syn=22)|(syn=23) /+ -if(syn=22) /+strcpy(op,"+");elsestrcpy(op,"-");scanner();strcpy(num2,T();strcpy(res,n

37、ewTemp();emit(res,num1,op,num2);strcpy(num1,res);return num1;char* T() /Term項char *res,*num1,*op,*num2;res=(char *)malloc(10);num1=(char *)malloc(10);op=(char *)malloc(10);num2=(char *)malloc(10);strcpy(num1,F();while(syn=24)|(syn=25) /* /if(syn=24) strcpy(op,"*");elsestrcpy(op,"/&quo

38、t;);scanner();strcpy(num2,F();strcpy(res,newTemp();emit(res,num1,op,num2);strcpy(num1,res);return num1;char* F() /Factor因子char *res;res=(char *)malloc(10);if(syn=10) /字符串strcpy(res,token);scanner();else if(syn=20) /二進制數(shù)itoa(int)sum,res,10); /整數(shù)轉換為字符串scanner();else if(syn=26) /(scanner();res=E();if(s

39、yn=27) /)scanner();else isError=1;elseisError=1;return res;char *newTemp()char *p;char varTemp10;p=(char *)malloc(10);kk+;itoa(kk,varTemp,10);strcpy(p+1,varTemp);p0='T'return p;/將p所鏈接的每個四元式的第四個分量都回填tvoid backpatch(int p,int t) int w,circle=p;while(circle) /circle不為0的時候w=atoi(fourComcircle.re

40、sult); /四元式circle第四分量內容/strcpy(fourComcircle.result,t); /把t填進四元式circle的第四分量sprintf(fourComcircle.result,"%d",t);circle=w; /w記錄的是鏈條上下一個四元式，移動！return;int merge(int p1,int p2) /合并p1和p2char circle,nResult;if(p2=0)nResult=p1;elsenResult=circle=p2;while(atoi(fourComcircle.result) /四元式第四個分量不為0cir

41、cle=atoi(fourComcircle.result); /strcpy(fourComcircle.result,p1);sprintf(fourComcircle.result,"%s",p1);/目的是用p1的值覆蓋0return nResult; /p2是頭，p1覆蓋0，接在p2后邊void emit(char *res,char *num1,char *op,char *num2)strcpy(fourComnextq.result,res);strcpy(fourComnextq.arg1,num1);strcpy(fourComnextq.opera,o

42、p);strcpy(fourComnextq.arg2,num2);nextq+;void scanner() sum=0; decimal=0; m=0; for(n=0;n<8;n+) tokenn=NULL; ch=progp+; /從prog中讀出一個字符到ch中 while(ch=' '|ch='n') /跳過空字符（無效輸入） ch=progp+; if(ch>='a')&&(ch<='z')|(ch>='A')&&(ch<='Z&#

43、39;) /ch是字母字符 while(ch>='a')&&(ch<='z')|(ch>='A')&&(ch<='Z')|(ch>='0')&&(ch<='9') tokenm+=ch; /ch=>token ch=progp+; /讀下一個字符 tokenm+='0' p-; /回退一格 syn=10; /標識符 /如果是"begin","if",&qu

44、ot;then","while","do","end"標識符中的一個 for(n=0;n<9;n+) if(strcmp(token,rwtabn)=0) syn=n+1; break; else if(ch>='0')&&(ch<='9') IsNum: if(isSignal=1) /tokenm+='-' while(ch>='0')&&(ch<='9') sum=sum*10+

45、ch-'0' /ch中數(shù)字本身是當做字符存放的 ch=progp+; if(ch='.') isDecimal=1; ch=progp+; count=0; /之前忘了清零,123.123+123.123#兩個浮點數(shù)就無法識別 while(ch>='0')&&(ch<='9') /pow(x,y)計算x的y次冪 temp=(ch-'0')*pow(0.1,+count); decimal=decimal+temp; /AddToDec(); ch=progp+; sum=sum+deci

46、mal; if(ch='e'|ch='E') isExp=1; ch=progp+; if(ch='-') isNegative=1; ch=progp+; while(ch>='0')&&(ch<='9') /指數(shù) index=index*10+ch-'0' ch=progp+; /10的冪 /123e3代表123*10(3) /sum=sum*pow(10,index);是錯誤的 if(isNegative) sum=sum*pow(0.1,index); else sum=sum*pow(10,index); if(isSignal=1)sum=-sum;isSignal=0; p-; syn=20; else switch(ch