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

《编译原理_07中间代码及其他概要》由会员分享，可在线阅读，更多相关《编译原理_07中间代码及其他概要（27页珍藏版）》请在金锄头文库上搜索。

1、第第8 8章章 语法制导翻译和 中间代码生成 1 主要内容 概述 属性文法 语法制导翻译概述 中间语言 课题：中间代码及其他 目的要求： 1.掌握中间代码的表示方式； 2.了解 教学重点： 中间代码的表示方式。 教学难点 ： 教学课时：2 教学方法：多媒体教学 教学内容和步骤 ：（如下） 第 十五 讲 3 概 述 编译程序的任务是把源程序翻译成语义上等价的目标 程序。通常，在编译过程中，经过词法分析和语法分析 之后， 接下来将进行语义分析与处理。 编译中的语义处理包括两个功能：第一，审查每个语 法结构的静态语义，即验证语法结构合法的程序是否真 正有意义。有时把这个工作称为静态语义分析或静态审

2、查。第二，如果静态语义正确，语义处理则要执行真正 的翻译，即生成某种中间代码或者实际的目标代码。 本章引入属性文法和语法制导翻译方法的基本思想， 介绍几种典型的中间代码形式和一些常见语法成分的翻 译方法。 4 8.1 属性文法 属性，通常用来描述事物的特征、性质、品质等。 属性文法的形式定义：一个属性文法形式上可定义为 一个三元组A，A=（G，V，F）。其中G表示一个上下文 无关文法；V表示属性的有穷集；F表示有关属性的断 言或谓词的有穷集。 在属性文法中: （1）每个属性t都与某个文法符号N相关联，用N.t来表 示。例如N.type表示与N关联的属性type。 （2）每个断言与文法的某个规则

3、相关联。 （3）如果对G中的某一输入串（句子）而言， A中的 所有断言对该输入串的语法树结点的属性全为真，则该 串也是A语言中的句子。 5 编译程序的静态语义审查工作就是验证关于所编译的 程序的断言是否全部为真。 如文法GS： EF1F2F1 or F2 Fnumtrue false 与每个非终结符F相联的属性有type，type为int或者 bool。关于类型检验的属性文法可以表示为： EFlF2 F1.type := int AND F2.type := int EF1 or F2 F1.type := bool AND F2.type := bool Fnum F.type := int

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

5、:= E.val 7. Fdigit F.val := digit.lexval 每一个非终结符都有一个表示整数值的属性val。规则 左部符号E、T、F的属性值取决于各自规则的右部，称 为综合属性；对于文法符号S，其属性是虚的或空的。 7 8.3 中间语间语 言 所谓中间语言，也称中间代码，是复杂性介于源程序 语言和机器语言的一种记号系统。一般来说，快速编译 程序直接生成目标代码，没有将中间代码翻译成目标代 码的额外开销。但是为了使编译程序结构在逻辑上更为 简单明确，使生成的的目标代码更为高效，通常采用中 间语言。 编译程序所使用的中间语言形式较多。常见的有逆波 兰式、三元式、四元式和树形表示

6、等等。 8 8.3.1 逆波兰式 逆波兰式是最简单的一种中间语言形式，也称做后缀 式。它的特点是将运算对象写在前面，把运算符号写在 后面。对于简单表达式E，相应的逆波兰式E遵循下面 的转换规则： 表达式 逆波兰式 E E (E) E E E （负号“”是一元运算符，为了区别于减号“”， 通常写成） E1 op E2 E1 E2 op 9 用逆波兰式表示表达式，其最大的优点是易于计算机 进行计算处理。 例.算术表达式xyz 的逆波兰式为xyz，在栈 中的计值过程如图所示。 t1:=x xt1 y z t2:=yz t1 t2 t3:=t1t2 同时y、z入栈 t3 由于逆波兰式表示上的简单和计值

7、的方便，因此特别 适用于解释执行的程序设计语言的中间表示，也方便具 有堆栈体系的计算机的目标代码生成。 10 8.3.2三元式和树形表示 一三元式 三元式是中间语言的另一种形式，每个三元式由三个部 分组成:op，arg1，arg2。其一般格式为： （i）（op，arg1，arg2） 表达式abcd可用三元式表示为： （1）（ ， a ， ） （2）（ ， （1）， b ） （3）（ ， c ， d ） （4）（ ， （2），（3） “”是一目运算符（这里用表示），用来使a取反 ，对于一目运算，不妨规定只用arg1。 11 二树形表示 树形表示实际上是三元式的另一种表示形式。表达式 的树形表示非

8、常容易实现：简单直观。 例如，表达式a bc d的树形表示： a b d c 12 三间接三元式 间接三元式是对三元式的一种补充。为了在进行代码 优化时尽量不改变三元式表，于是另设一张间接码表来 表示有关三元式在三元式表的计值顺序。用这种方法获 得的中间代码称为间接三元式。如表达式 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） 13 8.3.3 四元式和三地址码 一四元式 四元式是比较普遍采用的一种

