计算机科学与工程学院
课程设计报告
题目全称：常用边缘算法的实现
学生学号： 2506203010 姓名：王 嘉
指导老师： 职称：
指导老师评语：
签字： 课程设计成绩： 设计过程表现 设计报告质量 总分 编译器中间代码生成的研究与实现
作者： 王嘉
学号：2506203010 指导老师：吴洪
摘要： 在编译器的翻译流水线中，中间代码生成是处于核心地位的关键步骤。它的实现基于语法分析器的框架，并为目标机器代码的实现提供依据。虽然在理论上没有中间代码生成器的编译器也可以工作，但这将会带来编译器的高复杂度，低稳定性和难移植性。现代编译理论不仅要求中间代码的生成，还要求基于中间代码的优化。本文研究并实现了一个轻量级类C语言的中间代码生成器，并就中间代码生成的原理进行了细致的阐述。
关键字：中间代码生成、语法制导翻译、翻译模式、语法树、三地址码
一、 目的及意义
在编译器的分析综合模型中，前端将源程序翻译成一种中间表示，后端根据这个中间表示生成目标代码。目标语言的细节要尽可能限制在后端。尽管源程序可以直接翻译成目标语言，但使用与机器无关的中间形式具有以下优点：
1.重置目标比较容易：不同机器上的编译器可以在已有前端的基础上附近一个适合这 台新机器的后端来生成。
2.可以在中间表示上应用与机器无关的代码优化器。
本文介绍如何使用语法制导方法，基于一种轻量级的类C语言FineC的词法分析器和语法分析器，一遍地将源程序翻译成中间形式的编程语言结构，如声明、赋值及控制流语句。为简单起见，我们假定源程序已经经过一遍扫描，生成了相应的词法记号流和符号表、词素表结构。基于FineC语法标准的语法分析器框架也已经能够正常工作。我们的任务就是补充这个框架，使其在语法分析的过程中生成相应的中间代码，并将必要的变量和函数声明存放在一个符号表链中。
二、 目标语言词法和语法标准：
这里定义一个编程语言称作FineC（“fine”指代轻量、精妙）。它是一种适合编译器设计方案的语言。本质上是C语言的一个限制了数据类型、算术操作、控制结构和处理效率的轻量子集。
1. FineC语言的词法描述：
[1]语言的关键字： else if
return while int
void
所有的关键字都是保留字，并且必须是小写 [2]下面是专用符号：
+ - * / < <= > >= == !=
/* */
RELOP = {< <= > >= == !=} ADDOP = {+ -}
MULOP = {* /}
[3]其他标记是NUM和ID，由正则表达式定义： ID = letter (letter|digit)* NUM = digit digit* letter = a|?|z|A|?|Z digit = 0|?|9
小写和大写字母是有区别的
[4]空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开NUM、ID关 键字
[5]注释用通常的C语言符号/*?*/围起来。注释可以放在任何空白出现的位置(即注释 不能放在标记内)上，且可以超过一行。注释不能嵌套。不支持单行//注释。
FineC语言的词法分析器输出记号流，记号是一个二元组(tokentype, lexeme)。tokentype包含了记号的类型，lexeme包含记号的词素。例如一个标识符gcd的记号是(ID, 6)。6表示这个标识符在符号表的第7项里（与首元的距离是6，可以把这个整数看作指向符号表的指针）。词法分析器后面的步骤分析这个标识符时，就可以根据此指针访问符号表，并取出它的词素,也就是字符串“gcd”。又例如一个整型值36的记号是(NUM, 36)。这里的36不是指向符号表的指针，而是NUM类型的数值。编译器会根据tokentype决定lexeme的含义。
2. FineC语言的语法描述
语法分析器调用词法分析器，对源程序做一遍词法分析，返回的记号流放在缓冲区tokens中。在FineC的实践中，我们用一个vector
语法分析器的原理和实现不是本文讨论的范畴，这里只给出FineC语言的文法标准和简单的语义解释，供中间代码生成时建立翻译模式使用：
= ; , { } ( )
(1) program --> declaration-list
程序由一个声明表组成
(2) declaration-list --> declaration declaration-list | declaration
声明表包含至少一条声明
(3) declaration --> var-declaration | fun-declaration
声明可以是变量声明或函数声明 (4) var-declaration --> “int”ID;
由于FineC只支持整型，所以变量声明也只有“int ID”的形式。注意，不支持变量声明时赋初值。
(5) fun-declaration --> type-specifier ID (params) compound-stmt
| type-specifier ID () compound-stmt
函数的返回类型可以是“int”或“void”， 函数可以有参数也可以没有 (6) type-specifier --> \(7) params --> param params | param
如果函数有形参，则至少要有一个参数 (8) param --> “int”ID
函数的形参也只支持“int”一种
(9) compound-stmt --> {local-declarations statement-list}
函数的主体是一个语句块，包含局部变量的声明和语句表。注意，所有的局部变量声明必须出现在语句之前。
(10) local-declarations --> var-declaration local-declarations | empty
局部变量声明可以为空，一个，或多个
(11) statement-list --> statement statement-list | empty 语句表也可以为空，或有一个或多个语句组成
(12) statement --> expression-stmt | compound-stmt | selection-stmt
| iteration-stmt | return-stmt
语句有五种类型，分别是表达式语句，语句块，选择语句，循环语句和返回语句 (13) expression-stmt --> expression; | ;
表达式语句可以没有内容，或者由一个表达式构成。
(14) selection-stmt --> \
| “if”(condition-expression) statement “else”statement 选择语句支持一路分支和二路分支。根据condition-expression的真假决定程序控制流
的流向。
(15) iteration-stmt --> \ 循环语句只支持“while”的形式，while语句的含义与C语言一致。 (16) return-stmt --> “return”; | “return”expression; 返回语句可以返回值，也可以什么都不返回。
(17) expression --> ID = additive-expression | additive-expression 表达式可以是赋值语句或者加法运算语句，其中赋值语句返回ID的值。
(18) condition-expression --> additive-expression RELOP additive-expression 条件表达式比较两个整型值的关系，包括大于，小于，大于等于，小于等于，不等于
和等于，根据其真值指向不同的语句流向
(19) additive-expression --> addtive-expression ADDOP term | term (20) term --> term MULOP factor | factor
(21) factor --> (additive-expression) | ID | call | NUM
以上三条文法生成算术表达式，ADDOP包括加和减，MULOP包括乘除。运算的因子可以
是变量，整数字面值，表达式或者函数返回的结果。这样安排文法是为了满足运算符的优先级和结合性。即加减比乘除优先级低，加减乘除都是左结合的。 (22) call --> ID (args) | ID () 函数调用可以有实参也可以没有。
(23) args --> additive-expression, args | additive-expression
三、 中间代码生成原理
1. 中间代码生成器的作用：
中间代码生成器不是一个独立的部件，而是建立在语法分析器框架中的语义动作。可以把编译器比作一个流水线，源程序是源材料，词法分析器是过滤器，源程序经过词法分析器后形成记号流。语法分析器是一系列相互相关的函数，控制流在这些函数中的转移过程就是语法分析的过程。记号流比作精炼过的材料被送到语法分析器这个流水线上流动。如果没有中间代码生成动作，语法分析器就像是只有履带没有加工机的流水线，记号流流过之后没有任何变化。
由上面的比喻可以看出，中间代码生成和语法分析应该构成一遍（“遍”的概念请参考文献[1]），以词法分析生成的记号流作为输入，以某种表示程序结构的中间表示（语法树或三地址码）作为输出。生成的中间代码是介于源代码和目标代码中间的一种结构化表示。它的意义在于能够把前端和后端分开，提高编译器的可移植性（因为结构清晰，对于编译器研究者来说也提高了可读性）和易优化性（对中间代码的优化可以独立于机器）。
2. 语法制导翻译：
语法制导翻译是一种实现翻译的思路，不仅可以用来指导中间代码生成。实际上，应用语法制导翻译的概念，可以实现任何基于语法分析器框架的语义动作，应用非常广泛。比如把源代码中的算术表达式中缀表示化成前缀表达式，或者类似数学排版语言EQN的构造等等。本文不对语法制导定义做广泛抑或深入的探讨，只简单介绍其基本原理，指导中间代码生成器的设计。 [1]语法制导定义：
语法制导定义是对上下文无关文法的推广，其中每个文法符号都有一个相关的属性集。属性分为两个子集，分别称为该文法符号的综合属性和继承属性。属性可以代表任何对象：