編譯原理課程設(shè)計(jì)---小型程序設(shè)計(jì)語言編譯器的設(shè)計(jì)與實(shí)現(xiàn)

1、 課 程 設(shè) 計(jì) 報(bào) 告課程設(shè)計(jì)名稱： 編譯技術(shù) 系 ： 三 系 學(xué)生姓名： 王 輝 班 級： 09軟件（1）班 學(xué) 號： 20090307141 成 績： 指導(dǎo)教師： 石 魯 生 開課時(shí)間： 2011-2012 學(xué)年 2 學(xué)期目錄一設(shè)計(jì)題目1二主要內(nèi)容1三具體要求1四進(jìn)度安排2五成績評定2六設(shè)計(jì)思路31.詞法分析3（1）單詞符號及種別表32.SLR的分析表：41). 算術(shù)表達(dá)式的SLR(1)分析表：42). 布爾表達(dá)式的SLR分析表：43). 程序語句的SLR分析表：6七源程序及運(yùn)行結(jié)果71）源代碼：72）運(yùn)行截圖28八心得體會(huì)311編譯原理課程設(shè)計(jì)報(bào)告一設(shè)計(jì)題目小型程序設(shè)計(jì)語言編譯器的設(shè)計(jì)

2、與實(shí)現(xiàn)二主要內(nèi)容 自定義一種簡單的小型高機(jī)程序設(shè)計(jì)語言，采用任意一種編程語言和編程工具設(shè)計(jì)并實(shí)現(xiàn)其編譯器，展示編譯系統(tǒng)中詞法分析和語法分析的全過程。三具體要求1、對單詞的構(gòu)詞規(guī)則有明確的定義；2、編寫的詞法分析程序能夠正確識別源程序中的單詞符號；3、識別出的單詞以<種別碼，值>的二元式形式保存在符號表中并輸出；4、構(gòu)造出程序設(shè)計(jì)語言各語法單位的SLR分析表；(其他分析表亦可)5、能夠?qū)斎氲脑闯绦蜃龀稣_的語法分析并輸出清晰的結(jié)果；6、高級語言的規(guī)模不易過大，注重編譯器內(nèi)核的設(shè)計(jì)，對于界面無要求；7、課程設(shè)計(jì)報(bào)告中應(yīng)對所自定義高級語言進(jìn)行簡單描述，對編譯器的設(shè)計(jì)進(jìn)行簡單的需求分析，

3、給出設(shè)計(jì)說明和程序結(jié)構(gòu)框架，闡明設(shè)計(jì)思路、用到的原理和方法。8、不可更改課程設(shè)計(jì)報(bào)告中已有的字體和格式，課程設(shè)計(jì)報(bào)告中新加入內(nèi)容，漢字采用宋體五號字，英文字符和數(shù)字采用Times New Roman五號字。9、課程設(shè)計(jì)報(bào)告中的運(yùn)行結(jié)果應(yīng)以程序運(yùn)行截圖形式出現(xiàn)。10、程序源代碼以郵件名稱：“班級學(xué)號姓名”發(fā)送至指定郵箱：sqckcsj08四進(jìn)度安排序號內(nèi) 容時(shí)間（天）1布置題目、查找資料12概要設(shè)計(jì)13詳細(xì)設(shè)計(jì)34調(diào)試分析15測試結(jié)果0.56總結(jié)和完成設(shè)計(jì)報(bào)告1合 計(jì)7.5五成績評定1.考核方法：通過現(xiàn)場考勤、檢查源程序和批改課程設(shè)計(jì)報(bào)告相結(jié)合的方式考察學(xué)生的動(dòng)手能力，獨(dú)立分析解決問題的能力和創(chuàng)

4、新精神，并根據(jù)學(xué)生的學(xué)習(xí)態(tài)度綜合考評。2.成績評定：成績分優(yōu)、良、中、及格和不及格五等。六設(shè)計(jì)思路1.詞法分析（1）單詞符號及種別表符號種別編碼說明sy_if0保留字 ifsy_then1保留字 thensy_else2保留字 elsesy_while3保留字 whliesy_begin4保留字 beginsy_do5保留字 dosy_end6保留字 enda7賦值語句semicolon8 “；”e9布爾表達(dá)式j(luò)inghao10“#”S11語句L12復(fù)合語句tempsy15臨時(shí)變量EA18B andEO19B orplus34“+”times36“*”becomes38“：=”op_and39

