将词法、语法、代码生成等实验组合成一个大的编译程序.doc

郑州轻工业学院课程设计说明书题目： 将词法、语法、代码生成等实验组合成一个大实验 姓 名： 院 （系）： 计算机与通信工程学院 专业班级： 计算机科学与技术10-01 学 号： 指导教师： 马吉明 成 绩： 时间： 2013年6月 17 日至 2013 年 6 月21日郑州轻工业学院课 程 设 计 任 务 书题目 将词法、语法、代码生成等实验组合成一个大实验 专业、班级 计算机科学与技术10-01 学号 姓名 主要内容 自选一种常见高级语言为背景，对其进行简化例如只包括整型常数和其四则运算以及相应的赋值语句，转移语句，条件语句和最简单的输入输出语句等编制一个包括必要处理阶段（词法分析、语法分析、语义分析、代码生成）简化又完整的编译程序。基本要求（1）写出符合给定的语法分析方法的文法及属性文法。（2）完成题目要求的中间代码四元式的描述。（3）写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。主要参考资料程序设计语言编译原理陈火旺编著 国防工业出版社编译原理吕映芝 张素琴 蒋维杜编著 清华大学出版社完 成 期 限： 2013 年 6 月 21日指导教师签名： 课程负责人签名： 年 月 日46编译原理目录1绪论21.1设计目的21.2设计要求21.2.1 算法过程21.2.2主流程图21.3设计内容31.3.1题目31.3.2内容32总体设计32.1算法描述42.2函数说明和数据结构43详细设计与实现53.1词法分析53.2语法分析73.3代码生成器93.4 结果94参考文献115心得体会116附录代码111绪论1.1设计目的编译原理是理论与实践并重的课程，而其实验课要综合运用所学的多门课程的内容，用来完成一个小型编译程序。从而巩固和加强对词法分析、语法分析、语义分析、代码生成和报错处理等理论的认识和理解；培养学生对完整系统的独立分析和设计的能力，进一步培养学生的独立编程能力。1.2设计要求1.2.1 算法过程 词法分析程序 语法分析程序 语义分析程序 编译器。不断完善，不断改进。渐变的过程。1.2.2主流程图 1.3设计内容 1.3.1题目 将词法、语法、代码生成等实验组合成一个大实验 1.3.2内容涉及词法分析、自下而上语法分析程序的实现：SLR（1）分析器的实现以及生成中间代码。 2总体设计 2.1算法描述语法分析阶段的基本任务是将词法分析阶段产生的二元组作为输入，根据语言的语法规则，识别出各种语法成分，并判断该单词符号序列是否是该语言的一个句子。在语法分析阶段，采用自上而下的递归下降分析法，根据递归下降分析函数编写规则来编写相应的函数，在各个函数的分析过程中调用词法分析程序中的扫描程序，发出“取下一个单词符号”的命令，以取得下一个单词符号的语法分析。词法分析和语法分析的整体设计思想可由以下图示表示： 语法分析是在词法分析的基础上加上判断是否符合语法规则的语句。语法分析的基本任务是使用词法分析的结果，使用递归下降算法分析是否符合语法规则，如果符合，则输出“分析成功”，若果不符合，则输出“分析失败”。2.2函数说明和数据结构在main函数调用e()函数，如果调用之后返回时,如果(flagstemp=0)&is_right)为真，就输出“分析成功”，否则输出“分析失败”。其中is_right为设定的标志，初值为1，如果在调用子函数的过程中如果有错误，则置is_right为0。e函数: 调用t函数，调用f函数, 调用p函数,返回后看是否是+或-，如果是，则调用 e1函数，再调用e2函数，如果不是，进行出错处理，置is_right为0。e1函数：判断是不是”+”或者“-” 如果是，调用f函数，如果不是，进行出错处理，置is_right为0。t函数: 调用f函数, 调用p函数,返回后看是否是*或/，如果是，则调用t1函数，再调用t2函数，如果不是，进行出错处理，置is_right为0。t1函数：判断是不是”*”或者“/” 如果是，调用f函数，如果不是，进行出错处理，置is_right为0。f函数：调用p函数，f1函数。f1函数：判断是不是”,如果是，调用f函数，如果不是，进行出错处理，置is_right为0。p函数: 检查是否标识符，如果是，调用f1函数，如果不是，检查是否是数值，如果是，调用f1函数，如果不是，检查是否是(，如果不是，进行出错处理，置is_right为0。如果是，调用e函数，返回后检查是否是),如果不是，进行出错处理，置is_right为0。如果是，调用f1函数，返回。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表示，查表时遇到相应的数进行相应的操作。根据状态转换图(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;3.3代码生成器 算法描述：下面以简单算术表达式语句的翻译为例详细说明算法设计。实现简单算术表达式的翻译一般采取下列步骤： 分析文法。 设置一系列语义变量，定义语义过程，语义函数。 设计算术表达式的递归下降子程序的程序分析算法。 函数说明和数据结构：Strn用来存放临时变量的序号。temp用来存放数组的下表，在主程序中语法分析结束后，置0.定义函数newtemp()用于门生一个新的临时变量的名字，具体实现时每产生一个T，就及时送到符号表中，也可以不进符号表，直接将单词值用整数码表示。定义函数siyuan（）,输出一个四元式。定义函数ye() 进行中间代码生成3.4 结果4参考文献程序设计语言编译原理陈火旺编著 国防工业出版社编译原理吕映芝 张素琴 蒋维杜编著 清华大学出版社编译原理Alfred V.Aheo等 李建中译 机械工业出版社 5心得体会刚拿到课设题目的时候，感觉很难，没有头绪。虽然之前实验时候，词法分析程序和语法分析程序的代码都是自己一个一个敲的。但是后来发现，更难的东西在后边。接下来熟悉了一下原先写的代码，然后开始继续后边的部分。个人认为这次课设的机会非常宝贵，加深了我对编译器处理语言的过程的理解。我想，作为学计算机的学生，不应该只会用Java，或者C+，或者C#。一门高级语言其实学起来是很不容易的，而在校期间，这些计算机基础课程一定要学好！才能为将来打好基础。6附录代码#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%d状态%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;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); if(top=100) addr-; return; j=analysis_table1topj; if(jD;归约); pop(2); top_seq1(s1,top); goto1(top,S); push_seq2(s3,_); else if(j=-2) out_seq1(s1);printf(tt);out_seq2(s2);printf(tt);out_seq2(s3);printf(tt用D-int id归约); change(str1,int); for(int k=0;kfloat id归约); change(str1,float); for(int k=0;kD,id归约); for(int k=0;k0) 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分析成功！endl;cout*0) action2(top,get1); else if(jid=E;归约); pop(4); top_seq1(s1,top); goto2(top,A); for(int i=0;iE+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用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(); emit(*,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);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;inum归约); pop(1); top_seq1(s1,top); goto2(top,F); for(int i=0;in;i+) if(screamp1(constant1i.constantname,pnum-1)