中间代码生成

《中间代码生成》由会员分享，可在线阅读，更多相关《中间代码生成（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 语法制导定义：语法制导定义是对上下文无关文

16、法的推广，其中每个文法符号都有一个相关的属性集。 属性分为两个子集，分别称为该文法符号的综合属性和继承属性。属性可以代表任何对象： 字符串、数字、类型、内存单元或其他对象。分析树节点上属性的值由该节点所用产生式的 语义规则来定义。节点的综合属性是通过分析树中其子节点的属性值计算出来的；而继承属 性值则是由该节点的兄弟节点和父节点的属性值计算出来的。2 语法制导定义的形式：在语法制导定义中，每个产生式A - a都有一个形如b := f(cl,c2,ck)的语义规 则集合与之相关联，其中 f 是函数，且满足下列两种情况之一：i) b是A的一个综合属性，且cl,c2,ck是该产生式文法符号的属性ii

17、) b是产生式右部某个文法符号的一个继承属性，且cl,c2,ck也是该产生式文法 符号的属性。对这两种情况都称为属性b依赖于属性cl,c2,ck。有时，语法制导定义中的某个规 则的目的就是为了产生副作用，比如输出某个字符串或者操作某个结构等。这种语义规则一 般被写成过程调用或程序段。在针对语法制导定义的翻译中，把副作用看作非终结符的一个 虚综合属性值处理会比较方便。为了便于理解，以下给出一个台式计算器程序的语法制导定义表 1 台式计算器程序的语法制导定义产生式语义规则L弓Enpri nt( E.val)E 弓 E1 + TE.val=El.val + T.valE弓TE.val=T.valT

18、弓 T1 * FT.val=Tl.val * F.valT弓FT.val=F.valF 弓(E)F.val=E.valF T digitF.val=digit. lexval该定义将一个整数值综合属性 val 与每个非终结符 E,T 和 F 联系起来。对每个以 E,T 和F为左部的产生式,语义规则从产生式右部非终结符的val值计算出产生式左部非终结符 的 val 值。记号digit具有综合属性lexval，其值由词法分析器提供，而产生式LTEn所对应的 语义规则只是打印 E 所产生的算术表达式的值的过程，我们可以认为该规则为非终结符 L 定义了一个虚属性。3. 翻译模式语法制导定义只是给出了属

19、性值的计算标准，并没有给出属性值的计算顺序。实际上 在一个产生式中，右端非终结符的综合属性、继承属性、左端符号的继承属性的计算顺序是 有要求的。否则，则会出现引用尚未得到的值的翻译错误。由语法制导定义可以得到某种特 定的翻译模式，这个翻译模式不仅包含了语法制导定义的属性关系，还包括了计算它们的顺 序。当得到一个具体的翻译模式后，编码将变得非常简单。1 L 属性定义在介绍翻译模式之前，先介绍一种属性定义：L属性定义。它的特点是其属性总可以用 深度优先顺序来计算。基于带回溯的递归下降分析法的语法分析器和L属性结合，能够对词 法记号流进行自顶向下的一遍翻译。L 属性的规范化定义是：一个语法制导定义是

20、 L 属性定义，如果对每个产生式 ATXlX2Xn，其右部符号Xj (1= j addop T R1 | R - addop T print ddop.lexeme) R11 T - numT - num print(num.val)图是输入串9-5+2的分析树，每个语义动作都作为产生式左部所对应节点的子节点。实际上，我们将语义动作看成终结符，对确定动作何时执行来说，它是一种方便的助记符号。 图中用具体的数字和加(减)运算符代替了记号num和addop。当以深度优先顺序执行下图 中的动作时，其输出为 95-2+。ERTprint( - )R+ T print( +)Rprint(5)2prin

21、t( 2 )图 19-5+2 的带有动作的分析树在构造翻译模式时，要注意，如果同时存在继承属性和综合属性，则(1) 产生式右部符号的继承属性必须在这个符号以前的动作中计算出来。(2) 一个动作不能引用该动作右边符号的综合属性。(3) 产生式左部非终结符的综合属性只有在其引用的所有属性都计算出来以后才能计算 计算该属性的动作通常放在产生式右部的末尾。从一个 L 属性语法制导定义，我们总能构造出满足上述3 个条件的翻译模式。4. 语法树语法树是分析树的压缩形式，对表示语言的结构很有用。如产生式S 9 f B then SI elseS2 在语法树中可能出现为：图 2 if-then-else 语句

