中间代码生成

本章内容 介绍几种常用的中间代码表示 用语法制导定义和翻译方案来说明源语言的各种 构造怎样被翻译成中间表示 抽象语法树（上一章已介绍） 有向无环图 三地址代码 用语法制导定义和翻译方案来说明源语言的各种 构造怎样被翻译成中间表示 声明（和类型） 表达式和赋值 类型检查和类型转换 控制流 过程

编译器的前端 前端是对源语言进行分析并产生中间表示 前端后端分开的好处：不同的源语言、不同的机 器可以得到不同的编译器组合 处理与源语言相关的细节，与目标机器无关 前端后端分开的好处：不同的源语言、不同的机 器可以得到不同的编译器组合

建立组合编译的做法 Source program in Language-1 Source program in Language-2 Language-1 Front End Language-2 Front End Non-optimized Intermediate Code Intermediate-code Optimizer Optimized Intermediate Code Target-1 Code Generator Target-2 Code Generator Target-1 machine code Target-2 machine code

中间代码表示及其好处 形式 重定位 “抽象”的编译优化 多种中间表示，不同层次 抽象语法树 三地址代码 为新的机器建编译器，只需要做从中间代码到新的目 标代码的翻译器（前端独立） “抽象”的编译优化 优化与源语言和目标机器都无关

抽象语法树回顾 例：a + a * (b – c) + (b – c) * d 产 生 式 语 义 规 则 E  E1 +T 产 生 式 语 义 规 则 E  E1 +T E.node = new Node(‘+’, E1.node, T.node) E  E1 T E.node = new Node(‘’, E1.node, T.node) E  T E.node = T.node T  T1 F T.node = new Node( ‘’, T1.node, F.node) T  F T.node = F.node F  (E) F.node = E.node F  id F.node = new Leaf (id, id.entry) F  num F.node = new Leaf (num, num.val) 例：a + a * (b – c) + (b – c) * d

有向无环图（Directed Acyclic Graph, DAG） 语法树中，公共子表达式每出现一次，就有一个对应的 子树 表达式的有向无环图能够指出表达式中的公共子表达式， 更简洁地表示表达式 例：a + a * (b – c) + (b – c) * d

构造赋值语句语法树/DAG的语法制导定义 修改构造结点的函数Node和Leaf可生成DAG：构 造新节点前先检查是否已存在同样的节点，如果 已经存在，则返回这个已有的节点 产 生 式 语 义 规 则 E  E1 +T E.node = new Node(‘+’, E1.node, T.node) E  E1 T E.node = new Node(‘’, E1.node, T.node) E  T E.node = T.node T  T1 F T.node = new Node( ‘’, T1.node, F.node) T  F T.node = F.node F  (E) F.node = E.node F  id F.node = new Leaf (id, id.entry) F  num F.node = new Leaf (num, num.val)

a + a * (b – c) + (b – c) * d的DAG的构造 产 生 式 语 义 规 则 E  E1 +T E.node = new Node(‘+’, E1.node, T.node) E  E1 T E.node = new Node(‘’, E1.node, T.node) E  T E.node = T.node T  T1 F T.node = new Node( ‘’, T1.node, F.node) T  F T.node = F.node F  (E) F.node = E.node F  id F.node = new Leaf (id, id.entry) F  num F.node = new Leaf (num, num.val) + + * * d – a b c

三地址代码 一般形式：x = y op z 一条指令右侧最多有一个运算符 例 表达式x + y  z翻译成的三地址语句序列是 三地址代码拆分了多运算符表达式和控制流语句的嵌 套结构，所以适用于目标代码的生成 例 表达式x + y  z翻译成的三地址语句序列是 t1 = y  z t2 = x + t1

三地址代码 三地址代码是语法树或DAG的一种线性表示 例：a + a * (b – c) + (b – c) * d 语法树对应的代码？

三地址代码中的“地址” 名字（源程序中的变量） 实现中，使用指向符号表条目的指针 常量 编译器生成的临时变量

本书用的三地址指令 一条指令右侧最多有一个运算符 改变控制流的指令使用标号 赋值x = y op z，x = op y，x = y 无条件转移goto L 条件转移if x goto L，ifFalse x goto L，if x relop y goto L 过程调用param x 和call p , n 过程返回 return y 索引赋值x = y[i]和 x[i] = y y[i]表示距离位置y处i个内存单元的位置 地址和指针赋值x = &y，x = *y和*x = y

