37
布尔表达式的回填翻译（1）


布尔表达式用于语句的控制流时，它总是在为 true时或为false分别跳转到某个位置 引入两个综合属性


辅助函数

truelist: 包含跳转指令的列表，为true时执行这些指 令 falselist：包含跳转指令的列表，为false时执行这些 指令
D →T id ; D | ε T → B C | record ‘{’ D ‘}’ B → int | float C → ε | [num] C D生成一系列声明； T生成不同的类型； B生成基本类型int/float； C表示分量，生成[num]序列； 注意record中包含了各个字段的声明。字段声明和变量 声明的文法一致。
4)声明序列的SDT（2）

我们可以把offset看作是D的继承属性

P{D.offset=0} D D T id; {D1.offset= D.offset+ T.width;} D1
19
例 int a；声明过程的语法翻译
语法制导定义的SDT P→MD M→ε{offset=0;} D→T id;N D N→ε{ top.put(id.lexname,T.t,offset); offset=offset+T.w} D→ε T→BKC{T.t=C.t;T.w=C.w} K→ε{t=B.t;w=B.w;} B→int {B.t=integer;B.w=4;} C→ε{C.t=t;C.w=w;}
1)三地址代码（1）

特点

形式简单、语义明确、便于翻译 独立于目标语言 一般情况可以写成x=y op z 名字：用源程序中名字作为三地址代码的地址 常量：源程序中出现的、或者生成的常量 编译器生成的临时变量
4

每条指令右侧最多有一个运算符


运算分量：

三地址代码（2）

指令

27
1)控制流语句的翻译
S if （B） S1 | if （B） S1 else S2 | while （B） S1 | S1;S2 | assign
28
控制流语句的翻译
B.code B.true: S1.code ... (a) if begin: B.true: B.code S1.code goto begin ... (c) while 指向B.true 指向B.false 指向B.true 指向B.false

在处理一个过程/函数时，它声明的变量应该放 到单独的符号表中去； 这些变量的内存布局独立


SDT的处理方法

相对地址从0开始； 假设变量的放置和声明的顺序相同；

top.put(id.lexeme, T.type, offset)创建符号 表条目
18
变量offset记录当前可用的相对地址； 每“分配”一个变量，offset的值增加相应的位置

20
int a;
语法分析 语义信息 语法分析 语义信息
ε M offset=0 M int MB B.t=int, B.w=4 MBε MBK t=int w=4 MBKε MBKC C.t=int C.w=4 MT T.t=int T.w=4
MTid; MTid;ε MTid;N id的属性入表 offset=4 MTid;Nε MTid;ND MD P
30

继承属性


B.true，B为真时控制到达的位置； B.false，B为假时控制到达的位置。
if a<b goto B.true goto B.false
如果B1为真，则立即可知B为真，即B1.true与B.true相同； 如果B1为假，则必须计算B2的值，令B1.false为B2的开始 B2的true、false分别与E的true、false相同
第6章 中间代码生成
1
第6章 中间代码生成

中间代码表示

三地址码
四元式

类型和声明 赋值语句的翻译 控制语句的翻译

布尔表达式的翻译

控制语句的翻译
2
6.1 中间代码表示

作用

过渡：经过语义分析被译成中间代码序列
中间语言的语句 便于编译系统的实现、移植、代码优化

形式


优点

3
31

a<b


B→B1||B2

布尔表达式代码的例子


if (x<100 || x > 200 && x!= y ) x = 0; 相应的代码
32
布尔表达式的代码的SDD（1）
33
布尔表达式的代码的SDD（2）
接上表
34
混合模式布尔表达式的翻译示例
例如：4+a>b-c && d t1=4+a t2=b-c if t1>t2 goto L1 goto Lfalse L1: if d goto Ltrue goto Lfalse
14
1)局部变量的存储布局

变量的类型可以确定变量需要的内存


称为类型的宽度 可变大小的数据结构先只需要考虑指针


一个函数的局部变量总是分配在连续的区间； 因此我们可以给每个变量分配一个相对于这 个区间开始处的相对地址 变量的类型信息保存在符号表中；
15
2)计算T的类型和宽度的SDT


综合属性：type,width t和w用于类型和宽度信息从B传递到C→ε


语义


B → B‖B false
| B && B | !B | (B) | E rel E | true |

短路代码

B1‖B2中B1为真时，不计算B2，整个表达式为真。因 此，当B1为真时应该跳过B2的代码。 B1&&B2中B1为假时，不计算B2，整个表达式为假
通过跳转指令实现控制流的处理 运算符本身不在代码中出现；

运算/赋值指令：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
5
三地址代码（3）

指令


过程调用/返回：
param x1 param x2 … param xn call p, n
35
回填（1）


布尔表达式和控制流语句生成目标代码的关 键问题：某些跳转指令应该跳转到哪里 例如：if (B) S



按照短路代码的翻译方法，B的代码中有一些跳 转指令在B为假时执行， 这些代码的目标应该跳过S对应的代码。 我们把这个目标的标号作为语句的继承属性next 进行传递。但这个方法需要第二趟处理。
包括：控制结构、数据结构、单词
充分了解它们的实现方法 了解中间代码的语义 了解运行环境
23

目标语言的语义

6.3 赋值语句的翻译


将一个表达式翻 译成为三地址指 令序列 表达式的SDD



属性code表示 代码 addr表示存放 表达式结果的 地址 new Temp() 可以生成一个 临时变量 gen(…)生成 一个指令
21
5)记录中的域的处理


我们可以为每个记录创建单独的符号表 处理时



首先创建一个新的符号表，压到栈顶； 然后处理对应于字段声明的D，字段都被加入到新符 号表中； 最后根据栈顶的符号表构造record类型表达式；符号 表出栈
22
6.3 赋值语句的翻译
翻译的需求

Байду номын сангаас
充分了解各种语言现象的语义

B.code
S1.code goto S.next B.false: S2 .code ... (b) if-else B.true:
指向B.true 指向B.false
继承属性 B.true, B.false S.next
29
6.4.1布尔表达式的翻译

布尔表达式可以用于改变控制流/计算逻辑值。 文法
Makelist(i) Merge(p1,p2) Backpatch(p,i)
38
翻译模式用到如下三个函数： 1．makelist(i)：创建一个仅包含i的新表，i 是三地址码/四元式的一个索引（下标）， 或说i是代码序列的一个标号。 2．merge(p1，p2)：连接由指针p1和p2指向 的两个表并且返回一个指向连接后的表的 指针。 3．backpatch（p，i）：把i作为目标标号回 填到p所指向的表中的每一个转移指令中去。 此处的“表”都是为“回填”所拉的链

如何一趟处理完毕呢？
36
回填（2）

基本思想：
记录B中所有原来生成goto S.next， if … goto S.next的代码位置; 当S.next的值已知时，把记录中的所有指令的目标 都填上这个值。


回填技术：

生成跳转指令时暂时不指定目标标号， 使用列表分别记录这些不完整的指令； 等直到正确的目标时再填写目标标号； 每个列表中的指令都指向同一个目标
9
3)三地址代码与四元式的的关系
一般形式 x := y op z

其中 x, y, z 为变量名、常数或编译产生的临 时变量 四元式（op, y, z, x）