for循环语句的翻译.doc

武汉理工大学编译原理课程设计课程设计任务书学生姓名： 辛波 专业班级： 计算机0707班 指导教师： 彭德巍 工作单位：计算机科学与技术学院 题目: FOR循环语句的翻译程序设计（递归下降法、输出四元式）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1） 写出符合给定的语法分析方法的文法及属性文法。（2） 完成题目要求的中间代码四元式的描述。（3） 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（5） 设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：1 系统描述（问题域描述）；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5 编译系统的概要设计；6 详细的算法描述（流程图或伪代码）；7 软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9 参考文献（按公开发表的规范书写）。时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试及测试。周5：撰写课程设计报告。设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次周星期一上午10点。指导教师签名： 2010年 01月 08日系主任（或责任教师）签名： 2010年 01月 08日FOR循环语句的翻译程序设计-递归下降法、输出四元式1 系统描述11目的通过设计、编制、调试一个FOR循环语句的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。12设计内容及步骤对循环语句： FOR（表达式1；表达式2；表达式3） 赋值语句(1)写出递归下降语法分析方法要求的文法和属性文法描述。(2)描述递归下降语法分析方法的思想。(3)给出中间代码序列的结构设计。(4)完成相应的词法分析、语法分析和语义分析程序设计。 121 词法分析 将词法分析程序设计成一个子程序，每当语法分析程序需要一个单词时，则调用该子程序。词法分析程序每调用一次，便从源程序文件中读入一些字符，直到识别出一个单词。 122 语法分析 采用递归下降方法，为对应文法中的每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串。若输入串是给定文法的句子，则从文法的开始符号出发一定能推导出与输入的单词串完全相同的句子。 123 语义分析 在语法分析的同时可由语法分析程序调用相应的语义子程序进行语义处理，完成附加在所使用的产生式上的语义规则描述，并生成四元式的中间代码形式。 124 测试用例和测试结果 设计不同的测试用例以显示程序的各种功能，包括简单的for循环和for循环的嵌套。并记录测试结果。2 文法及属性文法的描述21文法描述 本系统中所使用FOR循环语句的文法包括FOR语句本身，赋值表达式和布尔表达式。具体文法产生式如下：211 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-Ax212 布尔表达式：9）B-B|L 10)B-L11)L-L&M 12)L-M13)M-!M 14)M-K15)K-(B) 16)K-false17)K-true 18)K-id19)K-idScid 20)Sc- !=21)Sc- = 22)Sc- = 24)Sc- 213 赋值表达式：26)Ax-A; 27)A-id=E28)E-E+T 29)E-E-T30)E-T 31)T-T*F32)T-T/F 33)T-F34)F-id 35)F-(E)36)F-num22属性文法的描述产生式属性文法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 语法分析方法描述及语法分析表设计 31语法分析方法描述递归下降分析方法是一种自顶向下语法分析方法，其目的是从文法的开始符号开始，根据输入字符串进行最左推导，试图推导出给定的字符串。或者说，从根节点（文法开始符号）开始，自上而下，从左到右地为输入字符串建立一棵语法树，并以预先确定的顺序创建语法树的节点。递归下降分析法可能需要回溯，即需要重复地扫描输入。递归子程序法的实现思想是对应每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时，能够按照LL（1）形式唯一地确定选择某个候选式进行推导，因此首先要消除左递归。其文法及属性文法如图1和图2所示。由于递归下降法对每个过程可能存在直接或间接的递归调用，所以对某个过程在退出之前可能又要被调用，因此有些信息需要保留，通常在入口时需保留某些信息，出口时需恢复。由于递归过程是遵循先进后出规律，通常开辟栈来处理。32操作符优先级在对for循环语句进行翻译时，涉及到对赋值表达式和布尔表达式语句的翻译。在文法的描述中给出了算术运算符、关系运算符和逻辑运算符之间的优先级关系，其结合性由下表所示：优先级操作符类型操作对象的个数结合性1（）逻辑运算符左右2!逻辑非运算符单目运算符右左3*,/算术运算符双目运算符左右4+，-算术运算符双目运算符左右5,=关系运算符双目运算符左右6=,!=关系运算符双目运算符左右7&逻辑与运算符双目运算符左右8|逻辑或运算符双目运算符左右9=赋值运算符双目运算符右左图3操作符优先级4 给出中间代码形式的描述及中间代码序列的结构设计41中间代码形式的描述常见的中间代码形式有逆波兰记号，三元式，四元式和树形表示。本课程设计输出的中间代码的表示方法是四元式。它是带有四个域的记录结构，这四个域分别称为算符op，第一运算对象arg1，第二运算对象arg2及结果result。域op包含一个代表运算符的内部码。例如x = y op z的四元式表示为（op,y,z,x）,即将y置于arg1域，z置于arg2域，x置于result域，= 置于算符域op，如果op是单目运算符，例如非！( x = !y )的四元式表示形式中不用填arg2。通常，四元式中的arg1，arg2和result的内容都是一个指针，此指针指向有关名字的符号表入口。这样，临时变量名也要填入符号表中。42中间代码序列的结构设计型如for parse1;parse2;parse3list的中间代码序列的结构设计如下：parse1parse2parse3listTRUEENDFALSE图4中间代码序列结构设计5 简要的分析和概要设计51简要的分析本程序采用递归下降的方法实现FOR循环语句的翻译，并以四元式的中间代码形式输出。经过词法分析，语法分析，同时执行语法制导翻译将中间结果表达出来，然后通过一个函数转化成要求的四元式结构的中间代码。上述的这个过程在一遍扫描过程中完成：在语法分析的过程中调用词法分析来不断的分解出下一个句柄；在用递归下降方法进行语法分析的同时进行中间形式数据的保存，在分析出操作符号的同时结合当前栈中的数据输出四元式。程序中各阶段的功能如下：（1） 词法分析阶段对源程序流进行扫描，每识别出一个单词，若是标识符，则到符号表中查找，如果符号表中没有此标识符的记录，那么将此标识符插入符号表。最后按照单词其所属的类别，把类标识返回，作为语法分析阶段的输入。（2） 语法及语义分析阶段由文法开始符号对应的子程序控制 for循环语句各个模块的执行顺序，并由文法开始符号对应的子程序递归调用其他的子程序，对各个模块采用自顶向下，自左至右的推导方法完成对输入字符进行匹配的工作，试图推导出与输入符号串一致的文法的句子。（3） 中间代码生成阶段控制代码的输出形式，以四元式形式输出中间代码 52概要设计 521数据结构 本程序使用符号表以及数组来存储长短不一的标识符。将标识符的字符串放入一个单独的数组lexemes,每个字符串用一个字符串终结符EOS（0）结束。符号表采用结构体数组symtable来表示，每一个表项有两个域的记录：第一个域是指向数组lexemes中字符串的开始位置的指针域，另一个域是用来存放标识符记号的token域。KEYdivdiv div div数组symtablelexptrtokenforEOSiEOShowEOSareEOSyouEOS存储字符串的数组lexemes图5 符号表和存储字符串的数组定义符号表的数据结构如下：struct entrychar *lexptr; /*符号表的指针域*/int token; /*符号表的标识域*/;struct quadruplesint qt;/*保存将要输出的单词的标识*/int qtval;/*保存将要输出的单词的值*/;/*为符号表分配一个存储空间*/struct entry symtable999;/*保存将要输出的四元式信息*/struct quadruples quadtable38;522符号表初始化本程序要完成对FOR循环语句的翻译，所以首先要将for作为关键字插入到符号表中：struct entry keywords = for, KEY,0, 0;因此在遇到for这样的关键字时，函数直接返回关键字的标识号KEY，则程序不会把它们当作标识符插入到结构体数组中，而是将他们完整地归类到关键字集合中。且这种设计很利于程序的扩展。523多元操作符的处理在程序中使用到了!=,|,=这样的多元操作符,由于不能像一元操作符一样直接匹配，所以通过C语言中进行#define预处理，如NE代表!=,并在头文件中将这些多元操作符与整数之间建立映射关系，且存放在二维数组中。若词法分析返回的标识号为相应的宏定义的变量，则在语法分析阶段switch-case语句中直接通过对相对位置的计算得到多元操作符在数组中的存储位置，从而得到相应的操作符。通过这样的设计，使得在编写代码时要简单的多。6 详细的算法描述61词法分析的数据结构设计与详细的流程图6.1.1初始化部分介绍在程序正确执行前要完成如下的初始化工作：1）完成语法分析所要查找的关键字和各种标识符编号的图的初始化。2）读入源文件，对源文件进行初步的处理。3）对源文件的正确读入进行判断，读入错误则进行报错。4）初始化各种全局变量。6.1.2数据结构的设计6.1.2.1 string WordWordNum存储所有的单词（标识符，关键字，运算符，界限符，数字（整型，实型），WordNum为单词个数。6.1.2.2 map WordMap 存储所有单词和相应的类型码的map，用于识别单词类型时候方便查找，如能在表中找到，则能识别，如找不到，则报错处理。6.1.2.3 vector AllToken存储词法分析结果，Token为结点类。6.1.2.4 class Token每个单词类别的种类和类型结点信息，其主要的数据成员为单词的类型码和单词本身。6.1.3词法分析流程图对构成源程序的字符串从左到右的扫描，逐个字符地读入源程序字符并按照构词规则切分成一个一个具有独立意义的单词。并确定其属性（如保留字、标识符、运算符、界限符和常量等）。再把它们转换成长度统一的标准形式属性字（TOKEN）。 图2.词法分析流程图6.2语法制导翻译的数据结构与详细的设计图6.2.1数据结构的设计本程序语法分析所用到的数据结构如下表所示：数据结构作用stack sState状态栈，用来存放分析过程中的状态信息stack sNotation符号栈，用来存放分析过程中的产生的单词信息deque sInputToken输入串栈,存放的是单词结点deque TokenTableToken队列,单词结点和编号stack sLang语义栈，语义分析时用，存放的是实际输入符号串stack sNodeInfor每个非终结符的链信息栈,在语义分析的时候存储与回填与拉链相关信息newTemp newTempVar中间变量,每调用一次产生一个新的中间变量int nextstat四元式地址的序号，假设从100开始map pair, string,ltcomp ActionTableAction表，（，状态m），其中ltcomp是比较时要用到的比较符mapint ,pair objectCode存储目标代码的图，编号7 测试方法和测试结果71测试方法由于本程序在设计上考虑到for循环语句的多种表现形式，如for嵌套的方式，条件语句的表述等，所以在理论上能完成的功能很全，因此为了测试程序在实际应用中能否完成这些功能，我设计了两种测试途径：(1)输入最简单的for循环语句（无嵌套）(2)实现简单for嵌套，可包括多个赋值语句72 测试结果（1）简单的for循环语句（无嵌套）图7简单for的输入文件简单for的输入输出结果（2）简单的for嵌套简单for嵌套的输入文件简单for嵌套的输出结果8 研制报告81研制过程首先完整分析问题，得出需求和实现功能目标，然后划分程序大体的模块，确定模块之间的联系，细化模块功能，将功能以接口的形式给出，分析和设计for循环、赋值表达式的语法制导翻译模式，确定函数之间的调用关系，制定结构化程序代码方式，画出流程图，最后逐一对功能进行编码，得到程序并进行调试，反复测试代码，直到得到正确，完善的功能。 在完成程序架构设计之后各个过程中，如果发现设计上的缺陷，应该及早的对设计做出适当的调整。不然在编码的过程中擅自对接口功能做较大幅度改变，会导致接口功能上的不一致，在需要统一接口时候，会由于接受参数，传出参数，返回参数，甚至接口功能不一致而造成困难甚至错误。8. 2本设计的评价 编译原理的课程设计与其他课程设计有个本质的区别，就是在设计的过程中，更多地要结合课本几乎所有相关章节的理论知识，给人的感觉是一种在做工程设计的感觉。即设计要建立在大量的资料积累和工程目标和方案的取舍和折衷之上。比如，在设计符号表的时候，可以采取分配一个很大的二维数组结构体，然后分别存放符号实体和对应类型，一个元素的大小至少为最大的一个符号长度，这样在记忆大量的短符号时，就会造成符号表空间的浪费；在这样的一种情况的考虑下，就采取了如上所述的符号表结构的概念，最大限度的提高符号表空间利用率。其实在这个过程中还可以用hash函数表来加快符号表的查找，但是考虑到在这种单一for循环加赋值表达式的实现中，hash函数带来了一定的复杂性，所以在程序中没有加入hash查找的实现。通过对for循环、赋值表达式的语法制导翻译模式的分析设计，实现了程序中功能最复杂的递归下降语法分析过程。这种模式很清晰地展示了功能的分解和嵌套使用，使得在实际编码中很容易得到上下层的功能服务与被服务；同时，可以很方便的通过更改语法制导翻译模式而得到不同的语法需要和对应的语法分析代码，这个过程也就是提高了程序的可扩展性。在设计过程中根据词法、语法分析的特点，在C语言的语法上做出适当的调整，以符合自身设计的需要进而提高了效率。例如，在选择for循环控制语句的分隔符时，标准C采用小括号(、),考虑到本程序采用递归下降分析算法，当遇到小括号的时候只有通过向前多走几步（可能很长）才能判断他是控制for用的，还是一个操作符号。为了提高效率，对语法进行改进，采用中括号、来代替。83特点本程序实现的功能有：简单for循环，for循环嵌套，赋值语句，多个赋值语句（用分号隔开成语句），能完成的计算功能有布尔表达式，基本的四则运算，能将各个功能结合起来形成for循环，赋值语句，布尔表达式，空语句的复合出现。for语句的实现上，通过将之分解成三个表达式来分别调用，直接对应接口，使得代码冗余大大减小。for语句的分隔符是采用，来代替了小括号，避免了回溯所带来的算法效率低问题。在词法分析阶段，区分一元和二元操作符的方法是：当取得的第一个字符为一元操作符时，继续取下一个字符，若仍为操