編譯原理詞法分析器語(yǔ)法分析器實(shí)驗(yàn)報(bào)告

1、編譯技術(shù) 班 級(jí) 網(wǎng)絡(luò) 0802 學(xué) 號(hào) 3080610052姓 名 葉晨舟指導(dǎo)老師 朱 玉 全 2011年 7 月 4 日一、目的編譯技術(shù)是理論與實(shí)踐并重的課程，而其實(shí)驗(yàn)課要綜合運(yùn)用一、二年級(jí)所學(xué)的多門(mén)課程的內(nèi)容，用來(lái)完成一個(gè)小型編譯程序。從而鞏固和加強(qiáng)對(duì)詞法分析、語(yǔ)法分析、語(yǔ)義分析、代碼生成和報(bào)錯(cuò)處理等理論的認(rèn)識(shí)和理解；培養(yǎng)學(xué)生對(duì)完整系統(tǒng)的獨(dú)立分析和設(shè)計(jì)的能力，進(jìn)一步培養(yǎng)學(xué)生的獨(dú)立編程能力。二、任務(wù)及要求基本要求：1 詞法分析器 產(chǎn)生下述小語(yǔ)言的單詞序列這個(gè)小語(yǔ)言的所有的單詞符號(hào)，以及它們的種別編碼和內(nèi)部值如下表： 單詞符號(hào)種別編碼助記符內(nèi)碼值dimifdostopend標(biāo)識(shí)符常數(shù)（整）=

2、+*，（）1234567891011121314$dim$if$do$stop$end$id$int$assign$plus$star$power$comma$lpar$rpar-內(nèi)部字符串標(biāo)準(zhǔn)二進(jìn)形式-對(duì)于這個(gè)小語(yǔ)言，有幾點(diǎn)重要的限制：首先，所有的關(guān)鍵字（如ifwhile等）都是“保留字”。所謂的保留字的意思是，用戶不得使用它們作為自己定義的標(biāo)示符。例如，下面的寫(xiě)法是絕對(duì)禁止的： if（5）=x 其次，由于把關(guān)鍵字作為保留字，故可以把關(guān)鍵字作為一類特殊標(biāo)示符來(lái)處理。也就是說(shuō)，對(duì)于關(guān)鍵字不專設(shè)對(duì)應(yīng)的轉(zhuǎn)換圖。但把它們（及其種別編碼）預(yù)先安排在一張表格中（此表叫作保留字表）。當(dāng)轉(zhuǎn)換圖識(shí)別出一個(gè)標(biāo)識(shí)

3、符時(shí)，就去查對(duì)這張表，確定它是否為一個(gè)關(guān)鍵字。再次，如果關(guān)鍵字、標(biāo)識(shí)符和常數(shù)之間沒(méi)有確定的運(yùn)算符或界符作間隔，則必須至少用一個(gè)空白符作間隔（此時(shí)，空白符不再是完全沒(méi)有意義的了）。例如，一個(gè)條件語(yǔ)句應(yīng)寫(xiě)為 if i0 i= 1;而絕對(duì)不要寫(xiě)成 ifi0 i=1;因?yàn)閷?duì)于后者，我們的分析器將無(wú)條件地將ifi看成一個(gè)標(biāo)識(shí)符。這個(gè)小語(yǔ)言的單詞符號(hào)的狀態(tài)轉(zhuǎn)換圖，如下圖： 2 語(yǔ)法分析器 能識(shí)別由加+ 減- 乘* 除/ 乘方 括號(hào)（）操作數(shù)所組成的算術(shù)表達(dá)式，其文法如下：ee+t|e-t|ttt*f|t/f|ffpf|pp(e)|i 使用的算法可以是：預(yù)測(cè)分析法；遞歸下降分析法；算符優(yōu)先分析法；lr分析法

4、等。3 中間代碼生成器 產(chǎn)生上述算術(shù)表達(dá)式的中間代碼（四元式序列）三、實(shí)現(xiàn)過(guò)程給出各題目的詳細(xì)算法描述，數(shù)據(jù)結(jié)構(gòu)和函數(shù)說(shuō)明，流程圖。1、詞法分析器的流程圖2、語(yǔ)法分析器主程序圖3、中間代碼生成器流程圖：四、源程序詞法分析器:#include#include#includeusing namespace std;typedef struct table /分析表存儲(chǔ)結(jié)構(gòu) char m100; table;table m100100; /定義分析表typedef struct stacknode /定義棧內(nèi)元素節(jié)點(diǎn) (帶頭結(jié)點(diǎn)（為空）的) char data; struct stacknode *

