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

1、1 语法制导翻译和语法制导翻译和中间代码生成中间代码生成主要内容 概述概述 属性文法属性文法 语法制导翻译概述语法制导翻译概述 中间语言中间语言 3课题：课题：中间代码及其他目的要求：目的要求： 1.掌握中间代码的表示方式； 2.了解 教学重点：教学重点： 中间代码的表示方式。教学难点教学难点 ： 教学课时：教学课时：2教学方法：教学方法：多媒体教学教学内容和步骤教学内容和步骤 ：（如下）第 十五 讲4概概 述述 编译程序的任务编译程序的任务是把源程序翻译成语义上等价的目是把源程序翻译成语义上等价的目标程序。通常，在编译过程中，经过词法分析和语法标程序。通常，在编译过程中，经过词法分析和语法分

2、析之后，分析之后， 接下来将进行语义分析与处理。接下来将进行语义分析与处理。 编译中的编译中的语义处理包括两个功能语义处理包括两个功能：第一，审查每个：第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。有时把这个工作称为否真正有意义。有时把这个工作称为静态语义分析静态语义分析或或静态审查。第二，如果静态语义正确，语义处理则要静态审查。第二，如果静态语义正确，语义处理则要执行真正的翻译，即生成某种中间代码或者实际的目执行真正的翻译，即生成某种中间代码或者实际的目标代码。标代码。 本章引入属性文法和语法制导翻译方法的基本思想，本

3、章引入属性文法和语法制导翻译方法的基本思想，介绍几种典型的中间代码形式和一些常见语法成分的介绍几种典型的中间代码形式和一些常见语法成分的翻译方法。翻译方法。 58.1 8.1 属性文法属性文法 属性属性，通常用来描述事物的特征、性质、品质等。，通常用来描述事物的特征、性质、品质等。 属性文法的形式定义：一个属性文法形式上可定义属性文法的形式定义：一个属性文法形式上可定义为一个三元组为一个三元组A，A=A=（G G，V V，F F）。其中其中G表示一个上表示一个上下文无关文法；下文无关文法；V表示属性的有穷集；表示属性的有穷集；F表示有关属性表示有关属性的断言或谓词的有穷集。的断言或谓词的有穷集

4、。 在属性文法中在属性文法中:（1）每个属性）每个属性t都与某个文法符号都与某个文法符号N相关联，用相关联，用N.t来表来表示。例如示。例如N.type表示与表示与N关联的属性关联的属性type。（2）每个断言与文法的某个规则相关联。每个断言与文法的某个规则相关联。（3）如果对）如果对G中的某一输入串（句子）而言，中的某一输入串（句子）而言， A中的中的所有断言对该输入串的语法树结点的属性全为真，则所有断言对该输入串的语法树结点的属性全为真，则该串也是该串也是A语言中的句子。语言中的句子。 6 编译程序的静态语义审查工作就是验证关于所编译的编译程序的静态语义审查工作就是验证关于所编译的程序的断

5、言是否全部为真程序的断言是否全部为真。如文法如文法GS：EF1F2F1 or F2 Fnumtrue false 与每个非终结符与每个非终结符F相联的属性有相联的属性有type，type为为int或者或者bool。关于类型检验的属性文法可以表示为：关于类型检验的属性文法可以表示为： EFlF2 F1.type := int AND F2.type := intEF1 or F2 F1.type := bool AND F2.type := boolFnum F.type := intFtrue F.ype := boolFfalse F.ype := bool 由上可知，与非终结符由上可知，与

6、非终结符E的产生式相联的断言指明：的产生式相联的断言指明：两个两个F的属性必须相同。的属性必须相同。7 属性可以分为属性可以分为综合属性综合属性和和继承属性继承属性两类。综合属性一两类。综合属性一般用于自下而上传递信息，而继承属性常常用于自上而般用于自下而上传递信息，而继承属性常常用于自上而下传递信息。下述为简单算术表达式求值的属性文法：下传递信息。下述为简单算术表达式求值的属性文法： 规则规则 语义规则语义规则 1. SE print（E.val） 2. EE1T E.val := E1.valT.val 3. ET E.va1 := T.valv 4. TT1 F T.val := T1.

