编译原理_07中间代码及其他.ppt

1,第8章语法制导翻译和中间代码生成,主要内容,概述属性文法语法制导翻译概述中间语言,3,课题：中间代码及其他目的要求：1.掌握中间代码的表示方式；2.了解教学重点：中间代码的表示方式。教学难点：教学课时：2教学方法：多媒体教学教学内容和步骤：（如下）,第十五讲,4,概述,编译程序的任务是把源程序翻译成语义上等价的目标程序。通常，在编译过程中，经过词法分析和语法分析之后，接下来将进行语义分析与处理。编译中的语义处理包括两个功能：第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。有时把这个工作称为静态语义分析或静态审查。第二，如果静态语义正确，语义处理则要执行真正的翻译，即生成某种中间代码或者实际的目标代码。本章引入属性文法和语法制导翻译方法的基本思想，介绍几种典型的中间代码形式和一些常见语法成分的翻译方法。,5,8.1属性文法,属性，通常用来描述事物的特征、性质、品质等。属性文法的形式定义：一个属性文法形式上可定义为一个三元组A，A=（G，V，F）。其中G表示一个上下文无关文法；V表示属性的有穷集；F表示有关属性的断言或谓词的有穷集。在属性文法中:（1）每个属性t都与某个文法符号N相关联，用N.t来表示。例如N.type表示与N关联的属性type。（2）每个断言与文法的某个规则相关联。（3）如果对G中的某一输入串（句子）而言，A中的所有断言对该输入串的语法树结点的属性全为真，则该串也是A语言中的句子。,6,编译程序的静态语义审查工作就是验证关于所编译的程序的断言是否全部为真。如文法GS：EF1F2F1orF2Fnumtruefalse与每个非终结符F相联的属性有type，type为int或者bool。关于类型检验的属性文法可以表示为：EFlF2F1.type:=intANDF2.type:=intEF1orF2F1.type:=boolANDF2.type:=boolFnumF.type:=intFtrueF.ype:=boolFfalseF.ype:=bool由上可知，与非终结符E的产生式相联的断言指明：两个F的属性必须相同。,7,属性可以分为综合属性和继承属性两类。综合属性一般用于自下而上传递信息，而继承属性常常用于自上而下传递信息。下述为简单算术表达式求值的属性文法：规则语义规则1.SEprint（E.val）2.EE1TE.val:=E1.valT.val3.ETE.va1:=T.valv4.TT1FT.val:=T1.valF.val5.TT1T.val:=T1.val6.F（E）F.val:=E.val7.FdigitF.val:=digit.lexval每一个非终结符都有一个表示整数值的属性val。规则左部符号E、T、F的属性值取决于各自规则的右部，称为综合属性；对于文法符号S，其属性是虚的或空的。,8,8.3中间语言,所谓中间语言，也称中间代码，是复杂性介于源程序语言和机器语言的一种记号系统。一般来说，快速编译程序直接生成目标代码，没有将中间代码翻译成目标代码的额外开销。但是为了使编译程序结构在逻辑上更为简单明确，使生成的的目标代码更为高效，通常采用中间语言。编译程序所使用的中间语言形式较多。常见的有逆波兰式、三元式、四元式和树形表示等等。,9,8.3.1逆波兰式,逆波兰式是最简单的一种中间语言形式，也称做后缀式。它的特点是将运算对象写在前面，把运算符号写在后面。对于简单表达式E，相应的逆波兰式E遵循下面的转换规则：表达式逆波兰式EE(E)EEE（负号“”是一元运算符，为了区别于减号“”，通常写成）E1opE2E1E2op,10,用逆波兰式表示表达式，其最大的优点是易于计算机进行计算处理。例.算术表达式xyz的逆波兰式为xyz，在栈中的计值过程如图所示。,由于逆波兰式表示上的简单和计值的方便，因此特别适用于解释执行的程序设计语言的中间表示，也方便具有堆栈体系的计算机的目标代码生成。,11,8.3.2三元式和树形表示,一三元式三元式是中间语言的另一种形式，每个三元式由三个部分组成:op，arg1，arg2。其一般格式为：（i）（op，arg1，arg2）表达式abcd可用三元式表示为：（1）（，a，）（2）（，（1），b）（3）（，c，d）（4）（，（2），（3）“”是一目运算符（这里用表示），用来使a取反，对于一目运算，不妨规定只用arg1。,12,二树形表示树形表示实际上是三元式的另一种表示形式。表达式的树形表示非常容易实现：简单直观。例如，表达式abcd的树形表示：,13,三间接三元式间接三元式是对三元式的一种补充。为了在进行代码优化时尽量不改变三元式表，于是另设一张间接码表来表示有关三元式在三元式表的计值顺序。用这种方法获得的中间代码称为间接三元式。如表达式a:=xyzb:=tyz的间接三元式表示：,14,8.3.3四元式和三地址码,一四元式四元式是比较普遍采用的一种中间语言形式。与三元式类似，四元式由四个部分组成：op，arg1，arg2，t。四元式的一般格式为：（i）（op，arg1，arg2，t）例如，表达式a:=bcd的四元式表示如下:（1）（，c，d，t1）（2）（，b，t1，t2）（3）（:=，t2，b，a）四元式和三元式的不同之处主要在于对中间结果的引用方式：四元式之间的联系是通过引入临时变量来实现，而三元式则是通过三元式编号来传递中间结果的。,15,二三地址码三地址代码也可以看成是四元式的另一种表示方式，它比四元式更直观、更易于理解。三地址码的一般格式为t:=arg1oparg2其形式就是一个赋值语句，只是与赋值语句不同的是：在三地址码中赋值符号的右边最多只能有一个运算符。表达式a:=bcd的三地址码序列:（1）t1:=cd（2）t2:=bt1（3）a:=t2三地址码简单直观，这种表示形式对中间代码的优化和目标代码的生成非常有利。,16,符号表运行时存储空间的组织代码优化目标代码生成,17,一.符号表,一般来说符号表须保存如下一些内容：1.类型名以及它的定义；2.变量名以及类型；3.常量名、类型和值；4.过程或函数名、形参和局部变量、值单元及过程入口地址；5.类；6.继承；7.模块的大小，名字，根源，成员以及时间标志。,1.符号表的内容,18,(1)名子(2)类型(3)存储类别(4)作用域及可视性(5)存储分配信息(6)其它属性:数组内情向量、记录结构型的成员信息、函数及过程的形参,3.符号的主要属性有：,（1）下文语义的合法性检查的依据（2）代码生成阶段地址分配的依据,2.符号表的作用,19,大致可有如下几类：插入:往符号表中插入一个新的名字；查找：查询:对给定名字，在符号表中查询其有关信息；更新：对给定名字，在符号表填写或更新它的某些信息；删除：在符号表中删除一个或多个无用项。,4.对符号表的操作,20,运行时存储空间划分为：生成目标代码，数据对象和跟踪过程活动的控制栈。一个称为堆（heap)的运行时存储空间单独区域用来存放动态数据。运行时存储空间划分如图所示,1.运行时存储空间划分,二.运行时存储空间的组织,21,如果一个程序语言不允许有递归过程，不允许含有可变体积的数据项目或待定性质的名字，那么就能在编译时完全确定其程序的每个数据项目存储空间的位置，这种策略叫做静态分配策略。程序运行时，每当进入一个过程或分程序，其所需的数据空间就动态地分配于栈顶，一旦该过程或分程序运行结束，其所占用的空间就予以释放，这种方法叫做动态分配策略。,静态分配策略和动态分配策略：,2.存储分配策略,22,从优化的时间上来分，优化可分为对源程序的优化、对中间代码的有对目标代码的优化。从优化与源程序的关系出发，又可把优化分为局部优化、循环优化和全局优化。,三.代码优化,1.优化分类,合并常量运算；删除公共子表达式；减少复写传播；消除无用代码；削减运算强度；外提循环中的不变表达式；删除归纳变量。,2.常用的优化方法,23,合并常量运算；删除公共子表达式；减少复写传播；消除无用代码；削减运算强度；外提循环中的不变表达式；删除归纳变量,2.常用的优化方法,24,三.目标代码生成,将源程序的中间代码作为输入，生成等价目标程序的程序称为目标代码生成器（简称代码生成器）。一般而言目标代码有以下三种形式：(1)能够立即执行的机器语言代码，所有地址均已定位；(2)待装配的机器语言模块；(3)汇编语言代码，尚需经过汇编程序汇编，转换成可执行的机器语言代码。代码生成器在设计时要着重考虑两个问题：一是如何使生成的目标代码较短；另一是如何充分利用计算机的寄存器，减少目标代码中访问存储单元的次数。这两个问题都直接影响目标代码的执行速度。,25,设计代码生成器时需要处理的一般问题：（1）代码生成器的入口信息：包括中间代码和符号表中的信息（2）代码生成器的出口信息：是把语义分析后或优化后的