22、的语法树在语法树中，运算符和关键字不再是叶节点，而是作为内部节点成为分析树中叶节点 的父节点。语法树的另一个简化是单产生式(形如A 9 B)链可能消失mknode(head, descentl, descent2,)和 mkleaf(ID, id.place)是基于翻译模式构 造语法树的两种动作。前者建立一个树节点，如mknode(+, a, b)表示a+b的结构；后者 建立一个叶节点， id.place 指向标识符在符号表中的位置。语法树有两种表示，一种是指 针式，另一种是数组式。数组式用数组的下标取代节点的地址，是指针的另一种表现形式而 已，本质上没有大的差别。树的实现算法可以参考数据结构

23、。 本文的讨论重点是三地 址码的生成，故不对语法树做详细的阐述。5. 三地址码三地址码是下列一般形式的语句序列：x := y op z。其中，x、y以及z是名字、常 量或编译器生成的临时变量； op 代表操作符，例如定点或者浮点算术操作符，或者是布尔 型变量的逻辑操作符。注意这里不允许组合的算术表达式，因为语句右边只有一个操作符。 这样，像 x + y * z 这样的源语言表达式应该被翻译成如下序列：tl := y * zt2 := x + tltl 与 t2 是编译器生成的临时变量。这种复杂表达式及嵌套控制流语句的拆解使得三地 址码适合于目标代码生成及优化。由程序计算出来的中间值的名字的使用

24、使得三地址码容易 被重新排列。通用的三地址语句有以下几种(1) 形如x := y op z的赋值语句，其中，op是二元算术操作符或逻辑操作符。(2) 形如x := op y的赋值指令，其中op是一元操作符。(3) 形如x := y的复制语句，将y的值赋给x。(4) 无条件跳转语句goto L101。接下来将执行标号为L101的三地址语句。 形如if x relop y goto L101的条件跳转语句。这条指令对x和y应用逻辑操作符(， =,=等)，如果x与y满足relop关系则执行带有标号L101的语句。如果不满足，紧接 着执行 if x relop y goto L101 后面的语句，与通

25、常的顺序一样。 过程调用param x和call p及return y,其中y代表一个返回值，是可选的。它们的 典型应用如下面的三地址语句序列： param x1 param x2 param xncall p作为过程调用p(x1,x2, ，xn)的一部分生成。6. 中间代码生成1 三地址码的实现三地址码的实现方法为四元式。四元式是带有四个域的记录结构，即 op， arg1， arg2 以及result。其中视三地址码的类型，某些域可能为空arg1, arg2以及result域的内容 正常情况下是指向这些域所代表的名字在符号表表项的指针。这样的话，临时名字在生成时 一定要被填入符号表。对于支持

26、作用域规则的语言，生成三地址码时需要有一个符号表栈 栈顶的符号表代表当前作用域。源代码中的Par_table_chain结构实现了这个栈及其必须支 持的操作。2 声明语句的翻译这里用FineC语言声明语句的翻译模式说明声明语句翻译的原理FineC语言声明语句 的翻译模式及其解释如下：Ideclaration-list - declaration declaration-list1 | declaration1这条文法可以产生至少一个声明，declaration-list是起始符 IIdeclaration - var-declaration| Par_table_chain.mktable()

27、 fun-declarationPar_table_chain.jumpout()这条文法有两个候选式，第一个候选式var-declara tion匹配变量声明；当地一个候选 式匹配失败时，说明当前记号流是一个函数声明。进入一个函数声明后，会产生一个新的作 用域，一个作用域对应一个符号表，即Par_table。在这个函数声明中声明的变量如果和外 围作用域的变量重名，则应该在这个函数的符号表中加入这一变量。 Par_table_chain.mktable() 在进入下面的函数声明语法分析前，先生成一个新的符号 表，并把它置为当前符号表。外围符号表被挂起，外围符号表的地址被赋予新表。符号表链 Pa

28、r _t able_chain实际上是一个栈式结构，它的成员是有相互嵌套关系的符号表。函数声明 匹配完后，跳出它的作用域，把外围作用域置为当前活动作用域。III var-declaration - “int”ID; Par_table_chain.enter(ID.name, int, 4) 这条文法对应变量声明，当匹配完“分号”时，说明当前记号流的确是一个变量声明 (不需要回溯到II)。此时，在当前符号表中加入这个变量，三个参数分别是变量的名字, 类型和宽度。符号表中有一个offset值，初始为0,每加入一个变量则把offset值加上此变 量的宽度。如此一来，新加入的变量就能总是拥有正确的地