三地址代码示例 假设数组每个元素占8个内存单元 语句 do i=i+1; while (a[i]<v);

三地址代码的实现 用具体的数据结构实现三地址代码的方法 四元式 三元式 间接三元式 静态单赋值表示

四元式表示 四个字段 op arg1 arg2 result 例 双目运算符 + y z x 单目运算符 minus y x 传参数 param x 无条件转移 goto L

四元式表示 a = b﹡(-c) + b﹡(-c) result字段主要用于临时变量名。可否不用result字段？

三元式表示 三个字段 op，arg1，arg2 没有result，用位置表示结果 例：a = b﹡(-c) + b﹡(-c)的三元式表示

三元式表示 问题：优化编译器中，指令的位置常会发生变化 如果改变一条指令的位置，则引用该指令结果的 所有指令都要做相应的修改 例：a = b﹡(-c) + b﹡(-c)的三元式表示

间接三元式 间接三元式包含了一个指向三元式指针的列表作 为指令序列，而不是用三元式序列本身作为指令 序列。改变指令位置的编译器优化仅操作该列表

静态单赋值形式（Static Single Assignment Form, SSA） 和三地址代码的主要区别 所有赋值指令都是对不同名字的变量的赋值 三地址代码 静态单赋值形式 p = a +b p1 = a +b q = p  c q1 = p1  c p = q  d p2 = q1  d p = e  p p3 = e  p2 q = p + q q2 = p3 + q1 原有变量被分成多个“版本”

静态单赋值形式（Static Single Assignment Form, SSA） 和三地址代码的主要区别 所有赋值指令都是对不同名字的变量的赋值 好处：简化许多编译优化（死代码消除，常量传播，…） 三地址代码 静态单赋值形式 p = 1 p1 = 1 p = 2 p2 = 2 q = p q1 = p2 第一条赋值语句是无用的， 但要做 到达-定值分析 才能知道

静态单赋值形式（Static Single Assignment Form, SSA） 和三地址代码的主要区别 所有赋值指令都是对不同名字的变量的赋值 一个变量在不同路径上都定值的解决办法 if (flag) x = 1; else x = 1; y = x  a; 改成 if (flag) x1 = 1; else x2 = 1; x3 =  (x1, x2); //由flag的值决定用x1还是x2 y1 = x3  a;

本章内容 介绍几种常用的中间代码表示  用语法制导定义和翻译方案来说明源语言的各种 构造怎样被翻译成中间表示 抽象语法树（上一章已介绍） 有向无环图 三地址代码 用语法制导定义和翻译方案来说明源语言的各种 构造怎样被翻译成中间表示 声明（和类型） 表达式和赋值 类型检查和类型转换 控制流 过程

类型和声明 类型的用处 在过程或类中声明的变量，要考虑其存储空间的 布局问题 类型检查：保证运算分量的类型和运算符的预期类型 一致（本章后面介绍） 翻译时：根据一个名字的类型，编译器确定这个名字 在运行时刻需要多大的存储空间 在过程或类中声明的变量，要考虑其存储空间的 布局问题 实际存储空间是在运行时刻进行分配的（下一章介绍） 编译时刻，用相对地址（相对于数据区域开始位置的 偏移量）进行布局

类型表达式 类型自身有结构 int, int[3] 具体语法：出现在编程语言中 抽象语法：出现在类型检查的实现中 如int[2][3]对应的抽象语法array(2,array(3,integer)) array是类型构造算子，有两个参数：数字和类型 定义与具体语言相关

本书中类型表达式的抽象语法 基本类型是类型表达式，如boolean, char, integer, float, void 类型变量是类型表达式 array(n, t)得到一个类型表达式 record(a1 : t1, …, an : tn)得到一个类型表达式，a为字段名 pointer(t)得到指针类型的类型表达式 s → t得到函数类型的类型表达式 s  t是类型表达式，描述类型的元组（如函数参数列表） 可以为类型表达式命名，类型名也是类型表达式 例 struct {int a[5]; char c} st;

类型表达式的等价 当允许对类型表达式命名后， 类型表达式是否相同就有了不同的解释 出现了结构等价和名字等价两个不同的概念 type link = cell* ; link next ; link last ; cell* p ; cell* q, r;

