中间代码生成

计算机科学与工程学院课程设计报告题目全称：常用边缘算法的实现学生学号：2506203010姓名：王嘉指导老师：职称：指导老师评语：签字：课程设计成绩：设计过程表现设计报告质量总分编译器中间代码生成的研究与实现作者：王嘉学号：2506203010指导老师：吴洪摘要：在编译器的翻译流水线中，中间代码生成是处于核心地位的关键步骤。它的实现基于语法分析器的框架，并为目标机器代码的实现提供依据。虽然在理论上没有中间代码生成器的编译器也可以工作，但这将会带来编译器的高复杂度，低稳定性和难移植性。现代编译理论不仅要求中间代码的生成，还要求基于中间代码的优化。本文研究并实现了一个轻量级类C语言的中间代码生成器，并就中间代码生成的原理进行了细致的阐述。关键字：中间代码生成、语法制导翻译、翻译模式、语法树、三地址码一、目的及意义在编译器的分析综合模型中，前端将源程序翻译成一种中间表示，后端根据这个中间表示生成目标代码。目标语言的细节要尽可能限制在后端。尽管源程序可以直接翻译成目标语言，但使用与机器无关的中间形式具有以下优点：1.重置目标比较容易：不同机器上的编译器可以在已有前端的基础上附近一个适合这台新机器的后端来生成。2.可以在中间表示上应用与机器无关的代码优化器。本文介绍如何使用语法制导方法，基于一种轻量级的类C语言FineC的词法分析器和语法分析器，一遍地将源程序翻译成中间形式的编程语言结构，如声明、赋值及控制流语句。为简单起见，我们假定源程序已经经过一遍扫描，生成了相应的词法记号流和符号表、词素表结构。基于FineC语法标准的语法分析器框架也已经能够正常工作。我们的任务就是补充这个框架，使其在语法分析的过程中生成相应的中间代码，并将必要的变量和函数声明存放在一个符号表链中。二、目标语言词法和语法标准：这里定义一个编程语言称作FineC（“fine”指代轻量、精妙）。它是一种适合编译器设计方案的语言。本质上是C语言的一个限制了数据类型、算术操作、控制结构和处理效率的轻量子集。1.FineC语言的词法描述：[1]语言的关键字：elseifreturnwhileintvoid所有的关键字都是保留字，并且必须是小写[2]下面是专用符号：+-*/====!==;,{}()/**/RELOP={====!=}ADDOP={+-}MULOP={*/}[3]其他标记是NUM和ID，由正则表达式定义：ID=letter(letter|digit)*NUM=digitdigit*letter=a|…|z|A|…|Zdigit=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的实践中，我们用一个vectortoken容器来存放词法分析器返回的这些记号。语法分析器在这个缓冲区（容器）之上，进行匹配、回溯等必要的操作，实现语法分析。常见的语法分析方法有三种：带回溯的递归下降法、预测分析法（不带回溯的递归下降）以及常用于语法分析器自动生成的LR文法分析。前两者属于自顶向下的分析，后者属于自底向上的分析。FineC的语法分析器基于带回溯的递归下降法实现，在分析的过程中可能产生递归和回溯。当发生回溯时，意味着出现了某个记号的匹配失败，但在其之前某些记号可能已经被成功匹配并扫描。因此回溯到上层调用时，不仅要恢复指向记号流的指针，也需要考虑是否已经生成了无效的中间代码，并对其进行撤销。语法分析器的原理和实现不是本文讨论的范畴，这里只给出FineC语言的文法标准和简单的语义解释，供中间代码生成时建立翻译模式使用：(1)program--declaration-list程序由一个声明表组成(2)declaration-list--declarationdeclaration-list|declaration声明表包含至少一条声明(3)declaration--var-declaration|fun-declaration声明可以是变量声明或函数声明(4)var-declaration--“int”ID;由于FineC只支持整型，所以变量声明也只有“intID”的形式。注意，不支持变量声明时赋初值。(5)fun-declaration--type-specifierID(params)compound-stmt|type-specifierID()compound-stmt函数的返回类型可以是“int”或“void”，函数可以有参数也可以没有(6)type-specifier--int|void(7)params--paramparams|param如果函数有形参，则至少要有一个参数(8)param--“int”ID函数的形参也只支持“int”一种(9)compound-stmt--{local-declarationsstatement-list}函数的主体是一个语句块，包含局部变量的声明和语句表。注意，所有的局部变量声明必须出现在语句之前。(10)local-declarations--var-declarationlocal-declarations|empty局部变量声明可以为空，一个，或多个(11)statement-list--statementstatement-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|“if”(condition-expression)statement“else”statement选择语句支持一路分支和二路分支。根据condition-expression的真假决定程序控制流的流向。(15)iteration-stmt--while(condition-expression)statement循环语句只支持“while”的形式，while语句的含义与C语言一致。(16)return-stmt--“return”;|“return”expression;返回语句可以返回值，也可以什么都不返回。(17)expression--ID=additive-expression|additive-expression表达式可以是赋值语句或者加法运算语句，其中赋值语句返回ID的值。(18)condition-expression--additive-expressionRELOPadditive-expression条件表达式比较两个整型值的关系，包括大于，小于，大于等于，小于等于，不等于和等于，根据其真值指向不同的语句流向(19)additive-expression--addtive-expressionADDOPterm|term(20)term--termMULOPfactor|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]语法制导定义：语法制导定义是对上下文无关文法的推广，其中每个文法符号都有一个相关的属性集。属性分为两个子集，分别称为该文法符号的综合属性和继承属性。属性可以代表任何对象：字符串、数字、类型、内存单元或其他对象。分析树节点上属性的值由该节点所用产生式的语义规则来定义。节点的综合属性是通过分析树中其子节点的属性值计算出来的；而继承属性值则是由该节点的兄弟节点和父节点的属性值计算出来的。[2]语法制导定义的形式：在语法制导定义中，每个产生式A--a都有一个形如b:=f(c1,c2,…,ck)的语义规则集合与之相关联，其中f是函数，且满足下列两种情况之一：i)b是A的一个综合属性，且c1,c2,…,ck是该产生式文法符号的属性ii)b是产生式右部某个文法符号的一个继承属性，且c1,c2,…,ck也是该产生式文法符号的属性。对这两种情况都称为属性b依赖于属性c1,c2,…,ck。有时，语法制导定义中的某个规则的目的就是为了产生副作用，比如输出某个字符串或者操作某个结构等。这种语义规则一般被写成过程调用或程序段。在针对语法制导定义的翻译中，把副作用看作非终结符的一个虚综合属性值处理会比较方便。为了便于理解，以下给出一个台式计算器程序的语法制导定义表1台式计算器程序的语法制导定义产生式语义规则LEnprint(E.val)EE1+TE.val:=E1.val+T.valETE.val:=T.valTT1*FT.val:=T1.val*F.valTFT.val:=F.valF(E)F.val:=E.valFdigitF.val:=digit.lexval该定义将一个