9、中间语言形式。与三元式 类似，四元式由四个部分组成：op，arg1，arg2，t。 四元式的一般格式为： （i） （op， arg1， arg2， t） 例如，表达式a := bc d的四元式表示如下: （1）（ ， c， d， t1） （2）（ ， b， t1， t2） （3）（:= ， t2， b， a ） 四元式和三元式的不同之处主要在于对中间结果的引 用方式：四元式之间的联系是通过引入临时变量来实现 ，而三元式则是通过三元式编号来传递中间结果的。 14 二三地址码 三地址代码也可以看成是四元式的另一种表示方式， 它比四元式更直观、更易于理解。 三地址码的一般格式为 t:= arg1 o

10、p arg2 其形式就是一个赋值语句，只是与赋值语句不同的是 ：在三地址码中赋值符号的右边最多只能有一个运算符 。 表达式a := bc d的三地址码序列: （1）t1 := c d （2）t2 := bt1 （3）a := t2 三地址码简单直观，这种表示形式对中间代码的优化 和目标代码的生成非常有利。 15 符号表 运行时存储空间的组织 代码优化 目标代码生成 16 一.符号表 一般来说符号表须保存如下一些内容： 1.类型名以及它的定义； 2.变量名以及类型； 3.常量名、类型和值； 4.过程或函数名、形参和局部变量、值单元及过程入 口地址； 5.类； 6.继承； 7.模块的大小，名字，根

11、源，成员以及时间标志。 1. 符号表的内容 17 (1)名子 (2)类类型 (3)存储类别储类别 (4)作用域及可视视性 (5)存储储分配信息 (6)其它属性:数组组内情向量、记录结记录结 构型的 成员员信息、函数及过过程的形参 3. 符号的主要属性有： （1）下文语义语义 的合法性检查检查 的依据 （2）代码码生成阶阶段地址分配的依据 2. 符号表的作用 18 大致可有如下几类类： 插入: 往符号表中插入一个新的名字； 查查找： 查询查询 : 对给对给 定名字，在符号表中查询查询 其有关信息 ； 更新：对给对给 定名字，在符号表填写或更新它的某 些信息； 删删除：在符号表中删删除一个或多个无

12、用项项。 4. 对符号表的操作 19 运行时存储空间划分为：生成目标代 码，数据对象和跟踪过程活动的控制 栈。 一个称为堆（heap)的运行时存储空间 单独区域用来存放动态数据。 运行时存储空间划分如图所示 目标代码区域 静态区域 栈 自由空间 堆 1. 运行时存储空间划分 二.运行时存储空间的组织 20 如果一个程序语言不允许有递归过程，不允许含 有可变体积的数据项目或待定性质的名字，那么就 能在编译时完全确定其程序的每个数据项目存储空 间的位置，这种策略叫做静态分配策略。 程序运行时，每当进入一个过程或分程序，其所 需的数据空间就动态地分配于栈顶，一旦该过程或 分程序运行结束，其所占用的空

13、间就予以释放，这 种方法叫做动态分配策略。 静态分配策略和动态分配策略： 2. 存储分配策略 21 从优化的时间上来分，优化可分为对源程序的优 化、对中间代码的有对目标代码的优化。从优化与 源程序的关系出发，又可把优化分为局部优化、循 环优化和全局优化。 三.代码优化 1. 优化分类 合并常量运算；删除公共子表达式； 减少复写传播；消除无用代码； 削减运算强度；外提循环中的不变表达式； 删除归纳变量。 2. 常用的优化方法 22 合并常量运算； 删除公共子表达式； 减少复写传播； 消除无用代码； 削减运算强度； 外提循环中的不变表达式； 删除归纳变量 2. 常用的优化方法 23 三.目标代码生

14、成 将源程序的中间代码作为输入，生成等价目标程 序的程序称为目标代码生成器（简称代码生成器）。 一般而言目标代码有以下三种形式：(1) 能够立即 执行的机器语言代码，所有地址均已定位； (2)待装 配的机器语言模块；(3)汇编语言代码，尚需经过汇编 程序汇编，转换成可执行的机器语言代码。 代码生成器在设计时要着重考虑两个问题：一是 如何使生成的目标代码较短；另一是如何充分利用计 算机的寄存器，减少目标代码中访问存储单元的次数 。这两个问题都直接影响目标代码的执行速度。 24 设计设计 代码码生成器时时需要处处理的一般问题问题 ： （1）代码生成器的入口信息：包括中间代码和符号 表中的信息 （2）代码生成器的出口信息：是把语义分析后或优 化后的中间代码变换成目标代码 （3）指令选择； （4）寄存器分配； （5）计算顺序的选择； 25 编译中的语义处理主要包括两个方面的功能，即 静态语义审查和中间代码生成； 属性文法的形式定义为一个三元组， A=(G，V，F)，其中G是一个二型文法，V是属性的 有穷集，F是谓词的有穷集； 中间代码的主要表示方式有：三元式，四元式， 逆波兰式和树形表示。 教学总结 26 习 题 教材P202-203练习练习 ：1、2 27