编译原理课程设计报告（一个完整的编译器）

编译原理程序设计报告

一个简单文法的编译器的设计与实现

专业班级 ：计算机1406班

组长姓名 ： 宋世波

组长学号 ： 20143753

指导教师 ： 肖 桐

2016年12月

1

设计分工

组长学号及姓名：宋世波20143753 分工：文法及数据结构设计

词法分析 语法分析（LL1） 基于DAG的中间代码优化 部分目标代码生成

组员1学号及姓名：黄润华20143740 分工：中间代码生成(LR0)

部分目标代码生成

组员2学号及姓名：孙何奇20143754 分工：符号表组织

部分目标代码生成

2

摘要

编译器是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序。编译是从源代码（通常为高阶语言）到能直接被计算机或虚拟机执行的目标代码（通常为低阶语言或机器语言）的翻译过程。

一．编译器的概述 1.编译器的概念

编译器是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序。编译器将原始程序作为输入，翻译产生使用目标语言的等价程序。源代码一般为高阶语言如Pascal、C++、Java 等，而目标语言则是汇编语言或目标机器的目标代码，有时也称作机器代码。

2．编译器的种类

编译器可以生成用来在与编译器本身所在的计算机和操作系统（平台）相同的环境下运行的目标代码，这种编译器又叫做“本地”编译器。另外，编译器也可以生成用来在其它平台上运行的目标代码，这种编译器又叫做交叉编译器。交叉编译器在生成新的硬件平台时非常有用。“源码到源码编译器”是指用一种高阶语言作为输入，输出也是高阶语言的编译器。例如: 自动并行化编译器经常采用一种高阶语言作为输入，转换其中的代码，并用并行代码注释对它进行注释（如OpenMP）或者用语

3

言构造进行注释（如FORTRAN的DOALL指令）。

3.本编译器概述

编译程序的工作过程一般可以分为五个阶段：词法分析、语法分析、语义分析与中间代码产生、优化、目标代码生成。每一个阶段在功能上是相对独立的，它一方面从上一个阶段获取分析的结果来进行分析，另一方面由将结果传递给下一个阶段。由编译程序的五个阶段就对应了编译系统的结构，这五个对应阶段分为编译器的前段，中间代码以及后端。

其中词法分析器利用超前搜索、状态转换等方法，将源程序转化成为一个一个的单词符号二元式。一般程序语言的单词符号包括关键字、运算符、常数、标识符和界符。语法分析器将这些单词符号作为输入，对它进行语法分析。语法分析采用LL1分析法，语法分析器把语法单元作为输入供语义分析器使用。在语法分析的同时进行语法分析，并产生一定的语义动作，来生成中间代码。优化和目标代码生成是针对某一种处理器而言的。代码优化是将语义分析生成的中间代码进行优化，产生执行效率更高的代码。目标代码生成最终生成可以在某种机器上运行的机器语言或者汇编语言。还要有符号表可供查询。在整个编译过程中还包括对表格的操作和对错误的处理，这些也都是非常重要的环节。

环境：

编译器整体全部使用visualstudio2015编写 目标代码在8086指令集机器上运行

关键词：编译原理，前端，中间代码生成，后端，

4

目录

设计分工 .......................................................................................................... 2 摘要 .................................................................................................................. 3 1. 概述 ............................................................................................................. 7 2. 课程设计任务及要求 ................................................................................. 9

2.1 设计任务 ........................................................................................... 9 2.2 设计要求 ......................................................................................... 10 2.3设计的文法结构 .............................................................................. 11 3. 算法及数据结构 ....................................................................................... 17

3.1 算法的总体思想（流程） ............................................................. 17 3.2 词法分析器模块 ............................................................................. 18

3.2.1 功能 ...................................................................................... 18 3.2.2 数据结构 .............................................................................. 19 3.2.3 流程图 .................................................................................. 20 3.2.4 算法 ...................................................................................... 20 3.2.5 运行截图 .............................................................................. 22 3.3 语法分析器模块 ............................................................................. 23

