編譯原理課設(shè)-(詞法分析、自下而上語法分析程序、生成中間代碼)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 課程設(shè)計(jì)任務(wù)書課題名稱編譯原理課程設(shè)計(jì)完成時間 指導(dǎo)教師 職稱 學(xué)生姓名 班級 總體設(shè)計(jì)要求總體設(shè)計(jì)要求： 課程設(shè)計(jì)內(nèi)容共給定1個題目，每個學(xué)生按照課程設(shè)計(jì)要求，在規(guī)定的兩周時間內(nèi)獨(dú)立完成。題目： 編譯程序構(gòu)造涉及內(nèi)容：詞法分析、語法分析、語義分析生成中間代碼工作內(nèi)容及時間進(jìn)度安排第一周、周：設(shè)計(jì)動員，布置課程設(shè)計(jì)任務(wù)，查閱資料，制定方案，進(jìn)行程序方案設(shè)計(jì)。第一周、周2-周5：編寫和調(diào)試程序第二周、周1-周3：編寫和調(diào)試程序第二周、周4：整理，撰寫設(shè)計(jì)報(bào)告。第二周、周5：驗(yàn)收，提交設(shè)計(jì)報(bào)告，評定成績。畢業(yè)設(shè)計(jì)成果1、課程設(shè)計(jì)報(bào)告書一份2、源程序清單一份3、成果使用說

2、明書一份內(nèi)容摘要 第1章 緒論1.1、課程設(shè)計(jì)目的 1.2、課程設(shè)計(jì)意義 1.3、課程設(shè)計(jì)要求 1.4、課程設(shè)計(jì)內(nèi)容1.4.1、題目編譯程序構(gòu)造1.4.2、內(nèi)容涉及詞法分析、自下而上語法分析程序的實(shí)現(xiàn)：SLR（1）分析器的實(shí)現(xiàn)以及生成中間代碼。1.4.3、具體要求根據(jù)LR分析算法構(gòu)造SLR（1）分析程序，并完成語法分析動作（當(dāng)需要一個單詞時，調(diào)用詞法分析程序獲?。?，同時完成語義分析生成四元式輸出。要求程序具有通用性，改變文法時只需改變程序的數(shù)據(jù)初值，無需改變程序主體；要求完成一條說明語句、一條算數(shù)表達(dá)式和賦值語句的翻譯，生成中間代碼。變量說明語句的文法及相應(yīng)的語義子程序：.att表示數(shù)據(jù)類型屬

3、性，fill函數(shù)表示將單詞id及其類別屬性填寫符號表。（0）SD； acc（1）Dint id fill（id，int）；D.att=int; （2）Dfloat id fill(id,float); D.att=float; （3）DD（1），id fill(id,D(1).att);D.att=D(1).att; 算數(shù)表達(dá)式和賦值語句的文法及相應(yīng)的語義子程序。（1）Aid=E； p=lookup(); emit（E.PALCE, , p）; （2）EE(1)+T E.PALCE=newtemp(); emit(+，E(1).PALCE，T.PALCE，E.PALCE)（3）E

4、T E.PALCE=T.PALCE;（4）TT(1)*F T.PALCE=newtemp(); emit(+，T(1).PALCE，F(xiàn).PALCE，T.PALCE)（5）TF T.PALCE=F.PALCE;（6）F(E) F.PALCE=E.PALCE;（7）Fid P=LOOKUP(); F.PALCE=P;（8）Fnum P=LOOKUP(num.value)F.PALCE=P;構(gòu)造其用于SLR(1)分析的識別活前綴的DFA以及action表和goto表。然后編程實(shí)現(xiàn)。（關(guān)于詞法分析部分只需識別出與此文法相關(guān)的單詞即可（+，*，(，)，id，=）。1.4.4、程序設(shè)計(jì)提示（

