編譯原理實驗報告

1、中南林業(yè)科技大學(xué)實驗報告課程名稱： 編譯原理專業(yè)班級：2012級計算機(jī)科學(xué)與技術(shù)2班姓 名： 陳曉燚 學(xué) 號： 201245802015年 7 月 8日實驗一 詞法分析一、實驗?zāi)康木幹埔粋€讀單詞過程，從輸入的源程序中，識別出各個具有獨立意義的單詞，即基本保留字、標(biāo)識符、常數(shù)、運算符、分隔符五大類。并依次輸出各個單詞的內(nèi)部編碼及單詞符號自身值。 二、實驗題目如源程序為c語言。輸入如下一段：main()int a=-5,b=4,j;if(a=b) j=a-b; else j=b-a;要求輸出如下：（2，”main”）（5，”（”） （5，”）”）（5，”） （1，”int”） （2，”a”）（4，

2、”=”） （3，”-5”） （5，”,”）（2，”b”） （4，”=”） （3，”4”）（5，”,”） （2，”j”） （5，”;”）（1，”if”） （5，”（”） （2，”a”）（4，”=”） （2，”b”） （5，”）”）（2，”j”） （4，”=”） （2，”a”）（4，”-”） （2，”b”） （5，”;”）（1，”else”） （2，”j”） （4，”=”）（2，”b”） （4，”-”） （2，”a”）（5，”;”） （5，”）三、實驗理論依據(jù)(一)識別各種單詞符號1、 程序語言的單詞符號一般分為五種：(1) 關(guān)鍵字（保留字/ 基本字）if 、while 、begin(2) 標(biāo)識符

