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

编译原理程序设计报告一个简单文法的编译器的设计与实现 专业班级 ： 计算机1406班 组长姓名 ： 宋世波 组长学号 ： 20143753 指导教师 ： 肖 桐 2016年12月设计分工 组长学号及姓名：宋世波20143753分工：文法及数据结构设计词法分析语法分析（LL1）基于DAG的中间代码优化部分目标代码生成 组员1学号及姓名：黄润华20143740分工：中间代码生成(LR0)部分目标代码生成 组员2学号及姓名：孙何奇20143754分工：符号表组织部分目标代码生成摘要编译器是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序。编译是从源代码（通常为高阶语言）到能直接被计算机或虚拟机执行的目标代码（通常为低阶语言或机器语言）的翻译过程。一编译器的概述1.编译器的概念编译器是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序。编译器将原始程序作为输入，翻译产生使用目标语言的等价程序。源代码一般为高阶语言如Pascal、C+、Java 等，而目标语言则是汇编语言或目标机器的目标代码，有时也称作机器代码。2编译器的种类编译器可以生成用来在与编译器本身所在的计算机和操作系统（平台）相同的环境下运行的目标代码，这种编译器又叫做“本地”编译器。另外，编译器也可以生成用来在其它平台上运行的目标代码，这种编译器又叫做交叉编译器。交叉编译器在生成新的硬件平台时非常有用。“源码到源码编译器”是指用一种高阶语言作为输入，输出也是高阶语言的编译器。例如: 自动并行化编译器经常采用一种高阶语言作为输入，转换其中的代码，并用并行代码注释对它进行注释（如OpenMP）或者用语言构造进行注释（如FORTRAN的DOALL指令）。3.本编译器概述 编译程序的工作过程一般可以分为五个阶段：词法分析、语法分析、语义分析与中间代码产生、优化、目标代码生成。每一个阶段在功能上是相对独立的，它一方面从上一个阶段获取分析的结果来进行分析，另一方面由将结果传递给下一个阶段。由编译程序的五个阶段就对应了编译系统的结构，这五个对应阶段分为编译器的前段，中间代码以及后端。其中词法分析器利用超前搜索、状态转换等方法，将源程序转化成为一个一个的单词符号二元式。一般程序语言的单词符号包括关键字、运算符、常数、标识符和界符。语法分析器将这些单词符号作为输入，对它进行语法分析。语法分析采用LL1分析法，语法分析器把语法单元作为输入供语义分析器使用。在语法分析的同时进行语法分析，并产生一定的语义动作，来生成中间代码。优化和目标代码生成是针对某一种处理器而言的。代码优化是将语义分析生成的中间代码进行优化，产生执行效率更高的代码。目标代码生成最终生成可以在某种机器上运行的机器语言或者汇编语言。还要有符号表可供查询。在整个编译过程中还包括对表格的操作和对错误的处理，这些也都是非常重要的环节。环境：编译器整体全部使用visual studio2015编写目标代码在8086指令集机器上运行关键词：编译原理，前端，中间代码生成，后端，目录设计分工2摘要31. 概 述72. 课程设计任务及要求92.1 设计任务92.2 设计要求102.3设计的文法结构113. 算法及数据结构173.1 算法的总体思想（流程）173.2 词法分析器模块183.2.1 功能183.2.2 数据结构193.2.3 流程图203.2.4 算法203.2.5 运行截图223.3 语法分析器模块233.3.1 功能233.3.2 数据结构243.3.3 流程图253.3.4 算法263.3.5 运行截图333.4符号表生成模块343.4.1 功能343.4.2 数据结构353.4.3 流程图373.4.4 算法383.4.5 运行截图393.5中间代码生成模块393.5.1 功能403.5.2 数据结构403.5.3 流程图433.5.4 算法433.5.5 运行截图443.6中间代码优化模块443.6.1 功能443.6.2 数据结构453.6.3 流程图463.6.4 算法473.6.5运行截图493.7目标代码生成模块503.7.1 功能503.7.2 数据结构513.7.3 流程图513.7.4 算法523.7.5 运行截图54这里不得不提到目标代码生成中存在的一些问题，554. 程序设计与实现584.1 程序说明584.2 实验结果615. 结论635.1组长：宋世波635.2组员：孙何奇645.3组员：黄润华646. 收获、体会和建议。666.1组长：宋世波666.2组员：孙何奇666.3组员：黄润华677.附录69源代码：697.1可执行文件链接698、参考文献701. 概 述本程序实现的数据类型有整型（int）、浮点型（float）、char（字符型）、字符串型（string），同时在最后的目标代码生成部分允许出现布尔（bool）类型，实现的操作有if，else以及while循环，和输入输出语句，能做到直接生成目标代码并运行。做到了类型检查和重定义的判断，同时也有优化部分。词法分析部分构建得到的词法序列为二元式，二元式由两部分组成，其种别码和类型组成，其中关键字和界符记录其数字，用到时只需查其对应的关键字表和界符表即可，而字符类型、字符串类型、数字类型、以及标识符类型的值一律用字符串存储，其中数字类型存储时对其使用atoi和itoa函数进行数字转字符串即可，要使用到其数字时只需要将对其使用字符串转数字函数再获得即可。语法分析部分采用的是LL1分析方法，这是一种自上而下的语法分析法，又称为预测分析法，语法分析器部分实现了自动求first集合和follow集合，采用的是递归程序获得select集合，在实现对产生式完全扫描以后，便可以获得一张完整的分析表，表中标注了是否为预测以及对应的产生式序列，而后进行语法分析，通过于获得的分析表进行比对，进行入栈出栈，匹配到相同的则认为匹配成果，当文法匹配成功，同时单词也匹配成功的时候，认为语法分析完成，语法无错误，否则报错。在符号表生成部分，程序对获取的单词序列中的标识符进行再分析，确定每一个标识符的存储范围，同时从此之中获取函数的参数表，函数表部分，构建出编译器全局可用的活动记录表，以供目标代码生成使用，同时也为编译器增添新内容做准备。中间代码生成部分，在此之前需注意到，由于再语法分析部分已经生成了一个具体可理解的动作序列，所以中间代码生成部分的所用方法并非语法制导，其本身也与语法分析相割裂开来，中间代码生成采取的是自底向上进行分析，不过是基于单词序列进行的分析，其操作等于是使用已获得的伪动作序列，与源程序去作比较，找出伪动作序列的实际含义，将其顺序填好，最后便完成了整个中间代码（四元式）的生成，并将其重新输出到文件中。中间代码优化部分是对填装完毕的中间代码的再处理，也就是减少无用式子，给目标代码的生成提供便利，先进行基本块划分，而后采取的是DAG图优化，即无环有向图优化，顺序是构建DAG图（无环有向图），减少无用分支，或删改部分同义分支，完成DAG图改造后便又重新由树组装四元式，组装好的四元式又再次重新输出到文件中。目标代码生成部分较长，也并不仅仅包含目标代码生成部分，在这个部分文件中，同时需要对前述获得的符号表，中间代码进行再处理，以得到符号目标代码生成所用的符号表和中间代码，再进行预处理完成之后，具体为根据四元式动作，按顺序依次生成目标代码，需要依据不同的四元式动作每个采取不同的操作方法，生成相应目标代码。测试部分采用的emu8086软件，这个软件支持的指令集为8086指令集，由于64位机器上对汇编的支持并不算好，所以在8086机上最后进行的是对目标代码的正确性检验以及运行，运行通过且符合源程序实际操作即认为编译器任务完成。2. 课程设计任务及要求2.1 设计任务1.一个简单文法的编译器前端的设计与实现定义一个简单程序设计语言文法（包括变量说明语句、算术运算表达式、赋值语句；扩展包括逻辑运算表达式、If语句、While语句等）；扫描器设计实现；语法分析器设计实现；中间代码设计；中间代码生成器设计实现。 2.难度相当的自选题目, 如:一个简单文法的编译器后端的设计与实现。一个简单文法的编译器的设计与实现。自选一个感兴趣的与编译原理有关的问题加以实现以下为本组选择部分：一个简单文法的编译器的设计与实现。1. 定义一个简单程序设计语言文法（包括变量说明语句、算术运算表达式、赋值语句；扩展包括逻辑运算表达式、If语句、While语句等）；2. 扫描器设计实现3. 语法分析器设计实现；4. 符号表设计5. 符号表生成器设计实现6. 中间代码设计；7. 中间代码生成器设计实现。8. 中间代码优化9. 中间代码优化实现10. 目标代码设计11. 目标代码生成器设计实现2.2 设计要求1、在深入理解编译原理基本原理的基础上，对于选定的题目，以小组为单位，先确定设计方案；2、设计系统的数据结构和程序结构，设计每个模块的处理流程。要求设计合理；3、编程序实现系统，要求实现可视化的运行界面，界面应清楚地反映出系统的运行结果；4、确定测试方案，选择测试用例，对系统进行测试；5、运行系统并要通过验收，讲解运行结果，说明系统的特色和创新之处，并回答指导教师的提问；6、提交课程设计报告。以下为本组设计要求：给出一个源程序文件，作为编译器前端的输入，输出相关编译阶段的运行结果。词法分析阶段：Token序列；关键字表、界符表、符号表系统。语法分析阶段：LL1型产生式、分析表、语法分析所用栈符号表生成阶段：符号表系统中间代码生成阶段：四元式序列；符号表系统。中间代码优化阶段：四元式序列、DAG图、优化完成的四元式序列目标代码生成阶段：符号表系统、四元式序列、目标代码(8086指令集)2.3设计的文法结构产生式中文对照:1. - ( ) 2. -int|float|char|void|$3. - ( ) | | |4. - 5. - 6. - * | / | $ 7. - + | - | $ 8. - | $ 9. - |10. - = | $ 11. - 12. - , | $ 13. - 14. - | $ 15. - ;16. - | | | | $ 17. - 18. - = ; | ( ) ; 19. - 20. - , | $ 21. - | | 22.-while()23. - 24. - | = |=|= 25. - if ( ) 26. - else | $ 27. - return ; 28.-cout ;|cout ;|cout ;29.-cin;产生式如下：funcdef%type&id&(¶state&)&funcblock&|(¶list&)&;()123456789101112131415161718字符表Ch字符串表st3. 算法及数据结构3.1 算法的总体思想（流程）算法总体思想文字解释如下：1. 从文件中读取代码，调入词法分析，生成词法序列。2. 而后将词法序列传递给语法分析器，语法分析器从文件中读入产生式，自动产生first集和follow集，构建出完整的分析表，而后与得到的词法序列进行比较，吮吸进行语法分析，按照分析表查得产生式进行入栈出栈，完成LL1语法分析的整个过程。3. 符号表继续使用词法序列，不依赖于语法分析而直接构建符号表，依据词法中的标识符直接构建函数表、参数表、符号表和活动记录表，并对于其后的目标代码生成产生作用。4. 中间代码生成模块使用语法分析过程中所获得的伪动作序列，同时依靠获得的词法分析序列，逐个进行比对，同时将标识符依次入栈，需要时取出，通过完整栈区的出栈入栈实现整个中间代码（四元式）的填写。5. 中间代码优化模块获取前述过程中所生成的四元式文件，而后依托于四元式构建DAG图，由产生的DAG图采用教材ppt所述方法按节点进行优化，直接产生优化后的DAG图并生成优化后的四元式填装回文件中。6. 目标代码生成部分直接提取之前编译器部分所获得的四元式和符号表，依据其成果直接构建目标代码（汇编代码，8086指令集），同时在此其中进行类型检查，重定义等，完成语义分析。3.2 词法分析器模块（负责人：宋世波）3.2.1 功能1.获取待处理的源代码2.生成二元式序列3.采用DFA和自动机实现二元式的填写4.将获得的二元式输入到文件中 词法分析过程是将字符序列转换为Token序列的过程。此阶段的任务是从左到右依次扫描源程序中的字符，即对构成字符流进行扫描然后根据构词规则识别Token。设计的词法分析器能相对完善地构造出不同的单词，用二元式的形式存储，简显易懂，并将新的标识符单词填入变脸表当中，实现在计算机内单词序列的统一存储。3.2.2 数据结构enum styleI,C,K,P,Ch,St,def;/*枚举种类*/static char *keyword18 = int,float,char,void,if,else,switch,case,for,do,while,continue,break,default,sizeof,return,cout,cin ;/*关键字表*/static char *delimiters18 = =,=ifelsereturncoutcin000000000000000000000000000000000001616000001919000000000000000000000000000000000000000000000000031031313100000000035036373800000000000000000000000000000000000000000000000005455000000056000000585758585800005900000006000000006100000000063063636300640646464每个产生式大括号中的内容便是该产生式的select集合。可以看出同一产生式select集合不相交即为LL(1)文法。根据上述集合即可构造出LL(1)分析表，由于产生式数目较多， LL(1)分析器主要由LL(1)分析表和LL(1)控制程序两部分构成：LL(1)分析表是存储文法select集合的知识表，可通过预先设置的语法栈的栈顶符和当前扫描的单词来确定产生式的序号，从而进行下一步判断或者压栈操作。其后的语法分析主函数便是根据上述所写的分析表，获取要分析单词，与堆栈区栈顶然后进入分析表，按照分析表所写进行入栈出栈，完成分析即认为语法无错误，否则则认为有错误，发现情况无法对应分析表时也认为是发生了错误。3.3.5 运行截图可以直观地看出LL(1)的分析过程，可以看出对于一个稍微简单的文法，LL(1)分析过程需要多步才能判断完全。至此，LL(1)分析方法设计完成。3.4符号表生成模块（负责人：孙何奇）3.4.1 功能1. 构建活动记录表2. 构建符号表3. 构建函数表4. 构建长度表5. 添加活动记录6. 添加变量表7. 符号表预处理8. 添加函数表9. 添加参数表10. 构建活动记录与变量表（二合一） 符号表是在目标代码生成中不可以缺少的提供查询服务的表，在其中记录了程序收集，记录于使用的源程序的语法符号的类型、特征等相关信息，信息集中反映了标识符的语义特征属性。在词法分析及语法在分析过程中不断积累和更新表中的信息，并在词法分析到代码生成的各阶段，按各自的需要从表中获取不同的属性信息。在本次课设中，符号表的作用和地位是重要关键的。符号表是一个编译器的核心数据结构，它代表了标识符的动态语义词典，属于编译中语义分析的知识库。符号表中所登记的信息在编译的不同阶段都要用到，对于一个多遍扫描的编译程序，不同遍所用的符号表也往往各有不同，因为每遍所关心的信息各有差异。符号表的组织方式也决定了未来处理符号表内容时的效率。我所设计的符号表生成器能够在定义标识符时把对应的语义信息填入符号表中；当在语句中使用该标识符时，通过查找相应的表项来判断该标识符是否存在且使用正确。符号表常见的功能有定义和重定义检查、类型匹配校验、数据的越界和溢出检查、值单元存储分配信息和函数的参数传递与校验。由于时间有限，我设计的符号表系统只完成了上述功能中的一部分。 3.4.2 数据结构在编译程序中，符号表项的组织传统上采用三种构造方法：线性组织排列组织及二分法散列组织线性表按符号扫描的顺序有序填入，但在查询时效率较低；排列表按首字符大小来填写符号表，查询效率较高，但填写时实现较复杂。因此，散列表可以通过一定的散列函数来实现符号表的高效填写和查询。至此，我们可以写出符号表总体的数据结构：char variate1615 = ;/*变量表*/enum TYPin,real,ch,b,default1;/*类型，包括int，float,char,bool型*/enum CATf,con,t,d,v,vn,vf,default2;/*种类，包括f函数，c常量，t类型，d域名，v变量，vn换名形参，vf，赋值形参*/enum ADDRPFINFL,LENL,VALL,default3;/*地址表，包括函数表，活动记录表*/int idlocate16;/*记录标识符在代码中首次出现的位置*/struct symbol /*符号表*/char name15;TYP type;CAT kind;ADDR addr;struct pfinfl /*函数表*/int level;int off;int fn;symbol para5;/*参数表*/int entry;struct vall /*活动记录表，采用链表结构*/char name15;char name115;int low;int up;struct vall *next;vall *firstnode=new vall;struct lenl /*长度表*/char name10;int length;lenl lengt10;符号表是标识符的动态语义词典，属于编译中语义分析的知识库；主要内容： 名字 标识符源码，用作查询关键字； 类型 - 该标识符的数据类型及其相关信息； 种类 - 该标识符在源程序中的语义角色； 地址 - 与值单元相关的一些信息；在我设计的符号表生成器中，填写阶段主要使用词法序列，来实现符号表的动态填写。我将填写符号表的过程分为四个阶段：明确当前符号表的作用域，