5、1）分析棧設(shè)計(jì)時可以用一個棧完成，也可以設(shè)計(jì)三個棧：一個符號棧，一個狀態(tài)棧，一個語義棧，則歸約時，則需要在符號棧中退掉n個符號，在狀態(tài)棧中退掉n個符號（n為產(chǎn)生式符號個數(shù)），語義棧中退掉n個符號對應(yīng)的語義；（2）終結(jié)符表和非終結(jié)符表的組織和預(yù)測分析程序中相同（將符號對應(yīng)到一個數(shù)字，表示在分析表中對應(yīng)的下標(biāo)）。（3）action表中的錯誤處理：簡化的錯誤處理：當(dāng)查找action表出現(xiàn)空白時，則當(dāng)前單詞無法移進(jìn)和規(guī)約，可簡單的認(rèn)為當(dāng)前單詞為多余的單詞，則拋棄當(dāng)前單詞，讀下一單詞繼續(xù)分析。1.4.5、測試數(shù)據(jù)源文件中數(shù)據(jù)：int area，r； r=1；area=r*r+r；程序要求輸出二元式序列、

6、符號表、語法分析過程、四元式序列。1.4.6、程序擴(kuò)展要求 第2章 程序總體設(shè)計(jì) 第3章 程序詳細(xì)設(shè)計(jì)與實(shí)現(xiàn)3.1、詞法分析首先定義結(jié)構(gòu)體typedef struct /狀態(tài)棧 int datamax;int top;seqstack1;typedef struct /符號棧 string datamax; int top;seqstack2;struct reserveedword/保留字表結(jié)構(gòu) string word;char value;reserveedword1maxsize;struct identifer/標(biāo)識符表結(jié)構(gòu) char identiname15; char identi

7、type15; int address;identifer1maxsize;struct constant/常量表結(jié)構(gòu)string constantname; string value; int constantaddress;constant1maxsize;詞法分析主要函數(shù)結(jié)構(gòu)： void Initscanner() /該函數(shù)用于用C語言當(dāng)中常見的關(guān)鍵字初始化保留表 void Isalpha(char s) /用于判斷讀入的字符是不是字母 void Isnumber(char s) /用于判斷讀入的字符是不是數(shù)字 void Isother(char s) /判斷除數(shù)字與字母之外的其他字符

8、void Lexscan() /用于循環(huán)從程序中讀入字符并判斷應(yīng)調(diào)用那個判斷函數(shù)字符 void Output(int i,int j,char ss15) /輸出二元式 本模塊程序的偽代碼如下：打開文件infile.open("input.txt",ios:in); if(!infile) cerr<<"讀取的文件打開失敗!"<<endl; exit(1); 初始化保留字表 Initscanner();循環(huán)讀入從文件當(dāng)中 Scanner()while(ch!='#') 在該函數(shù)中判斷應(yīng)該調(diào)用的判斷函數(shù) Lexsca

9、n() infile.get(ch); if(ch>='A')&&(ch<='Z')|(ch>='a')&&(ch<='z') Isalpha(ch) Output； else if(ch>='0')&&(ch<='9') Isnumber(ch) Output； else Isother(ch) Output； 關(guān)閉文件infile.close(); 詞法分析器中從源文件讀出一個單詞，判斷其類型是關(guān)鍵字、標(biāo)識符還是

10、普通符號，根據(jù)其類型為結(jié)構(gòu)體各項(xiàng)賦值，并將其傳給語法分析函數(shù)。3.2、語法分析由于說明語句與算術(shù)表達(dá)式和賦值語句所使用的是不同的文法，所以兩者的ACTION表和GOTO表也不一樣，本次課設(shè)采用二維數(shù)組存放ACTION表和GOTO表信息，其中移進(jìn)用大于0的數(shù)表示，歸約用小于0的數(shù)表示，成功用100表示(acc),其他處用0表示，查表時遇到相應(yīng)的數(shù)進(jìn)行相應(yīng)的操作。其中，歸約部分需要根據(jù)其產(chǎn)生式的信息進(jìn)行，所以程序中有如下定義：string v18="int","float","",",","id",

11、"#","D","S" /存放說明文法當(dāng)中的字符string v213="#","id","=","num","","+","*","(",")","F","A","E","T"/存放算本文法當(dāng)中的字符根據(jù)狀態(tài)轉(zhuǎn)換圖(DFA)構(gòu)造SLR(1)分析表：其中說明文法和算術(shù)文法分別構(gòu)造