5、next;stackk;void initlink(stackk *&s) /初始化新棧 s=(stackk *)malloc(sizeof(stackk); s-next=null;void poplink(stackk *&s) /頂元素出棧 stackk *p;char v; if(s-next!=null) p=s-next; v=p-data; s-next=p-next; free(p);void pushlink(stackk *&s,char x) /新 元 素 入 棧 stackk *p; p=(stackk *)malloc(sizeof(stackk); p-data=x

6、; p-next=s-next; s-next=p;void display(stackk *s) /打印 現(xiàn)實(shí)顯示 棧內(nèi)元素 stackk *p; int i=0,j; char st100; p=s-next; while(p!=null) sti+=p-data; p=p-next; for(j=i-1;j=0;j-) printf(%c,stj); for(j=0;jnext=null) return 0; else return s-next-data; int find(char c,char array) /查找函數(shù)，int i;int flag=0;for(i=0;i100;i

7、+)if(c=arrayi) flag=1;return flag;int location(char c,char array) /定位函數(shù),指出字符所在位置int i;for(i=0;i100;i+)if(c=arrayi) return i;void error() /出錯(cuò)函數(shù)定義 printf(%15c出錯(cuò)!n, );void analyse(char vn,char vt) int i,j,m,p,q,length,t,h; char w,x; char str100;opt0: scanf(%s,str); for(i=0;istrlen(str);i+) if(!find(str

8、i,vt) printf(輸入字符串有誤!請(qǐng)重新輸入!); goto opt0; break; stackk *st; initlink(st); pushlink(st,#); pushlink(st,vn0); /#與識(shí)別符號(hào)入棧 j=0; h=1; w=str0; printf(步驟%-12c分析棧%-24c剩余輸入串%-12c所用產(chǎn)生式n, , , );opt1: printf(%-16d,h); /顯示步驟 h+; display(st); /顯示分析棧中內(nèi)容 x=gettop(st); /上托棧頂符號(hào)放入x poplink(st); for(int k=0;k14+j;k+) /打

9、印對(duì)齊格式 printf(%c, ); for(t=j;t%sn,x,str0); /顯示對(duì)應(yīng)的產(chǎn)生式 if(strcmp(str0,$)=0) goto opt1; else length=strlen(str0); /逆序進(jìn)棧 for(m=length-1;m=0;m-) pushlink(st,str0m); goto opt1; int main() int i,k,n,r; char vn100,vt100,select; printf(*n); printf(對(duì)任意輸入ll(1)文法的分析表，判斷驗(yàn)證字符串是否為該文法的句子 n); printf(并能給出分析和演示過(guò)程。 n);

10、printf(*n);opt2: printf(請(qǐng)輸入各終結(jié)符（#號(hào)表示結(jié)束 ）vti:n); for(i=0;i100;i+) scanf(%c,&vti); if(vti=#) r=i; break; printf(請(qǐng)輸入非終結(jié)符個(gè)數(shù):n); scanf(%d,&n); getchar(); for (i=0;in;i+) printf(請(qǐng)輸入非終結(jié)符vn%d:n,i); scanf(%c,&vni); getchar(); printf(請(qǐng)輸入此非終結(jié)符對(duì)應(yīng)各終結(jié)符的產(chǎn)生式右部(null或null表示出錯(cuò);$表示空串):n); for(k=0;kselect; switch(select

11、) case 1: goto opt3;break; case 2: goto opt2; case 0: break; default: printf(輸入錯(cuò)誤!請(qǐng)重新選擇:); goto opt4; break; return 0;運(yùn)行結(jié)果：語(yǔ)法分析器 源程序：#include#includeusing namespace std;char prog100,token10;char ch;int syn,p,m=0,n,row,sum=0;char *rwtab20=dim,if,do,stop,end ,and,begin,bool,case,char,false,for,int,not

12、,or,set,then,true,until,while; void scaner()for(n=0;n=a&ch=a&ch=0&ch=a&ch=a&ch=z)tokenm+=ch;ch=progp+;tokenm+=0;p-;syn=21;for(n=0;n=0&ch=0&ch32767)syn=-1;else switch(ch) case=:syn=8+15;token0=ch;break;case+:syn=9+15;token0=ch;break;case*:m=0;tokenm+=ch;ch=progp+;if(ch=*)syn=11+15; tokenm+=ch;elsesyn

13、=10+15;p-; break;case,:syn=12+15;token0=ch;break;case(:syn=13+15;token0=ch;break;case):syn=14+15;token0=ch;break;case#:syn=0;token0=ch;break;case)syn=17+15;tokenm+=ch;else if(ch=)syn=16+15;tokenm+=ch;elsesyn=15+15;p-;break;case:m=0;tokenm+=ch;ch=progp+;if(ch=)syn=19+15;tokenm+=ch;elsesyn=18+15;p-;br

14、eak;case:m=0;tokenm+=ch;ch=progp+;if(ch=)syn=21+15;tokenm+=ch;elsesyn=20+15;p-;break;case/:syn=22+15;token0=ch;break;case-:syn=23+15;token0=ch;break;case;:syn=24+15;token0=ch;break;default: syn=-1;break;void main()p=0;row=1;coutendlendlendl;cout*小型詞法分析器*endlendl;cout請(qǐng)輸入一段程序（以#結(jié)束）:;docin.get(ch);prog

15、p+=ch;while(ch!=#);p=0;coutendl*詞法分析結(jié)果如下*endl;cout 種別編碼 自身值endl;doscaner();switch(syn)case 22 : cout (syn , sum)endl; break; case -1: cout error in rowrow!endl; break; default: cout (syn , token)endl;break;while (syn!=0);運(yùn)行結(jié)果：中間代碼生成器源程序：表達(dá)式生成四元式遞歸子程序法#include#include using namespace std;#define defa

16、ult_size 100char emachine(char w); /表達(dá)式e的自動(dòng)機(jī)char tmachine(char w); /表達(dá)式t的自動(dòng)機(jī)char fmachine(char w); /表達(dá)式f的自動(dòng)機(jī)bool zmachine(); /表達(dá)式z的自動(dòng)機(jī)string inttostring(int a); /整形變成字符串形函數(shù)class stack/棧類定義private: int top; string *stacka; int maxsize;public: stack(int size=default_size); stack() delete stacka; void

17、push(const string &item); string pop(void); string gettop(void) const ; bool empty(void) const return (top=-1); bool full(void) const return (top=maxsize-1); void clear(void) top=-1; ;stack:stack(int size) /棧類的構(gòu)造函數(shù) top=-1; maxsize=size; stacka=new stringmaxsize; if(!stacka) cerrallocate memory faile

18、d.endl; exit(1); void stack:push(const string &item) /壓棧操作 if(full() cerrstack full, cannot push.endl; return; top+; stackatop=item;string stack:pop(void) /出棧操作 if(empty() cerrstack empty, cannot pop.endl; exit(1) ; string item=stackatop; top-; return item;string stack:gettop(void) const /取棧頂操作 if(e

19、mpty() cerrstack empty, cannot gettop.endl; exit(1) ; return stackatop;static stack wordstack; /符號(hào)棧static int noofquet=0; /靜態(tài)四元式個(gè)數(shù)記錄static int nooft = 1; /靜態(tài)狀態(tài)個(gè)數(shù)記錄void main() /主函數(shù)char yesorno; /進(jìn)行一個(gè)循環(huán)操作控制docout請(qǐng)輸入算術(shù)表達(dá)式：endl;nooft = 1; /每次結(jié)束詢問(wèn)zmachine();coutendlyesorno; /輸入“y”則繼續(xù)while(yesorno=y); /否則程序結(jié)束bool zmachine() /z自動(dòng)機(jī)char w;cinw;w = emachine(w); /調(diào)用e自動(dòng)機(jī)if(w=#) /遇到“#”則結(jié)束return true;elsereturn false;char emachine(char w) /e自動(dòng)機(jī)string operate,a,b,c;string state5;w = tmachine(w); /調(diào)用t自動(dòng)機(jī)while(w=+|w=-) /是加或減符號(hào)operate = w;cinw; /讀入下一字符w = tmachine(w); /調(diào)用t自動(dòng)機(jī)b = wordstack.pop();