中间代码生成

《中间代码生成》由会员分享，可在线阅读，更多相关《中间代码生成（33页珍藏版）》请在金锄头文库上搜索。

1、计算机科学与工程学院课程设计报告题目全称：常用边缘算法的实现学生学号：2506203010姓名：王嘉指导老师：职称：指导老师评语：签字课程设计成绩：设计过程表现设计报告质量总分编译器中间代码生成的研究与实现作者： 王嘉学号：2506203010指导老师：吴洪摘要： 在编译器的翻译流水线中，中间代码生成是处于核心地位的关键步骤。它的实现基 于语法分析器的框架，并为目标机器代码的实现提供依据。虽然在理论上没有中间代码生成 器的编译器也可以工作，但这将会带来编译器的高复杂度，低稳定性和难移植性。现代编译 理论不仅要求中间代码的生成，还要求基于中间代码的优化。本文研究并实现了一个轻量级 类C语言的中间

2、代码生成器，并就中间代码生成的原理进行了细致的阐述。关键字：中间代码生成、语法制导翻译、翻译模式、语法树、三地址码一、目的及意义在编译器的分析综合模型中，前端将源程序翻译成一种中间表示，后端根据这个中间表 示生成目标代码。目标语言的细节要尽可能限制在后端。尽管源程序可以直接翻译成目标语 言，但使用与机器无关的中间形式具有以下优点：1. 重置目标比较容易：不同机器上的编译器可以在已有前端的基础上附近一个适合这台新机器的后端来生成。2. 可以在中间表示上应用与机器无关的代码优化器。本文介绍如何使用语法制导方法,基于一种轻量级的类C语言FineC的词法分析器和语 法分析器，一遍地将源程序翻译成中间形

3、式的编程语言结构，如声明、赋值及控制流语句 为简单起见，我们假定源程序已经经过一遍扫描，生成了相应的词法记号流和符号表、词素 表结构。基于FineC语法标准的语法分析器框架也已经能够正常工作。我们的任务就是补充 这个框架，使其在语法分析的过程中生成相应的中间代码，并将必要的变量和函数声明存放 在一个符号表链中。二、目标语言词法和语法标准：这里定义一个编程语言称作FineC （“fine”指代轻量、精妙）。它是一种适合编译器设 计方案的语言。本质上是C语言的一个限制了数据类型、算术操作、控制结构和处理效率的 轻量子集。1. FineC 语言的词法描述：1语言的关键字：else if return

