编译基本原理课程规划设计报告(一个完整编辑的编译器).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.<函数块闭包> -> <赋值函数> <函数块闭包> | <while循环> <函数块闭包> | <条件语句> <函数块闭包> | <函数返回> <函数块闭包> |<cout语句><函数块闭包>|<cin语句><函数块闭包>| $ 17.<赋值函数> -> <标识符> <赋值或函数调用> 18.<赋值或函数调用> -> = <右值> ; | ( <参数列表> ) ; 19.<参数列表> -> <参数> <参数闭包> 20.<参数闭包> -> , <参数> <参数闭包> | $ 21.<参数> -> <标识符> | <数字> | <字符串> 22.<While循环>->while(<逻辑表达式>)<函数块>23.<逻辑表达式> -> <表达式> <逻辑运算符> <表达式> 24.<逻辑运算符> -> < | > | = |>=|<= 25.<条件语句> -> if ( <逻辑表达式> ) <函数块> <否则语句> 26.<否则语句> -> else <函数块> | $ 27.<函数返回> -> return <因式> ; 28.<cout语句>->cout<< <标识符>|cout<< <数字>|cout<< <字符>29.<cin语句>->cin>><标识符>产生式如下：funcdef%type&id&(&parastate&)&&funcblock&|(&paralist&)&()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 = ">=","<=","=","=",">","<","+","-","*","/","","",",","","(",")" ,"",""/*界符表*/char variate1610 = ;/*变量表*/static struct twoele /*二元式数据结构*/style kind;char value125;int value2; 二元式包含三项，但实际使用时只会用到其中两项，单词种类的不同决定了其对应有不同的处理方式，kind用来存放种类，value1和value2都是用来存储单词所含值的，相对于不同类单词有不同处理方式。而其中kind所可为的值以及在上面数据结构中相应的有所列出的，对应查较即可。具体分配如下，当单词为关键字或者界符时，使用的是kind和value2项，即value2存储对应固定表中单词所对序列。而当单词为其他时，即单词为字符、字符串、标识符或者数字时，采取将单词直接字符串化直接存储其值，为数字时调用库函数将其字符化，取出时候按照其相应种别码采取不同的取出方式。static twoele TOKEN1000;/*词法序列（二元式结构）*/3.2.3 流程图3.2.4 算法static void init_twoele(twoele*tok) /*初始化二元式，同时将变量表初始化*/int tra(char*cmp) /*查询获得单词是否为关键字，是则返回关键字序号*/void addvar(char*cmp) /*加入变量表*/void prep(char ch) /*预处理，过滤注释*/static void scanner() /*词法扫描*/ 在词法分析之前有一段的注释处理部分，其相应方案是在遇到/符时即进入注释处理，而后再次遇到/符时候认为离开注释处理部分，但有所控制，若较长范围内并未再遇到/符则跳出自动机，认为/符号就是一个单纯的界符，由于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循环结束后需要在字符数组的最后一位后加上0。识别完毕后就需要判断该字符串到底是标识符还是关键字了，关键字个数是固定的，挨个匹配就可以了，界符：判断方法简单粗暴，直接switch即可，不过要注意比如=这种需要多判一次，即单词读取应向后延伸一位，其他并没有什么难题，需要注意的是，字符以及字符串判断也放入了这里面作字部分（由于字符和字符串开头的单引号和“双引号也算是实际意义上的界符）数字：最后是数字的识别，首先，识别数字直接进行if比较，接着同字符串一样进入循环识别整个数字，都存入整形数组。由于要存入常数表的应该是一个数而不是整形数组，所以应做出一个变量用于计算置位，大致思想就是用循环来将数组中的数乘10，数组的第一位先乘10，每循环一次增加数组下一位。将整数部分都识别完了后就要判断是否为小数或者科学计数法，若ch为小数点就进入小数的判断部分，小数部分从数组转变为小数的程序就是将上述的函数中的乘便为除，然后再识别符号后面的数，转化为整数，将之前识别出来的数除或乘该整数次数的10，而后用数字转字符串函数存入二元式中，二元式种类写一个常数种别码。3.2.5 运行截图3.3 语法分析器模块（负责人：宋世波）3.3.1 功能1.获取产生式2.自动求first和follow集合3.构建分析表4.构建分析栈5.通过查分析表进行语法分析6.输出动作序列LL1文法解释：LL(1)分析法是指从左到右扫描、最左推导(LL)和只查看一个当前符号（括号中的 1）之意； LL(1)分析法又称预测分析法，与递归子程序法同属于自顶向下确定性语法分析方法; LL(1) 分析法的基本要点有三：1 利用一个分析表，登记如何选择产生式的知识；2 利用一个分析栈，记录分析过程；3 此分析法要求文法必须是 LL(1)文法。语法分析是编译中的第二阶段，它的任务是识别和处理比单词更大的语法单位，判断源程序在结构上是否正确。从形式上来说，语法分析是对一个给定的字符串，判断它是否为文法的一个句子。在我设计的语法分析器中，直接采用LL(1)分析方法。当然由于本身文法为上下文无关文法，所以纯LL1并没有使用问题，此外，对于错误的识别，该语法分析器可以输出错误信息。3.3.2 数据结构struct pronode /*产生式节点*/type it;char symbol15;struct product /*产生式数据结构*/char vn15;pronode itself10;product c100;产生式是从文件中读入的，也就是本语言的文法结构，其中产生式结构的首点product为产生式左部，pronode部分为右部。与实际产生式进行比较，很容易知道这个数据结构所允许的任何产生式右部最多能容纳十个元素，左部元素长度不超过十五。对于文法中的终结符和非终结符，在递归子程序方法中非终结符直接转换为字符串，终结符则是对应的Token，但当调用LL(1)子程序时，需要将非终结符和终结符都转换为string类型，这样做的好处是统一格式之后便于进行压栈弹栈等操作，但是会提高算法的时间复杂度，属于以时间换空间，用简单的数据类型便于提高程序的可读性。typedef struct Node/*栈中元素节点*/char element15;struct Node *pNext;NODE, *PNODE;typedef struct Stack/*堆栈，包含栈顶和栈底*/PNODE pTop;PNODE pBottom;STACK, *PSTACK; 这就是一个正常的堆栈格式，唯一需要注意的是因为要与产生式进行入栈出栈，所以元素是用字符串存储。3.3.3 流程图3.3.4 算法bool traverse(char tra10015, char cmp15) /*遍历终结符和非终结符表，查看是否存在要加入元素*/int tableprep(char tra10015, char cmp15) /*准备填表*/void inittable() /*分析表的初始化*/void nor(int cmp) /*填表*/void cyclefirst(int i) /*查first集合*/void first(int x1,int i,int local) /*求first集合*/void follow(int i,int x1,int local) /*求follow集合*/void initproduct() /*初始化产生式结构*/void getselect(int n) /*判断为求first或follow集合*/void tableend() /*完成分析表*/char* pop(PSTACK out) /*获取栈顶元素用于比较*/void inistack(PSTACK begin) /*初始化分析栈*/void analysis(int m,int n, PSTACK out) /*分析栈进行匹配，按分析表进行*/void gra(PSTACK begin) /*语法分析主体程序*/void before() /*在开始运行前对所用文件进行清空重建*/ 由于分析函数部分过多，不采取完整讲述，可以简单进行理解为由于需要遍历整张产生式表，所以很容易知道first和follow函数（即求first集和follow集函数）采取的函数自递归，当从其产生元式子出发后就必须遍历完整个产生式表得出结果，同时与此传递一个产生式序号用于填表。 Getselect是一个区分函数，用于区分该产生式是否能推出空而决定是采用求first或求follow，其中求follow函数部分允许调用求first集合，这也是LL1文法的实际求法模拟。 Tableend则是根据上述操作获取的数字逐个的、顺序的形成属于该文法的分析表，并作为一个全局变量二维数组存储，留存用于马上的语法分析。LL(1)分析法是指从左到右扫描，最左推导和只查看一个当前符号的意思。它属于自顶向下确定性语法分析方法。LL(1)分析方法有以下三个基本要点： 利用一个分析表，登记如何选择产生式的知识； 利用一个分析栈，记录分析过程； 此分析法要求文法必须是 LL(1)文法。在分析的过程中，我们将以下变换后的LL(1)文法归为LL(1)分析方法的范畴，并且求出了它们对应的select集合(由于非终结符和终结符过多，无法在文档中完全描述出分析表，因此在此仅列出select集合，LL(1)分析表只需根据集合填写即可)：以下为完整的分析表：vn/vtid()intfuncdef000001type000002factor870000exp12120000divi13130000faccycle0016000item0019000parastate200210020state23000022init0025000rvalue26260000stateclo0028000funcblock29000029staclo310003130statement32000032funcbloclo33000390opera4000000callstate0420000paralist4300000paraclo0045000para4600000whilecycle000000logicexp50500000logicopera000000condistate000000nor58000580funcend000000coutstate000000cinstate000000do0006200we63000630ie64000640vn/vtfloatcharvoidstrnumberchfuncdef111100type345600factor0000910exp00001212divi00001313faccycle000000item000000parastate2020202000state2222222200init000000rvalue00002626stateclo000000funcblock2929292900staclo3030303000statement3232323200funcbloclo000000opera000000callstate000000paralist0000430paraclo000000para0000470whilecycle000000logicexp00005050logicopera000000condistate000000nor000000funcend000000coutstate000000cinstate000000do000000we000000ie000000vn/vtstring*/+-=funcdef000000type000000factor1100000exp1200000divi1300000faccycle0141516160item00017180parastate000000state000000init0000024rvalue2600000stateclo000000funcblock000000staclo000000statement000000funcbloclo000000opera000000callstate0000041paralist43000