7、val F.val 5. TT1 T.val := T1.val 6. F（E） F.val := E.val 7. Fdigit F.val := digit.lexval 每一个非终结符都有一个表示整数值的属性每一个非终结符都有一个表示整数值的属性val。规规则左部符号则左部符号E、T、F的属性值取决于各自规则的右部，的属性值取决于各自规则的右部，称为综合属性；对于文法符号称为综合属性；对于文法符号S，其属性是虚的或空的。其属性是虚的或空的。 88.3 8.3 中间语言中间语言 所谓所谓中间语言中间语言，也称中间代码，是复杂性介于源程序，也称中间代码，是复杂性介于源程序语言和机器语言的一种

8、记号系统。一般来说，快速编译语言和机器语言的一种记号系统。一般来说，快速编译程序直接生成目标代码，没有将中间代码翻译成目标代程序直接生成目标代码，没有将中间代码翻译成目标代码的额外开销。但是为了使编译程序结构在逻辑上更为码的额外开销。但是为了使编译程序结构在逻辑上更为简单明确，使生成的的目标代码更为高效，通常采用中简单明确，使生成的的目标代码更为高效，通常采用中间语言。间语言。 编译程序所使用的中间语言形式较多。常见的有编译程序所使用的中间语言形式较多。常见的有逆波逆波兰式兰式、三元式三元式、四元式四元式和和树形表示树形表示等等。等等。 98.3.1 8.3.1 逆波兰式逆波兰式 逆波兰式是逆

9、波兰式是最简单最简单的一种中间语言形式，也称做的一种中间语言形式，也称做后缀后缀式式。它的特点是将运算对象写在前面，把运算符号写在。它的特点是将运算对象写在前面，把运算符号写在后面后面。对于简单表达式对于简单表达式E，相应的逆波兰式相应的逆波兰式E遵循下面遵循下面的转换规则：的转换规则：表达式表达式 逆波兰式逆波兰式E E(E) EE E （负号负号“”是一元运算符，为了区别于减号是一元运算符，为了区别于减号“”，通常写成通常写成）E1 op E2 E1 E2 op10 用逆波兰式表示表达式，其最大的优点是易于计算机用逆波兰式表示表达式，其最大的优点是易于计算机进行计算处理。进行计算处理。例例

10、. .算术表达式算术表达式x xy y z z 的逆波兰式为的逆波兰式为xyzxyz ，在栈在栈中的计值过程如图所示。中的计值过程如图所示。 t1:=t1:=x xx xt1t1y yz zt2:=yt2:=y z zt1t1t2t2t3:=t1t3:=t1t2t2同时同时y y、z z入栈入栈t3t3 由于逆波兰式表示上的简单和计值的方便，因此特别由于逆波兰式表示上的简单和计值的方便，因此特别适用于解释执行的程序设计语言的中间表示，也方便适用于解释执行的程序设计语言的中间表示，也方便具有堆栈体系的计算机的目标代码生成。具有堆栈体系的计算机的目标代码生成。 118.3.28.3.2三元式和树形

11、表示三元式和树形表示 一三元式一三元式三元式是中间语言的另一种形式，每个三元式由三个部三元式是中间语言的另一种形式，每个三元式由三个部分组成分组成:op，arg1，arg2。其一般格式为：其一般格式为：（i i）（）（opop，arg1arg1，arg2arg2）表达式表达式a bc d可用三元式表示为：可用三元式表示为：（1）（）（ ， a ， ） （2）（）（ ， （1），）， b ）（3）（）（ ， c ， d ）（4）（）（ ， （2），（），（3）“”是一目运算符（这里用是一目运算符（这里用表示），用来使表示），用来使a取反，取反，对于一目运算，不妨规定只用对于一目运算，不妨规定只用

