FOR循环语句的翻译程序设计.doc

课程设计任务书学生姓名： 专业班级： 软件0406班 指导教师： 工作单位：计算机科学与技术学院 题目: FOR循环语句的翻译程序设计（简单优先法、输出三地址表示）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1） 写出符合给定的语法分析方法的文法及属性文法。（2） 完成题目要求的中间代码三地址表示的描述。（3） 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（5） 设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：1 系统描述（问题域描述）；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 给出中间代码形式的描述及中间代码序列的结构设计；5 简要的分析与概要设计；6 详细的算法描述（流程图或伪代码）；7 给出软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9 参考文献（按公开发表的规范书写）。时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试及测试。周5：撰写课程设计报告。设计验收安排：16周的星期五第1节课开始到实验室进行上机验收。设计报告书收取时间：17周的星期一上午10点。指导教师签名： 2007年 5 月 20 日系主任（或责任教师）签名： 2007年 5 月 20 日FOR循环语句的翻译程序设计（简单优先法、输出三地址表示）1 系统描述11目的通过设计、编制、调试一个for循环语句的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。12 设计内容对循环语句：for表达式；循环条件；表达式赋值语句（1） 设计符合自身语法分析方法要求的文法和属性文法。（2） 设计语法分析表（简单优先级表）。（3） 对源文件进行词法和语法分析同时对源文件进行语义处理。（4） 设计中间代码格式并输出三地址中间代码到文件中保存。（5） 对源文件中的错误进行输出。 13 系统体系结构描述 本系统为管道过滤器的体系结构风格，系统由两大构件组成：1）词法分析程序2）语法分析程序系统中包含一个连接件：文件处理程序131 系统结构图词法分析语法分析中间代码源文件文件管理说明：系统输入源文件后，词法分析程序对文件进行处理输出中间代码（单词序列）文件管理中间件将上步产生的中间代码作为输入传递给语法分析程序，通过语法分析构件的处理和语义处理最终产生中间代码（语法分析）。132 词法分析描述单词归类输出中间代码源文件读取一个字符字符类型判断说明：对输入的源文件进行处理，逐个读如字符，将字符流进行合拢并进行判断归类，将单词和其类型进行输入保存，得到了中间代码（词法）。133 语法分析描述词法分析中间代码语法分析错误处理语法分析中间代码说明：接受由词法分析得到的中间代码（词法），进行语法分析和语法制导翻译，最后得到3地址代码即中间代码（语法）。2.文法及属性文法的描述： 21 文法：文法是用于描述语言的语法结构的形式规则（即语法规则）。这些规则必须是准确的、易于理解的以及有相当强的描述能力。由这种规则所产生的程序语言应有利于句子分析和翻译，而且，最好能通过这些规则自动产生有效的语法分析程序。FOR循环语句的文法如下所示：0S for(B;A;B)B1B id:=C2C (C+C)3C (C*C)4C (-C)5C (C)6C id7C n8A (A or A)9A (A and A)10A (not A)11A (A)12A id rop id13A true14A false2.2 属性文法： 属性文法是在上下文无关文法的基础上，为每个文法符号（终结符或者非终结符）配备若干相关的“值”（与文法符号相关的属性）。在一个属性文法中，对应于每个产生式Aa都有一套与之相关联的语义规则，每规则的形式为：b:=f(c1,c2,，ck)其中f是一个函数，而且或者b是A的一个综合属性并且c1,c2,，ck是产生式右边文法符号的属性或者非终结符既可有综合属性也可有继属性，文法开始符号的所有继承属性作为属性计算前的初始值。属性文法为：1-p:=lookup();if(p!=NULL)emit(:=,C.place,_,) else error2-C.place=newtemp;emit(+,C1.place,C2.place,C.place)3-C.place=newtemp;emit(*,C1.place,C2.place,C.place)4-C.place=newtemp;C.value=-C.value5-C.place=newtemp;C.place=C1.place6-p:=lookup();if(p!=NULL) C.place=p;else error7-p:=lookup();if(p!=NULL) C.place=p;else error8-backpath(A.false,A.codebegin);A.true:=merge(A.true,A.true);A.false=A.false9-backpath(A.true,A.codebegin);A.true=A.true;A.false:=merge(A.false,A.false); 10-(A.true=A.false;A.false=A.true)11-A.place=A1.place12-A.true=nextstat;A.codebegin=nextstat;A.false=nextstat+1;emit(if A1.place rop A2.place goto -) emit(goto -)13-A.place=newtemp14-A.place=newtemp3 语法分析方法描述及分析表设计3.1 语法分析为实现简单优先算法,可以使用工作栈.用以寄存操作数或运算结果.算法的基本思想是: (1) 置初始状态：S(1):=#, i:=1, j:=1(2) 若 S(i)与T(j)无任何关系，则出错停机(3) 若 S(i)= T(j)或S(i)T(j)，则把T(j)送入S栈中，读下一符，转（2）。(4) 若S(i)T(j)，则从S栈顶开始往前栈串Sj1 ,Sj1+1,Si其中 Sj1为第一个使 Sj1-1Sj1 ,然后用Sj1,Sj1+1,Si去查生产式表，若查到有相同右部的产生式即USj1,Sj1+1,Si，则从栈中退掉子串Sj1,Sj1+1,Si，并把U进栈；然后转(2)。若查不到转出错处理。(5) 若T(j)=#,并且S栈的内容为# Z(Z为文法开始符号)则正确停机。否则，出错停机。3.2 语法分析表设计SBACfor(;)+*-idorandnottruefalseropn=#SB=A=C=for= (=+=*=-=or=and=not=falserop=n=#(注解：ab表示a的优先级大于b，a=b表示a的优先级等于b)4.中间代码形式的描述及中间代码结构41 词法分析中间代码设计词法分析的中间代码有两个域来构成的：单词域和类型域。单词域：源文件中的单词符号串。类型域：是一个二进制代码的整形表示，它由八位组成，前三位表示单词类型，后八位表是它在相应表中的位置序号。例如：void$30 它的意思是单词void的类型是二进制码00011110，其中前3位000代表它是关键字，后5位代表它在关键字表的第30个位置上。42 语法分析及语义分析的中间代码设计中间代码是3地址形式来表示，即4元式。4元式由5个域构成：中间代码标号，操作符域，操作数1，操作数2，目的操作数操作符：操作符（=，+，-，*，/）操作数1，操作数2目的操作数：用来存放操作值的变量例如：0: j:=12表示第0条中间代码为，把12放到变量j中又例如：7: j i 0 9 8: j 12 表示当i0时，跳转到9号中间代码，否则跳转到12号中间代码。5.简要分析与概要设计51 系统分析5.1.1 词法分析输入源程序文本，对输入串进行预处理，然后从左至右逐个字符地对源程序进行扫（超前搜索法），产生一个一个的单词符号，在状态转换图的基础上，把作为字符串源程序改造成为单词符号串。源程序文件字符的分离单词的判断查找相应的表单词的类型的判断调用不同类型的单词处理函数进行单词的处理产生类型码将中间单词和其类型码写入文件处理完毕回收各种文件资源（关闭文件）5.1.2 语法分析在完成词法分析的基础上对FOR循环语句进行语法分析，对符号栈分别进行移进，规约（采用简单优先分析方法,自上而下进行规约），接受和出错处理四步操作，从而分析判定程序的语法结构是否符合语法规则。5.1.3 语义分析以及输出三地址表示当在栈中找到句柄后，进行规约时，根据相应产生式对应的语义子程序进行语法制导翻译（在语法的分析过程中，随着分析的步步进展，根据每一个产生式所对应的语义子程序进行翻译的方法）.三地址指令很类似于四元式,这种中间表示通常称为三地址代码,三个地址即是两个为运算对象,一个是运算结果.5.1.4 简单优先分析中的出错处理若在栈顶终结符号与下一输入符号之间不存在任何优先关系;若找到某一句柄(素短语),但不存在任一产生式,其右部为次句柄.若有无穷多个符号序列可以规约,则可使用一个一般的子程序去处理,以确定哪一个产生式右部与该规约序列的满足一定的界限.若存在这样的产生式,则假定以这个产生式为依据,并给出具体的错误信息.否则,可给出类似“该语句有错”这样的一般信息。5.2 概要设计521 系统总体描述源文件词法分析中间代码语法分析中间代码出错处理522 系统接口声明1) int lookupsimpletable(int row,int col,SimpleTable* simpletable,int size)2) int getId(char ch,char *simple_signs,int size)3) char getTop(sysm_stack* sysm)4) char pop(sysm_stack* sysm)5) void push(sysm_stack* sysm,char id)6) int search(char *name,sysmTable* table)7) void enter(int sysmId,int type)8) sysmItem* findItem(int sysmId)9) char * findByplace(int place)10) sysmItem* newSysmItem(int type,char * sysm)11) void toChar(char *ch,string s)12) int match(char * s,char &ch,SimpleFormula* simpleformula,int size)13) int searchThreeAddress(int id)14) void backpatch(int * p,int t,int size)15) void mergeList(int *p1,int *p2,int* p3,int size)16) void emit(char* opt,int v1,int v2,int v3,int id)17) int guiyue(SimpleTable* simpletable,SimpleFormula* simpleformula,char *simple_signs,int size1,int size2,int size3)18) void readLineAndAnalysis(ifstream& in,ofstream& out,sysmTable* table) 6 详细的算法描述 61 词法分析1）void binarydeal(A& ma,A sequence,int type)词法分析中的单词码处理函数参数说明：union A /一个联合结构，它里面存放一个unsigned类型的8位变量unsigned a:8;A()a=0; sequence：单词位置序号type:单词类型算法流程描述：根据单词的类型参数type,用一个中间8位unsigned类型标志数左移5位后和sequence进行安位或操作，得到了单词类型码。并且把这个码传递给参数ma .62 语法分析1)void backpatch(int * p,int t,int size)拉链回填函数，对p链进行回填。参数说明：p：链首地址指针 t:回填的跳转到的3地址代码序号 size：链的长度算法流程说明：对传递进来的出口链进行回填操作算法代码： int i=0;for(;isize;i+)if(pi!=-1)int tt=searchThreeAddress(pi);threeaddresstt.v3=t;elsebreak; 2）void emit(char* opt,int v1,int v2,int v3,int id)对存放3地址中间代码的结构数组进行写入参数说明：opt:操作符字符串指针 V1：操作数1 V2：操作数2 V2：操作数3 Id：三地址中间代码序号算法流程说明：首先对存放的结构数组中的每个元素的操作符域进行判断，如果为空则存入参数中传递进来的3地址值，如果不为空则对下一个元素进行判断。算法代码： int i=0; while(i20) if(strcmp(threeaddressi.opt,)!=0) i+; else break; if(i20) strcpy(threeaddressi.opt,opt); threeaddressi.v1=v1; threeaddressi.v2=v2; threeaddressi.v3=v3; threeaddressi.id=id; 3）void mergeList(int *p1,int *p2,int* p3,int size)把p1和p2复制拷贝到p3链中参数说明：p1：链1指针 P2：链2指针 P3：得到的结构链指针算法流程说明：将传递进来的真或假链进行归并，将结果放入另外一个链表中算法代码： int j=copyList(p2,p3,size); for(int i=0;isize;i+) if(p1i!=-1) p3j=p1i; j+; else break;7 系统测试结果分析 71系统测试用例11）测试输入源代码文件如下：1.txtvoid main()int i,a,b;float j;for(i=0;ia;i=(i+1);)i=(a+b);return 0;2)运行界面3）运行结果（中间代码）词法分析中间代码：void$1 main$1 ($3 )$3 $3 int$1 i$2 ,$3 a$2 ,$3 b$2 ;$3 float$1 j$2 ;$3 for$1 ($3i$2 =$4 0$5 ;$3 i$2 $4 a$2 ;$3 i$2 =$4 ($3 i$2 +$4 1$5 )$3 ;$3 )$3 i$2 =$4 ($3 a$2 +$4 b$2 )$3 ;$3 return$1 0$5 ;$3 $3语法分析几语义分析的3地址（4元式）代码：(0) 10:=9(1) 1:=10(2) j -1 -1 3(3) 1 3 10(4) j -1 -1 15(5) 14:=1(6) 16:=15(7) 17:=14+16(8) 1:=17(9) j -1 -1 3(10) 19:=3(11) 20:=5(12) 21:=19+20(13) 1:=21(14) j -1 -1 572 系统测试用例21）测试输入源代码文件如下：2.txtvoid main()int i,a,b;float j;for(i=0;ia;i=(i+1;)i=(a+b);return 0;2)运行界面3）运行结果（中间代码）词法分析中间代码：void$1 main$1 ($3 )$3 $3 int$1 i$2 ,$3 a$2 ,$3 b$2 ;$3 float$1 j$2 ;$3 for$1 ($3i$2 =$4 0$5 ;$3 i$2 $4 a$2 ;$3 i$2 =$4 ($3 i$2 +$4 1$5 ;$3 )$3 i$2 =$4 ($3 a$2 +$4 b$2 )$3 ;$3 return$1 0$5 ;$3 $3语法分析几语义分析的3地址（4元式）代码：输出3地址4元式为空，因为源程序的第4行有语法错误。73 系统测试用例31）测试输入源代码文件如下：3.txtvoid main()int i,a,b;float j;for(h=0;ia;i=(i+1;)i=(a+b);return 0;2)运行界面3）运行结果（中间代码）词法分析中间代码：void$1 main$1 ($3 )$3 $3 int$1 i$2 ,$3 a$2 ,$3 b$2 ;$3 float$1 j$2 ;$3 for$1 ($3h$2 =$4 0$5 ;$3 i$2 $4 a$2 ;$3 i$2 =$4 ($3 i$2 +$4 1$5 ;$3 )$3 i$2 =$4 ($3 a$2 +$4 b$2 )$3 ;$3 return$1 0$5 ;$3 $3语法分析几语义分析的3地址（4元式）代码：输出3地址4元式为空，因为源程序的第4行有语法错误。研制报告1 研制过程作为一名计算机软件工程专业大三的学生，我觉得能做类似的课程设计是十分有意义。它对我们的能力的提升很有好处。在已度过的大三的时间里我们大多数接触的是专业基础课。我们在课堂上掌握的仅仅是专业基础课的理论面，如何把我们所学到的专业基础理论运用到实践中？课程设计为我们提供了良好的平台。课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程.回顾起此次while循环课程设计，我感慨颇多，的确，从考察到定稿，从理论到实践，在这一个多星期的日子里，可以说是苦多于甜，但是我学到了很多很多的的东西，不仅巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。在本次课程设计中，我先是具体了解了各种文法，然后进行了自己的文法的设计，将二者结合起来，作出一个自己的文法，然后我开始设计一些基本的构件并描述出它们的具体接口功能，接口设计好之后，下一步便是进行类接口几实现了，最关键的一步是总控程序的设计，对其他构件类的调用。在以上功能完成之后，我们便开始遍程了。最后，进行调试。至此，我的while语法分析及翻译系统出炉了，余下的工作便是进一步的完善系统功能。2 设计评价对于自己的劳动