编译原理课程设计报告-简单编译器的设计与实现.docx
《编译原理课程设计报告-简单编译器的设计与实现.docx》由会员分享,可在线阅读,更多相关《编译原理课程设计报告-简单编译器的设计与实现.docx(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、现有能够识别的运算符有:+,-,*,/,%,+,-,=,=,,?,#;/界符表char OT233+,-,*,/,%,+,-,=,=, FunctionFunctionFunction - FType i4 ( Parameter ) Declaration Content 类型文法:FType - void|TypeType - int|real|charParameter - |void|Type Id , Type Id Id - i4|i4 i1 结构体声明文法:Declaration - |struct i4 Base_declaration ;|Base_declaration 基
15、本类型定义文法:Base_declaration - | Type Id , Id ; 语句块文法:Content - Structure Structure Structure - |E ;|If|While|Fun|Cout函数调用文法:Fun - i4 ( ) ;|i4 ( Assignment , Assignment ) ;if条件语句文法:If - if ( Expression ) Content | if ( Expression ) Content else Content while循环语句文法:While - while ( Expression ) Content 逗号
16、表达式文法:Expression - Assignment , Assignment 赋值表达式文法:Assignment - i4 . Id = Logical_or | Id = Logical_or | Logical_or逻辑表达式文法:Logical_or - Logical_and | Logical_and Logical_and - Inclusive_or & Inclusive_or Inclusive_or -Exclusive_or | Exclusive_or Exclusive_or -And And And - Equality & Equality 关系表达式文
17、法:Equality - Relational w0 Relational Relational - Shift w1 Shift 算术表达式文法:Shift - Additive w2 Additive Additive - Multiplicative w3 Multiplicative Multiplicative - Unary w4 Unary 前置算符文法:Unary - w5 Postfix | Postfix后置算符文法:Postfix -Primary w6 Primary -i4|constant| ( Expression )其中符号表示:w0 - = | !=w1 -
18、| =w2 - w3 - + | -w4 - * | / | %w5 - ! | | + | - | sizeofw6 - + | - | Expression | . i4其中constant为整数、实数或者字符类型数据,i4为用户自定义标识符,可以由字母、数字和下划线组成,不能以数字开头,并且不能与关键字相同。该模块还要执行相应的语义功能以及中间代码的生成。语义功能主要包括变量的定义、表达式四元式的生成、if条件语句和while循环语句的四元式生成等。变量的定义需要实现与符号表进行信息交换的功能,该变量定义的文法通过检验后,会向符号表中查找该标识符名称,如果没有查到则将该变量的类型和相关信
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 课程设计 报告 简单 编译器 设计 实现
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【可****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【可****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。