类型表达式的结构等价 当无类型名时，两个类型表达式完全相同 类型表达式的抽象语法树（或DAG）一样 相同的类型构造算子作用于相同的子表达式 有类型名时，用它们所定义的类型表达式代换它 们，所得表达式完全相同(类型定义无环时) type link = cell* ; link next ; link last ; cell* p ; cell* q, r; cell* cell* next, last, p, q和r的类型结构等价

类型表达式的名字等价 next和last的类型名字等价 p, q和r的类型名字等价 把每个类型名看成是一个可区别的类型 两个类型表达式名字等价当且仅当这两个类型表 达式不进行名字代换就能结构等价 type link = cell* ; link next ; link last ; cell* p ; cell* q, r; next和last的类型名字等价 p, q和r的类型名字等价

类型表达式的名字等价 这时，p与q、r的类型 不是名字等价 type link = cell*; type np = cell*; type nqr = cell*; link next ; link last ; np p; nqr q ; nqr r; 这时，p与q、r的类型 不是名字等价

类型表示中的环 替换递归定义的类型名会引入环 type link = cell* ; type cell = record ( info : integer , next : link ) ; cell = record ， : info pointer next integer cell 替换递归定义的类型名会引入环

类型表示中的环 结构等价测试过程有可 type link = cell* ; type cell = record ( info : integer , next : link ) ; cell = record ， : info pointer next integer 结构等价测试过程有可 能不终止

类型表达式的等价 C语言对除了记录（结构体）以外的所有类型使 用结构等价，而记录类型用的是名字等价，以避 免类型图中的环 cell = record ， : info pointer next integer cell

声明语句 下面介绍 为局部名字建立符号表条目 为它确定存储单元的大小和相对地址 符号表中包含名字的类型和分配给它的存储单元 的相对地址等信息

本书的声明语句的文法 处理基本类型、数组类型、记录类型的文法 为该文法设计语法制导的翻译，除了计算类型表 达式之外，还得进行各种类型的存储布局 一次仅声明一个名字

局部变量名的存储布局 在编译时刻，根据类型，为每个名字分配一个相 对地址（相对于数据区域开始位置的偏移量） 类型和相对地址信息保存在符号表中 从变量类型可知该变量在运行时刻需要的内存大小 类型和相对地址信息保存在符号表中 约定： 存储区域是连续的字节块 字节是可寻址的最小内存单位 一个字节通常是8个二进制位，若干字节组成一个机 器字 类型的宽度：该类型一个对象所需的存储单元的 数量。比如，一个整型数的宽度是4；一个浮点 数的宽度是8

计算数组类型和宽度的翻译方案 T → B C B → int B → float C → ε C →[num] C1 综合属性type和width

计算数组类型和宽度的翻译方案 T → B {C.t=B.type; C.w=B.width;} C {T.type=C.type;T.width=C.width;} B → int {B.type=integer; B.width=4;} B → float {B.type=float; B.width=8;} C → ε C →[num] C1 t和w是C的继承属性 综合属性type和width

计算数组类型和宽度的翻译方案 T → B {C.t=B.type; C.w=B.width;} C {T.type=C.type;T.width=C.width;} B → int {B.type=integer; B.width=4;} B → float {B.type=float; B.width=8;} C → ε {C.type=C.t; C.width=C.w;} C →[num] {C1.t=C.t; C1.w=C.w; } C1 {C.type=array(num.value,C1.type); C.width=num.value*C1.width; } t和w是C的继承属性 综合属性type和width

计算数组类型和宽度的翻译方案 T → B {t=B.type; w=B.width;} C {T.type=C.type;T.width=C.width;} B → int {B.type=integer; B.width=4;} B → float {B.type=float; B.width=8;} C → ε {C.type=t; C.width=w;} C →[num] C1 {C.type=array(num.value,C1.type); C.width=num.value*C1.width} t和w是变量 综合属性type和width

例：int[2][3] T → B {t=B.type; w=B.width;} C {T.type=C.type;T.width=C.width;} B → int {B.type=integer; B.width=4;} B → float {B.type=float; B.width=8;} C → ε {C.type=t; C.width=w;} C →[num] C1 {C.type=array(num.value,C1.type); C.width=num.value*C1.width} 例：int[2][3]

声明的序列 要做两件事： 插入符号表条目 跟踪下一个可用的相对地址 top.put(id.lexeme, T.type, offset)创建一个符号表条目 （top指向当前符号表） 跟踪下一个可用的相对地址 变量offset（D的继承属性）