3.3.1 功能 ...................................................................................... 23 3.3.2 数据结构 .............................................................................. 24 3.3.3 流程图 .................................................................................. 25 3.3.4 算法 ...................................................................................... 26 3.3.5 运行截图 .............................................................................. 38 3.4符号表生成模块 .............................................................................. 38

3.4.1 功能 ...................................................................................... 38 3.4.2 数据结构 .............................................................................. 39 3.4.3 流程图 .................................................................................. 42 3.4.4 算法 ...................................................................................... 43 3.4.5 运行截图 .............................................................................. 44 3.5中间代码生成模块 .......................................................................... 44

3.5.1 功能 ...................................................................................... 45 3.5.2 数据结构 .............................................................................. 46 3.5.3 流程图 .................................................................................. 48 3.5.4 算法 ...................................................................................... 48 3.5.5 运行截图 .............................................................................. 49 3.6中间代码优化模块 .......................................................................... 49

5

3.6.1 功能 ...................................................................................... 49 3.6.2 数据结构 .............................................................................. 50 3.6.3 流程图 .................................................................................. 51 3.6.4 算法 ...................................................................................... 52 3.6.5运行截图 ............................................................................... 54 3.7目标代码生成模块 .......................................................................... 55

3.7.1 功能 ...................................................................................... 55 3.7.2 数据结构 .............................................................................. 56 3.7.3 流程图 .................................................................................. 56 3.7.4 算法 ...................................................................................... 57 3.7.5 运行截图 .............................................................................. 60

这里不得不提到目标代码生成中存在的一些问题， ................................ 60 4. 程序设计与实现 ....................................................................................... 63

4.1 程序说明 ......................................................................................... 63 4.2 实验结果 ......................................................................................... 66 5. 结论 ........................................................................................................... 68

5.1组长：宋世波 .................................................................................. 68 5.2组员：孙何奇 .................................................................................. 69 5.3组员：黄润华 .................................................................................. 69 6. 收获、体会和建议。 ............................................................................... 71

6.1组长：宋世波 .................................................................................. 71 6.2组员：孙何奇 .................................................................................. 72 6.3组员：黄润华 .................................................................................. 72 7.附录 ............................................................................................................. 74

源代码： ................................................................................................ 74

7.1可执行文件链接 ..................................................................... 74

8、参考文献 .................................................................................................. 75

6

1.概述

本程序实现的数据类型有整型（int）、浮点型（float）、char（字符型）、字符串型（string），同时在最后的目标代码生成部分允许出现布尔（bool）类型，实现的操作有if，else以及while循环，和输入输出语句，能做到直接生成目标代码并运行。做到了类型检查和重定义的判断，同时也有优化部分。

词法分析部分构建得到的词法序列为二元式，二元式由两部分组成，其种别码和类型组成，其中关键字和界符记录其数字，用到时只需查其对应的关键字表和界符表即可，而字符类型、字符串类型、数字类型、以及标识符类型的值一律用字符串存储，其中数字类型存储时对其使用atoi和itoa函数进行数字转字符串即可，要使用到其数字时只需要将对其使用字符串转数字函数再获得即可。

语法分析部分采用的是LL1分析方法，这是一种自上而下的语法分析法，又称为预测分析法，语法分析器部分实现了自动求first集合和follow集合，采用的是递归程序获得select集合，在实现对产生式完全扫描以后，便可以获得一张完整的分析表，表中标注了是否为预测以及对应的产生式序列，而后进行语法分析，通过于获得的分析表进行比对，进行入栈出栈，匹配到相同的则认为匹配成果，当文法匹配成功，同时单词也匹配成功的时候，认为语法分析完成，语法无错误，否则报错。

在符号表生成部分，程序对获取的单词序列中的标识符进行再分析，确定每一个标识符的存储范围，同时从此之中获取函数的参数表，函数表部分，构建出编译器全局可用的活动记录表，以供目标代码生成使用，同时也为编译器增添新内容做准备。

7