29、址(在符号表中的位置)。IV fun-declaration - type-specifier ID Par_table_chain.set_name_type(ID.name, type-specifier.type)Par_table_chain.add_to_previous() Quads_code.gen_entry(ID.name) (params) compound-stmt| type-specifier ID Par_table_chain.set_name_type(ID.name,type-specifier.type)Par_table_chain.add_to_pre

30、vious() Quads_code.gen_entry(ID.name) () compound-stmt这条文法很长。当匹配函数声明，得到其返回值类型和函数名时。先在当前函数的符号 表中附上当前函数的信息。然后在其外围作用域中加入这个函数项，参数为函数名，类型和 当前函数作用域编号(隐含加入，详见源代码)。然后生成一个“ntry函数名”的三地址 码，代表函数的入口在这里，调用函数时转向这个入口 Quads_code是三地址码数组。然后 视情况判断是否匹配参数，然后匹配函数体。注意，因为作用域的跳出在文法II中,所以在 匹配当前函数的参数和函数体时,发生的任何变量或函数声明,都被加入到当前函

31、数域中,也 就是我们想要的结果。V type-specifier - int type-specifier.type := int| void type-specifier.type := void匹配函数返回值的类型。VI params - param, params | param 这条文法生成至少一个参数。VII param - int ID Par_table_chain.enter(ID.name, int, 4) Quads_code.gen_param_load(Par_table_chain, load, ID.name)当发生参数的声明时，把此参数加入当前作用域中，然后生成形

32、如“load形参名”的 三地址码，与过程调用时的“param实参名” 一一对应。3 算术表达式的翻译FineC 算术表达式的翻译模式如下I additive-expression - term additive-expressionR.i := term.nameadditive-expressionRadditive-expression.name := additive-expressionR.s additive-expressionR - ADDOP term additive-expressionR.n := newtempPar_table_chain.enter(additive

33、-expressionR.n, int, 4) Quads_code.gen_tri(Par_table_chain, ADDOP.name,additive-expressionR.n, additive-expressionR.i, term.name) additive-expressionR1.i := additive-expressionR.n additive-expressionR1additive-expressionR.s := additive-expressionR1.s additive-expressionR - empty additive-expressionR

34、.s := additive-expressionR.i 上面的文法是经过了消除左递归的(语法制导翻译中消除左递归的算法参见参考文献l)newtemp在当前作用域中返回一个临时变量的名字，第一次调用返回$1,第二次调用 返回$2，以此类推。然后把这个临时变量放进符号表中。再生成以临时变量为result,以匹 配到的标识符为argl和arg2,(先在符号表中找到它，当前作用域的符号表找不到，则顺着 符号表栈往上找，如果找到最外层符号表依然找不到，说明发生了未声明变量的调用，程序 出错)，以ADDOP的真值(+或-)为op的四元式，放进Quads_code结构中。II. term - factor

35、 termR.i := factor.nametermR term.name := termR.stermR - MULOP factortermR.n := newtemp Par_table_chain.enter(termR.n, int, 4) Quads_code.gen_tri(Par_table_chain, MULOP.name, termR.n, termR.i, factor.name)termR1.i := termR.ntermR1 termR.s := termR1.stermR - empty termR.s := termR.i文法II实现的功能与I无异，II和I

36、结合，能够实现算术表达式的左结合性和优先级规 则。III. factor - (additive-expression) factor.name := additive-expression.name| ID factor.name := ID.name| call factor.name := call.name| NUM factor.name := int_to_str(NUM.value) 操作符运算对象或者是变量，或者是函数调用返回的结果，或者是整型字面值，或者 是括号中的表达式求得的值。4 控制流语句的翻译I selection-stmt - if ( to_true := new

37、label; to_false := newlabel condition-expression.to_true := to_true condition-expression.to_false := to_false condition-expression) Quads_code.gen_label(to_true) statement Quads_code.gen_label(to_false)| if ( to_true := newlabel; to_false := newlabel condition-expression.to_true := to_true condition

38、-expression.to_false := to_false condition-expression) Quads_code.gen_label(to_true) statement1 to_next = newlabel“else”Quads_code.gen_goto(to_next)Quads_code.gen_label(to_false)statement2 Quads_code.gen_label(to_next)FineC中的控制流语句有if-else和while两种。以上文法是if-else的翻译模式。f-then, f-then-else生成的三地址码如下图所示图3 f