声明的序列 插入符号表条目，跟踪下一个可用的相对地址

记录和类 确定记录和类中的字段的类型和相对地址：

记录和类中的字段 约定： 记录类型使用一个专用的符号表，对它们的各个 字段类型和相对地址进行单独编码 一个记录中各个字段的名字必须互不相同 字段名的偏移量（相对地址），是相对于该记录的数 据区字段而言的 记录类型使用一个专用的符号表，对它们的各个 字段类型和相对地址进行单独编码 记录类型record(t)，其中t是一个符号表对象，保 存该记录类型的各个字段信息

记录和类中的字段 保存top指向的当前符号表 令top指向新的符号表 保存当前offset值 恢复早先保存的符号表和offset值 注：记录类型存储方式可以推广到类

本章内容 介绍几种常用的中间代码表示  用语法制导定义和翻译方案来说明源语言的各种 构造怎样被翻译成中间表示 抽象语法树（上一章已介绍） 有向无环图 三地址代码 用语法制导定义和翻译方案来说明源语言的各种 构造怎样被翻译成中间表示 声明（和类型）  表达式和赋值 类型检查和类型转换 控制流 过程

返回id的实例id.lexeme对应的符号表条目的指针 表达式和赋值语句的翻译 E.code和S.code表示三地址代码，E.addr表示存放E的值的地址 总是返回新的临时变量 返回id的实例id.lexeme对应的符号表条目的指针

t1 = minus c t2 = b + t1 a = t2 例：a = b + ( - c ); 翻译成

增量翻译 类似上一章的边扫描边生成 gen不仅构造新的三地址指令，还要将它添加到至今为止已生成的 指令序列之后 不再用code属性。对gen的连续调用将生成一个指令序列（可暂放 在内存中）

数组引用 文法 S  id = E ; | L = E ; E  E + E | id | L 翻译成三地址代码要解决的问题 数组元素的寻址 S  id = E ; | L = E ; E  E + E | id | L L  id [ E ] | L [ E ]

base + i1*w1 + i2*w2 + … + ik*wk 数组元素的地址计算 数组元素存储在一块连续的存储空间中 在C中，n个数组元素是0,1,…,n-1进行顺序编号的 假设每个数组元素宽度是w， base是A[0]的相对地址， 那么数组A[i]的相对地址为 base + i * w C的二维数组：A[i1][i2]表示第i1行第i2个元素。假设一行 的宽度是w1，同一行中每个元素的宽度是w2。 A[i1][i2]的 相对地址是 base + i1*w1 + i2*w2 推广到k维数组，A[i1][i2]…[ik]的相对地址 base + i1*w1 + i2*w2 + … + ik*wk

base + ((…(i1 * n2 + i2) *n3 + i3)…) * nk + ik) * w 数组元素的地址计算 另一种计算k维数组引用的相对地址的方法： 根据第j (1  j  k)维上的数组元素的个数nj和该数组每个元 素的宽度w进行计算 二维数组A[i1][i2]的相对地址 base + (i1*n2 + i2) * w 对于k维数组A[i1][i2]…[ik] 的地址 base + ((…(i1 * n2 + i2) *n3 + i3)…) * nk + ik) * w

数组元素的地址计算 有时下标不一定从0开始 比如一维数组编号low, low+1, …, high，此时base是A[low] 的相对地址。那么A[i]的相对地址是 base + ( i  low ) * w 可以变换成 i * w + (base  low * w) 减少了运行时的计算

base + ( (i1  low1)  n2 + (i2  low2 ) )  w 数组元素的地址计算 i2  A[1,2] A[1,3] … A[2,2] A[2,3] … … … … 有时下标不一定从0开始 比如二维数组： 设base是A[low1][low2]的相对地址。那么A[i1][i2]的相对地 址是 base + ( (i1  low1)  n2 + (i2  low2 ) )  w 其中n2 = high2  low2 + 1 可以变换成 ( (i1  n2 ) + i2 )  w + (base  ( (low1  n2 ) + low2 )  w) i1

数组元素的地址计算 多维数组下标变量A[i1][i2]...[ik]的相对地址 ( (… ( (i1  n2 + i2 )  n3 + i3 ) … )  nk + ik)  w + base  ( ( … ( (low1  n2 + low2)  n3 + low3) … )  nk + lowk )  w