中间代码生成部分，在此之前需注意到，由于再语法分析部分已经生成了一个具体可理解的动作序列，所以中间代码生成部分的所用方法并非语法制导，其本身也与语法分析相割裂开来，中间代码生成采取的是自底向上进行分析，不过是基于单词序列进行的分析，其操作等于是使用已获得的伪动作序列，与源程序去作比较，找出伪动作序列的实际含义，将其顺序填好，最后便完成了整个中间代码（四元式）的生成，并将其重新输出到文件中。

中间代码优化部分是对填装完毕的中间代码的再处理，也就是减少无用式子，给目标代码的生成提供便利，先进行基本块划分，而后采取的是DAG图优化，即无环有向图优化，顺序是构建DAG图（无环有向图），减少无用分支，或删改部分同义分支，完成DAG图改造后便又重新由树组装四元式，组装好的四元式又再次重新输出到文件中。

目标代码生成部分较长，也并不仅仅包含目标代码生成部分，在这个部分文件中，同时需要对前述获得的符号表，中间代码进行再处理，以得到符号目标代码生成所用的符号表和中间代码，再进行预处理完成之后，具体为根据四元式动作，按顺序依次生成目标代码，需要依据不同的四元式动作每个采取不同的操作方法，生成相应目标代码。

测试部分采用的emu8086软件，这个软件支持的指令集为8086指令集，由于64位机器上对汇编的支持并不算好，所以在8086机上最后进行的是对目标代码的正确性检验以及运行，运行通过且符合源程序实际操作即认为编译器任务完成。

8

2.课程设计任务及要求

2.1 设计任务

1.一个简单文法的编译器前端的设计与实现

①定义一个简单程序设计语言文法（包括变量说明语句、算术运算表

达式、赋值语句；扩展包括逻辑运算表达式、If语句、While语句等）；

②扫描器设计实现； ③语法分析器设计实现； ④中间代码设计；

⑤中间代码生成器设计实现。

2.难度相当的自选题目, 如:

①一个简单文法的编译器后端的设计与实现。 ②一个简单文法的编译器的设计与实现。

③自选一个感兴趣的与编译原理有关的问题加以实现

以下为本组选择部分：

一个简单文法的编译器的设计与实现。

1. 定义一个简单程序设计语言文法（包括变量说明语句、算术运算表达式、赋值语句；扩展包括逻辑运算表达式、If语句、While语句等）； 2. 扫描器设计实现 3. 语法分析器设计实现； 4. 符号表设计

5. 符号表生成器设计实现 6. 中间代码设计；

9

7. 中间代码生成器设计实现。 8. 中间代码优化 9. 中间代码优化实现 10. 目标代码设计

11. 目标代码生成器设计实现 2.2 设计要求

1、在深入理解编译原理基本原理的基础上，对于选定的题目，以小组为单位，先确定设计方案；

2、设计系统的数据结构和程序结构，设计每个模块的处理流程。要求设计合理；3、编程序实现系统，要求实现可视化的运行界面，界面应清楚地反映出系统的运行结果；

4、确定测试方案，选择测试用例，对系统进行测试；

5、运行系统并要通过验收，讲解运行结果，说明系统的特色和创新之处，并回答指导教师的提问； 6、提交课程设计报告。

以下为本组设计要求：

给出一个源程序文件，作为编译器前端的输入，输出相关编译阶段的运行结果。

词法分析阶段：Token序列；关键字表、界符表、符号表系统。 语法分析阶段：LL1型产生式、分析表、语法分析所用栈 符号表生成阶段：符号表系统

中间代码生成阶段：四元式序列；符号表系统。

中间代码优化阶段：四元式序列、DAG图、优化完成的四元式序列

10

3.5.2 数据结构

structfourelem {/*四元式结构*/ };

structspo {/*动作序列*/ };

spo sport[100]; char actid[20][10] =

{ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\ ,\,\,\,\};/*枚举动作*/ int sem[1000];/*语义栈*/

四元式是一种更接近目标代码的中间代码形式。由于这种形式的中间代码便于优化处理，因此，在目前许多编译程序中得到了广泛的应用。 四元式实际上是一种“三地址语句”的等价表示。它的一般形式为： (op,arg1,arg2,result)