12、，同時在每個表當(dāng)中既有action表 又有g(shù)oto表int analysis_table1108=3,4,0,0,0,0,2,1, 0,0,0,0,0,100,0,0,0,0,5,6,0,0,0,0,0,0,0,0,7,0,0,0,0,0,0,0,8,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,9,0,0,0,0,0,-2,-2,0,0,0,0,0,0,-3,-3,0,0,0,0,0,0,-4,-4,0,0,0,0;int analysis_table21713=0,2,0,0,0,0,0,0,0,0,1,0,0, 100,0,0,0,0,0,0,0,0,0,0,0,0, 0

13、,0,3,0,0,0,0,0,0,0,0,0,0, 0,9,0,8,0,0,0,7,0,6,0,4,5, 0,0,0,0,10,11,0,0,0,0,0,0,0, 0,0,0,0,-3,-3,12,0,-3,0,0,0,0, 0,0,0,0,-5,-5,-5,0,-5,0,0,0,0, 0,9,0,8,0,0,0,7,0,6,0,13,5, 0,0,0,0,-8,-8,-8,0,-8,0,0,0,0, 0,0,0,0,-7,-7,-7,0,-7,0,0,0,0, -1,0,0,0,0,0,0,0,0,0,0,0,0, 0,9,0,8,0,0,0,7,0,6,0,0,14, 0,9,0,8,0,

14、0,0,7,0,15,0,0,0, 0,0,0,0,0,11,0,0,16,0,0,0,0, 0,0,0,0,-2,-2,12,0,-2,0,0,0,0, 0,0,0,0,-4,-4,-4,0,-4,0,0,0,0, 0,0,0,0,-6,-6,-6,0,-6,0,0,0,0;語法分析當(dāng)中各個函數(shù)說明及偽代碼：void action1(int i,string s) /通過詞法分析傳過來的值判斷移進(jìn)動作三個棧(狀態(tài)棧,符號棧,語義棧)應(yīng)該讀入哪些值。void action2(int i,string s) /同action1只是表示算術(shù)文法int address(string m,int i,

15、string x) /獲得在分析表中的列下標(biāo)void goto1(int i,string s) /通過判斷棧中的元素，來判斷用那個產(chǎn)生式來進(jìn)行規(guī)約void goto2(int i,string s) /同goto1void slr1() /對說明文法進(jìn)行語法分析void slr1() /對算術(shù)文法進(jìn)行語法分析 偽代碼如下： 先判斷是說明文法還是算術(shù)文法 If(說明文法) Slr1()push_seq1(s1,0); push_seq2(s2,"#");push_seq2(s3,"_");while(1) j=address(v1,8,get1); to

16、p_seq1(s1,top); j=analysis_table1topj; if(j<0) if(j=-1) 用S->D;歸約 else if(j=-2)用D->int id歸約 else if(j=-3)用D->float id歸約" else if(j=-4)用D->D,id歸約" else if(j>0) action1(top,get1); else Slr2() push_seq1(s1,0); push_seq2(s2,"#"); push_seq2(s3,"_"); while(1)

17、 j=address(v2,13,get1); j=analysis_table2topj; if(j>0) action2(top,get1); else if(j<0) if(j=-1)用A->id=E;歸約" else if(j=-2)用E->E+T歸約" else if(j=-3)用E->T歸約" else if(j=-4) 用T->T*F歸約"); else if(j=-5)用T->F歸約" else if(j=-6)用F->(E)歸約" else if(j=-7)用F->

18、;id歸約" else if(j=-8)用F->num歸約" 3.3、語義分析一個程序經(jīng)過詞法分析，語法分析之后，表明該院程序在書寫上是正確的，但是未對程序的內(nèi)部邏輯語義進(jìn)行分析，接下來是進(jìn)行語義分析。語義分析當(dāng)中各個函數(shù)說明： void print(string s) /打印四元式str1,string str2,string str3,string str4) /產(chǎn)生四元式string newtemp() /產(chǎn)生一個新的臨時變量 3.4、程序?qū)崿F(xiàn)結(jié)果圖圖3-4 語義分析結(jié)果圖圖3-5二元式圖3-6符號表圖3-7四元式 專心-專注-專業(yè)附錄#include<i