5、“and”op_or40“or”op_not41“not”rop42關(guān)系運(yùn)算符lparent48“（”rparent49“）”ident56變量intconst57整常量2.SLR的分析表：1). 算術(shù)表達(dá)式的SLR(1)分析表：算數(shù)表達(dá)式文法GE如下：E->E+E|E*E|(E)|i將文法GE拓廣為文法GE:(0) SE(1) EE+E(2) EE*E(3) E(E)(4) Ei由此得到算數(shù)表達(dá)式的SLR（1）分析表如下： 狀態(tài) ACTIONGOTOi+*()#E0s3s211s4s5acc2s3s263r4r4r4r44s3s275s3s286s4s5s97r1s5r1r18r2r2

6、r2r29r3r3r3r32). 布爾表達(dá)式的SLR分析表：布爾表達(dá)式的文法如下：B->BB|BB|¬B|I rop i|i為了便于語法分析時(shí)加工處理，我們將上述文法改為文法GS: BBAB|B0B|¬B|(B)|I rop i|i BABB0 B將文法GS拓廣為文法GS:(0）SB(1) B i(2) B I rop i(3) B (B)(4) B NOT B(5) A B AND(6) B AB(7) O B OR(8) B OB由此得到布爾表達(dá)式的SLR（1）分析表如下：狀態(tài) ACTION GOTOirop()NOTANDOR#BAO0s1s4s513781s2

7、r1r1r1r12s33r2r2r2r24s1s4s511785s1s4s56786r4s9s10r47s1s4s514788s1s4s515789r5r5r510r7r7r711s12s9s1012r3r3r3r313s9s10acc14r6s9s10r615r8s9s10r83). 程序語句的SLR分析表：程序語句的文法GS如下 Sif e then S else S|while e do S|begin L end|a LS;L|S由于在編譯程序設(shè)計(jì)與視線中，我們是將賦值語句與算數(shù)表達(dá)式歸為一類處理的，故在此將賦值語句僅看作是程序語句文法中一個(gè)終結(jié)符a，將布爾表達(dá)式B也看作為終結(jié)符e。將

8、文法GS拓廣為文法GS： (0)S S(1) S if e then S else S(2) S while e do S(3) S begin L end(4) S a(5) L S(6) L S;L由此得到程序語句的SLR（1）分析表如下：狀態(tài) ACTION GOTOifthenelsewhilebegindoenda;e#SL0s2s3s4s511acc2s63s74s2s3s4s5985r4r4r4r46s107s118s129r5s1310s2s3s4s51411s2s3s4s51512r3r3r3r313s2s3s4s591614s1715r2r2r2r216r617s2s3s4s

9、51818r1r1r1r1七源程序及運(yùn)行結(jié)果1）源代碼：#include<stdio.h>#include<string.h>#include<stdlib.h>#define ACC -2/*/#define sy_if0#define sy_then1#define sy_else2#define sy_while3#define sy_begin4#define sy_do5#define sy_end6#define a7#define semicolon8#define e9#define jinghao10#define S11#define L

10、12#define tempsy15#define EA18#define EO19#define plus34#define times36#define becomes38#define op_and39#define op_or40#define op_not41#define rop42#define lparent48#define rparent49#define ident56#define intconst57/*/charch='0'intcount=0;static char spelling10=" "static char line8

11、1=" "char*pline;staticchar ntab110010;structntabint tc;int fc;ntab2200;intlabel=0;struct rwordschar sp10;intsy;struct rwords reswords10="if",sy_if,"do",sy_do,"else",sy_else,"while",sy_while,"then",sy_then,"begin",sy_begin,"en

12、d",sy_end,"and",op_and,"or",op_or,"not",op_not;struct aaint sy1;int pos;buf1000, n, n1, E, sstack100, ibuf100, stack1000; struct aa oth;struct fourexpcharop10;structaa arg1;structaa arg2;intresult;fexp200;intssp=0;structaa *pbuf=buf;intnlength=0;intlnum=0;inttt1=0;

13、FILE*cfile;/*/intnewt=0;intnxq=100;intlr;intlr1;intsp=0;intstack1100;intsp1=0;intnum=0;structllint nxq1;int tc1;int fc1;labelmark10;int labeltemp10;int pointmark=-1,pointtemp=-1;int sign=0;/* 程序語句的LR分析表 */static int action1913=/* 0*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,1,-1,/* 1*/-1,-1,-1,-1,-1,-1,-1,-1,-1,

