《编译原理课程设计报告.doc》由会员分享，可在线阅读，更多相关《编译原理课程设计报告.doc（44页珍藏版）》请在金锄头文库上搜索。
1、编译原理课程设计简单编译器的设计与实现班 级：组长：组员： 指导教师：设计时间：2016年12月姓名分工组长：语法分析部分，语义分析和中间代码生成部分，符号表的管理，目标代码的生成，数据结构的设计和总体框架的设计。组员：中间代码优化部分，负责从DAG图中获得优化后的四元式代码，以及将中间变量填写入符号表内。组员：中间代码优化部分，负责优化DAG图的建立。组员：词法分析部分，词法分析部分的符号表和错误表的记录。摘要41.概述52.课程设计任务及要求62.1 设计任务62.2 设计要求63.算法及数据结构73.1算法的总体思想（流程）73.2词法分析模块83.2.1功能83.2.2数据结构83.2
2、.3算法103.3语法分析（含语义分析和中间代码生成）模块113.3.1功能113.3.2数据结构133.3.3算法163.4中间代码优化模块193.4.1功能193.4.2数据结构203.4.3算法203.5目标代码生成模块233.5.1功能233.5.2数据结构243.5.3算法244.程序设计与实现264.1程序流程图264.2 程序说明264.3实验结果325.系统特色406.结论417.参考文献418.收获、体会和建议41摘要一个编译器所进行的工作一般可以划分为五个阶段：词法分析、语法分析、语义分析和中间代码产生、中间代码的优化、目标代码生成。我们设计了并且实现了一个简单的类C语言编
3、译器，该编译器拥有完整的前端和后端，能够进行基本的编译功能并产生可执行文件向屏幕输出源程序的运行结果。该编译器的词法分析器可以识别绝大部分标准C语言支持的词法符号，该词法分析器可以过滤空格、Tab和回车，并且支持注释功能。该词法分析器主要通过有限自动机的状态跳转来实现，根据自动机结束状态来得到该单词的TOKEN值。该模块具有词法错误位置提示功能。该编译器的语法部分采用了递归下降子程序的文法分析方法，所设计的文法支持了函数、函数类型声明、变量类型声明、变量定义、表达式语句、if条件语句和while循环语句以及简单输出功能。在表达式语句方面，我们设计了支持所有算术运算、关系运算、逻辑运算和位运算功
4、能的语法结构，并且语法上支持一维数组和结构体。该编译器语义分析和生成四元式阶段能够对变量定义和语法错误进行检测，能够识别出未定义的标识符和重复定义标识符，该阶段最终实现生成中间代码四元式。该编译器拥有中间代码优化模块，采用DAG优化算法按基本块对四元式进行了优化，该编译器的目标代码是8086汇编语言代码，能够实现将优化后的四元式序列转化生成可执行的汇编语言文件，并且运行执行该文件，向屏幕输出运算结果。该编译程序的主要特色是能够将最终结果输出显示到屏幕，并且该编译程序能够支持前置+和后置+这种语法，拥有类似C语言的这种简便性。关键词：编译原理，词法分析，语法分析，四元式，DAG算法1.概述 编译
5、原理课程兼有很强的理论性和实践性，是计算机专业的一门非常重要的专业基础课程，在系统软件中占有十分重要的地位。编译原理课程设计是本课程重要的综合实践教学环节，是对平时实验的一个补充。通过编译器相关子系统的设计，使学生能够更好地掌握编译原理的基本理论和编译程序构造的基本方法和技巧，融会贯通本课程所学专业理论知识；培养学生独立分析问题、解决问题的能力，以及系统软件设计的能力；培养学生的创新能力及团队协作精神。一个编译器所进行的工作一般可以划分为五个阶段：词法分析、语法分析、语义分析和中间代码产生、中间代码的优化、目标代码生成。首先是词法分析，针对词法分析，我们设计了一个可以识别绝大部分标准C语言支持
6、的词法符号，该词法分析器可以过滤空格、Tab和回车，并且支持注释功能，即过滤掉注释符号$后面的代码。该词法通过有限自动机的状态跳转来实现，根据自动机结束状态来得到该单词的TOKEN值，词法分析器在识别到一个单词后，将该单词记录下来，如果是数据，则会在符号表的相应位置记录它的值，如果是标识符，则会先在符号表上进行查询，若没有则将其记录到符号表上，并将相应TOKEN的指针指向表中该位置。接下来进行语法分析，在语法分析部分，会对所编写的代码的语法进行检验，看是否合乎我们所设定的语法规则，这里我们采用了递归下降子程序的文法分析方法，所设计的文法支持了函数、函数类型声明、变量类型声明、变量定义、表达式语
7、句、if条件语句和while循环语句以及cout简单输出功能。在表达式语句方面，我们设计了支持所有算术运算、关系运算、逻辑运算和位运算功能的语法结构，并且语法上支持一维数组和结构体。在语义分析和中间代码产生的阶段。我们在语法分析程序的相应部分加上了语义动作，实现将输入的语句转换成可识别的中间代码四元式形式。在语义分析部分，主要做的工作是在识别到数据和标识符时将它们压入语义栈，当语法分析到需要生成相应四元式时，执行构建四元式的动作，并将语义栈中的数据作为四元式的数据组成部分。还有就是符号表的构建，当语法分析到变量的定义语句时，需要将被定义的变量记录到符号表内，在记录之前需要检查符号表内该符号是否
8、已经被定义，从而检查重复定义的错误。语义分析和中间代码产生是与语法分析同时进行的，当语法分析结束后，若输入内容的语法正确，则可以获得相应的四元式序列。然后是优化阶段。在优化阶段，我们主要运用了DAG优化算法。首先将编译器前端生成的四元式划分基本块，然后对每一个基本块执行DAG优化算法，通过该算法可以删除多余的赋值操作和无用的中间变量，从而减少四元式的数量，得到更简洁的四元式序列。最后一个阶段是目标代码生成。该阶段将四元式进一步翻译生成相应的目标代码，我们所选定的目标代码是8086汇编语言代码，所以该阶段的任务是将优化后的四元式序列转化生成可执行的汇编语言文件，从而进一步运行执行该文件，向屏幕输
9、出运算结果。2.课程设计任务及要求2.1 设计任务设计一个简单的文法编译器，该编译器包括完整的前端和后端。该编译器可以划分为词法分析、语法分析和语义动作、中间代码优化和目标代码生成四个模块。词法分析：能够识别标准C语言所支持的大部分词法，能够进行简单的词法错误判断，输出错误提示，并且具有注释功能，能够过滤掉无用符号，如空格、Tab和回车等。语法分析和语义动作：能够支持基本类似于C语言的基本语法。语法上能够支持声明语句、基本类型的变量定义，如整型、实型和字符型数据；能够支持表达式语句，包括赋值表达式、算术表达式、逻辑表达式、关系表达式和位运算表达式；能够支持if条件语句和while循环语句。中间
10、代码优化：采用DAG优化算法，能够对四元式进行优化，从而减少中间代码的数量，提高编译后生成的程序的效率。目标代码生成：将中间代码生成汇编语言代码，并且实现目标代码的运行，从而验证编译器编译结果的正确性。2.2 设计要求1、在深入理解编译原理基本原理的基础上，对于选定的题目，以小组为单位，先确定设计方案；2、设计系统的数据结构和程序结构，设计每个模块的处理流程。要求设计合理；3、编程序实现系统，要求运行界面应清楚地反映出系统的运行结果；4、确定测试方案，选择测试用例，对系统进行测试；5、运行系统并要通过验收，讲解运行结果，说明系统的特色和创新之处，并回答指导教师的提问；6、提交课程设计报告。3.
11、算法及数据结构3.1算法的总体思想（流程）我们将编译器的设计按照功能划分为以下四个部分，通过这四个部分来实现编译器的全部功能。如下图。图3.1 算法总体思想图词法分析器用来对输入的字符流进行词法分析，识别每一个单词并生成相应的TOKEN码，并记录它们的数据信息。语法分析和语义分析以及中间代码的生成被划分为一个模块是因为它们的不可分割性，当某个语法分析通过后，就开始产生语义动作生成相应的四元式，因此该部分用来对词法分析产生的TOKEN序列进行语法分析，从而在符号表中记录相关数据信息，并且产生中间代码。中间代码优化模块是为了简化中间代码而设计的，该部分通过四元式构建相应的无向图，通过算法产生优化后
12、的四元式序列。目标代码生成模块用于产生汇编代码，将优化后的四元式进行翻译，生成对应的汇编语言。该编译器包含了前端和后端的基本功能，能够进行词法错误检测、语法错误检测、标识符定义错误检测，并提示错误行数，且编译后生成可以直接运行的汇编程序，可以算是一个较为完整的简单编译器。3.2词法分析模块3.2.1功能通过将源程序输入该模块，词法分析器能够进行分析，检测词法是否正确，从而生成相应的TOKEN码，并向符号表中记录，如果遇到错误词法，则记录在错误表中。该词法分析器所能识别的词法包括以下几个部分。整数：TOKEN值为0实数：TOKEN值为1字符：TOKEN值为2字符串：TOKEN值为3标识符：TOK
13、EN值为4关键字：TOKEN值为10-49现有能够识别的关键字有：auto,short,int,long,real,double,char,struct,union,enum,typedef,const,unsigned,signed,extern,register,static,volatile,void,if,else,switch,case,for,do,while,goto,continue,break,default,sizeof,return,bool,cout.界符：TOKEN值为50-69现有能够识别的界符有：，(，)，”，;，,，.，-，?，#运算符：TOKEN值为70-99
14、现有能够识别的运算符有：+，-，*，/，%，+，-，=，=，3.2.2数据结构关键字表、界符表和运算符表都采用二维数组的形式进行存储。TOKEN表采用结构体的数据结构进行存储，里面包含该单词的token码，该单词的所在行数，并且会根据该单词的类型指向相应的符号表区域。错误表也采用结构体形式，其中包含错误的行数、错误的类型和错误的内容等信息，用来向用户报告源程序的相关词法、语法和声明错误。char KT3415=auto,short,int,long,real,double,char,struct,union,enum,typedef,const,unsigned,signed,extern,register,static,volatile,void,if,else,switch,case,for,do,while,goto,continue,break,default,sizeof,return,bool,cout;/关键字表char PT143,(,),;