39、-t hen， f-t hen-else 的中间代码当匹配到if后，调用newlabel返回一个语句编号(第一次调用返回101,第二次102, 第三次103, 次类推)，to_true, to_false作为condition-expression的两个继承属性， 用于生成E.code中条件转向三地址码的goto目的地。condition-expresson成功匹配后，生 成一个三地址码“L101”，表示当上面的条件为真时，转向这一条语句往下执行，然后调用 stat emen t函数匹配if-then的执行函数体。匹配结束后，生成一个三地址码L102”，表示 当上面的条件为假是，转向这一条语句

40、往下执行。这样一来，当condition-expression为假 时，就自然地跨过了stat emen t的语句不执行。if-then-else的翻译与if-then有一样的原理，区别只在于E.false的指向是另一个 stat emen t,而在Stat emen t1后面放一个无条件跳转语句，即表示“执行完stat emen t1后不 需要再执行stat emen t2”。II. iteration-stmt - while ( to_begin := newlabelQuads_code.gen_label(to_begin) to_true := newlabel; to_false

41、 := newlabel condition-expression.to_true := to_true condition-expression.to_false := to_false condition-expression) Quads_code.gen_label(to_true) statement Quads_code.gen_goto(to_begin)Quads_code.gen_label(to_false)while语句生成的三地址码如下图所示while语句的翻译思路也与if-then类似，只是在Sl.code后面有一条“ go to S.begin”， 表示函数体执行结

42、束后回到S.begin再次检查E.code的真假，当E.code为假时，跨过“goto S.begin”，也就结束了整个while的执行。注意，if-then语句和while语句的函数体都是 stat emen t,也就是说，它们都有各自的作用域。III. condition-expression-additive-expression1RELOPadditive-expression2 Quads_code.gen_condition(Par_table_chain, RELOP.name, additive-expression1.name, additive-expression2.na

43、me, condition-expression.to_true) Quads_code.gen_goto(condition-expression.to_false)文法III生成布尔表达式E.code的代码，需要与文法I，II的翻译思路相匹配。5 过程声明和调用的翻译函数声明的翻译已经在前面说明，下面是FineC语言中过程调用语句的翻译I call - ID ( call.name := newtemp Par_table_chain.enter(call.name, int, 4) Quads_code.gen_uni(begin_args)args ) Quads_code.gen_c