数组元素的地址计算 前面的计算基于按行存放的存储方式 A: array[1..2, 1..3] of T A[1,1] A[1,2] A[1,3] A[2,1] A[2,2] A[2,3] 按行存放策略和按列存放策略都可以推广到多维数组中

数组引用的翻译 为数组引用生成代码要解决的主要问题：将前面 的地址计算公式和数组引用的文法关联起来 假定数组编号从0开始，基于宽度来计算相对地 址：

数组引用生成代码的翻译方案 S  id = E ; | L = E ; E  E + E | id | L L  id [ E ] | L [ E ] 非终结符号L的三个综合属性 L.array是一个指向数组名字对应的符号表条目的指针， L.array.base为该数组的基地址 L.addr指示一个临时变量，计算数组引用的偏移量 L.type是L生成的数组的类型 对于任何数组类型t，其宽度由t.width给出，t.elem给出 其数组元素的类型

例 L  id [ E ] | L [ E ] 假设a是一个2*3的整数数组，那么 L.type是L生成的数组的类型 t.width给出类型t的宽度 t.elem给出其数组元素的类型 假设a是一个2*3的整数数组，那么 a的类型是array(2, array(3,integer))，类型宽度是24，其数 组元素的类型是array(3,integer) a[i]的类型是array(3,integer)，类型宽度是12，其数组元 素的类型是integer a[i]的偏移量 = i * 12 a[i][j]的类型是整型，类型宽度是4 a[i][j]的偏移量 = a[i]的偏移量 + j * 4

L.array.base为该数组的基地址，L.addr保存数组引用的偏移量

假设a是一个2*3的整数数组，c、i、j都是整数。 基于数组引用的翻译方案，表达式c+a[i][j]的注释分析树 及三地址代码序列如下：

本章内容 介绍几种常用的中间代码表示  用语法制导定义和翻译方案来说明源语言的各种 构造怎样被翻译成中间表示 抽象语法树（上一章已介绍） 有向无环图 三地址代码 用语法制导定义和翻译方案来说明源语言的各种 构造怎样被翻译成中间表示 声明（和类型）  表达式和赋值  类型检查和类型转换 控制流 过程

类型检查 类型检查 类型检查能够发现程序中的一些错误 设计语法制导的类型检查器 确定源程序每个程序构造的类型表达式 确定这些类型表达式是否满足一组逻辑规则 这些规则称为源语言的类型系统 类型检查能够发现程序中的一些错误 设计语法制导的类型检查器 对类型表达式采用抽象语法 具体：T[N] 抽象：array (N, T) T* pointer (T) 考虑到报错的需要，增加类型type_error

例：一个简单类型检查器 一个简单的语言 S  id := E | if E then S | while E do S | S ; S E  true | num | id | E + E | E [ E ] | *E | E (E )

类型检查 – 表达式 E  true {E.type = boolean } E  num {E.type = integer} E  id {E.type = top.gettype(id.lexeme)} E  E1 + E2 {E.type = if E1.type == integer and E2. type == integer then integer else type_error }

