下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 编译原理课程设计报告(一个完整的编译器)

编译原理课程设计报告(一个完整的编译器).doc

编译原理课程设计报告(一个完整的编译器)

差不多得夜生活
2019-05-12 0人阅读 举报 0 0 暂无简介

简介:本文档为《编译原理课程设计报告(一个完整的编译器)doc》,可适用于高等教育领域

编译原理程序设计报告一个简单文法的编译器的设计与实现专业班级:计算机班组长姓名:宋世波组长学号:指导教师:肖 桐 年月设计分工组长学号及姓名:宋世波分工:文法及数据结构设计词法分析语法分析(LL)基于DAG的中间代码优化部分目标代码生成组员学号及姓名:黄润华分工:中间代码生成(LR)部分目标代码生成组员学号及姓名:孙何奇分工:符号表组织部分目标代码生成摘要编译器是将便于人编写阅读维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序。编译是从源代码(通常为高阶语言)到能直接被计算机或虚拟机执行的目标代码(通常为低阶语言或机器语言)的翻译过程。一.编译器的概述编译器的概念编译器是将便于人编写阅读维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序。编译器将原始程序作为输入翻译产生使用目标语言的等价程序。源代码一般为高阶语言如Pascal、C、Java等而目标语言则是汇编语言或目标机器的目标代码有时也称作机器代码。.编译器的种类编译器可以生成用来在与编译器本身所在的计算机和操作系统(平台)相同的环境下运行的目标代码这种编译器又叫做“本地”编译器。另外编译器也可以生成用来在其它平台上运行的目标代码这种编译器又叫做交叉编译器。交叉编译器在生成新的硬件平台时非常有用。“源码到源码编译器”是指用一种高阶语言作为输入输出也是高阶语言的编译器。例如:自动并行化编译器经常采用一种高阶语言作为输入转换其中的代码并用并行代码注释对它进行注释(如OpenMP)或者用语言构造进行注释(如FORTRAN的DOALL指令)。本编译器概述编译程序的工作过程一般可以分为五个阶段:词法分析、语法分析、语义分析与中间代码产生、优化、目标代码生成。每一个阶段在功能上是相对独立的它一方面从上一个阶段获取分析的结果来进行分析另一方面由将结果传递给下一个阶段。由编译程序的五个阶段就对应了编译系统的结构这五个对应阶段分为编译器的前段中间代码以及后端。 其中词法分析器利用超前搜索、状态转换等方法将源程序转化成为一个一个的单词符号二元式。一般程序语言的单词符号包括关键字、运算符、常数、标识符和界符。语法分析器将这些单词符号作为输入对它进行语法分析。语法分析采用LL分析法语法分析器把语法单元作为输入供语义分析器使用。在语法分析的同时进行语法分析并产生一定的语义动作来生成中间代码。优化和目标代码生成是针对某一种处理器而言的。代码优化是将语义分析生成的中间代码进行优化产生执行效率更高的代码。目标代码生成最终生成可以在某种机器上运行的机器语言或者汇编语言。还要有符号表可供查询。在整个编译过程中还包括对表格的操作和对错误的处理这些也都是非常重要的环节。环境:编译器整体全部使用visualstudio编写目标代码在指令集机器上运行关键词:编译原理前端中间代码生成后端目录设计分工  摘要  概述  课程设计任务及要求  设计任务  设计要求  设计的文法结构  算法及数据结构  算法的总体思想(流程)  词法分析器模块  功能  数据结构  流程图  算法  运行截图  语法分析器模块  功能  数据结构  流程图  算法  运行截图  符号表生成模块  功能  数据结构  流程图  算法  运行截图  中间代码生成模块  功能  数据结构  流程图  算法  运行截图  中间代码优化模块  功能  数据结构  流程图  算法  运行截图  目标代码生成模块  功能  数据结构  流程图  算法  运行截图  这里不得不提到目标代码生成中存在的一些问题  程序设计与实现  程序说明  实验结果  结论  组长:宋世波  组员:孙何奇  组员:黄润华  收获、体会和建议。  组长:宋世波  组员:孙何奇  组员:黄润华  附录  源代码:  可执行文件链接  、参考文献  概述本程序实现的数据类型有整型(int)、浮点型(float)、char(字符型)、字符串型(string)同时在最后的目标代码生成部分允许出现布尔(bool)类型实现的操作有ifelse以及while循环和输入输出语句能做到直接生成目标代码并运行。做到了类型检查和重定义的判断同时也有优化部分。词法分析部分构建得到的词法序列为二元式二元式由两部分组成其种别码和类型组成其中关键字和界符记录其数字用到时只需查其对应的关键字表和界符表即可而字符类型、字符串类型、数字类型、以及标识符类型的值一律用字符串存储其中数字类型存储时对其使用atoi和itoa函数进行数字转字符串即可要使用到其数字时只需要将对其使用字符串转数字函数再获得即可。语法分析部分采用的是LL分析方法这是一种自上而下的语法分析法又称为预测分析法语法分析器部分实现了自动求first集合和follow集合采用的是递归程序获得select集合在实现对产生式完全扫描以后便可以获得一张完整的分析表表中标注了是否为预测以及对应的产生式序列而后进行语法分析通过于获得的分析表进行比对进行入栈出栈匹配到相同的则认为匹配成果当文法匹配成功同时单词也匹配成功的时候认为语法分析完成语法无错误否则报错。在符号表生成部分程序对获取的单词序列中的标识符进行再分析确定每一个标识符的存储范围同时从此之中获取函数的参数表函数表部分构建出编译器全局可用的活动记录表以供目标代码生成使用同时也为编译器增添新内容做准备。中间代码生成部分在此之前需注意到由于再语法分析部分已经生成了一个具体可理解的动作序列所以中间代码生成部分的所用方法并非语法制导其本身也与语法分析相割裂开来中间代码生成采取的是自底向上进行分析不过是基于单词序列进行的分析其操作等于是使用已获得的伪动作序列与源程序去作比较找出伪动作序列的实际含义将其顺序填好最后便完成了整个中间代码(四元式)的生成并将其重新输出到文件中。中间代码优化部分是对填装完毕的中间代码的再处理也就是减少无用式子给目标代码的生成提供便利先进行基本块划分而后采取的是DAG图优化即无环有向图优化顺序是构建DAG图(无环有向图)减少无用分支或删改部分同义分支完成DAG图改造后便又重新由树组装四元式组装好的四元式又再次重新输出到文件中。目标代码生成部分较长也并不仅仅包含目标代码生成部分在这个部分文件中同时需要对前述获得的符号表中间代码进行再处理以得到符号目标代码生成所用的符号表和中间代码再进行预处理完成之后具体为根据四元式动作按顺序依次生成目标代码需要依据不同的四元式动作每个采取不同的操作方法生成相应目标代码。测试部分采用的emu软件这个软件支持的指令集为指令集由于位机器上对汇编的支持并不算好所以在机上最后进行的是对目标代码的正确性检验以及运行运行通过且符合源程序实际操作即认为编译器任务完成。课程设计任务及要求设计任务一个简单文法的编译器前端的设计与实现①定义一个简单程序设计语言文法(包括变量说明语句、算术运算表达式、赋值语句扩展包括逻辑运算表达式、If语句、While语句等)②扫描器设计实现③语法分析器设计实现④中间代码设计⑤中间代码生成器设计实现。难度相当的自选题目,如:①一个简单文法的编译器后端的设计与实现。②一个简单文法的编译器的设计与实现。③自选一个感兴趣的与编译原理有关的问题加以实现以下为本组选择部分:一个简单文法的编译器的设计与实现。定义一个简单程序设计语言文法(包括变量说明语句、算术运算表达式、赋值语句扩展包括逻辑运算表达式、If语句、While语句等)扫描器设计实现语法分析器设计实现符号表设计符号表生成器设计实现中间代码设计中间代码生成器设计实现。中间代码优化中间代码优化实现目标代码设计目标代码生成器设计实现设计要求、在深入理解编译原理基本原理的基础上对于选定的题目以小组为单位先确定设计方案、设计系统的数据结构和程序结构设计每个模块的处理流程。要求设计合理、编程序实现系统要求实现可视化的运行界面界面应清楚地反映出系统的运行结果、确定测试方案选择测试用例对系统进行测试、运行系统并要通过验收讲解运行结果说明系统的特色和创新之处并回答指导教师的提问、提交课程设计报告。以下为本组设计要求:给出一个源程序文件作为编译器前端的输入输出相关编译阶段的运行结果。词法分析阶段:Token序列关键字表、界符表、符号表系统。语法分析阶段:LL型产生式、分析表、语法分析所用栈符号表生成阶段:符号表系统中间代码生成阶段:四元式序列符号表系统。中间代码优化阶段:四元式序列、DAG图、优化完成的四元式序列目标代码生成阶段:符号表系统、四元式序列、目标代码(指令集)设计的文法结构产生式中文对照:  <函数定义>><类型><标识符>(<参数声明>){<函数块>}   <类型>>int|float|char|void|$  <因式>>(<表达式>)|<标识符>|<数字> |<字符>  <表达式>><因子><项>  <因子>><因式><因式递归>  <因式递归>>*<因式><因式递归>|<因式><因式递归>|$   <项>><因子><项>|<因子><项>|$   <参数声明>><声明><声明闭包>|$   <声明>><类型><标识符><赋初值> |<标识符><赋初值>  <赋初值>>=<右值>|$   <右值>><表达式>  <声明闭包>>,<声明><声明闭包>|$   <函数块>><声明语句闭包><函数块闭包>  <声明语句闭包>><声明语句><声明语句闭包>|$   <声明语句>><声明>  <函数块闭包>><赋值函数><函数块闭包>|<while循环><函数块闭包>|<条件语句><函数块闭包>|<函数返回><函数块闭包>|<cout语句><函数块闭包>|<cin语句><函数块闭包>|$   <赋值函数>><标识符><赋值或函数调用>  <赋值或函数调用>>=<右值>|(<参数列表>)   <参数列表>><参数><参数闭包>  <参数闭包>>,<参数><参数闭包>|$   <参数>><标识符>|<数字>|<字符串>  <While循环>>while(<逻辑表达式>){<函数块>}  <逻辑表达式>><表达式><逻辑运算符><表达式>  <逻辑运算符>><|>|==|>=|<=   <条件语句>>if(<逻辑表达式>){<函数块>}<否则语句>  <否则语句>>else{<函数块>}|$   <函数返回>>return<因式>   <cout语句>>cout<<<标识符>|cout<<<数字>|cout<<<字符>  <cin语句>>cin>><标识符>产生式如下:funcdeftypeid(¶state){funcblock}#typeint|float|char|void#factor(exp)|id|number|ch#expdiviitem#divifactorfaccycle#faccycle*factorfaccycle|factorfaccycle|$#itemdiviitem|diviitem|$#parastatestatestateclo|$#statetypeidinit|idinit#init=rvalue|$#rvalueexp#stateclo,stateclo|$#funcblockstaclofuncbloclo#staclostatementstaclo|$#statementstate#funcbloclooperafuncbloclo|whilecyclefuncbloclo|condistatefuncbloclo|funcendfuncbloclo|coutstatefuncbloclo|cinstatefuncbloclo|$#operaidcallstate#callstate=rvalue|(¶list)#paralistpara¶clo#paraclo,¶¶clo|$#paraid|number|string#whilecyclewhile(logicexp)do{funcblock}we#logicexpexplogicoperaexp#logicopera>|<|==|>=|<=#condistateif(logicexp){funcblock}norie#norelse{funcblock}|$#funcendreturnfactor#coutstatecout<<id#cinstatecin>>id#do$#we$#ie$#词法分析序列表:标识符表i 常数表C 关键字表KIntFloatCharStringVoidIfElseSwitchCaseForDoWhileContinueBreakDefaultSizeofReturnCoutCin界符表P>=<====><*{},()字符表Ch 字符串表st     算法及数据结构算法的总体思想(流程)算法总体思想文字解释如下:从文件中读取代码调入词法分析生成词法序列。而后将词法序列传递给语法分析器语法分析器从文件中读入产生式自动产生first集和follow集构建出完整的分析表而后与得到的词法序列进行比较吮吸进行语法分析按照分析表查得产生式进行入栈出栈完成LL语法分析的整个过程。符号表继续使用词法序列不依赖于语法分析而直接构建符号表依据词法中的标识符直接构建函数表、参数表、符号表和活动记录表并对于其后的目标代码生成产生作用。中间代码生成模块使用语法分析过程中所获得的伪动作序列同时依靠获得的词法分析序列逐个进行比对同时将标识符依次入栈需要时取出通过完整栈区的出栈入栈实现整个中间代码(四元式)的填写。中间代码优化模块获取前述过程中所生成的四元式文件而后依托于四元式构建DAG图由产生的DAG图采用教材ppt所述方法按节点进行优化直接产生优化后的DAG图并生成优化后的四元式填装回文件中。目标代码生成部分直接提取之前编译器部分所获得的四元式和符号表依据其成果直接构建目标代码(汇编代码指令集)同时在此其中进行类型检查重定义等完成语义分析。词法分析器模块(负责人:宋世波)功能获取待处理的源代码生成二元式序列采用DFA和自动机实现二元式的填写将获得的二元式输入到文件中词法分析过程是将字符序列转换为Token序列的过程。此阶段的任务是从左到右依次扫描源程序中的字符即对构成字符流进行扫描然后根据构词规则识别Token。设计的词法分析器能相对完善地构造出不同的单词用二元式的形式存储简显易懂并将新的标识符单词填入变脸表当中实现在计算机内单词序列的统一存储。数据结构enumstyle{I,C,K,P,Ch,St,def}*枚举种类*staticchar*keyword={"int","float","char","void","if","else","switch","case","for","do","while","continue","break","default","sizeof","return","cout","cin"}*关键字表*staticchar*delimiters={">=","<=","==","=",">","<","","","*","","{","}",",","","(",")","",""}*界符表*charvariate={}*变量表*staticstructtwoele{*二元式数据结构*stylekindcharvalueintvalue}二元式包含三项但实际使用时只会用到其中两项单词种类的不同决定了其对应有不同的处理方式kind用来存放种类value和value都是用来存储单词所含值的相对于不同类单词有不同处理方式。而其中kind所可为的值以及在上面数据结构中相应的有所列出的对应查较即可。具体分配如下当单词为关键字或者界符时使用的是kind和value项即value存储对应固定表中单词所对序列。而当单词为其他时即单词为字符、字符串、标识符或者数字时采取将单词直接字符串化直接存储其值为数字时调用库函数将其字符化取出时候按照其相应种别码采取不同的取出方式。statictwoeleTOKEN*词法序列(二元式结构)*流程图算法staticvoidinittwoele(twoele*tok)*初始化二元式同时将变量表初始化*inttra(char*cmp)*查询获得单词是否为关键字是则返回关键字序号*voidaddvar(char*cmp)*加入变量表*voidprep(charch)*预处理过滤注释*staticvoidscanner()*词法扫描*在词法分析之前有一段的注释处理部分其相应方案是在遇到符时即进入注释处理而后再次遇到符时候认为离开注释处理部分但有所控制若较长范围内并未再遇到符则跳出自动机认为符号就是一个单纯的界符由于c语言中并没有所用的语言如果此时并不在字符串中可直接进行报错处理。以下就词法分析遇到的单词处理方法进行分情况解释:字符:首先是用if判断字符字符都会带单引号所以若识别出单引号则进入字符判别部分执行ch=fgetc(fp)进入下一个判断语句若条件为假则输出error这样可以完成一个简单的报错功能。若为真的话执行ch=fgetc(fp)判断是否为单引号若为假则输出error为真就要将找到ch对应的token。(这一段包括在界符处理的字部分中)字符串:字符串的判断与字符的判断差不多不同的是字符串要识别的是双引号而且需要加一个循环来将整个字符串识别完毕。首先ch若为“则进入字符串的判别部分ch=fgetc(fp)然后就要进入一个while循环每循环一次就执行ch=fgetc(fp)若为数字或字母就将其装入字符数组否则跳出循环。剩下的就同识别字符一样若识别不到”就输出error。然后查找token和压队列的操作。标识符:由于关键字也是一些字符串所以一般放在一起来判断若不是关键字则为标识符。由于关键字和标识符都必须是以字母开头所以用if为字符来判断为真接着判断while循环来识别完整个标识符或关键字的部分与识别字符串相同也是装入字符数组但比字符串部分多出一点就是标识符可以有下划线所以中间判断条件会变成数字字符下划线均可。While循环结束后需要在字符数组的最后一位后加上‘’。识别完毕后就需要判断该字符串到底是标识符还是关键字了关键字个数是固定的挨个匹配就可以了界符:判断方法简单粗暴直接switch即可不过要注意比如》=这种需要多判一次即单词读取应向后延伸一位其他并没有什么难题需要注意的是字符以及字符串判断也放入了这里面作字部分(由于字符和字符串开头的‘单引号和“双引号也算是实际意义上的界符)数字:最后是数字的识别首先识别数字直接进行if比较接着同字符串一样进入循环识别整个数字都存入整形数组。由于要存入常数表的应该是一个数而不是整形数组所以应做出一个变量用于计算置位大致思想就是用循环来将数组中的数乘数组的第一位先乘每循环一次增加数组下一位。将整数部分都识别完了后就要判断是否为小数或者科学计数法若ch为小数点就进入小数的判断部分小数部分从数组转变为小数的程序就是将上述的函数中的乘便为除然后再识别符号后面的数转化为整数将之前识别出来的数除或乘该整数次数的而后用数字转字符串函数存入二元式中二元式种类写一个常数种别码。运行截图语法分析器模块(负责人:宋世波)功能获取产生式自动求first和follow集合构建分析表构建分析栈通过查分析表进行语法分析输出动作序列LL文法解释:LL()分析法是指从左到右扫描、最左推导(LL)和只查看一个当前符号(括号中的)之意LL()分析法又称预测分析法与递归子程序法同属于自顶向下确定性语法分析方法 LL()分析法的基本要点有三:利用一个分析表登记如何选择产生式的知识利用一个分析栈记录分析过程此分析法要求文法必须是LL()文法。语法分析是编译中的第二阶段它的任务是识别和处理比单词更大的语法单位判断源程序在结构上是否正确。从形式上来说语法分析是对一个给定的字符串判断它是否为文法的一个句子。在我设计的语法分析器中直接采用LL()分析方法。当然由于本身文法为上下文无关文法所以纯LL并没有使用问题此外对于错误的识别该语法分析器可以输出错误信息。数据结构structpronode{*产生式节点*typeitcharsymbol}structproduct{*产生式数据结构*charvnpronodeitself}productc产生式是从文件中读入的也就是本语言的文法结构其中产生式结构的首点product为产生式左部pronode部分为右部。与实际产生式进行比较很容易知道这个数据结构所允许的任何产生式右部最多能容纳十个元素左部元素长度不超过十五。对于文法中的终结符和非终结符在递归子程序方法中非终结符直接转换为字符串终结符则是对应的Token但当调用LL()子程序时需要将非终结符和终结符都转换为string类型这样做的好处是统一格式之后便于进行压栈弹栈等操作但是会提高算法的时间复杂度属于以时间换空间用简单的数据类型便于提高程序的可读性。typedefstructNode*栈中元素节点*{charelementstructNode*pNext}NODE,*PNODEtypedefstructStack*堆栈包含栈顶和栈底*{PNODEpTopPNODEpBottom}STACK,*PSTACK这就是一个正常的堆栈格式唯一需要注意的是因为要与产生式进行入栈出栈所以元素是用字符串存储。流程图算法booltraverse(chartra,charcmp)*遍历终结符和非终结符表查看是否存在要加入元素*inttableprep(chartra,charcmp)*准备填表*voidinittable()*分析表的初始化*voidnor(intcmp)*填表*voidcyclefirst(inti)*查first集合*voidfirst(intx,inti,intlocal)*求first集合*voidfollow(inti,intx,intlocal)*求follow集合*voidinitproduct()*初始化产生式结构*voidgetselect(intn)*判断为求first或follow集合*voidtableend()*完成分析表*char*pop(PSTACKout)*获取栈顶元素用于比较*voidinistack(PSTACKbegin)*初始化分析栈*voidanalysis(intm,intn,PSTACKout)*分析栈进行匹配按分析表进行*voidgra(PSTACKbegin)*语法分析主体程序*voidbefore()*在开始运行前对所用文件进行清空重建*由于分析函数部分过多不采取完整讲述可以简单进行理解为由于需要遍历整张产生式表所以很容易知道first和follow函数(即求first集和follow集函数)采取的函数自递归当从其产生元式子出发后就必须遍历完整个产生式表得出结果同时与此传递一个产生式序号用于填表。Getselect是一个区分函数用于区分该产生式是否能推出空而决定是采用求first或求follow其中求follow函数部分允许调用求first集合这也是LL文法的实际求法模拟。Tableend则是根据上述操作获取的数字逐个的、顺序的形成属于该文法的分析表并作为一个全局变量二维数组存储留存用于马上的语法分析。LL()分析法是指从左到右扫描最左推导和只查看一个当前符号的意思。它属于自顶向下确定性语法分析方法。LL()分析方法有以下三个基本要点:⑴ 利用一个分析表登记如何选择产生式的知识⑵ 利用一个分析栈记录分析过程⑶ 此分析法要求文法必须是LL()文法。在分析的过程中我们将以下变换后的LL()文法归为LL()分析方法的范畴并且求出了它们对应的select集合(由于非终结符和终结符过多无法在文档中完全描述出分析表因此在此仅列出select集合LL()分析表只需根据集合填写即可):以下为完整的分析表:vnvtid(){}intfuncdeftypefactorexpdivifaccycleitemparastatestateinitrvaluestateclofuncblockstaclostatementfuncbloclooperacallstateparalistparacloparawhilecyclelogicexplogicoperacondistatenorfuncendcoutstatecinstatedoweie       vnvtfloatcharvoidstrnumberchfuncdeftypefactorexpdivifaccycleitemparastatestateinitrvaluestateclofuncblockstaclostatementfuncbloclooperacallstateparalistparacloparawhilecyclelogicexplogicoperacondistatenorfuncendcoutstatecinstatedoweie       vnvtstring*=funcdeftypefactorexpdivifaccycleitemparastatestateinitrvaluestateclofuncblockstaclostatementfuncbloclooperacallstateparalistparacloparawhilecyclelogicexplogicoperacondistatenorfuncendcoutstatecinstatedoweie       vnvt,while><==funcdeftypefactorexpdivifaccycleitemparastatestateinitrvaluestateclofuncblockstaclostatementfuncbloclooperacallstateparalistparacloparawhilecyclelogicexplogicoperacondistatenorfuncendcoutstatecinstatedoweie       >=<=ifelsereturncoutcin       每个产生式大括号中的内容便是该产生式的select集合。可以看出同一产生式select集合不相交即为LL()文法。根据上述集合即可构造出LL()分析表由于产生式数目较多LL()分析器主要由LL()分析表和LL()控制程序两部分构成:LL()分析表是存储文法select集合的知识表可通过预先设置的语法栈的栈顶符和当前扫描的单词来确定产生式的序号从而进行下一步判断或者压栈操作。其后的语法分析主函数便是根据上述所写的分析表获取要分析单词与堆栈区栈顶然后进入分析表按照分析表所写进行入栈出栈完成分析即认为语法无错误否则则认为有错误发现情况无法对应分析表时也认为是发生了错误。运行截图可以直观地看出LL()的分析过程可以看出对于一个稍微简单的文法LL()分析过程需要多步才能判断完全。至此LL()分析方法设计完成。符号表生成模块(负责人:孙何奇)功能构建活动记录表构建符号表构建函数表构建长度表添加活动记录添加变量表符号表预处理添加函数表添加参数表构建活动记录与变量表(二合一)符号表是在目标代码生成中不可以缺少的提供查询服务的表在其中记录了程序收集记录于使用的源程序的语法符号的类型、特征等相关信息信息集中反映了标识符的语义特征属性。在词法分析及语法在分析过程中不断积累和更新表中的信息并在词法分析到代码生成的各阶段按各自的需要从表中获取不同的属性信息。在本次课设中符号表的作用和地位是重要关键的。符号表是一个编译器的核心数据结构它代表了标识符的动态语义词典属于编译中语义分析的知识库。符号表中所登记的信息在编译的不同阶段都要用到对于一个多遍扫描的编译程序不同遍所用的符号表也往往各有不同因为每遍所关心的信息各有差异。符号表的组织方式也决定了未来处理符号表内容时的效率。我所设计的符号表生成器能够在定义标识符时把对应的语义信息填入符号表中当在语句中使用该标识符时通过查找相应的表项来判断该标识符是否存在且使用正确。符号表常见的功能有定义和重定义检查、类型匹配校验、数据的越界和溢出检查、值单元存储分配信息和函数的参数传递与校验。由于时间有限我设计的符号表系统只完成了上述功能中的一部分。数据结构在编译程序中符号表项的组织传统上采用三种构造方法:①线性组织②排列组织及二分法③散列组织线性表按符号扫描的顺序有序填入但在查询时效率较低排列表按首字符大小来填写符号表查询效率较高但填写时实现较复杂。因此散列表可以通过一定的散列函数来实现符号表的高效填写和查询。至此我们可以写出符号表总体的数据结构:charvariate={}*变量表*enumTYP{in,real,ch,b,default}*类型包括intfloat,char,bool型*enumCAT{f,con,t,d,v,vn,vf,default}*种类包括f函数c常量t类型d域名v变量vn换名形参vf赋值形参*enumADDR{PFINFL,LENL,VALL,default}*地址表包括函数表活动记录表*intidlocate*记录标识符在代码中首次出现的位置*structsymbol{*符号表*charnameTYPtypeCATkindADDRaddr}structpfinfl{*函数表*intlevelintoffintfnsymbolpara*参数表*intentry}structvall{*活动记录表采用链表结构*charnamecharnameintlowintupstructvall*next}vall*firstnode=newvallstructlenl{*长度表*charnameintlength}lenllengt符号表是标识符的动态语义词典属于编译中语义分析的知识库主要内容:⑴名字标识符源码用作查询关键字⑵类型该标识符的数据类型及其相关信息⑶种类该标识符在源程序中的语义角色⑷地址与值单元相关的一些信息在我设计的符号表生成器中填写阶段主要使用词法序列来实现符号表的动态填写。我将填写符号表的过程分为四个阶段:①明确当前符号表的作用域将作用域名称填入符号表集合。②填写当前作用域的符号表插入的动作主要在说明符子程序这是对普通变量的填写。③填写当前作用域内的数组类型由于数组类型相比于其他变量类型较为特殊需要单独考虑它的填写过程。④完成符号表的填写使当前作用域和临时变量回归到初始状态。由于函数体和主函数这四个阶段填写过程大致相同我只列出填写结构体符号表所实现的过程具体设计实现的流程图如下:流程图算法voidvalladd(vall*head,intt,intt,char*id,char*id){*添加活动记录*voidvallprint(vall*head){*打印活动记录表*voidfuncpro(pfinfl*function){*函数表预处理*voidtableadd(charidtable,char*cmp,intloc){*标识符表元素添加*voidfinshanalysis(){*完成符号表*运行截图至此符号表生成算法的设计就完成了。可以看出符号表的填写阶段一般是在变量函数和结构体的声明阶段在使用变量时符号表的作用主要是进行错误检测。中间代码生成模块(负责人:黄润华)功能构建语义栈重新导入二元式获取动作序列初始化四元式获取动作序列位置在已有动作序列的基础上生成四元式(自底向上)输出四元式四元式的预处理及优化中间代码是高级程序语言中各种语法成分的语义结构表示它介于源语言和目标语言之间。中间代码设置的目的是便于编译的后期处理(优化和目标代码生成)。因此生成四元式是制作一个编译器必不可少的一环。中间代码生成属于语义分析的阶段中间代码是高级程序语言中各种语法成分的语义结构表示它介于源语言和目标语言之间。设置中间代码有以下三点好处:便于进行与机器无关的代码优化工作。是编译程序改变目标机更容易。使编译程序的结构在逻辑上更为简单明确。以中间语言为界面编译前端和后端的接口更清晰。我设计的四元式生成器是在语法分析的基础上直接获取动作序列而后直接基于词法序列进行分析采用了自底向上的LR分析法对于每一个作用域都生成唯一的四元式结构体数组便于接下来中间代码的优化作用域和作用域之间的四元式序列互不干扰。数据结构structfourelem{*四元式结构*intidactcharidcharidtypetypetypetypecharid}structspo{*动作序列*charnamecharvaluefloatvalue}sposportcharactid={"","","*","",">","<",">=","<=","==","=","if","else","ie","while","do","we","return","cout","cin","#"}*枚举动作*intsem*语义栈*四元式是一种更接近目标代码的中间代码形式。由于这种形式的中间代码便于优化处理因此在目前许多编译程序中得到了广泛的应用。四元式实际上是一种“三地址语句”的等价表示。它的一般形式为:(op,arg,arg,result)其中op为一个二元(也可是一元或零元)运算符arg,arg分别为它的两个运算(或操作)对象它们可以是变量、常数或系统定义的临时变量名运算的结果将放入result中。四元式还可写为类似于PASCAL语言赋值语句的形式:result∶=argoparg需要指出的是每个四元式只能有一个运算符所以一个复杂的表达式须由多个四元式构成的序列来表示。例如表达式AB*C可写为序列T∶=B*CT∶=AT其中TT是编译系统所产生的临时变量。当op为一元、零元运算符(如无条件转移)时arg甚至arg应缺省即result∶=oparg或opresult对应的一般形式为:(op,arg,,result)或(op,,,result)在实际产生的四元式中op往往用一整型数表示(操作符的代码)它可能附带有不止一种属性。例如加运算可以分为定点加法和浮点加法两种我们可用不同的整数值区分这两种加法。至于四元式中运算对象arg、arg和结果域result它们可以是指向符号表中某项的指示字也可以是某个临时变量的序号因此在实际的翻译过程中还需要进行相应的查填符号表工作。四元式类型定义如上所述:其中idact为动作编号四元式中的每一个对象都用Token类型表示这样做的目的是利于四元式在机内的连续存储而后的ididid则很容易清楚其对应着四元式的后三项其中type和type为枚举类型这是为了再符号表生成之外确定好四元式的结构构成这样的好处就是在生成目标代码时会有一定方便。

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/47

编译原理课程设计报告(一个完整的编译器)

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利