12、arg1。 12二树形表示二树形表示 树形表示实际上是三元式的另一种表示形式。表达式树形表示实际上是三元式的另一种表示形式。表达式的树形表示非常容易实现：简单直观。的树形表示非常容易实现：简单直观。例如，表达式例如，表达式a bc d的树形表示：的树形表示： a a b b d dc c13三间接三元式三间接三元式 间接三元式是对三元式的一种补充。为了在进行代码间接三元式是对三元式的一种补充。为了在进行代码优化时尽量不改变三元式表，于是另设一张间接码表来优化时尽量不改变三元式表，于是另设一张间接码表来表示有关三元式在三元式表的计值顺序。用这种方法获表示有关三元式在三元式表的计值顺序。用这种方法

13、获得的中间代码称为间接三元式。如表达式得的中间代码称为间接三元式。如表达式a := xy z b := ty z的间接三元式表示的间接三元式表示 ：三元式列表三元式列表间接码表间接码表（1）（）（ ，y，z）（2）（，）（，x，（，（1）（3）（）（:=，a，（，（2）（4）（，）（，t，（，（1）（5）（）（:=，（，（4）（1）（2）（3）（1）（4）（5）148.8.3.3 3.3 四元式和三地址码四元式和三地址码 一四元式一四元式四元式是比较普遍采用的一种中间语言形式。与三元式四元式是比较普遍采用的一种中间语言形式。与三元式类似，四元式由四个部分组成：类似，四元式由四个部分组成：op，

14、arg1，arg2，t。四元式的一般格式为：四元式的一般格式为： （i） （op， arg1， arg2， t）例如，表达式例如，表达式a := bc d的四元式表示如下的四元式表示如下:（1）（）（ ， c， d， t1）（2）（）（ ， b， t1， t2）（3）（）（:= ， t2， b b， a ） 四元式和三元式的不同之处主要在于对中间结果的引四元式和三元式的不同之处主要在于对中间结果的引用方式：四元式之间的联系是通过引入临时变量来实现，用方式：四元式之间的联系是通过引入临时变量来实现，而三元式则是通过三元式编号来传递中间结果的。而三元式则是通过三元式编号来传递中间结果的。 15二三

15、地址码二三地址码 三地址代码也可以看成是四元式的另一种表示方式，三地址代码也可以看成是四元式的另一种表示方式，它比四元式更直观、更易于理解。它比四元式更直观、更易于理解。 三地址码的一般格式为三地址码的一般格式为 t:= arg1 op arg2t:= arg1 op arg2 其形式就是一个赋值语句，只是与赋值语句不同的是：其形式就是一个赋值语句，只是与赋值语句不同的是：在三地址码中赋值符号的右边最多只能有一个运算符。在三地址码中赋值符号的右边最多只能有一个运算符。 表达式表达式a := bc d的三地址码序列的三地址码序列:（1）t1 := c d（2）t2 := bt1（3）a := t

16、2 三地址码简单直观，这种表示形式对中间代码的优化三地址码简单直观，这种表示形式对中间代码的优化和目标代码的生成非常有利。和目标代码的生成非常有利。16符号表符号表运行时存储空间的组织运行时存储空间的组织代码优化代码优化目标代码生成目标代码生成17一一. .符号表符号表一般来说符号表须保存如下一些内容：一般来说符号表须保存如下一些内容：1.1.类型名以及它的定义；类型名以及它的定义； 2.2.变量名以及类型；变量名以及类型；3.3.常量名、类型和值常量名、类型和值；4. .过程或函数名、形参和局部变量、值单元及过程入过程或函数名、形参和局部变量、值单元及过程入口地址；口地址；5.5.类；类；6

17、.6.继承；继承；7.7.模块的大小，名字，根源，成员以及时间标志。模块的大小，名字，根源，成员以及时间标志。1. 符号表的内容符号表的内容18(1)(1)名子名子 (2)(2)类型类型 (3)(3)存储类别存储类别 (4)(4)作用域及可视性作用域及可视性 (5)(5)存储分配信息存储分配信息 (6)(6)其它属性其它属性: :数组内情向量、记录结构型的成数组内情向量、记录结构型的成员信息、函数及过程的形参员信息、函数及过程的形参 3. 符号的主要属性有：符号的主要属性有：（1 1）下文语义的合法性检查的依据）下文语义的合法性检查的依据 （2 2）代码生成阶段地址分配的依据）代码生成阶段地址

