报告——DOWHILE循环语句的翻译程序设计（LL（1）法、输出三地址表示）.doc

武汉理工大学编译原理课程设计说明书学 号： 0120910340223课 程 设 计题 目DO-WHILE循环语句的翻译程序设计（LL（1）法、输出三地址表示）学 院计算机科学与技术学院专 业计算机科学与技术专业班 级姓 名指导教师2012年01月07日课程设计任务书学生姓名： 专业班级： 指导教师： 工作单位： 计算机科学与技术学院 题目: DO-WHILE循环语句的翻译程序设计（LL（1）法、输出三地址表示）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1） 写出符合给定的语法分析方法的文法及属性文法。（2） 完成题目要求的中间代码三地址表示的描述。（3） 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（5） 设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：1 系统描述（问题域描述）；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5 编译系统的概要设计；6 详细的算法描述（流程图或伪代码）；7 软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9 参考文献（按公开发表的规范书写）。时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试及测试。周5：撰写课程设计报告。设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次周星期一上午10点。指导教师签名： 2011年 11月 18日系主任（或责任教师）签名： 2011年 11月 18日DO-WHILE循环语句的翻译程序设计（LL（1）方法、输出三地址表示）1. 系统描述1.1目的通过设计、编制、生成、调试一个do-while循环语句的语法及语义分析程序，以加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。1.2 设计内容对循环语句：do 赋值语句 while 1) 设计符合自身语法分析方法要求的文法和属性文法（LL(1)语法）。2) 设计LR分析法相关的语法分析表（LL(1)分析表）。3) 设计中间代码格式（三地址中间代码）。4) 对源文件进行词法和语法分析的同时进行语义处理（语法制导分析）。5) 对源文件中的错误进行输出。 1.3 系统体系结构描述 本系统为子模块的体系结构风格，系统由两大模块组成：1) 词法分析模块2) 语法分析模块（调用语义分析模块）1.3.1 系统结构图 源代码词法分析语法分析语义分析中间代码说明：系统读入源文件后，词法分析模块对文件进行处理并输出单词序列到名字表（C+ vector 类型，存储在内存中），随后的语法分析模块将名字表内容作为输入，通过语法制导分析方法调用语义分析模块最终生成中间代码。1.3.2 词法分析模块源文件读取一个字符判断字符类型单词归类（关键字、标识符）存入名字表说明：对输入的源文件进行处理，逐个读入字符，将字符流进行合并并进行判断归类，将单词和其类型输入名字表并保存。1.3.3 语法分析模块名字表 token序列中间代码（三地址码）语法分析（LL(1)分析法）语义分析（语法制导）错误处理（打印错误）说明：接受由词法分析得到的token序列，进行语法分析和语法制导翻译，最后得到三地址中间代码。2. 文法及属性文法描述2.1 文法：文法是用于描述语言的语法结构的形式规则（即语法规则）。这些规则必须是准确的、易于理解的以及有相当强的描述能力。由这种规则所产生的程序语言应有利于句子分析和翻译，而且，最好能通过这些规则自动产生有效的语法分析程序。DO-WHILE循环语句的文法如下所示：1、E-do A while B2、A-C;3、C-D=DH4、H-+D5、H-D6、H-*D7、H-/D8、D-z9、B-(FG10、G-F)11、F-z2.2 属性文法： 属性文法是在上下文无关文法的基础上，为每个文法符号（终结符或者非终结符）配备若干相关的“值”（与文法符号相关的属性）。在一个属性文法中，对应于每个产生式Aa都有一套与之相关联的语义规则，每规则的形式为：b:=f(c1,c2,，ck)其中f是一个函数，而且或者b是A的一个综合属性并且c1,c2,，ck是产生式右边文法符号的属性或者非终结符既可有综合属性也可有继属性，文法开始符号的所有继承属性作为属性计算前的初始值。属性文法为：1- if(S.value = true) emit(if(, S.value, )goto, codebegin) else emit(-, -, goto, nextstate)2-p = lookup(); if(p != NULL) L.place = p; else error; E.place = L.place; emit(=, id, -, L.place)3-L.place = newtemp; emit(+, F1.place, F2.place, F.place)4-S.place = newtemp; S.value = (F1.value F2.value); emit(, F1.place, F2.place, S.place)5-F.place = newtemp; p = lookup(); if(p != NULL) F.place = p; else error6-F.place = newtemp; p = lookup(); if(p != NULL) F.value = digit.value; else error3. 语法分析方法描述及语法分析表设计3.1语法分析为实现LL(1)算法,可以使用栈结构，算法的基本思想是: 首先定义栈结构，栈中的元素是一个结构体：typedef structchar sta100;int top;S;3.2 预测分析部分：int table810= /0 1 2 3 4 5 6 7 8 9 /d + - * / ( z/*00 E*/ 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*01 A*/ -1, 1, -1, -1, -1, -1, -1, -1, -1, -1,/*02 B*/ -1, -1, -1, -1, -1, -1, 8, -1, -1, -1,/*03 C*/ -1, -1, -1, -1, -1, -1, -1, -1, -1, 2,/*04 D*/ -1, -1, -1, -1, -1, -1, -1, -1, -1, 7,/*05 H*/ -1, -1, 3, 4, 5, 6, -1, -1, -1, -1,/*06 F*/ -1, -1, -1, -1, -1, -1, -1, -1, -1, 11,/*07 G*/ -1, -1, -1, -1, -1, -1, -1, 9, 10, -1,;3.3 语法分析过程：cout语法分析结果：endl;cout符号栈 输入栈endl;for(int i=0;i=w;)char temp=pop(store);for(int j=0;j7;j+)if(Vnj=temp)break;for(int k=0;k9;k+)if(stacki0=Vtk)break;if(k=9)break;int c=tablejk;if(c=-1)cout规约出错endl;exit(0);int d=blengthc;for(int m=0;md;m+)push(store,*(bc+m);for(int o=0;o=100;o+)coutendl;out_stack1(store);for(int u=i;u=w;u+)cout=a&stacki0=0&stacki0（文法仅定义这些操作）；左操作数，右操作数：id，digit；目的操作数：用来存放操作值的变量。例如：0: t = 12表示第0条中间代码作用是把12放到变量t中。又如：7: if (i) goto 9 8: goto 10 表示当i为true时，跳转到9号中间代码，否则跳转到10号中间代码。 4.3 词法分析 cout词法分析结果endl;in.open(first.txt);ch=in.get();out.open(second.txt);while(ch!=EOF)if(ch= |ch=t|ch=n)ch=in.get();else if(IsLetter()Letter(); /调用关键字-标识符处理函数else if(IsNumber()Number();else if(IsOperator() /调用运算符处理函数Operator();else if(IsBound()Bound(); /调用界符处理函数 in.close(); /关闭文件out.close();S * store=new S;init_stack(store);push(store,#);push(store,E);5. 简要分析与概要设计 5.1 系统分析5.1.1 词法分析输入源程序文本，对输入串进行预处理，然后从左至右逐个字符地对源程序进行扫（超前搜索法），产生一个一个的单词符号，在状态转换图的基础上，把作为字符串源程序改造成为单词符号串。5.1.2 语法分析在完成词法分析的基础上对DO-WHILE循环语句进行语法分析，对状态栈、符号栈分别进行移进、规约（采用LL(1)分析方法,自底而上进行规约）、接受和出错处理四步操作，从而分析判定程序的语法结构是否符合语法规则。5.1.3 语义分析以及三地址码表示当在栈中找到可归前缀后，进行规约时，根据相应产生式对应的语义子程序进行语法制导翻译（在语法的分析过程中，随着分析的步步进展，根据每一个产生式所对应的语义子程序进行翻译的方法）.三地址指令很类似于四元式,这种中间表示通常称为三地址代码,三个地址即是两个为操作数,一个是操作符。5.1.4 LL（1）语法分析中的出错处理1) 若在栈顶终结符号与下一输入符号之间不存在任何移进或规约规则；2) 若找到某一终结符号属于文法未定义的，则并给出具体的错误信息；否则，可给出类似“该句子不符合所给文法”的出错提示。5.2 概要设计5.2.1 系统总体描述源代码词法分析语法分析语义分析中间代码5.2.2 系统接口声明1、double exp(int a) /计算指数2、 bool IsLetter() /判断是否为字母3、 bool IsNumber() /判断是否为数字4、 bool IsOperator() /判断是否为运算符5、 bool IsBound() /判断是否为界限符6、 void Letter() /第一个字符为字母,转到关键字-标识符处理程序7、 void Number() /第一个字符为数字,转到数字处理程序8、 void Operator() /第一个字符为运算符,转到运算符处理程序9、 void Bound()10、void init_stack(S *p) /初始化栈11、void push(S *p,char x) /压栈12、char pop(S *p) /弹栈13、char get_top(S *p) /取栈顶元素14、void out_stack1(S *p) /自栈底到栈顶遍历栈元素15、void out_stack2(S *p) /自栈顶到栈底遍历栈元素6. 详细的算法描述a) 词法分析6.1.1数据结构定义typedef structchar sta100;int top;S;/symbol_instr *operate,*character;/操作符栈和符号栈/初始化栈6.1.2程序流程图6.2 语法分析6.1.1数据结构定义typedef structchar sta100;int top;S;/symbol_instr *operate,*character;/操作符栈和符号栈/初始化栈6.1.2程序相关算法cout语法分析结果：endl;cout 符号栈 输入栈endl;for(int i=0;i=w;)char temp=pop(store);for(int j=0;j7;j+)if(Vnj=temp)break;for(int k=0;k9;k+)if(stacki0=Vtk)break;if(k=9)break;int c=tablejk;if(c=-1)cout规约出错endl;exit(0);int d=blengthc;for(int m=0;md;m+)push(store,*(bc+m);for(int o=0;o=100;o+)coutendl;out_stack1(store);for(int u=i;u=w;u+)cout=a&stacki0=0&stacki0a )#2)运行界面7.2系统测试用例2 8. 研制报告 8.1 研制过程课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程。作为一名计算机软件工程专业大三的学生，我觉得能做类似的课程设计是十分有意义。它对我们的能力的提升很有好处。 回顾起此次DO-WHILE循环课程设计，我感慨颇多，的确，从考察到定稿，从理论到实践，在这一个多星期的日子里，可以说是苦多于甜，但是我学到了很多很多的的东西，不仅巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。在本次课程设计中，我先是具体了解了各种文法，然后进行了自己的文法的设计，将二者结合起来，作出一个自己的文法，然后我开始设计一些基本的构件并描述出它们的具体接口功能，接口设计好之后，下一步便是进行类接口几实现了，最关键的一步是总控程序的设计，对其他构件类的调用。在以上功能完成之后，我们便开始遍程了。最后，进行调试。至此，我的DO-WHILE语法分析及翻译系统出炉了，余下的工作便是进一步的完善系统功能。8.2 设计评价对于自己的劳动成果，精心研制的程序，我不想给以过高的评价。但是，它是我通过不段学习实践得来的。我对它做一下客观的评价：从性能上来看，本系统性能还可以，由于运行效率较高的C+变成语言，且系统较小，所以在时间复杂度和空间复杂度上的优势或者劣势不是很明显，但是就算法运用上来说，我用了很多泛型算法，它们的效率都很高很有高效性。本系统的容错能力一般，对错误的处理还不够完善，比如：不能将语法错误定位到行，等等。此特性还有待改进和完善。系统在Windows XP SP2SP3运行比较稳定，移植到同一操作系统的不同机器上也能正确运行。本系统的优点是精简，效率高，代码简练而具有粒度，系统的结构合理，布局搭配很巧妙，而且系统的封装性很高，内部构件的灵活性和内聚性和低偶合性很高。函数的设计和算法的应用很合适。另外，系统的交互性很好，很适合用户使用。本系统存在很大的不足，其中最大的不足是系统仅仅实现了编译过程的前两部，词法和语法分析，没有进行中间代码优化。这也是由于课程设计的要求不完整导致的。并且，系统的内部对内存的控制和掌握不是很合适，对内存的要求较大。8.3 体会和收获在整个设计过程中,最大的收获就是切身体会了编程语言在具体分析方法下进行翻译的实现机制和步骤.其次才是对LL（1）算法的理解和运用以及对堆栈的操作原理的掌握. 因为之前学理论的时候,感觉和实际的编程语言联系不是很大,也不知道所学理论如何在