44、all(Par_table_chain, ID.name) | ID ( call.name := newtemp Par_table_chain.enter(call.name, int, 4)Quads_code.gen_uni(begin_args) Quads_code.gen_call(Par_table_chain, ID.name) II args - additive-expression Quads_code.gen_param_load(Par_table_chain,param,additive-expression.name) , args| additive-expr

45、ession Quads_code.gen_param_load(Par_table_chain, param, additive-expression.name) 当发生函数调用时，先生成一个当前作用域下的临时变量，用来代表返回值。然后生成 一个“begin_args”的三地址码，表示开始发送实参。然后进入文法I匹配实参，每次匹配 到一个，输出一个“param实参”形式的三地址码。实参匹配完毕后，生成“all函数名” 语句，转向相应的“enter函数名”。四、FineC语言中间代码生成的完整翻译模式I. program - Par_table_chain.mktable() declarat

46、ion-list2declaration-list - declaration declaration-list1 | declaration1 3declaration - var-declaration| Par_table_chain.mktable() fun-declaration Par_table_chain.jumpout()4 var-declaration - “int”ID; Par_table_chain.enter(ID.name, int, 4) 5 fun-declaration - type-specifier ID Par_table_chain.set_na

47、me_type(ID.name, type-specifier.type) Par_table_chain.add_to_previous() Quads_code.gen_entry(ID.name) (params) compound-stmt| type-specifier ID Par_table_chain.set_name_type(ID.name, type-specifier.type) Par_table_chain.add_to_previous() Quads_code.gen_entry(ID.name) () compound-stmt6 type-specifier

48、 - int type-specifier.type := int| void type-specifier.type := void7 params - param, params | param8 param - int ID Par_table_chain.enter(ID.name, int, 4) Quads_code.gen_param_load(Par_table_chain, load, ID.name)9. compound-stmt - local-declarations statement-list10. local-declarations - var-declara

49、tion local-declarations | emptyII. statement-list - statement statement-list | empty12. statement - expression-stmt | selection-stmt | iteration-stmt| return-stmt| Par_table_chain.mktable() Par_table_chain.add_to_previous()compound-stmt Par_table_chain.jumpout() 13. expression-stmt - expression; | ;

50、14 selection-stmt - if ( to_true := newlabel; to_false := newlabel condition-expression.to_true := to_true condition-expression.to_false := to_false condition-expression) Quads_code.gen_label(to_true) statement Quads_code.gen_label(to_false)| if ( to_true := newlabel; to_false := newlabel condition-

51、expression.to_true := to_truecondition-expression.to_false := to_false condition-expression) Quads_code.gen_label(to_true) statement1 to_next = newlabel“else”Quads_code.gen_goto(to_next)Quads_code.gen_label(to_false)statement2 Quads_code.gen_label(to_next)15. iteration-stmt - while ( to_begin := new

52、labelQuads_code.gen_label(to_begin) to_true := newlabel; to_false := newlabel condition-expression.to_true := to_true condition-expression.to_false := to_false condition-expression) Quads_code.gen_label(to_true) statement Quads_code.gen_goto(to_begin)Quads_code.gen_label(to_false)16. condition-expre

53、ssion - additive-expression1 RELOP additive-expression2 Quads_code.gen_condition(Par_table_chain, RELOP.name,additive-expression1.name, additive-expression2.name, condition-expression.to_true) Quads_code.gen_goto(condition-expression.to_false) 17.return-stmt - “return”; Quads_code.gen_uni(return) |

54、“ return ”expression; Quads_code.gen_param_load(Par_table_chain, return, expression.name)18.expression - ID = expression1 Quads_code.gen_bi(Par_table_chain, ID.name,expression1.name) expression.name := ID.name | additive-expression expression.name :=additive-expression.name 19 additive-expression -

55、term additive-expressionR.i := term.nameadditive-expressionRadditive-expression.name := additive-expressionR.s 20 additive-expressionR - ADDOP term additive-expressionR.n := newtempPar_table_chain.enter(additive-expressionR.n, int, 4) Quads_code.gen_tri(Par_table_chain, ADDOP.name,additive-expressio

56、nR.n, additive-expressionR.i, term.name)additive-expressionR1.i := additive-expressionR.n additive-expressionR1additive-expressionR.s := additive-expressionR1.s | empty additive-expressionR.s := additive-expressionR.i21. term - factor termR.i := factor.name termR term.name := termR.s22. termR - MULO

57、P factor termR.n := newtemp Par_table_chain.enter(termR.n, int, 4) Quads_code.gen_tri(Par_table_chain, MULOP.name,termR.n, termR.i, factor.name)termR1.i := termR.n termR1 termR.s := termR1.s| empty termR.s := termR.i23. factor - (additive-expression) factor.name := additive-expression.name| ID facto

58、r.name := ID.name| call factor.name := call.name| NUM factor.name := int_to_str(NUM.value) 24. call - ID ( call.name := newtemp Par_table_chain.enter(call.name, int, 4) Quads_code.gen_uni(begin_args)args ) Quads_code.gen_call(Par_table_chain, ID.name) | ID ( call.name := newtemp Par_table_chain.ente

59、r(call.name, int, 4)Quads_code.gen_uni(begin_args) Quads_code.gen_call(Par_table_chain, ID.name) 25 args - additive-expression Quads_code.gen_param_load(Par_table_chain,param,additive-expression.name) , args| additive-expression Quads_code.gen_param_load(Par_table_chain, param,additive-expression.na

60、me) 五、程序运行结果把如下源程序作为输入：/* A J */int gcd (int u, int v) if (v = 0) return u ;else return gcd(v, u-u/v*v);/* u-u/v*v = u mod v */void main() int x; int y; int z;x = 3;y = 4;z = gcd(x,y);运行结果是生成的三地址码序列，如下图所示：六、总结中间代码生成作为编译器设计中的中间步骤，肩负着与前端和后端协作的重要任务。设 计良好的中间代码生成器能够生成结构清晰的中间代码，为其后的中间代码优化和代码生 成，乃至最终形成的可执行代码的效率提升打下良好的基础。本文讨论了一个轻量级语言的 中间代码生成问题，通过研究FineC语言的中间代码生成器，发现随着语言文法定义变得复 杂，中间代码生成器的代码规模将急剧增长。在如此迅速增长的情况下设计出稳定、高效的 中间代码生成器对于编译器设计者是一个很大的挑战。遗憾的是由于中间代码生成原理的复 杂性，现在还没有找到一种规范化的数学模式，能够构造出中间代码生成器的生成器，而只 能靠手工编写。附录中的源代码是作者实践的结果，不足之处依然很明显，尤其在错误处理 方面尚待改善。参考文献1 编译原理：