14、-1,ACC,-1,-1,/* 2*/-1,-1,-1,-1,-1,-1,-1,-1,-1,6,-1,-1,-1,/* 3*/-1,-1,-1,-1,-1,-1,-1,-1,-1,7,-1,-1,-1,/* 4*/2,-1,-1,3,5,-1,-1,5,-1,-1,-1,9,8,/* 5*/-1,-1,104,-1,-1,-1,104,-1,104,-1,104,-1,-1,/* 6*/-1,10,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/* 7*/-1,-1,-1,-1,-1,11,-1,-1,-1,-1,-1,-1,-1,/* 8*/-1,-1,-1,-1,-1,

15、-1,12,-1,-1,-1,-1,-1,-1,/* 9*/-1,-1,-1,-1,-1,-1,105,-1,13,-1,-1,-1,-1,/*10*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,14,-1,/*11*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,14,-1,/*12*/-1,-1,103,-1,-1,-1,103,-1,103,-1,103,-1,-1,/*13*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,9,16,/*14*/-1,-1,17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/*15*/-1,-1,10

16、2,-1,-1,-1,102,-1,102,-1,102,-1,-1,/*16*/-1,-1,-1,-1,-1,-1,106,-1,-1,-1,-1,-1,-1,/*17*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,18,-1,/*18*/-1,-1,101,-1,-1,-1,101,-1,101,-1,101,-1,-1;/* 算術(shù)表達(dá)式的LR分析表 */static int action1107=/* 0*/3,-1,-1,2,-1,-1,1,/* 1*/-1,4,5,-1,-1,ACC,-1,/* 2*/3,-1,-1,2,-1,-1,6,/* 3*/-1,104,104

17、,-1,104,104,-1,/* 4*/3,-1,-1,2,-1,-1,7,/* 5*/3,-1,-1,2,-1,-1,8,/* 6*/-1,4,5,-1,9,-1,-1,/* 7*/-1,101,5,-1,101,101,-1,/* 8*/-1,102,102,-1,102,102,-1,/* 9*/-1,103,103,-1,103,103,-1;/* 布爾表達(dá)式LR分析表 */static int action21611=/* 0*/1,-1,4,-1,5,-1,-1,-1,13,7,8,/* 1*/-1,2,-1,101,101,101,-1,-1,-1,/* 2*/3,-1,-1,

18、-1,-1,-1,-1,-1,-1,-1,-1,/* 3*/-1,-1,-1,102,-1,102,102,102,-1,-1,-1,/* 4*/1,-1,4,-1,5,-1,-1,-1,11,7,8,/* 5*/1,-1,4,-1,5,-1,-1,-1,6,7,8,/* 6*/-1,-1,-1,104,-1,9,10,104,-1,-1,-1,/* 7*/1,-1,4,-1,5,-1,-1,-1,14,7,8,/* 8*/1,-1,4,-1,5,-1,-1,-1,15,7,8,/* 9*/105,-1,105,-1,105,-1,-1,-1,-1,-1,-1,/*10*/107,-1,107

