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

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

2、义分析的综合，外加上扩展任务 中间代码的优化和目标代码的生成，主要是锻炼学生的逻辑思维能力， 进一步理解编译原理的方法和步骤。关键词：编译原理，前端，目标代码，后端2目录摘要.31. 概述.62. 课程设计任务及要求.82.1 设计任务.82. 2 设计要求.92. 算法及数据结构.103.1 算法的总体思想.103.2 词法分析器模块.113.2.1 功能.113.2.2 数据结构.113.2.3 算法.123.3 语法分析器模块.133.3.1 功能.133.3.2 数据结构.133.3.3 算法.143.4 中间代码产生器模块.243.4.1 功能.243.4.2 数据结构.243.4.

3、3 算法.253.5 优化器模块.273.5.1 功能.273.5.2 数据结构.273.5.3 算法.283.6 目标代码生成器模块.303.6.1 功能.303.6.2 数据结构.303.6.3 算法.3134. 程序设计与实现.324.1 程序流程图.324.2 程序说明.334. 3 实验结果.354. 结论.425. 参考文献.436. 收获、体会和建议.4441概述在计算机上执行一个高级语言程序一般要分为两步；第一步，用 一个编译程序把高级语言翻译成机器语言程序；第二步，运行所得的机 器语言程序求得计算结果。在学习编译原理课程过程中，逐渐掌握 各章节构造编译程序的基本理论，并能独立

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

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

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

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

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

9、语句_1 |=表达式 变量声明语 句_1|?赋值语句-标识符=表达式;表达式-算数表达式 逻辑表达式逻辑表达式- =算数表达式|T E17E1-+ T E1|- T E1|?T-F T1T1-* F T1|/ F T1|?F-标识符常数|(E)这个文法满足老师的要求，但是也存在一些不足，比如变量类型中 没有处理实数，数组和结构体以及 if 语句和 while 语句后必须有大括 弧匹配。2.2设计要求1、在深入理解编译原理基本原理的基础上，对于选定的题目，以小组为单位，先确定设计方案；2、 设计系统的数据结构和程序结构，设计每个模块的处理流程。 要求设计合理；3、 编程序实现系统，要求实现可视化

10、的运行界面，界面应清楚地 反映出系统的运行结果；4、 确定测试方案，选择测试用例，对系统进行测试；5、 运行系统并要通过验收，讲解运行结果，说明系统的特色和创 新之处，并回答指导教师的提问；8词法分析器语法分析器语义分析及中间代码产生器优化器目标代码生成器符号表出错处理33.1 算法的总体思想算法及数据结构词法分析器又称为扫描器，它的任务就是对输入的源程序进行词法分析输出单词符号供语法分析使用，语法分析器简称分析器，对单词符号串进行语法分析，根据语法规则进行推导，识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。语义分析与中间代码产生器，按照语义规则对语法分析器推导出的语法单位进

11、行语义分析并把它们翻译成一定形式的中间代码。优化器就是对中间代码进行优化处理。目标代码生成器，把中间代码翻译成目标程序。符号表用来登记源程序中出现的变量及其属性。另外，如果源程序有错误，编译发现错误， 把有关错误信息报告给用户，即出错处理。流程图如下：源程序单词符号语法单位中间代码中间代码目标代码93.2 词法分析器模块3.2.1 功能词法分析器功能室输入源程序，输出单词符号。单词符号是一个 程序语言的基本语法符号。程序语言的单词符号一般可分为下列 5 种。（1）关键字是由程序语言定义的具有固定亿的标识符。有时称这些标识符为保留字或基本字。（2）标识符用来标示各种名字，如变量名，数组名，函数名

12、等。（3）常数 （4）运算符程序中出现用来运算的数值我们所定义的文法包括+，-，*，/算术运算符，还有 and，or，not，=，,四元式的个数y出口以上为优化器的第一个模块，构造基本块内优化的 DAG；出口之后是 另外一个模块。27生成四元式 A=B C按结点编码顺序，依 次读取每一结点信息生成四元式 Ai=B生成 A i=A(i=1,2,.)标记的非叶结点有两个假设：临时变量的作用域是基本块内非临时变量的作用 域也可以是基本块内。入口该结点为带有附 加标记的叶结点结点为带有附加n n结构：B|A1，A2. A|A1，A2结构：y B|. C|. y A i 为非临时变量(i=1,2,.)n

13、A i 为非临时变 量yni结点个数 y结束283.6 目标代码生成器模块3.6.1 功能编译模型的最后一个阶段是代码生成。它以源程序的中间代码作 为输入，并产生等价的目标程序作为输出。代码生成器的输入包括中间 代码和符号表的信息。代码生成是把语义分析后或优化后的中间代码换 成目标代码。目标代码一般都有三种形式。（1） 能够立即执行的机器语言代码，所有地址均已定位。（2） 待装配的机器语言模块。当需要执行时，由连接装入程序把它们 和某些运行程序连接起来，转换成能执行的机器语言代码。（3） 汇编语言代码，尚需经过汇编程序汇编，转换成可执行的机器语 言代码。代码生成主要考虑两个问题：一是如何使生成

