编译原理课程设计---小型程序设计语言编译器的设计与实现

1、 课 程 设 计 报 告课程设计名称： 编译技术 系 ： 三 系 学生姓名： 王 辉 班 级： 09软件（1）班 学 号： 20090307141 成 绩： 指导教师： 石 鲁 生 开课时间： 2011-2012 学年 2 学期目录一设计题目1二主要内容1三具体要求1四进度安排2五成绩评定2六设计思路31.词法分析3（1）单词符号及种别表32.SLR的分析表：41). 算术表达式的SLR(1)分析表：42). 布尔表达式的SLR分析表：43). 程序语句的SLR分析表：6七源程序及运行结果71）源代码：72）运行截图28八心得体会311编译原理课程设计报告一设计题目小型程序设计语言编译器的设计

2、与实现二主要内容 自定义一种简单的小型高机程序设计语言，采用任意一种编程语言和编程工具设计并实现其编译器，展示编译系统中词法分析和语法分析的全过程。三具体要求1、对单词的构词规则有明确的定义；2、编写的词法分析程序能够正确识别源程序中的单词符号；3、识别出的单词以<种别码，值>的二元式形式保存在符号表中并输出；4、构造出程序设计语言各语法单位的SLR分析表；(其他分析表亦可)5、能够对输入的源程序做出正确的语法分析并输出清晰的结果；6、高级语言的规模不易过大，注重编译器内核的设计，对于界面无要求；7、课程设计报告中应对所自定义高级语言进行简单描述，对编译器的设计进行简单的需求分析，

3、给出设计说明和程序结构框架，阐明设计思路、用到的原理和方法。8、不可更改课程设计报告中已有的字体和格式，课程设计报告中新加入内容，汉字采用宋体五号字，英文字符和数字采用Times New Roman五号字。9、课程设计报告中的运行结果应以程序运行截图形式出现。10、程序源代码以邮件名称：“班级学号姓名”发送至指定邮箱：sqckcsj08四进度安排序号内 容时间（天）1布置题目、查找资料12概要设计13详细设计34调试分析15测试结果0.56总结和完成设计报告1合 计7.5五成绩评定1.考核方法：通过现场考勤、检查源程序和批改课程设计报告相结合的方式考察学生的动手能力，独立分析解决问题的能力和创

4、新精神，并根据学生的学习态度综合考评。2.成绩评定：成绩分优、良、中、及格和不及格五等。六设计思路1.词法分析（1）单词符号及种别表符号种别编码说明sy_if0保留字 ifsy_then1保留字 thensy_else2保留字 elsesy_while3保留字 whliesy_begin4保留字 beginsy_do5保留字 dosy_end6保留字 enda7赋值语句semicolon8 “；”e9布尔表达式jinghao10“#”S11语句L12复合语句tempsy15临时变量EA18B andEO19B orplus34“+”times36“*”becomes38“：=”op_and39

5、“and”op_or40“or”op_not41“not”rop42关系运算符lparent48“（”rparent49“）”ident56变量intconst57整常量2.SLR的分析表：1). 算术表达式的SLR(1)分析表：算数表达式文法GE如下：E->E+E|E*E|(E)|i将文法GE拓广为文法GE:(0) SE(1) EE+E(2) EE*E(3) E(E)(4) Ei由此得到算数表达式的SLR（1）分析表如下： 状态 ACTIONGOTOi+*()#E0s3s211s4s5acc2s3s263r4r4r4r44s3s275s3s286s4s5s97r1s5r1r18r2r2

6、r2r29r3r3r3r32). 布尔表达式的SLR分析表：布尔表达式的文法如下：B->BB|BB|¬B|I rop i|i为了便于语法分析时加工处理，我们将上述文法改为文法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由此得到布尔表达式的SLR（1）分析表如下：状态 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由于在编译程序设计与视线中，我们是将赋值语句与算数表达式归为一类处理的，故在此将赋值语句仅看作是程序语句文法中一个终结符a，将布尔表达式B也看作为终结符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）分析表如下：状态 ACTION GOTOifthenelsewhilebegindoenda;e#SL0s2s3s4s511acc2s63s74s2s3s4s5985r4r4r4r46s107s118s129r5s1310s2s3s4s51411s2s3s4s51512r3r3r3r313s2s3s4s591614s1715r2r2r2r216r617s2s3s4s

9、51818r1r1r1r1七源程序及运行结果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;/* 算术表达式的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;/* 布尔表达式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;/* 从文件读取一行到缓冲区 */void readline()char ch1;pline=line;ch1=getc(cfile);while(

20、ch1!='n')*pline=ch1;pline+;ch1=getc(cfile);*pline='0'pline=line;/* 从缓冲区读取一个字符 */void readch()if(ch='0')readline();lnum+;ch=*pline;pline+;/* 标识符和关键字的识别 */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+;/*关键字匹配*/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+;/* 数字识别 */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-;/* 扫描主函数 */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;/* 布尔表达式的匹配 */int merg(int p1,int p2)/拉链函数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)/返填函数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算数表达式或赋值语句出错！n");getchar();exit(0);if(lr1<10)&&(lr1>=0) /移进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;/* 布尔表达式的分析 */int lrparse2(int num)int templabel;lr1=action2stack1sp1change2(n1.sy1);if(lr1=-1)if(sign=2) printf("nwhile语句出错！n");if(sign=3) printf("nif语句出错！ 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;/* 测试字符是否为表达式中的值（不包括“；”）*/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