4、whileintvoid所有的关键字都是保留字，并且必须是小写2 下面是专用符号：+ - * / = = != = ; , ( ) /* */RELOP = = = !=ADDOP = +-MULOP = */3 其他标记是 NUM 和 ID ，由正则表达式定义：ID = letter (letter|digit)*NUM = digit digit*letter = a| |z|A| |Zdigit = 0| |9 小写和大写字母是有区别的4 空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开NUM、ID关 键字5 注释用通常的C语言符号/*/围起来。注释可以放在任何空白出现的位

5、置(即注释 不能放在标记内)上，且可以超过一行。注释不能嵌套。不支持单行/注释。FineC语言的词法分析器输出记号流，记号是一个二元组(tokentype, lexeme)。 token type包含了记号的类型，lexeme包含记号的词素。例如一个标识符gcd的记号是(ID, 6)。 6表示这个标识符在符号表的第7项里(与首元的距离是6，可以把这个整数看作指向 符号表的指针)。词法分析器后面的步骤分析这个标识符时，就可以根据此指针访问符号表， 并取出它的词素，也就是字符串“gcd”。又例如一个整型值36的记号是(NUM, 36)。这里的 36不是指向符号表的指针，而是NUM类型的数值。编译器

6、会根据token type决定lexeme的 含义。2. FineC 语言的语法描述语法分析器调用词法分析器，对源程序做一遍词法分析，返回的记号流放在缓冲区 tokens中。在FineC的实践中，我们用一个vectortoken容器来存放词法分析器返回的这 些记号。语法分析器在这个缓冲区(容器)之上，进行匹配、回溯等必要的操作，实现语法 分析。常见的语法分析方法有三种：带回溯的递归下降法、预测分析法(不带回溯的递归下 降)以及常用于语法分析器自动生成的LR文法分析。前两者属于自顶向下的分析，后者属 于自底向上的分析。FineC的语法分析器基于带回溯的递归下降法实现，在分析的过程中可 能产生递归

7、和回溯。当发生回溯时，意味着出现了某个记号的匹配失败，但在其之前某些记 号可能已经被成功匹配并扫描。因此回溯到上层调用时，不仅要恢复指向记号流的指针，也 需要考虑是否已经生成了无效的中间代码，并对其进行撤销。语法分析器的原理和实现不是本文讨论的范畴，这里只给出FineC语言的文法标准和简 单的语义解释，供中间代码生成时建立翻译模式使用：(1) program - declaration-list 程序由一个声明表组成(2) declaration-list - declaration declaration-list | declaration 声明表包含至少一条声明(3) declarati

8、on - 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 - int | void(7)

9、 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 - stat

10、ement 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|

11、 “if”(condition-expression) statement “else”statement 选择语句支持一路分支和二路分支。根据condi tion-expression的真假决定程序控制流 的流向。(15) iteration-stmt - while (condition-expression) statement 循环语句只支持“while”的形式，while语句的含义与C语言一致。(16) return-stmt - “return”; | “return”expression; 返回语句可以返回值，也可以什么都不返回。(17) expression - ID = ad

12、ditive-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 | fact

13、or(21) factor - (additive-expression) | ID | call | NUM以上三条文法生成算术表达式，ADDOP包括加和减，MULOP包括乘除。运算的因子可以是变量，整数字面值，表达式或者函数返回的结果。这样安排文法是为了满足运算符 的优先级和结合性。即加减比乘除优先级低，加减乘除都是左结合的。(22) call - ID (args) | ID ()函数调用可以有实参也可以没有。(23) args - additive-expression, args | additive-expression三、中间代码生成原理1. 中间代码生成器的作用：中间代码生成器

14、不是一个独立的部件，而是建立在语法分析器框架中的语义动作。可以 把编译器比作一个流水线，源程序是源材料，词法分析器是过滤器，源程序经过词法分析器 后形成记号流。语法分析器是一系列相互相关的函数，控制流在这些函数中的转移过程就是 语法分析的过程。记号流比作精炼过的材料被送到语法分析器这个流水线上流动。如果没有 中间代码生成动作，语法分析器就像是只有履带没有加工机的流水线，记号流流过之后没有 任何变化。由上面的比喻可以看出，中间代码生成和语法分析应该构成一遍(“遍”的概念请参考 文献1)，以词法分析生成的记号流作为输入，以某种表示程序结构的中间表示(语法树 或三地址码)作为输出。生成的中间代码是介

15、于源代码和目标代码中间的一种结构化表示。 它的意义在于能够把前端和后端分开，提高编译器的可移植性(因为结构清晰，对于编译器 研究者来说也提高了可读性)和易优化性(对中间代码的优化可以独立于机器)。2. 语法制导翻译：语法制导翻译是一种实现翻译的思路，不仅可以用来指导中间代码生成。实际上，应用 语法制导翻译的概念，可以实现任何基于语法分析器框架的语义动作，应用非常广泛。比如 把源代码中的算术表达式中缀表示化成前缀表达式，或者类似数学排版语言EQN的构造等 等。本文不对语法制导定义做广泛抑或深入的探讨，只简单介绍其基本原理，指导中间代码 生成器的设计。1 语法制导定义：语法制导定义是对上下文无关文法的推广，其中每个文法符号都有一个相关的属性集。 属性分为两个子集，分别称为该文法符号的综合属性和继承属性。属性可以代表任何对象： 字符串、数字、类型、内存单元或其他对象。分析树节点上属性的值由该节点所用产生式的 语义规则来定义。节点的综合属性是通过分析树中其子节点的属性值计算出来的；而继承属 性值则是由该节点的兄弟节点和父节点的属性值计算出来的。2 语法制导定义的形式：在语法制导定义中，每个产生式