14、的目标代码较短； 另一是如何充分利用计算机的寄存器，减少目标代码中访问存储单元的 次数。这两个问题都直接影响目标代码的执行速度。再次说明一下，本次课设没有涉及基本块的划分。3.6.2 数据结构typedef struct CODEchar *op;/汇编操作指令char *op1;/第一操作数char *op2;/第二操作数CODE;CODE Code1000;目标代码结构体数组char *R=NULL;/寄存器，里面放的是变量的名，就是一个描述表 另外还有一个常用栈的描述。29预处理取下一基本块结束处理释放寄存器变量信息生成取下一四元式编写目标指令基本块出口n3.6.3 算法开始取到了yn结

15、束y30词法分析器语法分析器中间代码产生器优化器目标代码生成器错误输出4程序设计与实现4.1 程序流程图程序的总体流程图如下：开始有错误ny结束各个模块的程序具体流程图参考第 3 节。314.2 程序说明main()：调用子模块的功能InitStack(S);初始化一个栈结构cifa_main();调用词法分析功能yufa_main();调用语法分析功能output_yuyi();输出四元式序列词法分析：cifa_main(): 词法分析可以生成 Token 序列及静态符号表并输出 IsLetter():判断字符是否为字母IsDigit():判断字符是否为数字IsKey():判断是否为关键字I

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

17、优化四元式编译后端（目标代码生成）：TargetCode():生成目标代码InitSEMStack():初始化信息栈ActiveInfo():生成活跃信息表CollectAndEdit():生成汇编代码output_code():输出目标代码334.3 实验结果采用如下一段 C 语言程序进行验证，包含了课设要求的基本语句。 这是一段正确的程序，就是符合我们定义的文法。用它来进行程序的验 证，各模块输出结果如下所示。在这里先说明一下，若待验证的程序没 有错误，那么语法分析就检测不出错误，为了能检测到错误，展示语法 分析的功能，就认为的制造出错误，具体见下面语法分析输出模块。 void main(

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

19、写正确与否表达式的正确与否。给出检测程序如 下：void main()int a,b,x;char a;/a 重定义if()/if 判断条件为空x=(a+b)*c;else x=5-a*b;while(a=b)a =c+5*(3+2);b =a+x;d=a+b;/d 没定义3637（3）中间代码产生器模块输出的结果如下： 用四元式序列来表示。38（4）优化器模块输出结果如下：39（5）目标代码生成模块输出结果如下：因为生成目标代码需要获取相关变量的活跃度信息，所以先展示一下符 号表的内容。40（6）可视化界面如下图所示：各模块要输出的内容在上面已经被标出。415结论我们所设计的 C 语言编译系

20、统可以根据自己所定义的文法成功的 进行词法分析，生成相应的 Token 序列，另外，通过测试，也可以成功 地生成静态符号表，并能对静态符号表随时进行查看。我们所设计的 C 语言编译系统也可以成功地对文档中的内容采用 LL1 分析法进行语法分 析。通过测试，可以检查出所有的错误，并提示出错，但只能输出部分 与错误有关的信息，而不能输出全部错误信息。总体来说还算成功。另 外，在进行语法分析的同时，我们通过插入语义动作可以同时生成四元 式。通过测试，我们可以成功的生成所需的四元式。我们也对四元式的 优化进行了测试，我们可以成功地对原始的四元式进行部分的优化，但 不能优化至最简，而是只能对两个操作数皆

21、为常数，及四元式重复冗余 这两种情况进行优化。我们也可以成功地生成活跃信息表，并通过活跃 信息表生成相应的机器代码。通过测试，我们所生成的机器代码是准确 无误的。因此，整体来说，我们所设计的 C 语言编译系统是成功的。但我们 也有遗憾，我们所设计的符号表，单独是可以运行的，并没有建立相应 的活动记录。426参考文献1、陈火旺.程序设计语言编译原理（第 3 版）. 业出版社.2000.北京：国防工2、 美 Alfred V.Aho Ravi Sethi Jeffrey D. Ullman 著.李建中， 姜守旭译.编译原理.北京：机械工业出版社.2003.3、 美 Kenneth C.Louden 著.冯博琴等译.编译原理及实践.北 京：机械工业出版社.2002.4、 金成植著.编译程序构造原理和实现技术. 北京：高等教育 出版社. 2002.437收获、体会和建议经过了为期 2 周的课程设计，让一开始都不知道编译器是何物的我 们成功蜕变，在完成基本任务的基础上又进一步实现了编译器后端。依 稀记得刚刚接触课程题目时，都不知道该如何下手，虽然同时也在进行 编译理论课，但当真正要将理论变为