3、：常量名、變量名(3) 常數(shù)：34 、56.78 、true 、a 、(4) 運算符：+ 、- 、* 、/ 、 、and 、or 、.(5) 界限符：， ； （ ） /*2、 識別單詞：掌握單詞的構(gòu)成規(guī)則很重要 (1) 標(biāo)識符的識別：字母| 下劃線+( 字母/ 數(shù)字/ 下劃線)(2) 關(guān)鍵字的識別：與標(biāo)識符相同，最后查表 (3) 常數(shù)的識別 (4) 界符和算符的識別 3、 大多數(shù)程序設(shè)計語言的單詞符號都可以用轉(zhuǎn)換圖來識別，如圖1-1 圖1-14、 詞法分析器輸出的單詞符號常常表示為二元式：（單詞種別，單詞符號的屬性值）(1) 單詞種別通常用整數(shù)編碼，如1 代表關(guān)鍵字，2 代表標(biāo)識符等 (2)

4、關(guān)鍵字可視其全體為一種，也可以一字一種。采用一字一種得分法實際處理起來較為方便。 (3) 標(biāo)識符一般統(tǒng)歸為一種 (4) 常數(shù)按類型（整、實、布爾等）分種 (5) 運算符可采用一符一種的方法。 (6) 界符一般一符一種的分法。 (二)超前搜索方法1、 詞法分析時，常常會用到超前搜索方法。如當(dāng)前待分析字符串為“a+” ，當(dāng)前字符為“” ，此時，分析器倒底是將其分析為大于關(guān)系運算符還是大于等于關(guān)系運算符呢？ 顯然，只有知道下一個字符是什么才能下結(jié)論。于是分析器讀入下一個字符+ ，這時可知應(yīng)將 解釋為大于運算符。但此時，超前讀了一個字符+ ，所以要回退一個字符，詞法分析器才能正常運行。又比如：+ 分析

5、為正號還是加法符號 (三)預(yù)處理預(yù)處理工作包括對空白符、跳格符、回車符和換行符等編輯性字符的處理，及刪除注解等。由一個預(yù)處理子程序來完成。四、詞法分析器的設(shè)計1、 設(shè)計方法：(1) 寫出該語言的詞法規(guī)則。 (2) 把詞法規(guī)則轉(zhuǎn)換為相應(yīng)的狀態(tài)轉(zhuǎn)換圖。 (3) 把各轉(zhuǎn)換圖的初態(tài)連在一起，構(gòu)成識別該語言的自動機(jī) (4) 設(shè)計掃描器 2、 把掃描器作為語法分析的一個過程，當(dāng)語法分析需要一個單詞時，就調(diào)用掃描器。 掃描器從初態(tài)出發(fā)，當(dāng)識別一個單詞后便進(jìn)入終態(tài)，送出二元式 開始讀標(biāo)識符是字母掠過空格和回車符查保留字表是否查到換成屬性字結(jié)束是數(shù)字是特殊符號error取數(shù)換成屬性字換成屬性字換成屬性字ynyy

6、ynnn圖1-2 取單詞程序框圖5、 程序代碼#include#include#includefile *fp;char cbuffer;char *key14=main,if,else,for,while,do,return,break,continue,int,float,double,boolean,long;int atype,id=4;/判斷單詞是保留字還是標(biāo)識符int search(char searchchar,int wordtype)int i=0;int p;switch(wordtype)case 1:for(i=0;i=13;i+)if(strcmp(keyi,sear

7、chchar)=0)/是保留字則p為非0且不重復(fù)的整數(shù)p=i+1;break;else p=0; /不是保留字則用于返回的p=0return(p);char digitprocess(char buffer)int i=-1;char digittp20;while(isdigit(buffer)|buffer=.)digittp+i=buffer;buffer=fgetc(fp);digittpi+1=0;printf(%s,常數(shù))n,digittp);id=3;return buffer;char alphaprocess(char buffer)int atype;/保留字?jǐn)?shù)組中的位置i

8、nt i=-1;char alphatp20;while(isalpha(buffer)|(isdigit(buffer)|buffer=_)alphatp+i=buffer;buffer=fgetc(fp);/讀一個完整的單詞放入alphatp數(shù)組中alphatpi+1=0;/對此單詞調(diào)用search函數(shù)判斷類型atype=search(alphatp,1);if(atype!=0)printf(%s,(基本保留字,%d)n,alphatp,atype-1);id=1;elseprintf(%s,標(biāo)識符)n,alphatp);id=2;return buffer;char otherproc

9、ess(char buffer)char ch20;ch0=buffer;ch1=0;if(ch0=,|ch0=;|ch0=|ch0=|ch0=(|ch0=)printf(%s,分隔符)n,ch);buffer=fgetc(fp);id=4;return(buffer);if(ch0=|ch0=!|ch0=)buffer=fgetc(fp);if(buffer=)ch1=buffer;ch2=0;printf(%s,運算符)n,ch);elseprintf(%s,運算符)n,ch);id=4;return(buffer);buffer=fgetc(fp);id=4;return(buffer)

10、;if(ch0=+|ch0=-)/在當(dāng)前符號以前是運算符，則此時為正負(fù)號if(id=4)buffer=fgetc(fp);/如果是-53顯示結(jié)果為（-5，3）（3,3）/*ch1=buffer;ch2=0;*/顯示為（-53,3）int i=1;while(isdigit(buffer)chi=buffer;buffer=fgetc(fp);i+;chi=0;printf(%s,常數(shù))n,ch);id=3;buffer=fgetc(fp);return(buffer);/添加+ -功能if(id=2)buffer=fgetc(fp);if(buffer=ch0)ch1=buffer;ch2=0

11、;printf(%s,運算符)n,ch);id=4;buffer=fgetc(fp);return(buffer);ch1=0;printf(%s,運算符)n,ch);buffer=fgetc(fp);id=4;return(buffer);void main()/以只讀方式打開一個文件if(fp=fopen(example.c,r)=null)printf(error);else/fgetc()函數(shù)：從磁盤文件讀取一個字符cbuffer=fgetc(fp);while(cbuffer!=eof)/掠過空格和回車符if(cbuffer= |cbuffer=n)cbuffer=fgetc(fp)

12、;elseif(isalpha(cbuffer)/如果該字符是字母cbuffer=alphaprocess(cbuffer);elseif(isdigit(cbuffer)/如果該字符是數(shù)字cbuffer=digitprocess(cbuffer);else/是其他字符cbuffer=otherprocess(cbuffer);6、 實驗結(jié)果 7 實驗增加內(nèi)容：判斷了小數(shù)的情況；添加了自增，自減運算。實驗二 ll（1）分析法一、實驗?zāi)康母鶕?jù)某一文法編制調(diào)試ll(1)分析程序，以便對任意輸入的符號串進(jìn)行分析。本次實驗的目的主要是加深對預(yù)測分析ll(1)分析法的理解。二、實驗題目實驗規(guī)定對下列文法

