编译原理课程设计报告简单文法的编译器的设计与实现

1、提供全套毕业论文，各专业都有课 程 设 计 报 告 设计题目：简单文法的编译器的设计与实现班 级：计算机1206组长学号：20123966组长姓名：指导教师：设计时间：2014年12月 摘 要 编译原理是计算机科学与技术专业一门重要的专业课, 它具有很强的理论性与实践性，目的是系统地向学生介绍编译系统的结构、工作原理以及编译程序各组成部分的设计原理和实现技术，在计算机本科教学中占有十分重要的地位。计算机语言之所以能由单一的机器语言发展到现今的数千种高级语言，就是因为有了编译技术。编译技术是计算机科学中发展得最迅速、最成熟的一个分支，它集中体现了计算机发展的成果与精华。  本

2、课设是词法分析、语法分析、语义分析的综合，外加上扩展任务中间代码的优化和目标代码的生成，主要是锻炼学生的逻辑思维能力，进一步理解编译原理的方法和步骤。关键词：编译原理，前端，目标代码，后端 目 录摘要.3 1. 概述.6 2. 课程设计任务及要求.8 2.1 设计任务.8 2.2 设计要求.9 3. 算法及数据结构.10 3.1算法的总体思想.10 3.2 词法分析器模块.11 3.2.1 功能.11 3.2.2 数据结构.11 3.2.3 算法.12 3.3 语法分析器模块.13 3.3.1功能.13 3.3.2 数据结构.13 3.3.3算法.14 3.4 中间代码产生器模块.24 3.4

3、.1 功能.24 3.4.2 数据结构.24 3.4.3 算法.25 3.5 优化器模块.27 3.5.1 功能.27 3.5.2 数据结构.27 3.5.3 算法.283.6 目标代码生成器模块.30 3.6.1功能.30 3.6.2 数据结构.30 3.6.3 算法.31 4. 程序设计与实现.32 4.1 程序流程图.32 4.2 程序说明.33 4.3 实验结果.355. 结论.426. 参考文献.437. 收获、体会和建议.44 1 概述 在计算机上执行一个高级语言程序一般要分为两步；第一步，用一个编译程序把高级语言翻译成机器语言程序；第二步，运行所得的机器语言程序求得计算结果。在学

4、习编译原理课程过程中，逐渐掌握各章节构造编译程序的基本理论，并能独立完成词法分析器、语法分析器和语义分析器实验，在基本实验完成的基础上，逐步完成课程设计。针对自己的理解和学习，实现一个小编译器括符号表的构造。 编译程序的工作过程一般可以划分为五个阶段：词法分析、语法分析、语义分析和中间代码产生、优化、目标代码生成。 第一阶段，词法分析。词法分析的任务是：输入源程序，对构成源程序的字符串进行分解和扫描，识别出一个个的单词或符号。我们设计了符号表，包括名字栏和信息栏，其中名字栏作为关键字，根据给定的名字，在符号表中查找其信息。如果该名字在符号表中不存在，则将其加入到符号表中，否则返回指向该名字的指

5、针，从符号表中删除给定名字的表项，并且设计了词法分析器，具体实现为设计各单词的状态转换图，并为不同的单词设计种别码。将词法分析器设计成供语法分析器调用的子程序。词法分析器具备预处理功能。将不翻译的注释等符号先滤掉，只保留要翻译的符号串，即要求设计一个供词法分析调用的预处理子程序；，能够拼出语言中的各个单词，将拼出的标识符填入符号表， 返回识别单词或符号的种别码和 属性值。 第二阶段，语法分析。在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位。通过语法分析，确定整个输入串是否构成语法上正确的“程序”。我们实现了语法分析器，能够使用预测分析法、递归下降分析

