编译原理综合实验指导书

编译原理综合实验指导书序言《编译原理综合实验》作为《编译原理》课程的延伸，其目的是让同学动手设计和实现一个简单语言的编译器和解释器。通过上机实践，来设计这个相对完整的编译器设计，一方面可以使学生增加对编译程序的整体认识和了解——巩固《编译原理》课程所学知识，另一方面，通过上机练习，学生也可以学到很多程序调试技巧和设计大型程序一般的原则，如模块接口的协调，数据结构的合理选择等等。一、上机实践要求（1）综合实验的成绩占总成绩的30%；（2）本次实验的所有代码都需要自行编码实现，不能用lex、yacc、JavaCC等软件自动生成；（3）本次实验要求单人独立完成，综合实验提交的截止日期是2016-6-20；（4）本次综合实验须经授课教师当面验收考核后才予评分，否则以缺交处理；（5）实验结束后提交：源代码和实验报告。实验报告的格式参见“实验报告模板”。注：实验报告中不要贴代码。二、实验内容：（一）词法分析程序的设计与实现：20分要求：设计一个词法分析程序，每调用一次就从源程序文件中顺序识别出一个单词符号。单词种类与识别规则○1标识符：首字符为字母或’#’，其后由字母、数字或’#’组成；○2整数：由一个或多个数字组成、带正负号的数字串，首位数字不能为0；○3小数：[+|-]正整数1·正整数2[+|-]：表示可选的+或-注意：正整数1不能为空，正整数2可以为空，例如：23.○4字符串：由一对双引号括起来的文本注意：字符串不需要支持多行，即假定任意一串字符串都不能超过一行；字符串不需要支持转义符。○5保留字：class、if、then、else、call、while、do、string、integer、float、○6单目运算符：＋－*/=○7双目运算符：====⑧布尔运算符：&&||⑨界符：(){}，；此外，该词法分析程序还要能支持单行注释和多行注释（注释语法同C语言）。（二）语法分析程序的设计与实现：30分要求：构造下列文法的语法分析程序，应能指出源程序中首次出现的错误及出错位置。1.程序—类[类]2.类—classid{[属性|方法]}3.属性—变量定义语句4.方法—数据类型id(参数列表)语句块5.参数列表—数据类型id[，数据类型id]|ε6.语句块—{[语句]}7.语句—分支语句|赋值语句|循环语句|函数调用语句|变量定义语句|语句块|ε8.变量定义语句—数据类型id[,id]；9.数据类型—integer|float|string|classid10.赋值语句—id=表达式；11.函数调用语句—callid(传递参数)；12.传递参数—id[,id]|ε13.分支语句—if布尔表达式then语句|if布尔表达式then语句else语句14.循环语句—while布尔表达式do语句15.表达式—项[+|－项]16.项—因子[*|/因子]17.因子—id|con|deci|(表达式)14.布尔表达式—关系表达式[&&|||布尔表达式]15.关系表达式—表达式关系表达式16.关系—|=||=|==|说明：(1)id是标识符；con是整数常量；deci是小数常量；(2)用左右尖括号括起来的是非终结符；(3)红色方括号[]相当于正则表达式中的()*，表示其中内容重复0次或N多次；(4)文法中用蓝色标注的都是终结符（即单词）；(5)文法中&&与||不存在优先级，两者优先级别一样，按左结合处理。1、基原理：递归下降法是语法分析中最易懂的一种方法。它的主要原理是，对每个非终极符按其产生式结构构造相应语法分析子程序，其中终极符产生匹配命令，而非终极符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。注意：每次进入子程序之前都预先读入下一个要分析的单词（而且是由调用程序完成的，切忌在进入子程序后才读入下一个单词，虽然这样语法效果是相当的，但运行时会出错的）。因为使用了递归下降方法,所以程序结构和层次清晰明了,易于手工实现,且时空效率较高。实际的语法分析工作,从调用总程序的分析子程序开始，根据产生式进行递归调用各个分析子程序。（三）类型检查程序的设计与实现：20分要求：（1）检查变量的定义和使用是否正确：变量是否重复定义、变量是否未定义就使用；（2）过程的名称是否重复定义；（3）过程的实参与形参的数目是否一致；（4）过程的实参与形参的数据类型是否一致。设计指导：如何利用符号表进行语义检查。符号表在编译的过程中起着非常重要的作用，它一方面可以帮助语义分析程序进行语义检查，一方面可以辅助代码生成程序生成正确的代码（请参见书本相关章节）。符号表是记录符号属性的表，它的每一表项表示一个标识符的属性信息。这些属性信息通常包括种类（常数、变量、数组、标号等），类型（整型、实型、逻辑型、字符型等），给名字分配的存储单元地址等。符号表中的各类信息将在编译程序工作过程中的适当时候填入。对在语义分析阶段建造符号表的编译程序，当遇到标识符声明部分时，每当遇到一个名字声明，就以此名字查符号表；若表中无此登记项，则将该名字填入表中；若该表中已有此登记项，则说明该名字是重复声明，报告语义错误。至于与该名字相关的一些信息，可视工作的方便，分别在编译程序工作过程中的适当时候填入：种类，类型等信息可在语义分析阶段完成；名字的存储地址等信息则要在代码生成阶段完成。几乎在编译程序工作的全部过程中，都需要对符号表进行频繁的访问，查表和填表等操作，是编译程序的一笔很大的开销。因此，合理地组织符号表，并相应地选择好查表和填表的方法，是提高编译程序工作效率的重要一环。（四）四元式翻译程序的设计与实现：30分要求：将语法和语义都正确的源程序翻译成四元式。设计参考：在IF语句语法分析程序的基础上添加语义翻译子程序和中间代码生成部分代码的方法。if语句::=if布尔表达式then执行句else执行句语法分析程序语法制导的翻译ifs(){token=getnexttoken();If(token!=if)error;token=getnexttoken();bexp();token=getnexttoken();If(token!=then)error;token=getnexttoken();ST_SORT();/*调用函数处理then后的可执行语句*/token=getnexttoken();If(token!=else)error;token=getnexttoken();ST_SORT();/*处理else后的可执行语句*/}ifs(){token=getnexttoken();If(token!=“if”)error;token=getnexttoken();(e.tc,e.fc)=bexp();token=getnexttoken();if(token！=then)error(缺then);backpatch(e.tc,nxq);/*回填真出口e.tc*/token=getnexttoken();s1.chain=st_sort(token);/*处理s1,返回s1链*/token=getnexttoken();iftoken＝else/*处理else部分*/{q=nxq;gencode(j,—,—,0);backpatch(e.fc,nxq);/*回填假出口e.fc*/t.chain=merg(s1.chain,q);getnexttoken(token);s2.chain=st_sort(token);s.chain=merg(t.chain,s2.chain);return(s.chain)}else/*if--then结构时*/return(merg(s1.chain,e.fc))}ST_SORT(token);/*处理各种可执行语句*/ST_SORT(chart*token)/*可执行语句分类处理模块主程序*/{if(token=if)ifs();/*调用IF语句分析模块*/elseif(token=while)whiles();/*调用while语句分析模块*/elseif(token=repeat)repeats();/*调用repeat语句分析模块*/elseif(token=for)fors();/*调用for语句分析模块*/elseassign();/*其余情况表示是赋值语句，直接调用赋值语句的分析*/}编写一个函数gencode,该函数在四元式表中加入新的四元式四元式的格式为：(op,arg1,arg2,result)。要先定义一个四元式表intertable，结构如下：NxqOpArg1Arg2result其中nxq为当前四元式的编号，可以设为全局变量，本实验中可以设为与数组的下标同。函数描述如下：voidgencode(char*op,char*arg1,char*arg2,char*result)/*生成新的四元式，加入表尾*/{strcpy(intertable[nxq].op,op);strcpy(intertable[nxq].arg1,arg1);strcpy(intertable[nxq].arg2,arg2);strcpy(intertable[nxq].result,result);nxq=nxq+1;}