13、，用ll（1）分析法對任意輸入的符號串進(jìn)行分析： （1）e:=tg（2）g:=+tg（3）g:=（4）t:=fs（5）s:=*fs（6）s:=（7）f:=(e)（8）f:=i若輸入串為i+i*i# ，則輸出為：#ei+i*i#gti+i*i#gsfi+i*i#gsii+i*i#gs+i*i#g+i*i#gt+i*i# tfs2. +7 g+tg6 s5 i4 fi3 etg1 產(chǎn)生式 剩余串 分析棧 步驟ll(1)的分析表為： i + * ( ) # 說 明 e e eselect(etg)=(,i ggg1g1select (g+tg)=+select (g)=#,) t t tselect

14、 (tfs)=(,i ss1 s s1 s1select (s*fs)=*select (s)=#,) + f f1 fselect (f(e)=(select (fi)=i3、 程序代碼#include#include#include#includechar a20;/分析串char b20;/剩余串char v120=i,+,*,(,),#;/終結(jié)符char v220=e,g,t,s,f;/非終結(jié)符int j=0,b=0,top=0,l;/l為輸入串的長度/生產(chǎn)式類型定義typedef struct type/大寫字符char origin;/產(chǎn)生式右邊字符char array5;/字符個

15、int length;type;/結(jié)構(gòu)體變量type e,t,g,g1,s,s1,f,f1;/預(yù)測分析表type c1010;/輸出分析棧void print()int a; /指針for(a=0;a=top+1;a+)printf(%c,aa);printf(tt);/輸出剩余串void print1()int j;/輸出對齊符for(j=0;jb;j+)printf( );for(j=b;j=l;j+)printf(%c,bj);printf(ttt);void main()int m,n,k=0,flag=0,finish=0;char ch,x;type cha;/把文法產(chǎn)生式賦值結(jié)構(gòu)

16、體e.origin=e;strcpy(e.array,tg);e.length=2;t.origin=t;strcpy(t.array,fs);t.length=2;g.origin=g;strcpy(g.array,+tg);g.length=3;g1.origin=g;g1.array0=;g1.length=1;s.origin=s;strcpy(s.array,*fs);s.length=3;s1.origin=s;s1.array0=;s1.length=1;f.origin=f;strcpy(f.array,(e);f.length=3;f1.origin=f;f1.array0=

17、i;f1.length=1;/初始化分析表for(m=0;m=4;m+)for(n=0;n=5;n+)cmn.origin=n;/全部賦為空/填充分析表c00=e; c03=e; c11=g;c14=g1; c15=g1; c20=t;c23=t; c31=s1; c32=s;c34=c35=s1; c40=f1; c43=f;/讀入分析串doscanf(%c,&ch);if(ch!=i)&(ch!=+)&(ch!=*)&(ch!=()&(ch!=)&(ch!=#)printf(輸入串中有非法字符n);exit(1);bj=ch;j+;while(ch!=#);/分析串長度l=j;/當(dāng)前分析字

18、符ch=b0;/# e入棧atop=#;a+top=e;printf(步驟tt分析棧tt剩余字符tt所用生產(chǎn)式n);do/x為當(dāng)前棧頂字符x=atop-;printf(%d,k+);printf(tt);/判斷是否為終結(jié)符for(j=0;j=5;j+)if(x=v1j)flag=1;break;/如果是終結(jié)符if(flag=1)if(x=#)finish=1;/結(jié)束標(biāo)志printf(acc!n);/接受getchar();getchar();exit(1);if(x=ch)print();print1();printf(%c匹配n,ch);/下一個輸入字符ch=b+b;flag=0;/恢復(fù)標(biāo)記

19、else/出錯處理print();print1();printf(%c出錯n,ch);/輸出出錯終結(jié)符exit(1);else/非終結(jié)符處理for(j=0;j=4;j+)if(x=v2j)m=j;/行號break;for(j=0;j,cha.origin);/輸出產(chǎn)生式for(j=0;j=0;j-)/產(chǎn)生式逆序入棧a+top=cha.arrayj;if(atop=)/為空則不進(jìn)棧top-;elseprint();print1();printf(%c出錯n,x);exit(1);while(finish=0);4、 實驗結(jié)果：實驗三 逆波蘭式的產(chǎn)生及計算一、實驗?zāi)康膶⒂弥芯Y式表示的算術(shù)表達(dá)式轉(zhuǎn)換

20、為用逆波蘭式表示的算術(shù)表達(dá)式，并計算用逆波蘭式來表示的算術(shù)表達(dá)式的值二、實驗題目如輸入如下：21+（42-2）*15+6）-18#輸出為：原來表達(dá)式： 21+（42-2）*15+6）- 18# 后綴表達(dá)式：21&42&2&-15&*6&+18&- 計算結(jié)果：609三、算法流程圖開始從左到右掃描中綴表達(dá)式結(jié)束運算分量error退棧輸出當(dāng)前運算符與棧頂運算符比較優(yōu)先級nyyn運算符左括號(右括號）棧為空棧為空入棧error入棧棧頂為（退棧棧為空棧頂為（退棧輸出入棧y輸出yy當(dāng)前大nyynynnnnyn退棧輸出ny圖3-1 生成逆波蘭式的程序流程圖讀入一個逆波蘭算術(shù)表達(dá)式ch=當(dāng)前輸入符號程序結(jié)束y

21、nch是運算符ch=#ny將該字符入棧根據(jù)運算符的特點從棧頂部取出若干個運算對象進(jìn)行該運算，將運算結(jié)果入棧圖3-2 計算逆波蘭式的程序流程圖四、程序代碼#include#include#include#includefloat stack60;int top=0;float compute(char com)int d=0;int p=0;char ch=comp;while(ch=comp)!=#)switch(ch)case +:stacktop-1=stacktop-1+stacktop;top-;+p;break;case -:stacktop-1=stacktop-1-stackto

22、p;top-;+p;break;case *:stacktop-1=stacktop-1*stacktop;top-;+p;break;case /:if(stacktop!=0)stacktop-1=stacktop-1/stacktop;elseprintf(n除零錯誤!n);exit(0);/異常退出top-;+p;break;case :/添加計算乘方stacktop-1=pow(stacktop-1,stacktop);top-;+p;break;case :+p;break;default:/*d=0;while(ch=0&ch=0&ch=0&chs（1）s-bb（2）b-ab（3

23、）b-b2、lr(1)分析表為：狀態(tài)actiongotoab#sbs0s3s412s1accs2s6s75s3s3s48s4r3r3s5r1s6s6s79s7r3s8r2r2s9r2(1)若輸入baba#，則輸出為：步驟 狀態(tài)棧 符號棧 輸入串 action goto 1 0 # baba# s4 2 04 #b aba# r3 23 02 #b aba# s64 026 #ba ba# s75 0267 #bab a# error(2)若輸入bb#，則輸出為：步驟 狀態(tài)棧 符號棧 輸入串 action goto 1 0 # bb# s4 2 04 #b b# r3 23 02 #b b# s

24、74 027 #bb # r3 55 025 #bb # r1 16 01 #s # acc三、算法流程圖errorys0進(jìn)狀態(tài)棧、#進(jìn)符號棧開始輸出狀態(tài)棧、輸出符號棧輸出輸入串、查動作表當(dāng)前符號進(jìn)棧y查狀態(tài)轉(zhuǎn)換表新的狀態(tài)進(jìn)棧讀字符移進(jìn)按某產(chǎn)生式歸約y符號棧、狀態(tài)棧的元素相應(yīng)退棧歸約后的符號進(jìn)棧查狀態(tài)轉(zhuǎn)換表、新的狀態(tài)進(jìn)棧結(jié)束n歸約n是否分析終止n四、程序代碼#include #include char *action103=s3#,s4#,null, /*action表*/ null,null,acc, s6#,s7#,null, s3#,s4#,null, r3#,r3#,null, nul

25、l,null,r1#, s6#,s7#,null, null,null,r3#, r2#,r2#,null, null,null,r2#; int goto1102= 1,2, /*goto表*/ 0,0, 0,5, 0,8, 0,0, 0,0, 0,9, 0,0, 0,0, 0,0; char vt3=a,b,#; /*存放非終結(jié)符*/ char vn2=s,b; /*存放終結(jié)符*/ char *lr4=e-s#,s-bb#,b-ab#,b-b#;/*存放產(chǎn)生式*/ int a10; char b10,c10,c1; int top1,top2,top3,top,m,n; void main() int g,h,i,j,k,l,p,y,z,count; char x,copy10,copy110; top1=0;top2=0;top3=0;top=0; a0=0;y=a0;b0=#; count=0;z=0; printf(請輸入表達(dá)式n); /*輸出狀態(tài)棧、輸出符號棧、輸出輸入串*/ do scanf(%c,&c1); ctop3=c1; top3=top3+1; while(c1!=#); print