6、法、算符优先分析法、SLR分析法实现对表达式、各种说明语句、控制语句进行语法分析。 第三阶段，语义分析和中间代码产生。对语法分析所识别的各类语法范畴，分析其含义，并进行初步翻译(产生中间代码）。这一阶段包括两个方面的工作。首先，对每种语法范畴进行静态语义检查。如果语义正确，则依循语言的语义规则进行中间代码的翻译。 第四阶段，优化。优化的任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效的目标代码。例如公共子表达式的提取、循环优化、删除无用代码。 第五阶段，目标代码生成，把中间代码变换成特定机器上的低级语言代码，有赖于硬件系统结构和机器指令含义来实现最后的翻译。在能完成指定

7、寄存器个数的情况下将一中间代码程序段翻译成汇编语言目标代码。 通过对编译器的设计实现，一方面再次熟悉了c语言的编程方法及思想，另一方面加深了而对所学编译知识的掌握和理解，也深刻的理解了编译器的思想和实现方法；从词法分析到语法分析，再到语义分析，整个独立而又紧密联系的环节，紧紧相扣，整体的实现理解的更加透彻。不过由于编译程序本身涉及到词法分析、语法分析、代码生成、错误恢复和优化等诸多模块，要在实验中做到面面俱到不太可能，所以本编译器不可避免的会存在各种问题，但作为一个具有基本功能的、可扩充的系统，完全达到了巩固编译原理的理论知识，并将其运用于实践的目的。 2 课程设计任务及要求2.1 设计任务任

8、务内容：定义一个简单程序设计语言文法（包括变量说明语句、算术运算表达式、赋值语句；扩展包括逻辑运算表达式、If语句、While语句等）；扫描器设计实现；语法分析器设计实现；中间代码设计；中间代码生成器设计实现；中间代码优化；生成目标代码。 分析完任务内容，我们制定出一套满足老师要求的语句的文法结构，具体内容如下（其中“？”代表空产生式）：程序->void main ()函数体函数体->变量声明语句 函数体|赋值语句 函数体|if(表达式)函数体else函数体函数体|while(表达式)函数体 函数体|?变量声明语句->类型 标识符 变量声明语句_1 ;类型->int |

9、char |bool变量声明语句_1->,标识符 变量声明语句_1 |=表达式 变量声明语句_1|?赋值语句->标识符=表达式;表达式->算数表达式 逻辑表达式逻辑表达式-> >=算数表达式|<=算数表达式|=算数表达式|and 算数表达式|or 算数表达式|not 算数表达式|?（此处的代表可选）算数表达式（这个地方直接写出老师上课讲授的形式）：E->T E1E1->+ T E1|- T E1|?T->F T1T1->* F T1|/ F T1|?F->标识符常数|(E)这个文法满足老师的要求，但是也存在一些不足，比如变量类型

10、中没有处理实数，数组和结构体以及if语句和while语句后必须有大括弧匹配。2.2 设计要求 1、在深入理解编译原理基本原理的基础上，对于选定的题目，以小组为单位，先确定设计方案；2、设计系统的数据结构和程序结构，设计每个模块的处理流程。要求设计合理；3、编程序实现系统，要求实现可视化的运行界面，界面应清楚地反映出系统的运行结果；4、确定测试方案，选择测试用例，对系统进行测试；5、运行系统并要通过验收，讲解运行结果，说明系统的特色和创新之处，并回答指导教师的提问； 3 算法及数据结构 3.1 算法的总体思想 词法分析器又称为扫描器，它的任务就是对输入的源程序进行词法分析输出单词符号供语法分析使

11、用，语法分析器简称分析器，对单词符号串进行语法分析，根据语法规则进行推导，识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。语义分析与中间代码产生器，按照语义规则对语法分析器推导出的语法单位进行语义分析并把它们翻译成一定形式的中间代码。优化器就是对中间代码进行优化处理。目标代码生成器，把中间代码翻译成目标程序。符号表用来登记源程序中出现的变量及其属性。另外，如果源程序有错误，编译发现错误，把有关错误信息报告给用户，即出错处理。流程图如下： 出 错 处 理 符 号 表 词法分析器 源程序 语法分析器 单词符号 优化器 语义分析及中间代码产生器 语法单位 目标代码生成器 中间代码 中

12、间代码 目标代码3.2 词法分析器模块 3.2.1 功能 词法分析器功能室输入源程序，输出单词符号。单词符号是一个程序语言的基本语法符号。程序语言的单词符号一般可分为下列5种。 （1）关键字 是由程序语言定义的具有固定亿的标识符。有时称这些标识符为保留字或基本字。 （2）标识符 用来标示各种名字，如变量名，数组名，函数名等。 （3）常数 程序中出现用来运算的数值 （4）运算符 我们所定义的文法包括+，-，*，/算术运算符，还有and，or，not，>=，>，<，<=，=逻辑运算符。 （5）界符 程序中用来分割的符号。 3.2.2 数据结构 一个程序语言的关键字，运算符和

13、界符都是确定的，一般只有几十个或上百个。而对于标识符或常数的使用都不加限制。词法分析器所输出的单词符号常常表示为二元式结构：（单词种别，单词符号的属性值）；相应的数据结构处理为如下表示： char*KeyWords="main","bool","int","char","void","if","else","while"/关键字kchar Definition='', '', '', &#

14、39;' , '(', ')' , '+' , '-' , '*' , '/' , '=' , '>','<', '',',',''','"'/界符表pchar *ID1000; int IdNum=0;/标识符表iint Cons1000; int ConsNumber=0;/算数常量表类码ctypedef struct TokenTypechar

15、code;int value;TokenType;/单词符号的二元式结构 开始 3.2.3 算法结束符符 界符算术常数关键字标识符 调用识别器 I.TOKENK.TOKEN n y查到 查KT表查填IT表 y nC.TOKEN查填CT表常数处理 y n P.TOKEN查到查PT表 y y n n 结束 y3.3语法分析器模块 3.3.1功能语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器在编译程序中的地位也是非常重要。语言的语法结构是用上下文无关文法描述的。因此，语法分析器的工作本质上就是按照文法的产生式，识别输入

16、符号串是否为一个句子。按照语法分析树的建立方法，可以粗略的把语法分析方法分成两类，一类是自上而下的分析方法，另一类是自下而上的分析方法。在本次的课程设计中使用的是自上而下的分析方法中的递归下降分析法，用这种分析法的好处是，直观易懂，便于表示做递归和因子提取。自上而下的分析方法的主旨就是，对任何输入串，试图用一切可能的办法。从文法开始符号出发，自上而下的为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。这种方法本质上就是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。3.3.2 数据结构对于语法分析过程而言，其处理的数据是来自于Token序列，是词法分析的产物。语法分析的任务就是

17、识别和处理比单词更大的语法单位，比如：程序设计语言中的表达式、各种说明和语句乃至全部程序。所以这个部分不需要构造新的数据结构，其数据结构是沿用上一部分的数据结构，在这里就不再列举了，具体数据结构请参见词法分析部分。3.3.3 算法主控程序：结束开始#A（w）NEXT(w) error n yA（w）子程序：NEXT(w)入口errorerrorNEXT(w)出口B(w)NEXT(w)errorerrorerrorerror)NEXT(w)main(NEXT(w)NEXT(w)void nB（w）子程序：入口判断是否是标识符int|char|bool N NY Y判断字符是否为符号表内容保存变量

18、类型 NEXT(w)push判断是否是标识符 Yerror NNEXT(w)Yerror判断字符是否为符号表内容 error= N 语义动作，送入符号表表 YNEXT(w) YNEXT(w)W(w)C(w)生成四元式； error N； Y errorNEXT(w)B（w）NEXT(w)出口出口errorwhileifN N NNEXT(w)判断是否符合文法中对if的规定 Y Yerror NWHILE（） Y（error error N N YNEXT(w) Y NEXT(w)B（w）W（w）error N Yerror YNEXT(w)NEXT(w)D（w）DO（）B（w）error出口

19、N Y NEXT(w) B（w） error NNEXT(w) YENDWHILE( )B（w）出口ENDWHILE()为插入的语义动作。C（w）子程序：入口=，error N N Y YpushNEXT(w) NEXT(w)判断该字符是否为标示符 W（w） 将其加入符号表 Y 生成四元式C（w）NEXT(w)出口C（w）D（w）子程序：入口else出口 N Y NEXT(w) EL（）error N YNEXT(w)B（w）error N Y NEXT(w)IE（）其中IE（）为if else结构的出口标志3.4 中间代码产生器模块 3.4.1 功能 中间代码是高级程序语言中，各种语法成分的

20、语义结构表示；它介于源语言和目标语言之间。 虽然源程序可以直接翻译为目标语言代码，但是许多编译程序却采用了独立于机器的复杂性介于源语言和机器语言之间的中间语言。这样做的好处是：便于进行与机器无关的代码优化工作；使编译程序改变目标机更容易；使编译程序的结构在逻辑上更为简单明确，以中间语言为界面，编译前端和后端的接口更清晰。 中间代码的形式有多种，但是在本实验中采用的是四元式形式。 3.4.2 数据结构 typedef struct QUAT char *operational;/操作符 char *figure1;/操作数1 char *figure2;/操作数2 char *result;/结

21、果QUAT;四元式的存储结构QUAT Quat1000;/四元式结构体数组 3.4.3算法 - NEXT (w) NEXT (w) 出口 GEQ(-) TGEQ(+) T + T 入口 结束 结果输出errorNEXT (w) E # 开始 初始化nnyyyn 入口 入口nn ( i Fyynn / * NEXT (w) PUSH(i)yn ) 出口error1error2E NEXT (w)yyGEQ(*) F NEXT (w) 出口 GEQ(/) F NEXT (w)3.5优化器模块 3.5.1 功能 优化处理是指产生更高效的目标代码所做的工作。他可以分为在中间代码级上的优化和在目标代码上

22、的优化。在本次课设中，采用的是在中间代码级上的优化。这类优化不依赖于具体的计算机。另外，在优化的基本块中，为了简单处理，没有划分基本块，就是把整个程序看做一个基本块，然后就是处理一个基本块内的优化。由优化编译程序提供的对代码的各种变换必须遵循一定的原则。（1） 等价原则。经过优化后不改变程序的运行结果。（2） 有效原则。使优化后所产生的目标代码运行时间较短，占用的存储空间较小。（3） 合算原则。应尽可能以较低的代价取得较好的优化效果。 3.5.2 数据结构 typedef struct DAGint n_num; /结点的编号char *operational; /操作符char *M; /主

23、标记 char *AdditionalMAX;/附加标记int additionalnum; /附加标记个数int next1; /下一个int next2; /下一个DAG; 开始 3.5.3 算法 把A附加于B上；若A已定义过且是附标记就删除，主标记免删计算常值C=C1C2；若C没有定义过，申请新结点；若A已经定义过且是附加标记，则删，主标记免删为常值表达式A=C1C2或A=C1为赋值四元式 A=BDAG置空；依次读取一四元式A=B C；分别定义B,C结点（若定义过，则免） n n y y i>四元式的个数 n 出口 y 以上为优化器的第一个模块，构造基本块内优化的DAG；出口之后是

24、另外一个模块。该结点为带有附加标记的叶结点结构：B|A1，A2.按结点编码顺序，依次读取每一结点信息 入口有两个假设：临时变量的作用域是基本块内非临时变量的作用域也可以是基本块内。 结点为带有附加标记的非叶结点结构： n n A|A1，A2 结束i>结点个数 生成A i=A(i=1,2,.)A i为非临时变量 生成四元式A=B C 生成四元式A i = B (i=1,2,.)A i为非临时变量 y B|. C|. y n y n y 3.6 目标代码生成器模块 3.6.1 功能 编译模型的最后一个阶段是代码生成。它以源程序的中间代码作为输入，并产生等价的目标程序作为输出。代码生成器的输入

25、包括中间代码和符号表的信息。代码生成是把语义分析后或优化后的中间代码换成目标代码。目标代码一般都有三种形式。（1） 能够立即执行的机器语言代码，所有地址均已定位。（2） 待装配的机器语言模块。当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码。（3） 汇编语言代码，尚需经过汇编程序汇编，转换成可执行的机器语言代码。 代码生成主要考虑两个问题：一是如何使生成的目标代码较短；另一是如何充分利用计算机的寄存器，减少目标代码中访问存储单元的次数。这两个问题都直接影响目标代码的执行速度。 再次说明一下，本次课设没有涉及基本块的划分。 3.6.2 数据结构 typedef

26、 struct CODEchar *op;/汇编操作指令char *op1;/第一操作数char *op2;/第二操作数CODE;CODE Code1000;目标代码结构体数组char *R=NULL;/寄存器，里面放的是变量的名，就是一个描述表另外还有一个常用栈的描述。 开始 3.6.3 算法 释放寄存器 编写目标指令 取下一四元式 变量信息生成 结束 结束处理 取到了 取下一基本块 预处理 n y 基本块出口 y n 4 程序设计与实现4.1程序流程图 错误输出中间代码产生器 目标代码生成器 结束 优化器有错误 语法分析器 词法分析器 开始 程序的总体流程图如下： y n各个模块的程序具体

27、流程图参考第3节。4.2 程序说明main()： 调用子模块的功能InitStack(S);初始化一个栈结构cifa_main();调用词法分析功能yufa_main();调用语法分析功能output_yuyi();输出四元式序列词法分析：cifa_main(): 词法分析可以生成Token序列及静态符号表并输出IsLetter():判断字符是否为字母IsDigit():判断字符是否为数字IsKey():判断是否为关键字IsDefinition():判断是否为界符InsertID():向符号表中添加标示符（可判断符号表之前是否已存在此标示符）InsertConst():向符号表中添加数字（可判

28、断符号表之前是否已存在此数字）语法分析,及中间代码生成： 递归下降子程序：判断文法是否正确，并输出自上而下的推导过程 输出错误情况 插入语义动作并生成未优化的四元式 储存原始的四元式编译后端（四元式的优化）：DAG_Main():四元式优化的主函数QuatBelongToNumber():判断四元式中操作数是不是为常数Replace():替换冗余的四元式DeleteQuat():删除冗余的四元式Geq():计算并优化四元式编译后端（目标代码生成）：TargetCode():生成目标代码InitSEMStack():初始化信息栈ActiveInfo():生成活跃信息表CollectAndEdit

29、():生成汇编代码output_code():输出目标代码 4.3 实验结果 采用如下一段C语言程序进行验证，包含了课设要求的基本语句。这是一段正确的程序，就是符合我们定义的文法。用它来进行程序的验证，各模块输出结果如下所示。在这里先说明一下，若待验证的程序没有错误，那么语法分析就检测不出错误，为了能检测到错误，展示语法分析的功能，就认为的制造出错误，具体见下面语法分析输出模块。void main() int a,b,c,x; if(a>b)x=(a+b)*c; else x=5-a*b; while(c>=x)a=c+5*(3+2);b=a+x; （1）词法分析器模块输出结果如下

30、所示：它的输出结果形式第一列代表所属类型，第二列为对应的单词。我们的程序也可以识别出字符常量和字符串常量。因为优化那部分没有涉及到这两种常量，所以就没有向大家展示出来。（2） 语法分析模块输出的结果如下： 因为用来验证的程序没有错误，所以需要人为的添加错误。程序能识别的错误有：能够识别出未定义标识符能够检测出标识符的重定义能够检测出括弧的匹配与否if和while的判断条件不能为空能够识别出关键字的拼写正确与否表达式的正确与否。给出检测程序如下：void main() int a,b,x; char a;/a重定义 if()/if判断条件为空x=(a+b)*c; else x=5-a*b; wh

31、ile(a>=b)a=c+5*(3+2);b=a+x; d=a+b;/d没定义 （3） 中间代码产生器模块输出的结果如下：用四元式序列来表示。（4） 优化器模块输出结果如下：（5） 目标代码生成模块输出结果如下：因为生成目标代码需要获取相关变量的活跃度信息，所以先展示一下符号表的内容。（6） 可视化界面如下图所示：各模块要输出的内容在上面已经被标出。 5 结论 我们所设计的C语言编译系统可以根据自己所定义的文法成功的进行词法分析，生成相应的Token序列，另外，通过测试，也可以成功地生成静态符号表，并能对静态符号表随时进行查看。我们所设计的C语言编译系统也可以成功地对文档中的内容采用LL1分析法进行语法分析。通过测试，可以检查出所有的错误，并提示出错，但只能输出部分与错误有关的信息，而不能输出全部错误信息。总体来说还算成功。另外，在进行语法分析的同时，我们通过插入语义动作可以同时生成四元式。通过测试，我们可以成功的生成所需的四元式。我们也对四元式的优化进行了测试，我们可以成功地对原始的四元式进行部分的优化，但不能优化至最简，而是只能对两个操作数皆为常数，及四元式重复冗余这两种情况进行优化。我们也可以成功地生成活跃信息表，并通过活跃信息表生成相应的机器代码。通过测试，我们所生成的机器代码是准确无误的。 因此，整体来说，我们所设计的C语言编译系统是成功的。但我们也有遗憾，我们