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

武汉理工大学编译原理课程设计说明书目录1 系统描述（问题域描述）21.1目的21.2设计步骤21.3系统体系结构描述22 文法及属性文法的描述32.1文法32.2属性文法33 语法分析方法描述及语法分析表设计53.1语法分析方法53.2语法分析表设计64中间代码形式的描述及中间代码序列的结构设计64.1中间代码形式描述64.2中间代码序列的结构设计75 编译系统的概要设计75.1系统分析75.1.1词法分析75.1.2语法分析85.1.3中间代码生成85.2概要设计95.2.1系统总体设计图95.2.2数据结构96 详细的算法描述（流程图或伪代码）106.1词法分析106.2语法分析117 软件的测试方法和测试结果127.1软件测试方法127.2测试结果127.2.1简单for循环语句（无嵌套）127.2.2 for循环嵌套语句148 研制报告168.1研制过程168.2对本设计特点和不足的评价168.3收获与体会179 参考文献（按公开发表的规范书写）17FOR循环语句的翻译程序设计（递归下降法、输出四元式）1 系统描述（问题域描述）1.1目的通过设计、编辑、调试和运行一个 对for 循环语句进行词法分析、语法及语义分析的编译程序，并通过对实验用例的测试来更加深刻的理解语言编译的过程和原理。从而达到在理论学习的基础上，对本课程有一个更深的掌握。1.2设计步骤对循环语句：for表达式；循环条件；表达式赋值语句（赋值语句中可以嵌套更多的for循环语句）（1） 设计符合自身语法分析方法要求的文法和属性文法。 （2） 设计对for循环语句进行词法分析的函数，输出单词序列。（3） 设计递归下降法对文法进行语法分析。（4） 对源文件进行语法分析同时对源文件进行语义处理。（5） 设计中间代码格式并输出四地址中间代码到文件中保存。 （6） 对源文件中的错误进行输出。1.3系统体系结构描述源文件词法分析语法分析中间代码文件管理 本系统包括两大部分：词法分析和语法分析；系统中还包含了一个文件管理的连接件，实现对词法分析结果和中间代码的输出保存功能。2 文法及属性文法的描述2.1文法文法是用于描述语言的语法结构的形式规则（即语法规则）。这些规则必须是准确的、易于理解的以及有相当强的描述能力。由这种规则所产生的程序语言应有利于句子分析和翻译，而且，最好能通过这些规则自动产生有效的语法分析程序。for 循环语句的文法如下所示：1)S-for(W)Sx 2)W-A;W13)W1-B;W2 4)W2-A5)Sx-Ax 6)Sx-Am7)Am-AmAx 8)Am-Ax2.2属性文法递归下降法的属性文法是在上下文无关文法的基础上，为每个文法符号（终结符或者非终结符）配备若干相关的“值”（与文法符号相关的属性）。 在一个属性文法中，对应于每个产生式 Aa 都有一套与之相关联的语义规则，每规则的形式为：b:=f（c1，c2，ck）。其中 f 是一个函数，b和c1，c2，ck是该产生式的文法符号的属性。并有如下规则：（1）如果b 是 A 的一个属性，c1，c2，ck 是产生式右边文法符号的属性或A的其他属性，则称b是A的综合属性。（2）如果b是产生式右部某文法符号X的一个属性，并且c1，c2，ck 是A或产生式右边任何文法符号的属性，则称b是文法符号X的继承属性。for循环语句的属性文法为：产生式属性文法S-for(W)Sxemit(1);/生成最后一个jumpbackpatch(nextstat,LastGotoAddress);/回填最后jump;backpatch(W.FalseOrEnd ,nextstat);/B为假跳到最后一个语句W1-B;W2backpatch(B.TrueOrChain , W2.TrueOrChain ); backpatch(W2.FalseOrEnd , B.codeBegin );W2-Aemit(4);/输出跳转W2.TrueOrChain = nextstat;W2.FalseOrEnd = nextstat-1;Sx-Am去掉B-B1|Lbackpatch(B1.FalseOrEnd, L.codeBegin );/回填B.codeBegin =B1.codeBegin ;B.TrueOrChain=chainMerge(B1.TrueOrChain, L.TrueOrChain);B.FalseOrEnd = L.FalseOrEnd ;LastGotoAddress=nextstat;/记录最后jump回填地址B-LLastGotoAddress=nextstat;/记录最后jump回填地址L-L1&Mbackpatch(L1.TrueOrChain , M.codeBegin );/回填L.codeBegin =L1.codeBegin ;L.TrueOrChain =M.TrueOrChain ;L.FalseOrEnd = chainMerge(L1.FalseOrEnd , M.FalseOrEnd );M-!M1M.TrueOrChain =M1.FalseOrEnd;M. FalseOrEnd =M1。TrueOrChainM.codeBegin =M1.codeBegin ;K-idScidK.TrueOrChain =nextstat;K.codeBegin =nextstat;K.FalseOrEnd = nextstat+1;emit(J+Sc,id,id, );/输出跳转语句emit(jump,-,-, );A-id=Eemit(E,- ,- ,id);/输出赋值语句E-EoperT(oper为+-*/)emit(oper , E , T , temp);/输出表达式3 语法分析方法描述及语法分析表设计3.1语法分析方法递归下降分析方法是一种自顶向下语法分析方法，其目的是从文法的开始符号开始，根据输入字符串进行最左推导，试图推导出给定的字符串。或者说，从根节点（文法开始符号）开始，自上而下，从左到右地为输入字符串建立一棵语法树，并以预先确定的顺序创建语法树的节点。递归下降分析法可能需要回溯，即需要重复地扫描输入。递归子程序法的实现思想是对应每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时，能够按照LL（1）形式唯一地确定选择某个候选式进行推导，因此首先要消除左递归。由于递归下降法对每个过程可能存在直接或间接的递归调用，所以对某个过程在退出之前可能又要被调用，因此有些信息需要保留，通常在入口时需保留某些信息，出口时需恢复。由于递归过程是遵循先进后出规律，通常开辟栈来处理。递归调用的语法调用关系图如下图所示：递归调用的语法调用关系图3.2语法分析表设计在对for循环语句进行翻译时，涉及到对赋值表达式和布尔表达式语句的翻译。在文法的描述中给出了算术运算符、关系运算符和逻辑运算符之间的优先级关系，其结合性由下表所示：优先级操作符类型操作对象的个数结合性1（）逻辑运算符左右2!逻辑非运算符单目运算符右左3*,/算术运算符双目运算符左右4+，-算术运算符双目运算符左右5,=关系运算符双目运算符左右6=,!=关系运算符双目运算符左右7&逻辑与运算符双目运算符左右8|逻辑或运算符双目运算符左右9=赋值运算符双目运算符右左4中间代码形式的描述及中间代码序列的结构设计4.1中间代码形式描述常见的中间代码形式有逆波兰记号，三元式，四元式和树形表示。本课程设计输出的中间代码的表示方法是四元式。四元式是一种更接近目标代码的中间代码形式。由于这种形式的中间代码便于优化处理，因此，在目前许多编译程序中得到了广泛的应用。 四元式实际上是一种“三地址语句”的等价表示。它的一般形式为： (op,arg1,arg2,result) 其中，op为一个二元 (也可是一元或零元)运算符；arg1,arg2分别为它的两个运算 (或操作)对象，它们可以是变量、常数或系统定义的临时变量名；运算的结果将放入result中。需要指出的是，每个四元式只能有一个运算符，所以，一个复杂的表达式须由多个四元式构成的序列来表示。例如，表达式A+B*C可写为序列 T1=B*C T2=A+T1 其中，T1，T2是编译系统所产生的临时变量名。当op为一元、零元运算符 (如无条件转移)时，arg2甚至arg1应缺省，即result=op arg1或 op result ；对应的一般形式为： (op,arg1,result) 或 (op,result) 4.2中间代码序列的结构设计对于循环语句：for（语句1；语句2；语句3）表达式，的中间代码序列的结构为：5 编译系统的概要设计5.1系统分析5.1.1词法分析对源程序流进行扫描，每识别出一个单词，若是标识符，则到符号表中查找，如果符号表中没有此标识符的记录，那么将此标识符插入符号表。最后按照单词其所属的类别，把类标识返回，作为语法分析阶段的输入。5.1.2语法分析由文法开始符号对应的子程序控制 for循环语句各个模块的执行顺序，并由文法开始符号对应的子程序递归调用其他的子程序，对各个模块采用自顶向下，自左至右的推导方法完成对输入字符进行匹配的工作，试图推导出与输入符号串一致的文法的句子。5.1.3中间代码生成控制代码的输出形式，以四元式形式输出中间代码5.2概要设计5.2.1系统总体设计图5.2.2数据结构这次课程设计中，在词法分析阶段，用一个KeyWord.txt文件存放所有的关键字，用一个结构体数组tableword table_word100来存放词法分析所输出的单词序列，并将单词序列输出到文件word.txt中。 在语法分析过程中，同样使用一个结构体数组item siyuanshi100来存放语法分析输出的中间代码四元式，并将结果输出到siyuanshi.txt中。KEYIDID ID ID数组tablewordlexptrtokenforEOSiEOShowEOSareEOSyouEOS字符串数组table_word定义字符表的数据结构如下：struct tablewordstring word;int type;/1表示ID，2表示数值常量，3表示字符常量，0表示其它;/*为符号表分配一个存储空间*/tableword table_word100;int tableword_length=0;int word_now=0;/*保存将要输出的四元式信息*/struct itemstring text;/四元式内容;item siyuanshi100;6 详细的算法描述（流程图或伪代码）6.1词法分析/词法分析相关函数（1）bool Keyword(char c,string *KEYWORD,int KNLength,ifstream &infile);/*对字符进行关键词的判断，将字符与关键词一个一个进行比较，如果比较成功，则返回真；如果比较到文件末尾，还未成功，则返回假。*/（2）bool Identify(char c,ifstream &infile,string &strtemp);/对字符进行标示符的判断（3）bool ConstChar(char c,ifstream &infile);/对字符进行字符串常量的判断（）bool ConstNum(char c,ifstream &infile);/对字符进行常数的判断（）bool Operator(char c,ifstream &infile);/对字符进行运算符的判断（）bool Delimiter(char c );/对字符进行界符的判断（）int classfify(char c);/对字符进行类型判断，相应返回类型号（）int classify_num(char c);/对读入的数字字符进行分类词法分析流程图6.2语法分析/语法语义函数，每个函数对应产生式的一个非终结符，从上到下进行递归调用，直到推出相应的终结符串。receive（）函数是对字符进行相应入栈出栈操作。emit()函数则是将产生的四元式中间代码输入到数组中。void S(tableword &word);void A(tableword &word);void E(tableword &word);void D(tableword &word);void O(tableword &word);void P(tableword &word);void G(tableword &word);void B(tableword &word);void S1(tableword &word);void X(tableword &word);void E1(tableword &word);void T(tableword &word);void T1(tableword &word);void F(tableword &word);void receive(tableword &word,string temp,int type);void emit(int row,string strtemp);7 软件的测试方法和测试结果7.1软件测试方法由于本程序在设计上考虑到for循环语句的多种表现形式，如for嵌套的方式，条件语句的表述等，所以在理论上能完成的功能很全，因此为了测试程序在实际应用中能否完成这些功能，我设计了两种测试途径：(1)输入最简单的for循环语句（无嵌套）(2)实现简单for嵌套，可包括多个赋值语句7.2测试结果7.2.1简单for循环语句（无嵌套）简单for循环语句的输入文件如下图所示：编译运行如下图所示：输出词法分析的单词序列：输出语法语义分析之后的四元式中间代码：7.2.2 for循环嵌套语句for循环嵌套语句的测试用例输入文件：词法分析后输出的单词序列文件：输出语法语义分析之后的四元式中间代码：8 研制报告8.1研制过程作为一名计算机科学与技术专业大三的学生，我觉得能做类似的课程设计是十分有意义。它对我们的能力的提升很有好处。 在已度过的大三的时间里我们大多数接触的是专业基础课。我们在课堂上掌握的仅仅是专业基础课的理论面，如何把我们所学到的专业基础理论运用到实践中？课程设计为我们提供了良好的平台。课程设计是培养学生综合运用所学知识发现提出分析和解决实际问题锻炼实践能力的重要环节是对学生实际工作能力的具体训练和考察过程. 回顾起此次 for循环课程设计，我感慨颇多，的确，从考察到定稿，从理论到实践，在这一个多星期的日子里，可以说是苦多于甜，但是我学到了很多很多的的东西，不仅巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。在本次课程设计中，我先是具体了解了各种文法，然后进行了自己的文法的设计，将二者结合起来，作出一个自己的文法，然后我开始设计一些基本的构件并描述出它们的具体接口功能，接口设计好之后，下一步便是进行类接口的实现了，最关键的一步是总控程序的设计，对其他构件类的调用。在以上功能完成之后，我们便开始遍程了。最后，进行调试。至此，我的for语法分析及翻译系统出炉了，余下的工作便是进一步的完善系统功能。8.2对本设计特点和不足的评价本程序实现的功能有：简单for循环，for循环嵌套，赋值语句，多个赋值语句（用分号隔开成语句），能完成的计算功能有布尔表达式，基本的四则运算，能将各个功能结合起来形成for循环，赋值语句，布尔表达式，空语句的复合出现。for语句的实现上，通过将之分解成三个表达式来分别调用，直接对应接口，使得代码冗余大大减小。for语句的分隔符是采用，来代替了小括号，避免了回溯所带来的算法效率低问题。在词法分析阶段，区分一元和二元操作符的方法是：当取得的第一个字符为一元操作符时，继续取下一个字符，若仍为操作符，则返回宏定义的标号，若不是操作符则将其放回，返回一元操作符的标号。在词法分析阶段在每一个类型判断中都需要进行放回操作。对语法分析，词法分析，四元式输出分离设计，同步控制，使得代码更灵活，结构更紧凑，不必要对中间结果进行大量重复的存储后，然后逐一检索后使用。由于没有对中间结果进行存储，造成语法上的某些错误处理不是很方便等缺点。不过这个缺点并非先天性的，可以通过冗余的存储中间结果来克服。同时，这个功能可以作为编译是的一个开关选项，当编译过程中为了追求效率时，不打开冗余存储开关(相当于gcc中的-On型开关)，当为了检测更多的错误时，打开冗余存储开关（相当于gcc中的-Wall）。词法分析的功能做得比较简单，主要是考虑到本程序的要求比较局限，只在for和赋值语句上做了要求，不过程序采用switch-case语句和if-else语句的配合使得词法分析有比较大的扩展空间。8.3收获与体会此次的课程设计我一共用了整整一周才全部完成，之前在学理论的时候，感觉和实际的编程联系不是很大，也不知道所学的理论如何在实际中发挥作用，如何应用，而通过这次的课程设计，才真正的体会到了平时所学的每一步在实际的程序中实现的，实践是检验知识的最好工具。在整个编程过程中，在词法分析和语法分析的实现过程中遇到了一些困难，比如在参数变量定义时出现错误，或者在设计循环和堆栈操作时也出现了一些错误，虽然通过同学的帮忙和自己的认真思考，都得到了解决。但是还是深深感觉到自己在实际编程的能力上需要进一步的更深的学习和实践，努力做到真正的把理论与实际相结合。9 参考文献（按公开发表的规范书写）1何炎祥编译原理（第二版）武汉：华中科技大学出版社2005年8月2陈火旺等程序设计语言编译原理（第3版）国防工业出版社2003年2月3AlfredV.Aho,Ravi Sethi,Jeffrey D.UllmanCompilers:Principles,Techniques,and Tools人民邮电出版社2002年2月4胡伦骏编译原理（第2版）电子工业出版社2005年2月5陈意云编译原理与技术（第二版）中国科学技术大学出版社2002年1月6胡元义等编译原理实践教程西安电子科技大学出版社2002年1月7王雷等编译原理课程设计机械工业出版社2005年3月8张素琴、吕映芝、蒋维杜、戴桂兰等编译原理（第2版）清华大学出版社2005年2月 17 / 17