18、分配的依据 2. 符号表的作用符号表的作用19大致可有如下几类：大致可有如下几类： 插入插入: : 往符号表中插入一个新的名字；往符号表中插入一个新的名字； 查找：查找： 查询查询: : 对给定名字，在符号表中查询其有关信息；对给定名字，在符号表中查询其有关信息； 更新：对给定名字，在符号表填写或更新它的某更新：对给定名字，在符号表填写或更新它的某些信息；些信息； 删除：在符号表中删除一个或多个无用项。删除：在符号表中删除一个或多个无用项。4. 对符号表的操作对符号表的操作20运行时存储空间划分为：生成目标代运行时存储空间划分为：生成目标代码，数据对象和跟踪过程活动的控制码，数据对象和跟踪过程

19、活动的控制栈。栈。 一个称为堆（一个称为堆（heap)的运行时存储空间的运行时存储空间单独区域用来存放动态数据。单独区域用来存放动态数据。 运行时存储空间划分如图所示运行时存储空间划分如图所示目标代码区域目标代码区域静态区域静态区域栈栈自由空间自由空间堆堆1. 运行时存储空间划分运行时存储空间划分二二. .运行时存储空间的组织运行时存储空间的组织21 如果一个程序语言不允许有递归过程，不允许含如果一个程序语言不允许有递归过程，不允许含有可变体积的数据项目或待定性质的名字，那么就有可变体积的数据项目或待定性质的名字，那么就能在编译时完全确定其程序的每个数据项目存储空能在编译时完全确定其程序的每个

20、数据项目存储空间的位置，这种策略叫做静态分配策略。间的位置，这种策略叫做静态分配策略。 程序运行时，每当进入一个过程或分程序，其所程序运行时，每当进入一个过程或分程序，其所需的数据空间就动态地分配于栈顶，一旦该过程或需的数据空间就动态地分配于栈顶，一旦该过程或分程序运行结束，其所占用的空间就予以释放，这分程序运行结束，其所占用的空间就予以释放，这种方法叫做动态分配策略。种方法叫做动态分配策略。静态分配策略和动态分配策略：静态分配策略和动态分配策略：2. 存储分配策略存储分配策略22 从优化的时间上来分，优化可分为对源程序的优从优化的时间上来分，优化可分为对源程序的优化、对中间代码的有对目标代码

21、的优化。从优化与化、对中间代码的有对目标代码的优化。从优化与源程序的关系出发，又可把优化分为局部优化、循源程序的关系出发，又可把优化分为局部优化、循环优化和全局优化。环优化和全局优化。 三三. .代码优化代码优化1. 优化分类优化分类合并常量运算；删除公共子表达式；合并常量运算；删除公共子表达式；减少复写传播；消除无用代码；减少复写传播；消除无用代码；削减运算强度；外提循环中的不变表达式；削减运算强度；外提循环中的不变表达式；删除归纳变量。删除归纳变量。2. 常用的优化方法常用的优化方法23合并常量运算；合并常量运算；删除公共子表达式；删除公共子表达式；减少复写传播；减少复写传播；消除无用代码；消除无用代码；削减运算强度；削减运算强度；外提循环中的不变表达式；外提循环中的不变表达式；删除归纳变量删除归纳变量2. 常用的优化方法常用的优化方法24三三. .目标代码生成目标代码生成 将源程序的中间代码作为输入，生成等价目标程将源程序的中间代码作为输入，生成等价目标程序的程序称为目标代码生成器（简称代码生成器）。序的程序称为目标代码生成器（简称代码生成器）。 一般而言目标代码有以下三种形式：一般而言目标代码有以下三种形式：(1) 能够立即能够立即执行的机器语言代码，所有地址均已定位；执行的机器语言代码，所有地址均已定位； (2)待装待装配的机器语言模块；配的机器语言模