19、ostream>#include<fstream>using namespace std;#define maxsize 50#define max 30ifstream infile;char ch;int m,n,kk=0,addr=0,t=1;string get1;string inmaxsize;string insmaxsize;string s4;int count=0;string v18="int","float","",",","id","#&qu

20、ot;,"D","S"string v213="#","id","=","num","","+","*","(",")","F","A","E","T"string E="",E1="",T="",T1="",F=&qu

21、ot;"int analysis_table1108=3,4,0,0,0,0,2,1, 0,0,0,0,0,100,0,0,0,0,5,6,0,0,0,0,0,0,0,0,7,0,0,0,0,0,0,0,8,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,9,0,0,0,0,0,-2,-2,0,0,0,0,0,0,-3,-3,0,0,0,0,0,0,-4,-4,0,0,0,0;int analysis_table21713=0,2,0,0,0,0,0,0,0,0,1,0,0, 100,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,3,0,0,0,0,0,0,

22、0,0,0,0, 0,9,0,8,0,0,0,7,0,6,0,4,5, 0,0,0,0,10,11,0,0,0,0,0,0,0, 0,0,0,0,-3,-3,12,0,-3,0,0,0,0, 0,0,0,0,-5,-5,-5,0,-5,0,0,0,0, 0,9,0,8,0,0,0,7,0,6,0,13,5, 0,0,0,0,-8,-8,-8,0,-8,0,0,0,0, 0,0,0,0,-7,-7,-7,0,-7,0,0,0,0, -1,0,0,0,0,0,0,0,0,0,0,0,0, 0,9,0,8,0,0,0,7,0,6,0,0,14, 0,9,0,8,0,0,0,7,0,15,0,0,0,

23、 0,0,0,0,0,11,0,0,16,0,0,0,0, 0,0,0,0,-2,-2,12,0,-2,0,0,0,0, 0,0,0,0,-4,-4,-4,0,-4,0,0,0,0, 0,0,0,0,-6,-6,-6,0,-6,0,0,0,0;typedef struct /狀態(tài)棧 int datamax;int top;seqstack1;typedef struct /符號棧 string datamax;int top;seqstack2;struct reserveedword/保留字表結(jié)構(gòu)string word;char value;reserveedword1maxsize;str

24、uct identifer/標(biāo)識符表結(jié)構(gòu)char identiname15;char identitype15;int address;identifer1maxsize;struct constant/常量表結(jié)構(gòu)string constantname;string value;int constantaddress;constant1maxsize;void Initscanner();void Lexscan();void Isalpha(char);void Isnumber(char);void Isother(char);void Output(int ,int ,char *);v