类型检查 – 表达式 E  E1 [E2 ] {E.type = if E2. type == integer and E1. type == array(s, t) then t else type_error } E  *E1 {E.type = if E1.type == pointer(t) then t E  E1 (E2 ) {E. type = if E2 . type == s and E1. type == s  t then t

类型检查 – 语句 S  id := E { if (id.type == E.type && E.type  {boolean, integer}) S.type = void; else S.type = type_error;} S  if E then S1 {S. type = if E. type == boolean then S1.type else type_error }

类型检查 – 语句 S  while E do S1 {S.type = if E.type == boolean then S1. type else type_error } S  S1; S2 {S. type = if S1. type == void and S2. type == void then void

类型检查 类型检查可以分为静态和动态两种 E  E1 [E2 ] {E.type = if E2. type == integer and 静态检查在编译时刻完成 动态检查在运行时刻完成，如数组元素访问越界 E  E1 [E2 ] {E.type = if E2. type == integer and E1. type == array(s, t) then t else type_error }

类型综合和类型推断 类型综合（type synthesis）：根据Typing Rules和 子表达式的类型来确定程序构造的类型 比如：如果f的类型为s→t且x的类型为s 那么表达式f(x)的类型为t 类型推断（type inference）：类型信息不完全的 情况下如何确定类型？ 根据一个语言结构的使用方式来推导出该结构的类型 比如：如果f(x)是一个表达式 那么存在某些α和β，f的类型为α→β且x的类型为α

类型转换 在某些运算时，编译器需要把运算分量进行必要 的转换 例：x + i，x是浮点数类型而i是整型 整型和浮点型在计算机中有不同的表示形式，使用不 同的机器指令完成整数和浮点数的运算 编译器需要对两个运算分量进行转换，以保证进行加 法运算时具有相同的类型 t1 = (float) i ; t2 = x + t1

类型转换 E  E1 op E2 {E.type = if E1.type == integer and E2.type == integer then integer else if E1.type == integer and E2.type == float then float else if E1.type == float and E2.type == integer else if E1.type == float and E2.type == float else type_error } 问题：需要转换的类型增多，情况会更多

类型转换 转换原则（源语言给出类型层次结构） 拓宽（widening）：在类型层次结构中位于较低层的 类型可以被拓宽为较高层的类型 窄化（narrowing）：存在一条s到t的路径，则可以将 类型s窄化为t

类型转换 隐式转换：类型转换由编译器自动完成，又称自 动类型转换（coercion） 很多语言中，自动类型转换仅限于拓宽转换 显式转换：需要程序员写出某些代码来引发类型 转换，又称强制类型转换（cast）

更通用的类型转换语义规则 两个函数 max(t1,t2) widen(a,t,w)

本章内容 介绍几种常用的中间代码表示  用语法制导定义和翻译方案来说明源语言的各种 构造怎样被翻译成中间表示 抽象语法树（上一章已介绍） 有向无环图 三地址代码 用语法制导定义和翻译方案来说明源语言的各种 构造怎样被翻译成中间表示 声明（和类型）  表达式和赋值  类型检查和类型转换  控制流 过程

控制流语句的翻译 if-else语句，while语句 应将语句的翻译和布尔表达式的翻译结合在一起

布尔表达式 布尔表达式通常用来： 布尔表达式的使用意图要根据其语法上下文确定 下面先考虑用于改变控制流的布尔表达式 改变控制流。例如if (E) S 布尔表达式的值由程序到达的某个位置隐含地指出 如if (E) S, 如果运行到语句S，则意味着E的取值为真 计算逻辑值后赋值。布尔表达式的值为true或false， 可以使用带有逻辑运算符的三地址指令进行求值（类 似算术表达式） 布尔表达式的使用意图要根据其语法上下文确定 下面先考虑用于改变控制流的布尔表达式

布尔表达式的文法 B  B || B | B && B | ! B | ( B ) | E rel E | true | false 布尔运算符: && 、 || 、 ! &&和||是左结合的 优先级： || 最低，其次是&&，最高是 ! 关系表达式 E1 rel E2 关系运算符：<、<=、=、!=、>、>=

布尔表达式的高效求值 B1 || B2 若B1为真，则不用求B2也能断定整个表达式为真 B1&&B2 若B1为假，则整个表达式肯定为假 若B1或B2具有副作用（比如包含了改变全局变量 的函数），则是否高效求值会影响程序运行结果 程序语言的语义定义决定是否可以高效求值 若允许，则编译器可以优化布尔表达式的求值过程， 只要已经求值部分足以确定整个表达式的值就可以了

短路的跳转代码 布尔运算符&&、 || 、 !被翻译成短路的跳转指令。 由跳转位置隐含的指出布尔表达式的值 if (x<100 || x>200 && x!=y) x=0;

控制流语句的翻译 文法 S  if B then S1 | if B then S1 else S2 | while B do S1 | S1; S2 | id = E ; B和S有综合属性code，表示翻译得到的三地址代码 B的继承属性true和false，S的继承属性next，表示跳转的 位置

控制流语句的翻译 B.code S1.code B.true: . . . 指向B.true 指向B.false B.false: goto S.next S2.code (b) if-then-else B.code S1.code B.true: . . . 指向B.true 指向B.false (a) if-then B.code S1.code B.true: . . . 指向B.true 指向B.false goto begin begin: (c) while-do S1.code S2.code S1.next: . . . (d) S1; S2

控制流语句的翻译 S  if B then S1的规则： B.true = newLabel(); B.false = S.next; B.code S1.code B.true: . . . 指向B.true 指向B.false (a) if-then S  if B then S1的规则： B.true = newLabel(); B.false = S.next; S1.next = S.next; S.code = B.code || label(B.true) || S1.code 假定每次调用newLabel()都会产生一个新的标号，并假设label(L)将标号L附加到即将生成的下一条三地址指令上

控制流语句的翻译 S  if B then S1 else S2的规则： B.true = newLabel(); B.code S1.code B.true: . . . 指向B.true 指向B.false B.false: goto S.next S2.code (b) if-then-else S  if B then S1 else S2的规则： B.true = newLabel(); B.false = newLabel(); S1.next = S.next; S2.next = S.next; S.code = B.code || label(B.true) || S1.code || gen(‘goto’ S.next) || label(B.false) || S2.code

控制流语句的翻译 S  while B do S1的规则： begin = newLabel(); B.code S1.code B.true: . . . 指向B.true 指向B.false goto begin begin: (c) while-do S  while B do S1的规则： begin = newLabel(); B.true = newLabel(); B.false = S.next; S1.next = begin; S.code = label(begin) || B.code || label(B.true) || S1.code || gen(‘goto’ begin) begin对于这个产生式的语义规则是局部的，故可用变量而非属性

控制流语句的翻译 S  S1; S2的规则： S1.next = newLabel(); S2.next = S.next; S1.code S2.code S1.next: . . . (d) S1; S2 S  S1; S2的规则： S1.next = newLabel(); S2.next = S.next; S.code = S1.code || label(S1.next) || S2.code

布尔表达式的控制流翻译 布尔表达式B被翻译成三地址指令，生成的条件 或无条件转移指令反映B的值 如果B是a < b的形式， 那么代码是： if a < b goto B.true goto B.false

布尔表达式的控制流翻译 例 表达式 a < b || c < d && e < f 的代码是： 例 表达式 a < b || c < d && e < f 的代码是： if a < b goto Ltrue goto L1 L1: if c < d goto L2 goto Lfalse L2: if e < f goto Ltrue

布尔表达式的控制流翻译 B  B1 || B2的规则： B1.true = B.true; B1.false = newLabel(); B2.false = B.false; B.code = B1.code || label(B1.false) || B2.code

布尔表达式的控制流翻译 B  B1 && B2的规则： B1.true = newLabel(); B1.false = B.false; B2.true = B.true; B2.false = B.false; B.code = B1.code || label(B1.true) || B2.code

布尔表达式的控制流翻译 B  ! B1的规则： B1.true = B.false; B1.false = B.true; B.code = B1.code B  (B1)的规则： B1.true = B.true; B1.false = B.false;

布尔表达式的控制流翻译 B  E1 rel E2的规则： B.code = E1.code || E2.code || gen(‘if’ E1.addr rel.op E2.addr ‘goto’ B.true) || gen(‘goto’ B.false) B  true的规则： B.code = gen(‘goto’ B.true) B  false的规则： B.code = gen(‘goto’ B.false)

控制流语句及布尔表达式翻译

布尔表达式及控制流语句翻译示例 if (x<100 || x>200 && x!=y) x=0; 优化

布尔表达式的两个功能 改变控制流，跳转 求值 刚刚前面重点讨论 翻译成短路的跳转代码 如x=true, x=a<b, x = (a<b)&&(c<d) 依然希望短路计算，如何翻译？ 首先为B生成跳转代码，然后在跳转代码的真假出口 分别将true或false赋给一个新的临时变量t。

示例 赋值语句x=a<b && c<d

本章内容 介绍几种常用的中间代码表示  用语法制导定义和翻译方案来说明源语言的各种 构造怎样被翻译成中间表示 抽象语法树（上一章已介绍） 有向无环图 三地址代码 用语法制导定义和翻译方案来说明源语言的各种 构造怎样被翻译成中间表示 声明（和类型）  表达式和赋值  类型检查和类型转换  控制流  过程

过程的中间代码 先计算参数的值 然后param指令传递参数 然后call指令调用 最后返回值赋值

过程的中间代码 几个关键概念 函数类型：形式参数类型和返回值类型，通过函数类 型构造符得到 符号表，为函数的形式参数构造一个独立的符号表 类型检查，函数调用时需要进行类型检查和必要的类 型转换 函数调用：id(E1,E2,…,En)

本章总结 介绍几种常用的中间代码表示 用语法制导定义和翻译方案来说明源语言的各种 构造怎样被翻译成中间表示 抽象语法树（上一章已介绍） 有向无环图 三地址代码 用语法制导定义和翻译方案来说明源语言的各种 构造怎样被翻译成中间表示 声明（和类型） 表达式和赋值 类型检查和类型转换 控制流 过程