编译原理课程设计报告-编译程序构造.doc

北华航天工业学院编译原理课程设计课程设计题目： 编译程序构造 作者所在系部： 计算机科学与工程系 作者所在专业： 计算机科学与技术 作者所在班级： 作 者 学 号： 作 者 姓 名 ： 指导教师姓名： 完 成 时 间 ： 2011年6月11日 课程设计任务书课题名称编译原理课程设计完成时间2011.6.10指导教师职称副教授学生姓名班级 总体设计要求总体设计要求： 课程设计内容共给定1个题目，每个学生按照课程设计要求，在规定的两周时间内独立完成。题目： 编译程序构造涉及内容：词法分析、语法分析、语义分析生成中间代码工作内容及时间进度安排第一周、周：设计动员，布置课程设计任务，查阅资料，制定方案，进行程序方案设计。第一周、周2-周5：编写和调试程序第二周、周1-周3：编写和调试程序第二周、周4：整理，撰写设计报告。第二周、周5：验收，提交设计报告，评定成绩。毕业设计成果1、课程设计报告书一份2、源程序清单一份3、成果使用说明书一份内容摘要本次课程设计涉及词法分析、自下而上语法分析程序的实现：slr（1）分析器的实现以及生成中间代码。通过词法分析识别单词和运算符，根据lr分析算法构造slr（1）分析程序，并完成语法分析动作，语法分析调用词法分析，然后查找用slr(1)构造的action表和goto表进行移进或归约，归约时根据不同的产生式进行不同的语义分析，最终输出分析过程，并形成符号表、二元式、四元式文件。本次程序将本次课程所学的词法分析，语法分析和语义分析结合起来，使我们进一步理解正则表达式，自动机以及语法分析方法。同时加深掌握语法制导翻译和中间代码生成，在语法分析的同时进行语义加工并产生出中间代码的方法。关键词：算数表达式和赋值语句，词法分析，语法分析，语义分析，slr(1)目录内容摘要3目录4第1章 绪论51.1、课程设计目的51.2、课程设计意义51.3、课程设计要求51.4、课程设计内容51.4.1、题目51.4.2、内容51.4.3、具体要求61.4.4、程序设计提示61.4.5、测试数据61.4.6、程序扩展要求71.5、课程设计地点与环境7第2章 程序设计内容82.1、设计方案介绍82.1.1、模块划分及模块调用关系82.1.2、程序流程图82.2、slr（1）分析表9第3章 程序详细设计与实现113.1、词法分析113.2、语法分析123.3、语义分析153.4、程序实现结果图15第4章 总结18参考文献19附录20第1章 绪论1.1、课程设计目的编译原理课程设计是编译原理课程必不可少的一个环节，通过课程设计，加深对编译原理的教学内容的了解，以及实现编译原理各部分知识的融合。进而提高学生分析问题、解决问题，从而运用所学知识解决实际问题的能力。1.2、课程设计意义计算机语言之所以能由单一的机器语言发展到现今的数千种高级语言，就是因为有了编译技术，编译技术是计算机科学中发展最迅速，最成熟的技术，它集中了计算机发展的成果与精华，它具有很强的理论性和实践性，本次课设将理论应用到实践，增强学生学习的热情。1.3、课程设计要求1明确课设任务，复习与查阅有关资料2按要求完成课设内容，课设报告要求文字和图工整、思路清楚、正确。3注意增强程序界面的友好性。凡用户输入时，给出足够的提示信息使用户感到方便使用。4注意提高程序的可读性和可理解性：程序中应有适当的注释，变量命名应符合实际含义，程序结构清晰，易于阅读和理解。1.4、课程设计内容1.4.1、题目编译程序构造1.4.2、内容涉及词法分析、自下而上语法分析程序的实现：slr（1）分析器的实现以及生成中间代码。1.4.3、具体要求根据lr分析算法构造slr（1）分析程序，并完成语法分析动作（当需要一个单词时，调用词法分析程序获取），同时完成语义分析生成四元式输出。要求程序具有通用性，改变文法时只需改变程序的数据初值，无需改变程序主体；要求完成一条说明语句、一条算数表达式和赋值语句的翻译，生成中间代码。变量说明语句的文法及相应的语义子程序：.att表示数据类型属性，fill函数表示将单词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; 算数表达式和赋值语句的文法及相应的语义子程序。（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）et e.palce=t.palce;（4）tt(1)*f t.palce=newtemp(); emit(+，t(1).palce，f.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;构造其用于slr(1)分析的识别活前缀的dfa以及action表和goto表。然后编程实现。（关于词法分析部分只需识别出与此文法相关的单词即可（+，*，(，)，id，=）。1.4.4、程序设计提示（1）分析栈设计时可以用一个栈完成，也可以设计三个栈：一个符号栈，一个状态栈，一个语义栈，则归约时，则需要在符号栈中退掉n个符号，在状态栈中退掉n个符号（n为产生式符号个数），语义栈中退掉n个符号对应的语义；（2）终结符表和非终结符表的组织和预测分析程序中相同（将符号对应到一个数字，表示在分析表中对应的下标）。（3）action表中的错误处理：简化的错误处理：当查找action表出现空白时，则当前单词无法移进和规约，可简单的认为当前单词为多余的单词，则抛弃当前单词，读下一单词继续分析。1.4.5、测试数据源文件中数据：int area，r； r=1；area=r*r+r；程序要求输出二元式序列、符号表、语法分析过程、四元式序列。1.4.6、程序扩展要求有能力的同学可将编译程序扩展布尔表达式的分析和四元式生成，布尔表达式的翻译参见教材（胡元义编译原理教程）104105页。1.5、课程设计地点与环境课设地点：计算机系软件实验室课设环境：vc+ 6.0第2章 程序总体设计2.1、设计方案介绍2.1.1、模块划分及模块调用关系单词符号表语法分析器词法分析器字符字符串形式的源程序主函数取下一个单词词图2-1：模块关系图2.1.2、程序流程图读一个字符开始合法字符字母读下一个字符字母或数字填写结构体报错语法分析函数结束nyyn图2-2：词法分析流程图查slr(1)表开始调用词法分析器合法标识符查找标识符符号在终结符表中的下标判断其值0移进0归约接受=100结束ny图2-3：语法分析流程图2.2、slr（1）分析表（1）说明语句的slr(1)表 表2-1 说明语句表状态actiongotointfloat;,id#d s0s3s41911002s5s63s74s8 5r16s97r2r28r3r3 9r4r4acc（2）表达式和赋值语句的slr(1) 表2-2 表达式和赋值语句表状态actiongoto#id=num:+*()faet0s211 acc2s33s9s8s76454s10s115r3r3s12r36r5r5r5r5 7s9s8s761358r8r8r8r89r7r7r7r710r111s9s8s761412s9s8s71513s11s1614r2r2s12r215r4r4r4r416r6r6r6r6第3章 程序详细设计与实现3.1、词法分析首先定义结构体typedef struct /状态栈 int datamax;int top;seqstack1;typedef struct /符号栈 string datamax; int top;seqstack2;struct reserveedword/保留字表结构 string word;char value;reserveedword1maxsize;struct identifer/标识符表结构 char identiname15; char identitype15; int address;identifer1maxsize;struct constant/常量表结构string constantname; string value; int constantaddress;constant1maxsize;词法分析主要函数结构： void initscanner() /该函数用于用c语言当中常见的关键字初始化保留表 void isalpha(char s) /用于判断读入的字符是不是字母 void isnumber(char s) /用于判断读入的字符是不是数字 void isother(char s) /判断除数字与字母之外的其他字符 void lexscan() /用于循环从程序中读入字符并判断应调用那个判断函数字符 void output(int i,int j,char ss15) /输出二元式 本模块程序的伪代码如下：打开文件infile.open(input.txt,ios:in); if(!infile) cerr读取的文件打开失败!=a)&(ch=a)&(ch=0)&(ch=9) isnumber(ch) output； else isother(ch) output； 关闭文件infile.close(); 词法分析器中从源文件读出一个单词，判断其类型是关键字、标识符还是普通符号，根据其类型为结构体各项赋值，并将其传给语法分析函数。3.2、语法分析由于说明语句与算术表达式和赋值语句所使用的是不同的文法，所以两者的action表和goto表也不一样，本次课设采用二维数组存放action表和goto表信息，其中移进用大于0的数表示，归约用小于0的数表示，成功用100表示(acc),其他处用0表示，查表时遇到相应的数进行相应的操作。其中，归约部分需要根据其产生式的信息进行，所以程序中有如下定义：string v18=int,float,;,id,#,d,s; /存放说明文法当中的字符string v213=#,id,=,num,;,+,*,(,),f,a,e,t;/存放算本文法当中的字符根据状态转换图(dfa)构造slr(1)分析表：其中说明文法和算术文法分别构造，同时在每个表当中既有action表 又有goto表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,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, 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;语法分析当中各个函数说明及伪代码：void action1(int i,string s) /通过词法分析传过来的值判断移进动作三个栈(状态栈,符号栈,语义栈)应该读入哪些值。void action2(int i,string s) /同action1只是表示算术文法int address(string m,int i,string x) /获得在分析表中的列下标void goto1(int i,string s) /通过判断栈中的元素，来判断用那个产生式来进行规约void goto2(int i,string s) /同goto1void slr1() /对说明文法进行语法分析void slr1() /对算术文法进行语法分析 伪代码如下： 先判断是说明文法还是算术文法 if(说明文法) slr1()push_seq1(s1,0); push_seq2(s2,#);push_seq2(s3,_);while(1) j=address(v1,8,get1); top_seq1(s1,top); j=analysis_table1topj; if(jd;归约 else if(j=-2)用d-int id归约 else if(j=-3)用d-float id归约 else if(j=-4)用d-d,id归约 else if(j0) action1(top,get1); else slr2() push_seq1(s1,0); push_seq2(s2,#); push_seq2(s3,_); while(1) j=address(v2,13,get1); j=analysis_table2topj; if(j0) action2(top,get1); else if(jid=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-id归约 else if(j=-8)用f-num归约 3.3、语义分析一个程序经过词法分析，语法分析之后，表明该院程序在书写上是正确的，但是未对程序的内部逻辑语义进行分析，接下来是进行语义分析。语义分析当中各个函数说明： void print(string s) /打印四元式str1,string str2,string str3,string str4) /产生四元式string newtemp() /产生一个新的临时变量 3.4、程序实现结果图图3-4 语义分析结果图图3-5二元式图3-6符号表图3-7四元式第4章 总结为期两周的编译原理课程设计结束了，整个过程当中，从构思、编程到调试、运行，我付出了许多，但也收获了许多。课设初期构思阶段，对整体结构有比较清晰的设计。程序编写过程中，对在何处写二元式文件比较模糊，如果在词法分析器中写二元式，对于说明语句会遇到标识符不能顺利获取其在标识符表中下标的问题，后来改为在语法分析器中写二元式，解决了此问题。程序调试运行后期，对于说明语句编译完成以后接着进行算术表达式和赋值语句连接编译，中间过渡不知如何处理，后来设置了一个全局变量，在词法分析程序中判断是说明语句将其值置为1，末尾遇到回车且此全局变量为1，则自动在末尾添加“#”并在读一个字符，这样就解决了读文件指针一直指向回车的问题，使得两条语句能过连续编译。虽然完成了课设任务，但是程序中还存在了许多不足，如：遇到非法字符或是遇到查表值为-1时，程序就自动结束，和程序中没有设计统计出错个数。此次课程设计，使我对编译原理课程中词法分析、语法分析、语义分析有了更深入的了解。虽然这次课设时间有点紧，但我从这次编程过程中加深了对课本知识的理解，灵活运用了各个分析器，熟悉了分析器的原理，透彻的掌握了“编译的原理”，是对编译原理这门课的比较理想的总结。参考文献1：胡元义，邓亚玲，胡英著。编译原理教程。西安：西安电子科技大学出版社，20022：周霭如，林伟健编著。c+程序设计基础。北京：电子工业出版社，20053：刘坚编著。编译原理基础。编译原理实践教程。西安：西安电子科技大学出版社，20024:崔冬华，冯秀芳，范辉编著。编译原理简明教程。北京：电子工业出版社，2002 附录3#include#includeusing 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,#,d,s;string v213=#,id,=,num,;,+,*,(,),f,a,e,t;string e=,e1=,t=,t1=,f=;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,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, 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 /状态栈 int datamax;int top;seqstack1;typedef struct /符号栈 string datamax;int top;seqstack2;struct reserveedword/保留字表结构string word;char value;reserveedword1maxsize;struct identifer/标识符表结构char identiname15;char identitype15;int address;identifer1maxsize;struct constant/常量表结构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 *);void scanner();void change(char c,string str) int len=str.length();for(int num=0;numlen;num+)cnum=strnum;clen=0;seqstack1 *init_seqstack1()seqstack1 *s;s=new seqstack1;if(!s)cout空间不足！top=-1;return s; int empty_seq1(seqstack1 *s)if(s-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_seq1(s)coutdatas-top;seqstack2 *init_seqstack2()seqstack2 *s;s=new seqstack2;if(!s)cout空间不足！top=-1;return s; int empty_seq2(seqstack2 *s)if(s-top=-1) return 1;else return 0;int push_seq2(seqstack2 *s,string 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;itop;i+)printf(%d,s-datai);void out_seq2(seqstack2 *s) char ch15;for(int i=0;itop;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;in;i+)pop_seq1(s1,&m);pop_seq2(s2,&s); pop_seq2(s3,&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;elsereturn 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; coutn生成的标识符表为：; coutntnamettypetvaluetaddress; for(int i=0;im;i+) printf(n%dt%st%s,i,identifer1i.identiname,identifer1i.identitype); coutn生成的常数表为：; coutntvaluettypetnametaddress; for(int j=0;jn;j+) change(str1,constant1j.constantname); change(str2,constant1j.value); printf(n%dt%st%s,j,str1,str2); int judge(string m,int i,string x) for(int j=0;ji;j+) if(screamp1(x,mj) return 1; return 0;int address(string m,int i,string x) for(int j=0;ji;j+) if(screamp1(x,mj) return j;void print(string s)coutn产生的四元式为endl;char chmax; for(int i=0;icount;i+)change(ch,si);printf(%s,ch);coutendl;coutendl;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 newtemp()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分析成功！endl; cout*endl;else printf(action%d,%s=s%