25、oid Scanner();void change(char c,string str) int len=str.length();for(int num=0;num<len;num+)cnum=strnum;clen='0'seqstack1 *init_seqstack1()seqstack1 *s;s=new seqstack1;if(!s)cout<<"空間不足！"<<endl;return NULL;else s->top=-1;return s; int empty_seq1(seqstack1 *s)if(s

26、->top=-1) return 1;else return 0;int push_seq1(seqstack1 *s,int x) if(s->top=max-1)return 0;else s->top+;s->datas->top=x;return 1;int pop_seq1(seqstack1 *s,int *x)if(empty_seq1(s)return 0;else *x=s->datas->top;s->top-;return 1;void top_seq1(seqstack1 *s,int &e)if(empty_se

27、q1(s)cout<<"占空!"else e=s->datas->top;seqstack2 *init_seqstack2()seqstack2 *s;s=new seqstack2;if(!s)cout<<"空間不足！"<<endl;return NULL;else s->top=-1;return s; int empty_seq2(seqstack2 *s)if(s->top=-1) return 1;else return 0;int push_seq2(seqstack2 *s,st

28、ring x) if(s->top=max-1)return 0;else s->top+;s->datas->top=x;return 1;int pop_seq2(seqstack2 *s,string *x)if(empty_seq2(s)return 0;else *x=s->datas->top;s->top-;return 1;void out_seq1(seqstack1 *s)for(int i=0;i<=s->top;i+)printf("%d",s->datai);void out_seq2(s

29、eqstack2 *s) char ch15;for(int i=0;i<=s->top;i+)change(ch,s->datai);printf("%s",ch);seqstack1 *s1=init_seqstack1();seqstack2 *s2=init_seqstack2();seqstack2 *s3=init_seqstack2();void pop(int n)int m;string s;for(int i=0;i<n;i+)pop_seq1(s1,&m);pop_seq2(s2,&s); pop_seq2(s3

30、,&s);int screamp(char a15,string b)int i=0,j=0; while(ai!='0'&&bi!='0')if(ai=bi)i+; j+; elsereturn 0;if(ai=bi)return 1;elsereturn 0;int screamp1(string a,string b)int i=0,j=0; while(ai!='0'&&bi!='0')if(ai=bi)i+; j+; elsereturn 0;if(ai=bi)return 1;e

31、lsereturn 0;void clear(seqstack1 *s1,seqstack2 *s2,seqstack2 *s3)int m;string s;while(!empty_seq1(s1)pop_seq1(s1,&m); pop_seq2(s2,&s); pop_seq2(s3,&s);void char_Table() char str115,str215; cout<<"n生成的標(biāo)識符表為：" cout<<"ntnamettypetvaluetaddress" for(int i=0;i&

32、lt;m;i+) printf("n%dt%st%s",i,identifer1i.identiname,identifer1i.identitype); cout<<"n生成的常數(shù)表為：" cout<<"ntvaluettypetnametaddress" for(int j=0;j<n;j+) change(str1,constant1j.constantname); change(str2,constant1j.value); printf("n%dt%st%s",j,str1,

33、str2); int judge(string m,int i,string x) for(int j=0;j<i;j+) if(screamp1(x,mj) return 1; return 0;int address(string m,int i,string x) for(int j=0;j<i;j+) if(screamp1(x,mj) return j;void print(string s)cout<<"n產(chǎn)生的四元式為"<<endl;char chmax; for(int i=0;i<count;i+)change(c

34、h,si);printf("%s",ch);cout<<endl;cout<<endl;void emit(string str1,string str2,string str3,string str4) scount+="("scount+=str1;scount+=","scount+=str2;scount+=","scount+=str3;scount+=","scount+=str4;scount+=")"count+;string newt

35、emp()char s2;s0='T's1=t;s2='0't+;return s;void action1(int i,string s)int pos,j;j=address(v1,8,s);pos=analysis_table1ij;char str15;change(str,s);out_seq1(s1);printf("tt");out_seq2(s2);printf("tt");out_seq2(s3);printf("tt");if(pos=100)cout<<"分析

36、成功！"<<endl; cout<<"*"<<endl;else printf("action%d,%s=S%d狀態(tài)%d入棧n",i,str,pos,pos);push_seq1(s1,pos); push_seq2(s2,s); push_seq2(s3,"_"); get1=inaddr;addr+;void goto1(int i,string s) int pos,j; if(judge(v1,8,s) j=address(v1,8,s);pos=analysis_table1ij

37、;char str15;change(str,s); printf("goto%d,%s=%dn",i,str,pos);push_seq1(s1,pos);push_seq2(s2,s);void slr1() clear(s1,s2,s3); char str115; push_seq1(s1,0); push_seq2(s2,"#"); push_seq2(s3,"_"); get1=inaddr; addr+; int top,j; while(1) j=address(v1,8,get1); top_seq1(s1,top)

38、; if(top=100) addr-; return; j=analysis_table1topj; if(j<0) if(j=-1) out_seq1(s1);printf("tt");out_seq2(s2);printf("tt");out_seq2(s3);printf("tt用S->D;歸約"); pop(2); top_seq1(s1,top); goto1(top,"S"); push_seq2(s3,"_"); else if(j=-2) out_seq1(s1);

39、printf("tt");out_seq2(s2);printf("tt");out_seq2(s3);printf("tt用D->int id歸約"); change(str1,"int"); for(int k=0;k<15;k+) identifer1kk.identitypek=str1k; kk+; pop(2); top_seq1(s1,top); goto1(top,"D"); push_seq2(s3,"_"); else if(j=-3) out

40、_seq1(s1);printf("tt");out_seq2(s2);printf("tt");out_seq2(s3);printf("tt用D->float id歸約"); change(str1,"float"); for(int k=0;k<15;k+) identifer1kk.identitypek=str1k; kk+; pop(2); top_seq1(s1,top); goto1(top,"D"); push_seq2(s3,"_"); els

41、e if(j=-4) out_seq1(s1);printf("tt");out_seq2(s2);printf("tt");out_seq2(s3);printf("tt用D->D,id歸約"); for(int k=0;k<15;k+) identifer1kk.identitypek=identifer1kk-1.identitypek; kk+; pop(3); top_seq1(s1,top); goto1(top,"D"); push_seq2(s3,"_"); else

42、 if(j>0) action1(top,get1); void action2(int i,string s)int pos,j; if(judge(v2,13,s) j=address(v2,13,s);pos=analysis_table2ij;char str15;change(str,s);out_seq1(s1);printf("tt");out_seq2(s2);printf("tt");out_seq2(s3);printf("tt");if(pos=100)cout<<"分析成功！&quo

43、t;<<endl;cout<<"*"<<endl;else printf("action%d,%s=S%d狀態(tài)%d入棧n",i,str,pos,pos);push_seq1(s1,pos); push_seq2(s2,s); push_seq2(s3,"_"); get1=inaddr;addr+;void goto2(int i,string s) int pos,j; if(judge(v2,13,s) j=address(v2,13,s);pos=analysis_table2ij;char

44、str15;change(str,s); printf("goto%d,%s=%dn",i,str,pos);push_seq1(s1,pos);push_seq2(s2,s); void slr2() t='1' clear(s1,s2,s3); push_seq1(s1,0); push_seq2(s2,"#"); push_seq2(s3,"_"); get1=inaddr; addr+; string p10;int num=0; pnum=insaddr-1;num+; int top,j; char str

45、115; while(1) j=address(v2,13,get1); top_seq1(s1,top); if(top=100) addr-; return; j=analysis_table2topj; if(j>0) action2(top,get1); else if(j<0) if(j=-1) out_seq1(s1);printf("tt");out_seq2(s2);printf("tt");out_seq2(s3);printf("tt用A->id=E;歸約"); pop(4); top_seq1(

46、s1,top); goto2(top,"A"); for(int i=0;i<m;i+) if(screamp(identifer1i.identiname,p0)&&(identifer1i.identitype!=NULL) change(str1,identifer1i.identiname); emit("=",E,"_",str1); push_seq2(s3,str1); else if(j=-2) out_seq1(s1);printf("tt");out_seq2(s2);pr

47、intf("tt");out_seq2(s3);printf("tt用E->E+T歸約"); pop(3); top_seq1(s1,top); goto2(top,"E"); E1=E; E=newtemp(); emit("+",E1,T,E); push_seq2(s3,E); else if(j=-3) out_seq1(s1);printf("tt");out_seq2(s2);printf("tt");out_seq2(s3);printf("tt

48、用E->T歸約"); pop(1); top_seq1(s1,top); goto2(top,"E"); E=T; push_seq2(s3,T); else if(j=-4) out_seq1(s1);printf("tt");out_seq2(s2);printf("tt");out_seq2(s3);printf("tt用T->T*F歸約"); pop(3); top_seq1(s1,top); goto2(top,"T"); T1=T; T=newtemp(); e

49、mit("*",T1,F,T); push_seq2(s3,T); else if(j=-5) out_seq1(s1);printf("tt");out_seq2(s2);printf("tt");out_seq2(s3);printf("tt用T->F歸約"); pop(1); top_seq1(s1,top); goto2(top,"T"); T=F; push_seq2(s3,F); else if(j=-6) out_seq1(s1);printf("tt")

50、;out_seq2(s2);printf("tt");out_seq2(s3);printf("tt用F->(E)歸約"); pop(3); top_seq1(s1,top); goto2(top,"F"); F=E; push_seq2(s3,E); else if(j=-7) pnum=insaddr-2;num+; out_seq1(s1);printf("tt");out_seq2(s2);printf("tt");out_seq2(s3);printf("tt用F->id歸約"); pop(1); top_seq1(s1,top); goto2(top,"F"); for(int i=0;i<m;i+) if(screamp(identifer1i.identiname,pnum-1)&&(identifer1i.identitype!=NULL) change(str1,identifer1i.identi