19、,-1,107,-1,-1,-1,-1,-1,-1,/*11*/-1,-1,-1,12,-1,9,10,-1,-1,-1,-1,/*12*/-1,-1,-1,103,-1,103,103,103,-1,-1,-1,/*13*/-1,-1,-1,-1,-1,9,10,ACC,-1,-1,-1,/*14*/-1,-1,-1,106,-1,9,10,106,-1,-1,-1,/*15*/-1,-1,-1,108,-1,9,10,108,-1,-1,-1;/* 從文件讀取一行到緩沖區(qū) */void readline()char ch1;pline=line;ch1=getc(cfile);while(

20、ch1!='n')*pline=ch1;pline+;ch1=getc(cfile);*pline='0'pline=line;/* 從緩沖區(qū)讀取一個(gè)字符 */void readch()if(ch='0')readline();lnum+;ch=*pline;pline+;/* 標(biāo)識符和關(guān)鍵字的識別 */int find(char spel)int ss1=0;int ii=0;while(ss1=0)&&(ii<nlength)if(!strcmp(spel,ntab1ii) ss1=1;ii+;if(ss1=1) ret

21、urn ii-1;else return -1;void identifier()int iii=0,j,k;int ss=0;k=0;dospellingk=ch;k+;readch();while(ch>='a')&&(ch<='z')|(ch>='0')&&(ch<='9');pline-;spellingk='0'while(ss=0)&&(iii<10)if(!strcmp(spelling,reswordsiii.sp) ss

22、=1;iii+;/*關(guān)鍵字匹配*/if(ss=1)bufcount.sy1=reswordsiii-1.sy;elsebufcount.sy1=ident;j=find(spelling);if(j=-1)bufcount.pos=tt1;strcpy(ntab1tt1,spelling);tt1+;nlength+;else bufcount.pos=j;count+;/* 數(shù)字識別 */void number()int ivalue=0;int digit;dodigit=ch-'0'ivalue=ivalue*10+digit;readch();while(ch>=

23、'0')&&(ch<='9');bufcount.sy1=intconst;bufcount.pos=ivalue;count+;pline-;/* 掃描主函數(shù) */void scan()/int i;while(ch!='')switch(ch)case ' ':break;case 'a':case 'b':case 'c':case 'd':case 'e':case 'f':case 'g'

24、:case 'h':case 'i':case 'j':case 'k':case 'l':case 'm':case 'n':case 'o':case 'p':case 'q':case 'r':case 's':case 't':case 'u':case 'v':case 'w':case 'x':case '

25、y':case 'z':identifier();break;case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9':number();break;case '<':readch();if(ch='=')bufcount.pos=0;elseif(ch=

26、'>') bufcount.pos=4;elsebufcount.pos=1;pline-;bufcount.sy1=rop;count+;break;case '>':readch();if(ch='=')bufcount.pos=2;elsebufcount.pos=3;pline-;bufcount.sy1=rop;count+;break;case '(':bufcount.sy1=lparent;count+;break;case ')':bufcount.sy1=rparent;count+

27、;break;case '#':bufcount.sy1=jinghao;count+;break;case '+':bufcount.sy1=plus;count+;break;case '*':bufcount.sy1=times;count+;break;case ':':readch();if(ch='=')bufcount.sy1=becomes;count+;break;case '=':bufcount.sy1=rop;bufcount.pos=5;count+;break;case

28、'':bufcount.sy1=semicolon;count+;break;readch();bufcount.sy1=-1;/*/void readnu()if(pbuf->sy1>=0)n.sy1=pbuf->sy1;n.pos=pbuf->pos;pbuf+;/* 中間變量生成 */int newtemp()newt+;return newt;/* 生成四元式 */int gen(char op1,struct aa arg11,struct aa arg22,int result1)strcpy(fexpnxq.op,op1);fexpnxq.

29、arg1.sy1=arg11.sy1;fexpnxq.arg1.pos=arg11.pos;fexpnxq.arg2.sy1=arg22.sy1;fexpnxq.arg2.pos=arg22.pos;fexpnxq.result=result1;nxq+;return nxq-1;/* 布爾表達(dá)式的匹配 */int merg(int p1,int p2)/拉鏈函數(shù)int p;if(p2=0) return p1;elsep=p2;while(fexpp.result!=0)p=fexpp.result;fexpp.result=p1;return p2;void backpatch(int p

30、,int t)/返填函數(shù)int tempq;int q;q=p;while(q!=0)tempq=fexpq.result;fexpq.result=t;q=tempq;/*/int change1(int chan)switch(chan)case ident:case intconst:return 0;case plus:return 1;case times:return 2;case lparent:return 3;case rparent:return 4;case jinghao:return 5;case tempsy:return 6;int change2(int cha

31、n)switch(chan)case ident:case intconst:return 0;case rop:return 1;case lparent:return 2;case rparent:return 3;case op_not:return 4;case op_and:return 5;case op_or:return 6;case jinghao:return 7;case tempsy:return 8;case EA:return 9;case EO:return 10;/* 賦值語句的分析 */void lrparse1(int num)lr1=action1stac

32、k1sp1change1(n1.sy1);if(lr1=-1)printf("n算數(shù)表達(dá)式或賦值語句出錯(cuò)！n");getchar();exit(0);if(lr1<10)&&(lr1>=0) /移進(jìn)sp1+;stack1sp1=lr1;if(n1.sy1!=tempsy)ssp+;num+;sstackssp.sy1=n1.sy1;sstackssp.pos=n1.pos;n1.sy1=ibufnum.sy1; if(lr1>=100)&&(lr1<105) /歸約switch(lr1)case 100:break;c

33、ase 101:E.pos=newtemp();gen("+",sstackssp-2,sstackssp,E.pos+100);ssp=ssp-2;sstackssp.sy1=tempsy;sstackssp.pos=E.pos;sp1=sp1-3;break;case 103:E.pos=sstackssp-1.pos;ssp=ssp-2;sstackssp.sy1=tempsy;sstackssp.pos=E.pos;sp1=sp1-3;break;case 104:E.pos=sstackssp.pos;sp1-;break;n1.sy1=tempsy;n1.pos

34、=E.pos;lrparse1(num);if(lr1=ACC)&&(stack1sp1=1) gen(":=",sstackssp,oth,ibuf0.pos);ssp=ssp-3;sp1=sp1-3;/* 布爾表達(dá)式的分析 */int lrparse2(int num)int templabel;lr1=action2stack1sp1change2(n1.sy1);if(lr1=-1)if(sign=2) printf("nwhile語句出錯(cuò)！n");if(sign=3) printf("nif語句出錯(cuò)！ n")

35、;getchar();exit(0);if(lr1<16)&&(lr1>=0)sp1+;stack1sp1=lr1;ssp+;sstackssp.sy1=n1.sy1;sstackssp.pos=n1.pos;if(n1.sy1!=tempsy)&&(n1.sy1!=EA)&&(n1.sy1!=EO)num+;n1.sy1=ibufnum.sy1;n1.pos=ibufnum.pos;lrparse2(num);if(lr1>=100)&&(lr1<109)switch(lr1)case 100:break

36、;case 101:ntab2label.tc=nxq;ntab2label.fc=nxq+1;gen("jnz",sstackssp,oth,0);gen("j",oth,oth,0);sp1-;ssp-;label+;n1.sy1=tempsy;break;case 102:ntab2label.tc=nxq;ntab2label.fc=nxq+1;switch(sstackssp-1.pos)case 0:gen("j<=",sstackssp-2,sstackssp,0);break;case 1:gen("j

37、<",sstackssp-2,sstackssp,0);break;case 2:gen("j>=",sstackssp-2,sstackssp,0);break;case 3:gen("j>",sstackssp-2,sstackssp,0);break;case 4:gen("j<>",sstackssp-2,sstackssp,0);break;case 5:gen("j=",sstackssp-2,sstackssp,0);break;gen("j"

38、;,oth,oth,0);ssp=ssp-3;sp1=sp1-3;label+;n1.sy1=tempsy;break;case 103:label=label-1;ssp=ssp-3;sp1=sp1-3;label+;n1.sy1=tempsy;break;case 104:label=label-1;templabel=ntab2label.tc;ntab2label.tc=ntab2label.fc;ntab2label.fc=templabel;ssp=ssp-2;sp1=sp1-2;label+;n1.sy1=tempsy;break;case 105:backpatch(ntab2

39、label-1.tc,nxq);label=label-1;ssp=ssp-2;sp1=sp1-2;label+;n1.sy1=EA;break;case 106:label=label-2;ntab2label.tc=ntab2label+1.tc;ntab2label.fc=merg(ntab2label.fc,ntab2label+1.fc);ssp=ssp-2;sp1=sp1-2;label+;n1.sy1=tempsy;break;case 107:backpatch(ntab2label-1.fc,nxq);label=label-1;ssp=ssp-2;sp1=sp1-2;lab

40、el+;n1.sy1=EO;break;case 108:label=label-2;ntab2label.fc=ntab2label+1.fc;ntab2label.tc=merg(ntab2label.tc,ntab2label+1.tc);ssp=ssp-2;sp1=sp1-2;label+;n1.sy1=tempsy;break;lrparse2(num);if(lr1=ACC) return 1;/* 測試字符是否為表達(dá)式中的值（不包括“；”）*/int test(int value)switch(value)case intconst:case ident:case plus:ca

41、se times:case becomes:case lparent:case rparent:case rop:case op_and:case op_or:case op_not:return 1;default:return 0;/*/int lrparse()int i1=0;int num=0;if(test(n.sy1)if(stacksp.sy1=sy_while) sign=2;elseif(stacksp.sy1=sy_if) sign=3;else sign=1;doibufi1.sy1=n.sy1;ibufi1.pos=n.pos;readnu();i1+;while(t

42、est(n.sy1);ibufi1.sy1=jinghao;ssp=0;if(sign=1)sp1=0;stack1sp1=0;n1.sy1=ibufnum.sy1;n1.pos=ibufnum.pos;lrparse1(num);n.sy1=a;if(sign=2)|(sign=3)pointmark+;labelmarkpointmark.nxq1=nxq;sp1=0;stack1sp1=0;num=0;n1.sy1=ibufnum.sy1;n1.pos=ibufnum.pos;lrparse2(num);labelmarkpointmark.tc1=ntab2label-1.tc;lab

43、elmarkpointmark.fc1=ntab2label-1.tc;backpatch(labelmarkpointmark.tc1,nxq);n.sy1=e;lr=actionstacksp.posn.sy1;printf("stack %d = %dttn= %dttlr= %dn",sp,stacksp.pos,n.sy1,lr);if(lr<19)&&(lr>=0)sp+;stacksp.pos=lr;stacksp.sy1=n.sy1;readnu();lrparse();if(lr<=106)&&(lr>=100)switch(lr)case 100:break;case 10