编译原理课程设计

课程设计报告设计题目：一个简单文法编译器的设计与实现班级：计算机1302组长学号：20133823组长姓名：高思坦指导教师：肖桐设计时间：2015年12月设计分工组长学号及姓名：20133823高思坦分工：目标代码生成组员1学号及姓名：20133826李北分工：语法分析、中间代码生成组员2学号及姓名：20133822方秋生分工：词法分析翻译器组员3学号及姓名：20133839吴永琪分工：词法分析识别器组员4学号及姓名：20133832刘向甲分工：符号表管理I摘要现代计算机的程序很多都是用高级语言编写的，而这些高级语言计算机是无法识别的，因此需要将它们转变成计算机能识别的语言，此时就需要借助到编译程序。编译程序是一种翻译程序，它特指把某种高级语言（如C、Java、Pascal）翻译成具体计算机上的低级程序设计语言。编译程序是计算机系统软件最主要的组成部分之，也是用户最直接关系的工具之一。一个编译程序的可以划分为前端和后端。前端包括词法分析、语法分析、语义分析与中间代码生成三个阶段，后端包括优化、目标代码生成两个阶段，另外还有符号表的管理和错误处理贯穿整个过程。一个编译程序，既可以一个阶段一个阶段地对源程序进行分析，也可以前端只对源程序进行一遍分析，后端也只进行一遍分析。本课设实现了对C语言中的一部分功能的编译，包括算术逻辑表达式、if语句、while语句以及一维数组等。前端对源程序扫描一遍实现词法分析、语法分析、语义分析与中间代码生成三个阶段，后端进行目标代码生成，整个过程穿插符号表管理和错误处理。关键词：编译程序，前端，后端II目录摘要.......................................................I1概述....................................................12课程设计任务及要求......................................22.1设计任务..........................................22.2设计要求...........................................23算法与数据结构...........................................33.1算法的总体思想（流程）.............................33.2词法分析识别器模块.................................43.2.1功能.........................................43.2.2数据结构.....................................53.2.3算法.........................................93.3语法分析模块......................................113.3.1功能........................................113.3.2数据结构....................................123.3.3算法........................................163.4语义分析和中间代码生成模块........................303.4.1功能........................................303.4.2数据结构....................................313.4.3算法........................................333.5符号表模块........................................413.5.1功能........................................413.5.2数据结构....................................41III3.5.3算法........................................433.6目标代码生成模块..................................433.6.1功能........................................433.6.2数据结构....................................443.6.3算法........................................454程序设计与实现..........................................474.1程序流程图........................................474.2程序说明..........................................474.3实验结果..........................................505结论....................................................616参考文献................................................627收获、体会和建议........................................6211概述在计算机上执行一个高级语言程序一般要分为两步；第一步，把高级语言翻译成机器语言程序；第二步，运行所得的机器语言程序求得计算结果。编译程序就是将高级语言程序翻译成机器语言程序或汇编语言程序的工具。工作过程一般可以划分为五个阶段：词法分析、语法分析、语义分析和中间代码生成、优化、目标代码生成。前端包含词法分析、语法分析、语义分析和中间代码生成三个阶段，后端包含优化、目标代码生成两个阶段。词法分析的任务是对构成源程序的字符串进行分解和扫描，识别出一个个Token序列，并标上类别码以区分关键字、标识符、常数、变量、数组界符等。词法分析器用自动机实现，每读入一个字符，就进行状态转移，当转移到终止状态的时候一个Token就识别出来了。此外，词法分析还要进行常数处理、关键字和标识符的区分操作。语法分析在词法分析的基础上，根据语言的语法规则，确定整个输入串在语法上是否是正确的。分析方法有递归下降子程序分析法、LL(1)分析法、LR(0)分析法、简单优先分析法等。在语义分析和中间代码生成这一过程中，对语法分析所识别的各类语法范畴，要分析其含义，并以四元式的形式产生中间代码。优化的任务在于对中间代码进行加工变换以产生出更为高效的目标代码，主要进行常数合并、公共子表达式节省、删除无用赋值、循环优化等操作。目标代码生成的任务是把中间代码变换成特定机器上的低级语言代码，这一步需要考虑硬件系统结构、机器指令以及寄存器个数等情况，2将一中间代码程序段翻译成汇编语言或机器语言目标代码。此外，在这五个阶段当中，符号表的管理、错误处理要穿插在当中进行。本次课设将前端的三个阶段整合到一起，通过对输入的源程序扫描一遍的方式实现，入口为语法分析，使用递归下降子程序分析法。将词法分析器作为语法分析的子程序，当语法分析需要用到Token时，调用词法分析器识别出一个Token串，同时在语法分析的过程中插入语义动作，每识别完一定的Token串就能生成四元式。在后端则直接根据四元式生成目标代码。符号表用于存储变量以及检查是否有重定义、未定义的变量。在错误处理中，一旦发现错误，就进行输出并立即停止编译过程。2课程设计任务及要求2.1设计任务定义一个简单程序设计语言文法（包括变量说明语句、算术运算表达式、赋值语句；扩展包括逻辑运算表达式、If语句、While语句等）；扫描器设计实现；语法分析器设计实现；中间代码设计；中间代码生成器设计实现；目标代码生成。2.2设计要求1、在深入理解编译原理基本原理的基础上，对于选定的题目，以小组为单位，先确定设计方案；32、设计系统的数据结构和程序结构，设计每个模块的处理流程。要求设计合理；3、编程序实现系统，要求实现可视化的运行界面，界面应清楚地反映出系统的运行结果；4、确定测试方案，选择测试用例，对系统进行测试；5、运行系统并要通过验收，讲解运行结果，说明系统的特色和创新之处，并回答指导教师的提问；6、提交课程设计报告。3算法与数据结构3.1算法的总体思想（流程）对给定的一段源程序，先进行前端分析。前端包括词法分析、语法分析、语义分析和中间代码生成三个阶段，这三个阶段通过对输入的源程序扫描一遍的方式即可实现，词法分析器作为语法分析的子程序，当语法分析需要用到Token时，调用词法分析器识别出一个Token串，同时在语法分析的过程中插入语义动作，在进行语法分析的同时也能生成四元式。然后将生成的四元式交给后端进行目标代码生成。此外，符号表用来记录源程序中出现的变量，如果在分析的过程中出现错误，则进行错误处理，将哪一行出现的哪种错误输出。具体流程图如下：43.2词法分析模块3.2.1功能识别器：词法分析器中识别器的具体功能为识别单词的有限自动机。单词符号是一个程序语言的基本语法符号。程序语言的单词符号一般可分为下列4种。（1）关键字：由程序语言定义的具有固定亿的标识符。有时称这些标识符为保留字或基本字。（2）标识符：标示各种名字，如变量名，数组名，函数名等。（3）常数：程序中出现用来运算的数值，即以自身形态面对用户和系统。（4）界符：单字符界符：+,—,*,/,！,%等。双字符界符：=,=,==,!=,&&,||等。源程序前端（词法分析、语法分析、语义分析和中间代码生成）后端（目标代码生成）中间代码目标代码符号表管理错误处理5翻译器：根据有限自动机所识别出的对象，完成从单词传到单词的TOKEN串的翻译。输入源程序，对构成源程序的字符串进行分解和扫描，识别出一个个的单词或符号。具体实现为设计各单词的状态转换图，并为不同的单词设计种别码。3.2.2数据结构识别器关键字或标识符以字母开头，数值型常量以字母开头，字符型常量或字符串常量以’或”开头，其它的多以自身形态识别之。如何识别单词并寻找其可达状态，我们的方法是利用链表构建一个识别单词的有限自动机。定义自动机状态的结构体链表：typedefstructstate{characceptkey;intnextstate;structstate*next;}state;//自动机状态链表结点构建链表结点：typedefstructtokennode{tokento;structtokennode*next;6}tokennode;自动机图：71230313234668791011121314151617282930212223242526272829ll[ll|ddddd.‘‘““=====!&||&{{]{—小数整数指数字符字符串====!=&&||其余8翻译器共用体：unionextramessage{doublenum;//常数intsubscript;//数组下标};Token结构体：typedefstructtoken{chars[20];intcode;extramessageextra;}token;//token结构体charstore[20]；tokenKT[15]；tokenPT[25]；state*st[33]一个程序语言的关键字，运算符和界符都是确定的，一般只有几十个或上百个。而对于标识符或常数的使用都不加限制。词法分析器所输出的单词符号常常表示为二元式结构：（单词种别，单词符号的属性值）；相应的数据结构处理为：TokenKT[15]={{void,4},{char,5},{short,6},{in