Ch7语义分析和中间代码产生.ppt

编译原理,第七章 语义分析和中间代码产生,程 序 设 计 语 言,2,本章在编译程序中的地位,表 格 管 理,词法分析器,语法分析器,语义分析与中间代码产生,优化器,目标代码生成器,源程序,单词符号,语法单位,中间代码,中间代码,目标代码,出 错 处 理,2019/8/5,Ch7.语义分析和中间代码产生,3,CH.7 语义分析和中间代码的产生,本章将把上一章所介绍的语法制导翻译方法和技术应用于程序语言典型结构的语义分析和中间代码的生成中。 应用到的主要方法技术有: 1.属性文法和翻译模式,翻译为中间代码。 2.一遍扫描的语法制导翻译方法(结合自下而上语法分析)。 3.引进标记非终结符及产生式,实现在自下而上分析过程中计算属性值。 4.改变基础文法,以避免使用继承属性。,2019/8/5,Ch7.语义分析和中间代码产生,4,语义分析和中间代码的产生,基本过程: 1. 先分析欲翻译的语言语句的结构以及欲翻译得到的中间代码的结构; 2. 在分析的基础之上，设计语言语句的属性文法或翻译模式; 3. 设计的属性文法或翻译模式能结合自下而上语法分析进行一遍扫描的语法制导翻译, 产生需要的中间代码。,5,静态语义检查,语义分析和中间代码生成阶段，编译程序要做的工作是进行静态语义检查和翻译。把经过语 法分析和语义分析而获得的源程序中间表示翻译为中间代码表示。 静态语义检查通常包括：参见P166. 1. 类型检查； 参见7.7 类型检查 2. 控制流检查； 3. 一致性检查； 4. 相关名字检查; 5. 其他检查，如名字的作用域分析，等。 静态语义检查和中间代码的地位, 参见图7.1,6,教学要求,掌握： 1. 逆波兰式, DAG图, 抽象语法树, 三地址代码, 三元式, 四元式等中间代码表示; 2. 简单赋值语句的翻译, 带数组元素引用的赋值句的翻译; 3. 布尔表达式的翻译, 控制语句中布尔表达式的翻译; 4. 控制语句的翻译。 了解理解：说明语句的翻译，过程调用和参数的处理。,7,教学内容,7.1 中间语言 后缀式，DAG，三地址码(四元式，三元式，间接三元式) *7.2 说明语句的翻译 7.3 赋值语句的翻译，数组元素引用的翻译 7.4 布尔表达式的翻译 求布尔式值的翻译，作为控制条件的翻译 7.5 控制语句的翻译 if ， while ， goto ， case 7.6 过程调用的处理, 参数传递的处理 *7.7 类型检查（不作要求，不讲）,8,7.1 中间语言,要掌握几种中间语言的基本结构： 逆波兰表示即后缀式 图表示法(抽象语法树、DAG图表示) 三地址代码(四元式、三元式、间接三元式) 7.1.1 后缀式 后缀式表示法又称逆波兰表示法。这种方法是，把运算量(操作数)写在算符的前面，把算符写在运算量的后面(后缀)。,9,后缀式的定义(P167.),一个表达式的后缀式可以如下定义： 1. 如果E是一个变量或常量，则E的后缀式是E自身。 2. 如果E是 E1 op E2 形式的表达式，这里op是任何二元操作符，则E的后缀式为 E1E2op,这里E1 和E2分别为E1和E2的后缀式。 3. 如果E是(E1)形式的表达式，则E1的后缀式就是E的后缀式。 要求会正确写出表达式的后缀式。,10,后缀式：例,写表达式的后缀式要点： 1.后缀式中运算量的顺序与中缀式的相同； 2.算符出现的次序即表达式的运算次序； 3.不使用括号。 例：a+b ab+ a*(b+c) abc+* (a+b)*(c+d) ab+cd+* -a+b*c abc*+ a/b*c-d*e abc*/de*- (A0B0) A0=B0,用 表示取负算符(uminus),11,写后缀式：练习,写出下列各式的逆波兰表示: (1) -a-(b*c/(c-d) + (-b)*a) (2) -A+B*C (D/E)/F (3) x := a-b/(c+d),解： (1) a bc*cd-/b a*+ - (2) A BCDE/*F/+ (3) x a b c d + / - := 用 表示取负算符(uminus) := 表示赋值算符(assign),12,把表达式翻译为后缀式的 语义规则描述(属性文法),P167.表7.1:,属性E.code: 是E的后缀式代码属性 op: 二元算符 : 后缀式的连接运算算符,13,7.1.2 图表示法,图表示法包括DAG与抽象语法树。两者都可以描述源程序的自然层次结构。DAG更加紧凑，可以标识出公共子表达式。 抽象语法树，在6.2.4节已讲过。 语法制导产生表达式的抽象语法树： P146.表6.4的S-属性文法 P155.图6.17的L-属性文法及翻译模式 P157.图6.20的递归下降构造抽象语法树的翻译器程序,14,图表示法：DAG,无循环有向图(Directed Acyclic Graph , 简称 DAG )。 是抽象语法树的改造。 与抽象语法树一样, 对于表达式中的每个子表达式, DAG图中都有一个结点。一个内部结点代表一个操作符, 它的子结点代表操作数。 与抽象语法树不同的是，在DAG图中代表公共子表达式的结点可以具有多个父结点，而在一棵抽象语法树中公共子表达式被表示为重复的子树。,15,抽象语法树 公共子表达式 重复出现,图7.3抽象语法树例： a:=b * - c+b * -c,16,(b) DAG 公共子表达式只出现一次，一个结点可以有多个父结点,图7.3 DAG例： a:=b * - c+b * -c,17,后缀式与抽象语法树(DAG)的关系,后缀式是抽象语法树(DAG)的线性表示形式。是树的后序遍历(左, 右, 根)的一个序列。 例如: 抽象语法树,后缀式: a b c uminus * b c uminus * + assign,18,表7.2 产生赋值语句的抽象语法树 的属性文法(P169.),19,抽象语法树或DAG的表示法: 图7.4,表7.2所示的产生赋值句的抽象语法树的属性文法也可以改写为产生DAG的属性文法，只要函数mknode(op, childe), mknode(op, left, right)每当可能就返回一个指向一个已存在的结点的指针，以代替建立新的结点。 抽象语法树或DAG的表示法：(P169.图7.4) 穿线树，结点的位置作为指向结点的指针。从根结点所处的位置开始沿指针所指的方向进行，可以访问树中所有的结点。 含指针域的记录数组,2019/8/5,Ch7.语义分析和中间代码产生,20,上次课主要内容(1),1. 几种中间代码形式及它们之间的关系 后缀式 P167. 图表示(抽象语法树, DAG) P167.169. 三地址代码 P169.171. 为赋值语句生成三地址代码的属性文法 三地址代码的实现(四元式, 三元式, 间接三元式) P172.173.,21,7.1.3 三地址代码,三地址代码是由下面一般形式的语句构成的序列: x := y op z 其中，x、y、z为名字、常数或编译时产生的临时变量；op代表运算符号。 每个三地址语句的右边只能有一个运算符。 例, 表达式x+y*z翻译为三地址代码: T1:=y*z T2:=x+T1 T1, T2是编译时产生的临时变量。,22,三地址代码：说明,1. 之所以称为三地址代码，是因为三地址代码语句类似与汇编指令, 涉及三个地址 x、y和z，其中y、z表示操作数，x存放结果。地址常用属性place表示。 名字.place：指向符号表名字入口的指针 临时变量.place：临时变量值存放的单元地址 常数.place：指向常数表中常数入口的指针 2. 三地址语句可以带符号标号, 标号代表存放中间代码的数组中三地址代码语句的下标。 3. 三地址代码是抽象语法树或DAG的线性化表示 - 每个内部结点对应一个三地址语句。,23,例, P170.图7.5，是相应于P168.图7.3的抽象语法树和DAG的三地址代码： (a) 对应抽象语法树的代码 (b) 对应DAG的代码 T1 : -c T1 : -c T2 : b* T1 T2 : b*T1 T3 : -c T5 : T2+T2 T4 : b* T3 a : T5 T5 : T2+T4 a : T5 注： 临时变量的名字对应抽象语法树的内部结点(算符结点), 表达式中的每个运算都要引入一个新的临时变量存放计算结果, 要多少引入多少。,抽象语法树与三地址代码的关系,24,(1) 赋值语句 x : y op z ; op是二元算术或逻辑运算符 (2) 赋值语句 x : op y ; op是一元算符，如取负、逻辑非、移位及类型转换 (3) 复制语句 x : y; (4) 无条件转移语句 goto L; 符号标号 L 代表存放中间代码的数组中三地址代码语句的下标 (5) 条件转移语句 if x relop y goto L ; if a goto L ; relop是关系运算符; a是布尔量,三地址代码语句的种类(P170.),25,(6) 过程调用语句 param x; x是实参数 call p, n ; p过程名, n实参个数 过程返回语句 return y; y返回值, 可有可无 (7) 索引赋值 x := yi; = 变址取数 xi := y ; =变址存数 (8) 地址和指针赋值 x : y; x : * y; * x : y; 注：选择适当的算符集合是中间代码设计的重要问题，应该不大不小，足以实现源语言的操作运算。,三地址代码语句的种类(续P170.),26,1. 赋值语句的三地址代码结构： 对表达式E求值的三地址语句序列 id := E T := E的值 id.place := T id := y 只一个三地址语句 id.place : y 2. 为赋值语句生成三地址代码的S-属性文法定义 见P171.表7.3,为赋值语句生成三地址代码的属性文法,(1) E.place 表示存放E值的名字。 (2) E.code 表示对E求值的三地址语句序列。 (3) S.code 表示赋值句S的三地址语句序列。 (4) 函数 newtemp 产生一个新的临时变量。 (5) 过程 gen( , , , , ) 产生一个三地址语句。 例如 gen(x, :=, y, +, z) 生成 x := y + z 注：实际实现中，三地址语句序列往往是被存放到一个输出文件中，而不是将三地址语句序列置入code属性之中。参见P179.图7.10的翻译模式。,赋值语句生成三地址代码属性文法：说明,28,例. 翻译赋值语句 a:=b*-c+b*-c 为三地址代码 自下而上语法制导翻译，结合P171.表7.3理解,赋值语句生成三地址代码：例, T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5,29,四元式 ( op, arg1, arg2, result ) 用了四个域 三元式 ( op, arg1, arg2 ) 只用三个域 间接三元式 间接码表+三元式表， 便于进行优化 四元式需要较多的临时单元, 四元式之间 的联系通过临时变量实现, 三元式之间的联系通过指针实现。 中间代码优化处理时，四元式比三元式方便得多, 间接三元式与四元式同样方便，四元式和三元式两种实现方式需要的存储空间大体相同。,三地址代码的实现,三地址代码的具体实现: 用记录结构, 含四个域,30,赋值语句a:=b*-c+b*-c 的三地址代码实现,三地址代码实现：四元式表示,四元式之间 的联系通过临时变量实现,31,P172. 表7.4(b) 三地址语句的三元式表示,三元式中使用了指向三元式语句的指针(序号)，序号也表示该三元式计算的结果值, 三元式之间 的联系通过指针实现。,三地址代码实现：三元式 a:=b*-c+b*-c,三元式表中没有了重复的三元式，语句的移动仅改变左边的间接码表。另外的例见P173.表7.6。,三地址代码实现：间接三元式a:=b*-c+b*-c,33,三地址语句 四元式表示 . x := -y ( uminus, y, _ , x ) x := y+z ( +, y, z, x ) goto L ( j, _, _, p ) 无条件转移 p 表示标号L代表的四元式的编号 if a goto L ( jnz, a, _, p ) 条件转移 a是逻辑量，a非0, 即a为真时转移 if x rop y goto L ( jrop, x, y, p ) 条件转移 x和y为算术量，x rop y 为真时转移 rop 是关系运算符。,几种形式的四元式,34,三地址语句 三元式表示 . x i := y (0) ( =, x, i ) (1) ( assign, (0), y ) 为数组元素赋值。 = 是变址存数算符, 由x(基址)和i(变址)求得数组元素xi的地址, 往此地址单元存数。 x := y i (0) ( = , y, i ) (1) ( assign, x, (0) ) 取数组元素的值赋给x 。= 是变址取数算符, 由y(基址)和i(变址)求得数组元素yi的地址, 从该地址单元取数赋给x。,数组元素引用的三元式表示(表7.5),35,写中间语言：练习,写出表达式：A+B*(C-D)-E/FG 的逆波兰表示、三元式表示、四元式表示。,解: 四元式表示： ( - , C , D , T1 ) (* , B , T1, T2 ) ( + , A , T2, T3 ) ( ,F , G , T4 ) ( / , E, T4, T5 ) ( - , T3, T5, T6 ),解: 三元式表示： ( - , C , D ) (* , B , ) ( + , A , ) ( ,F , G ) ( / , E, ) ( - , , ),解：逆波兰表示： ABCD -*+EFG/ -,36,7.2 说明语句(不讲),当考察一个过程或分程序的一系列说明语句时，便可为局部于该过程的名字分配存储空间。 对每个局部名字，将在符号表中建立相应的表项，并填入相应的信息如类型、嵌套深度、相对地址等。 说明语句的翻译目的就是建立符号表。,相对地址是指相对数据区基地址的一个偏移量。如图所示：,37,符号表的结构和组织(参见CH.8),符号表结构例, P235. FORTRAN语言的SD表结构。,符号表的组织: 指各表项的安排 线性表: 顺序填、查表 二叉树：按序填表，对折查找 杂凑技术：根据HASH( )函数值填、查表,P176. 嵌套过程的程序例子 P176. 图7.7 嵌套过程的符号表(5个过程, 5张表, 表之间的联系) P177. 图7.8 处理嵌套过程中的说明语句的翻译模式,说明语句翻译的例子,39,7.3 赋值语句的翻译,本节讨论的赋值语句，其表达式类型可以是整型、实型、数组和记录。 赋值语句的翻译将讨论如何在符号表中查找名字及如何存取数组和记录的元素。 本节只介绍7.3.1和7.3.2小节。 7.3.1 简单算术表达式及赋值语句的翻译 图7.10的翻译模式；赋值语句翻译为三地址代码 7.32. 数组元素引用的翻译 一维、二维数组元素地址计算 含有数组元素引用的赋值语句的翻译,40,7.3.1 简单算术表达式及赋值语句,P179.图7.10 给出了把简单算术表达式及赋值语句id := E 翻译为三地址代码的翻译模式。该翻译模式说明了如何查找符号表的入口。 属性表示id所代表的名字本身。 过程lookup()检查是否在符号表中存在此名字的入口。如果有，则返回一个指向该表项的指针，否则，返回nil表示没找到。 过程emit ( )生成三地址语句，并发送到输出文件中。 注: 以后，翻译赋值语句为三地址代码以图7.10的翻译模式为准。,41,例. 翻译赋值语句 x := -a+b*c 为三地址代码 自下而上语法制导翻译，结合图7.10 理解,赋值语句和算术表达式翻译：例,三地址语句:, T1:=uminus a, T2:=b*c, T3:=T1*T2, x:=T3,42,翻译赋值语句 x := -a+b*(-c+d)/e 为三地址代码。掌握手工生成赋值句的三地址代码的方法：按运算顺序写出三地址语句。,赋值语句和算术表达式翻译：练习,三地址语句序列:,T1:=uminus a,T2:=uminus c,T3:=T2+d,T4:=b*T3,T5:=T3/e,T6:=T1+T2,x:=T6,43,上次课主要内容(1),1. 几种中间代码形式及它们之间的关系 后缀式 P167. 图表示(抽象语法树, DAG) P167-169. 三地址代码 P169-171. 三地址代码的实现(四元式, 三元式, 间接三元式) P172-173. 2. 说明语句的翻译 P174-177. 填写符号表(名字, 类型, 相对地址) 嵌套过程说明语句的处理 3. 带简单算术表达式的赋值语句翻译为三地址代码(图7.10的翻译模式) P178-179. ，手工翻译赋值语句为三地址代码的方法,44,7.3.2 数组元素的引用,本小节讨论包括数组元素引用的表达式和赋值语句的翻译。 例如 x := Ai, j*2+y Ak := Bi+CDi+j-10 数组元素引用的关键问题: 数组元素地址的计算，由数组的存放方式决定 翻译时要产生计算数组元素地址的中间代码。 以后都假定：数组的元素存放在一片连续存储单元中，按行存放，数组的每个元素宽度为w。,45,一维数组元素地址计算-牢记,设一维数组：A low : high P179.180. 一维数组元素Ai 的相对地址为： base + (i low)*w (7.4) 其中：low为数组下标的下界，high为数组下标的下界，base是数组的起始地址，即base为A的第一个元素Alow的相对地址。 (7.4)式可以整理为： i*w + (base low*w) 其中：i*w 是随数组下标变量 i 而变化的部分； base low*w 是在数组元素地址计算公式中不变化的常数, 常记 C = low*w。,46,二维数组元素地址计算-牢记,设二维数组：A low1 : high1 , low2 : high2 每维 的长度( n1、n2) ni = highilowi +1 P180. 二维数组元素A i1, i2 的相对地址计算公式： base( i1 low1 )* n2 (i2 low2)*w 可整理为： base(low1 *n2low2)*w ( i1*n2 i2)* w (7.5) (7.5)分出地址不变部分和地址变化部分。常记 C=(low1 *n2low2)*w C值在处理数组说明时即可以计算出来, 与数组元素的下标无关, 是一个定数, C值可放在符号表数组A的表项中, 或数组内情向量中。,47,k维数组元素地址计算,一般, 对于一个 k维数组 P180. A low1 : high1 , lowk : highk 若按行存放，数组的每个元素的宽度为 w 各维的长度 ni = highilowi +1 则数组元素 A i1, i2 , , ik 的相对地址计算： D = base C + 变化部分 (7.6) 变化部分 =(.(i1*n2+ i2)* n3+ i3 ).)* nk + ik )*w C=(.(low1* n2 + low2)* n3 + low3 ).)* nk + lowk) * w (7.7),48,数组元素引用的代码结构,例, 赋值语句 x := Ai1, i2的 三地址代码结构： T1 := Ai1, i2的地址变化部分的计算值 T2 := base-C Ai1, i2地址的不变部分值 T3 := T2T1 x := T3 例, 赋值语句Ai1, i2 := E 的 三地址代码结构： T1 := Ai1, i2的地址变化部分的计算值 T2 := base-C Ai1, i2地址的不变部分值 T3 := 表达式E的值 T2T1 := T3,49,静态数组, 动态数组,静态数组： 数组说明中各维的上下界是确定的 C值在编译的时候就能计算出来 动态数组： 数组说明中各维的上下界有不确定的 C值在编译的时候不能计算出来, 运行时才能计算 计算动态数组元素地址的公式与静态数组是同样的，只是上、下界在编译时是未知的。,50,数组元素引用的文法: P181. L id Elist | id L表示简单变量或数组元素 Elist Elist,E | E Elist表示下标列表 Elist + i1, i2, , in 数组元素地址变化部分: (i1*n2+i2)*n3+i3)*n4+ nj := highj lowj + 1 (7.8) 递归公式 em = em-1 * nm + im (7.9) 为了从符号表获得有关数组各维长度 nj 的信息，改写文法为： LElist | id ElistElist , E | id E 让数组名与第一个下标联系,设计数组元素引用的文法,51,P181. 数组元素引用的文法: (1) SL : E S 赋值 语句 (2) EEE E 表达式, 可含数组元素 (3) E(E) (4) EL (5) LElist L 数组元素 (6) Lid L 简单变量 (7) ElistElist , E Elist 带数组名的下标表 (8) Elistid E 参见P181.183. 包含数组元素引用的赋值语句的翻译模式。,数组元素引用的文法及翻译模式,52,有关变量与函数的说明： Elist.ndim 综合属性：记录Elist中的下标表达式的个数，即维数; 函数limit(array, j)：返回nj ，即由array所指示的数组的第j维长度; Elist.place：临时变量，用来临时存放由Elist 中的下标表达式计算出来的值: em=em-1*nm Elist. Array 综合属性：数组名的符号表地址; 过程 emit( ) 产生一条三地址语句;,数组元素引用的翻译模式：说明(1),53,L.place, L.offset : 描述 L的左值的情况。 若 L 为简单变量, 则 L.place为符号表指针, 而L.offset 为 null; 若L为数组, 则 L.place 存放数组元素地址的不变部分的值, L.offset 存放地址的变化部分的值, L表示的数组元素的地址为: L.placeL.offset。 相应语义动作: 若L是一个简单变量的名字，则生成一般的赋值; 若L为数组元素引用，则生成对L所指示的数组元素地址的索引赋值。,数组元素引用的翻译模式：说明(2),54,例7.1 设A为一个10*20的二维数组 P183. 即设 A1:10, 1:20, n1= 10, n2= 20; w4； 数组第一个元素 为 A1, 1 则计算C值 = (low1*n2low2)*w=(1*201)*484 使用P181183.的翻译模式, 对赋值语句 x := Ay,z 进行翻译，带注释的分析树如 P183.图7.12所示。考虑结合自下而上分析的一遍扫描语法制导翻译。,带数组元素引用的赋值语句的翻译例,例7.1 x := Ay, z的带注释的分析树,L.place = x L.offset = null,L.place = T2 L.offset = T3,E.place = T4,Elist.place = T1 Elist.ndim = 2 Elist.array = A,S,:=,x, 4, 1, 6, 5, 7,图7.12,结合翻译模式理解,第7步产生2条, 第8步产生2条, 第9步产生1条, 10步产生1条,Elist.place = y Elist.ndim = 1 Elist.array = A,L.place = z L.offset = null,E.place = z,A,z,y,L.place = y L.offset = null,E.place = y,Elist(place=T1,ndim=2,array=A), 7, 4, 6, 8, 4, 6,(续上页）,x := Ay, z,在第7, 8, 9, 10步归约时产生计算数组元素地址的代码,57,数组元素的引用翻译: 例7.1,赋值语句 x := Ay, z 在自下而上的分析中被翻译成如下三地址语句序列：P183. T1 := y*20 T1 := T1z T2 := A-84 T3 : = 4*T1 T4 := T2T3 x : = T4 注意：20(第2维长度)、84(C值)、4(宽度)都是编译中引入的常量, 用A代表数组的首地址。,58,手工生成数组元素引用的代码,1. 先确定: 数组维数k; 宽度w; 各维的下界Lowj, 上界highj, 计算各维长度nj; 数组首地址(不同的数组用不同的符号, 比如A数组用A表示); 计算出常数C 一维数组 C=Low*w 二维数组 C=(low1*n2+low2)*w 2. 对一维数组元素Ai产生2个地址计算的三地址语句: T1 := w*i T2 := AC 地址表示T2T1 3. 对二维数组元素Ai,j产生4个地址计算的三地址语句: T1 := i* n2 T2 := AC T1 := T1+j T3 := w*T1 地址表示T2T3,59,手工生成数组元素引用的代码：例,翻译 Ai+2, j+1:=M+Bk 为三地址代码 设 A数组 A1:10,1:20; w=4; 数组首地址 A; CA=(1*20+1)*4=84 设 B数组 B1:10; w=4; 数组首地址B; CB=1*4=4 三地址语句: T1:=i+2 T5:=4*k T2:=j+1 T6:=B4 T1:=T1*20 T7:=T6T5 变址取数 T1:=T1+T2 T7:=M+T7 T3:=A84 T3T4:=T7 变址存数 T4:=4*T1,60,数组元素引用翻译: 练习1,设二维数组A1:10,1:20，则 n1=10, n2=20；设 W=2 (1) 赋值语句 X:= AI, J 的三地址代码序列； (2) 赋值语句AI+2, J+1 := M+N三地址代码。,(1) 解：C = 42 T1 := I*20 T1 := T1+J T2 := A-42 T3 := T1*2 T4 := T2T3 X := T4,(2) 解： C = 42 T1 := I+2 T2 := J+1 T3 := T1*20 T3 := T2+T3 T4 := A-42 T5 := T3*2 T6 := M+N T4T5 := T6,61,数组元素引用翻译: 练习2,(3) 赋值语句 X:= AI, J 的四元式序列； (4) 赋值语句AI+2, J+1 := M+N四元式序列。,(3) 解 ： C = 42 ( *，I, 20, T1 ) ( +, J, T1, T1 ) ( - ,A, 42, T2 ) ( * ,T1, 2, T3) ( = , T2T3,_,T4 ) ( := , T4 ,_,X ),(4) 解： C = 42 ( + , I , 2 , T1 ) ( + , J , 1 , T2 ) ( * , T1, 20 , T3 ) ( + , T2 , T3 , T3 ) ( - , A, 42 , T4 ) ( * ,T3, 2, T5) ( + , M, N ,T6 ) ( =, T6, _,T4T5 ),62,考虑表达式的类型,在前面关于算术表达式和赋值语句的翻译中，我们假定所有的 id 都是同一类型的。实际上，在表达式中可能出现各种类型的变量或常量。 编译程序必须做到：或者拒绝接受某种混合运算，或者产生有关类型转换的指令。 教材给出了这种表达式和赋值语句的语义规则。简单说明如下: 参见P183-184. (1) 引入综合属性 E.type 表示表达式 E 的类型 (2) 增加类型转换的三地址语句: x:=inttoreal y (3) 对EE1+E2 的语义动作进行修改, 增加判断,63,7.4 布尔表达式的翻译,布尔表达式是用布尔运算符号and、 or、not 作用到布尔变量或关系表达式上而组成的。 关系表达式形式如 E1 relop E2 , 其中E1 和E2是算术表达式， relop为关系运算符: =, , =, 。 程序设计语言中, 布尔表达式有两个基本作用： 一个是用作计算逻辑值(真1, 假0) 7.4.1节 另一个是用作控制流语句如 if-then、if-then-else和 while-do等中的条件表达式 7.4.2节,2019/8/5,Ch7.语义分析和中间代码产生,64,布尔表达式的文法,本节中考虑由下列文法产生的布尔表达式： EE or E | E and E | not E | (E) | id relop id | id 使用 relop 的 属性relop.op 来确定 relop 所指的6种关系运算中的哪一个。 假定按惯例确定and,、or 、not 的优先级和结合性。,注意: 此id表示布尔量,2019/8/5,Ch7.语义分析和中间代码产生,65,布尔表达式的语义,布尔式的语义是指明计算一个逻辑值的规则, 有两种计算规则: 1. 用数值(1/0)表示真和假, 同计算算术表达式一样, 一步不差地按序计算出整个布尔式的值。 例如: 计算 1 or (not 0 and 0) or 0 =1 2. 优化(短路)方法，不一定一步不差的计算，可以由某个子布尔式的值确定整个布尔式的值。,2019/8/5,Ch7.语义分析和中间代码产生,66,布尔表达式的计值规则,规则2用于翻译控制流语句中的布尔表达式尤其方便,解释为: if E1 then true else E2,解释为: if E1 then E2 else false,2019/8/5,Ch7.语义分析和中间代码产生,67,7.4.1 数值表示法,首先考虑用1表示真，用0表示假来实现布尔表达式的翻译。 1. 类似算术表达式求值方法计算布尔式值 例: a or b and not c 翻译为: T1 := not c T2 :=b and T1 T3 :=a or T2 注意: 此布尔式中的a, b, c是逻辑量(值0/1)!,68,数值表示法：第2种方法求布尔式值,一个形如 ab的关系表达式可等价的写成: if ab then 1 else 0 并将它翻译成如下三地址语句序列： 100 if ab goto 103 101 T:=0 102 goto 104 103 T:= 1 104 逻辑量 a也作同样翻译，只要将 ab 换为 a。 P186.图7.13 布尔式的数值表示法的翻译模式,69,P187.例7.2 翻译布尔式 ab or cd and ef 100 if ab goto 103 108 if ef goto 111 101 T1:=0 109 T3:=0 102 goto 104 110 goto 112 103 T1:=1 111 T3:=1 104 if cd goto 107 112 T4:=T2 and T3 105 T2:=0 113 T5:= T1 or T4 106 goto 108 114 107 T2:=1 注意: 这儿, 三地址代码的序号作标号!,布尔表达式的数值表示法翻译：图7.14,70,7.4.2 作为条件控制的布尔式翻译,出现在条件语句： 中的布尔表达式 E，它的作用仅在于控制对 S1 和 S2的选择。只要能完成这一使命，E 的值就无需最终保留在某个临时单元中。 因此，作为转移条件的布尔式 E，我们可以赋予它两种“出口”。 一个是“真”出口，为真时出向S1；一个是“假”出口，为假时出向S2。 语句 (7.10) 可翻译成如 P187.图7.15 所示的代码结构。,if E then S1 else S2 (7.10),71,If_then_else语句的代码结构,E.code: 综合属性 布尔式E的三地址代码 S.code: 综合属性 语句S的三地址代码,E.true: 继承属性, E为真时控制流转向的标号; E.false: 继承属性, E为假时控制流转向的标号； S.next: 继承属性, 标号, 紧随S代码之后的地址。,72,布尔式翻译为跳转代码,对于作为转移条件的布尔式，可以把它翻译成为一串跳转代码。 在翻译过程中，假定可以用符号标号来标识一条三地址语句，并且假定每次调用过程函数 newlabel 后都返回一个新的符号标号。 对于一个布尔表达式E，引用两个标号： E.true 是E为真时的控制流转向的标号 E.false 是E为假时控制流转向的标号 P188.表7.7是按此方式将布尔表达式翻译 成跳转三地址代码的语义规则, 是L-属性文法。,73,产生布尔式三地址跳转代码：例7.3,例7.3 应用P188.表7.7的属性文法语法制导翻译布尔表达式 E=ab or cd and ef 为跳转三地址代码：P189. if ab goto Ltrue - 表达式的真出口 goto L1 L1: if cd goto L2 goto Lfalse - 表达式的假出口 L2: if ef goto Ltrue goto Lfalse,74,例 考虑如下语句： if ac or bd then x := yz else x :y-z 根据表7.7 ，生成 代码如右：,L1 ： if ac goto L3 goto L2 L2 ： if bd goto L3 goto L4 L3 ： T1 := yz X :T1 goto Lnext L4 ： T2 := yz x : T2 Lnext：,产生布尔式三地址跳转代码：举例,练习: 若把 or 换成 and, 如何修改代码?,75,设实现三地址代码时采用四元式形式, 并且假定： ( jnz, a, _ , p ) 表示 if a goto p ( jrop, x, y, p ) 表示 if x rop y goto p ( j , _ , _ , p ) 表示 goto p 例7.3 布尔式 ab or cd and ef 翻译为跳转四元式序列: P189. 100 (j, a, b, Ltrue) 104 (j, e, f, Lture) 101 (j , _ , _ , 102) 105 (j, _ , _ , Lfalse) 102 (j, c, d, 104) 106 103 (j, _ , _ , Lfalse),布尔式翻译为四元式,注意: 有向前转移!,76,一遍扫描产生布尔式的转移代码的主要问题: 当生成某些转移语句时, 可能还不知道该语句将要转移到的标号究竟是什么, 即对向前转移, 转移目标还未产生。 解决这个问题的办法 - “拉链-回填” 1. 先产生暂时没有填写目标标号的转移四元式 - 产生不完全转移四元式(目标标号暂填0); 2. 对于每一条这样的四元式作适当的记录 - 建立一个链表, 把具有同一个转移目标的四元式链在一起, 也称为拉链; 3. 一旦目标标号被确定下来，再将它“回填”到相应链表的每一条四元式中。,布尔式一遍扫描的语法制导翻译考虑,77,布尔表达式文法： P190. （1）E E1 or M E2 （2） E E1 and M E2 （3） E not E1 （4） E (E1) （5） E id1 relop id2 （6） E true （7） E false （8） M 插入标记非终结符号M 是为了引入一个语义动作，以便在适当的时候获得即将产生的下一个四元式的序号(标号)。,使用回填技术翻译布尔表达式,78,1E.truelist: 综合属性, 真链表, 记录E对应的四元式中需要回填“真出口”的四元式的标号构成的链表。 2E.falselist: 综合属性, 假链表, 记录E对应的四元式中需要回填“假出口”的四元式的标号构成的链表。 3 nextquad: 变量, 表示下一条将要产生但尚未形成的四元式标号; 初值为1, 每当执行一次emit( )产生一条四元式之后, nextquad的值自动增加1。,翻译模式用到的变量和属性,79,1. emit( j， ， ，)：生成一条转移四元式。 2. makelist(i)：创建一个仅包含 i 的新链表，i是四元式数组的一个索引(下标)，或说 i 是四元式代码序列的一个标号，代表一条四元式。 3. merge(p1, p2)：连接由指针 p1 和 p2 指向的两个表并且返回一个指向连接后的表的指针。 4. Backpatch(p, i)：把 i 作为目标标号回填到 p 所指向的表中的每一个转移四元式中去。 此处的“表”都是为“回填”所拉的链表。,翻译模式用到的函数和过程,P190. 一遍扫描的布尔式的翻译模式(1),(1) E E1 or M E2 backpatch(E1.falselist, M.quad); E.truelist :=merge(E1.truelist, E2.truelist); E.falselist :=E2.falselist ,用此产生式进行归约时: 1. E1已处理完, 假出口已确定(就是M.quad), 可以回填 E1.falselist链 2. E.truelist := E1.truelist 与E2.truelist 的链合并 3. E.falselist := E2.falselist,P190. 一遍扫描的布尔式的翻译模式(2),(2) E E1 and M E2 backpatch(E1.truelist, M.quad); E.truelist :=E2.truelist; E.falselist :=merge(E1.falselist, E2.falselist); ,用此产生式进行归约时: 1. E1已处理完, 真出口已确定(即 M.quad), 可以回填 E1.truelist链 2. E.truelist := E2.truelist 3. E.falselist := E1.falselist 与E2.falselist 的并链,(3) Enot E1 E.truelist :=E1.falselist; E.falselist :=E1.truelist 取反传链,P190. 一遍扫描的布尔式的翻译模式(3),(4) E ( E1 ) E.truelist := E1.truelist; E.falselist :=E1.falselist 仅传链,(7) M M.quad :=nextquad 用M.quad 记录下一个四元式的标号,(5) E id1 relop id2 E.truelist := makelist(nextquad); E.falselist := makelist(nextquad+1); emit(j relop.op , id1.place , id2.place , 0); emit(j , _ , _ , 0); ,P190. 一遍扫描的布尔式的翻译模式(4),用此产生式进行归约时: 将产生2条不完全四元式, 并建立E的真链和假链 E.truelist := nextquad ( jrelop, id1, id2, _, 0 ) E.falselist := nextquad+1 ( j , _ , _ , 0 ),(6) E id E.truelist := makelist(nextquad); E.falselist := makelist(nextquad+1); emit( jnz , id.place , _ , 0 ); emit( j , _ , _ , 0 ); ,P190. 一遍扫描的布尔式的翻译模式(5),注意: 此处的id是逻辑量! 用此产生式进行归约时: 将产生2条不完全四元式, 建立E的真链和假链 E.truelist := nextquad ( jnz, id, _ , _ , 0 ) E.falselist := nextquad+1 ( j , _ , _ , 0 ),例7.4 布尔式 ab or cd and ef的翻译 一棵作了注释的分析树如图7.16 所示,E.t=100,104 E.f=103,105,E.t=100 E.f=101,E.t=104 E.f=103,105,or,M.q=102,a,b,E.t=102 E.f=103,E.t=104 E.f=105,and,M.q=104,c