其中， op为一个二元 (也可是一元或零元)运算符；arg1,arg2分

int idact; char id1[15]; char id2[15]; type type1; type type2; char id3[15];

char name[15]; char value1[15]; float value2;

46

别为它的两个运算 (或操作)对象，它们可以是变量、常数或系统定义的临时变量名；运算的结果将放入result中。四元式还可写为类似于PASCAL语言赋值语句的形式：

result ∶= arg1 op arg2

需要指出的是，每个四元式只能有一个运算符，所以，一个复杂的表达式须由多个四元式构成的序列来表示。例如，表达式A+B*C可写为序列

T1∶=B*C，T2∶=A+T1

其中，T1，T2是编译系统所产生的临时变量。当op为一元、零元运算符 (如无条件转移)时，arg2甚至arg1应缺省，即result∶=op arg1或 op result ；对应的一般形式为： (op,arg1,,result)或(op,,,result)

在实际产生的四元式中，op往往用一整型数表示 (操作符的代码)，它可能附带有不止一种属性。例如，加运算可以分为定点加法和浮点加法两种，我们可用不同的整数值区分这两种加法。至于四元式中运算对象arg1、arg2和结果域result，它们可以是指向符号表中某项的指示字，也可以是某个临时变量的序号，因此，在实际的翻译过程中，还需要进行相应的查填符号表工作。 四元式类型定义如上所述：

其中idact为动作编号，四元式中的每一个对象都用Token类型表示，这样做的目的是利于四元式在机内的连续存储，而后的id1，id2，id3则很容易清楚其对应着四元式的后三项，其中type1和type2为枚举类型，这是为了再符号表生成之外确定好四元式的结构构成，这样的好处就是在生成目标代码时会有一定方便。

47

3.5.3流程图

开始读取第一个动作序列从文件中读取动作序列动作序列已读完？否是读取下一个单词将操作数压栈否是动作序列吗？是根据动作序列弹出操作数，构建四元式将获得的四元式输出到文件中结束

3.5.4算法

voidinitact();/*初始化四元式*/ intact();/*获取动作序列位置*/ voidactanalysis();/*生成四元式*/ voidprintact();/*输出打印四元式*/

48

voidtranslate1();/*生成四元式翻译函数，即主函数*/ voidactionprep();/*四元式预处理，使之更适应生成目标代码*/ 这里需要注意到的是，动作序列的获取，其实是在LL1语法分析的时候已经获取道理相应动作，方法很简单，通过不断确定语法分析栈顶，直接确认其所可能具有的动作序列，并逐个直接导入文件中。 3.5.5运行截图

3.6中间代码优化模块 （负责人：宋世波） 3.6.1 功能 1.划分基本块 2.产生DAG图 3.优化节点

4.输出优化后的四元式到文件中

49

我们在编写程序中，很难做到所书写的程序是最优的，比如定义了后面不曾使用的变量，对同一对象赋了多个不同的变量名，这些虽然不影响程序的正确性，但是在程序进行编译成目标代码的过程中，会无端增加四元式的个数从而生成众多不必要的目标代码，

因此，在生成目标代码前，我们有必要进行这样一个优化的操作来尽可能的缩短最终四元式的个数，为产生更高效的目标代码提供前提保障。 优化方法：

DAG(Directed Acyclic Graph)是指无环有向图；这里用 来对基本块内的四元式序列进行优化。

采用老师上课时所讲的基于DAG的局部优化算法，重组中间代码生成

过程中生成的四元式序列，以达到对表达式的优化。 3.6.2 数据结构

structDAG_node {/*DAG图节点及链节点*/ };

structDAG {/*DAG图*/

char mes[15];/*节点信息*/ tvp it;/*节点类型*/ structDAG_node *synonymous;

int ope;/*节点运算符*/ int level;

structDAG *left;/*左叶子*/ structDAG *right;/*右叶子*/

50

本文来源：https://www.bwwdw.com/article/rj2h.html