6.1 中间代码生成6.2 中间代码表示方式6.2.1 后缀表达式6.2.2 有向无环图DAG语法树DAG6.2.3 三地址编码四元式三元式间接三元式6.3 算数表达式的翻译6.3.1 增量翻译6.3.2 带数组的算数表达式6.3.3 数组引用生成代码的翻译方案6.4 控制语句的翻译6.5 布尔表达式的翻译6.5.1 布尔表达式6.5.2 短路代码/跳转代码6.5.3 布尔表达式的翻译方案6.6 回填技术6.6.1 布尔表达式的回填6.6.2 回填和非回填的翻译定义比较6.6.3 布尔表达式的翻译6.6.4 控制语句的回填
6.1 中间代码生成
前端是对源语言进行分析并产生中间表示
处理与源语言相关的细节，与目标机器无关
前端后端分开的好处：不同的源语言、不同的机器可以得到不同的编译器组合
6.2 中间代码表示方式
一个编译器可能构造出一系列中间表示
高层表示接近于源语言，用于抽象地表示代码结构
低层表示接近于目标机器，适用于机器相关的处理任务
语法树是高层的表示
通过选择不同的运算符，三地址代码可以是高层表示或低层表示
6.2.1 后缀表达式
后缀表达式又称为逆波兰表示法：
把运算对象写在前面，把操作符写在后面（后缀）
这种表示法无需使用括号，如(a+b)*c可写成ab+c*
6.2.2 有向无环图DAG
语法树
语法树也是一种中间表示形式：
它刻画了源程序的自然层次结构
适用于静态类型检查等处理
DAG
DAG是一种更简洁的中间表示
用同样的语法制导定义构造语法树和DAG
DAG的区别在于，每次构造新节点时首先检查是否已存在
因此DAG能够自动提取左公因子
对比语法树和DAG
语法树中，公共子表达式每出现一次，就有一棵对应子树
有向无环图(Directed Acyclic Graph,DAG) 能够指出表达式中的公共子表达式，更简洁地表示表达式
6.2.3 三地址编码
三地址代码是语法树或DAG的线性表示形式
一条指令的右侧最多有一个运算符
三地址代码的名字对应语法树或DAG的内部节点
三地址代码适用于目标代码的生成和优化
三地址代码包含地址和指令：
地址包括：（源程序的）名字、常量、临时变量
指令包括：
x = y op z
x = op y
x = y
goto L
if x goto L 或 if False x goto L
if x relop y goto L
x = y [ i ] 或 x [ i ] = y
x = &y， x = *y, *x = y
语句
do i = i + 1; while (a[i] < v);
三地址代码如何用数据结构进行表示？
四元式
一个四元式(quadruple)有四个字段，分别是op, arg1, arg2, result。
单目运算符不使用arg2
param运算不使用arg2和result
条件转移/非条件转移将目标标号放在result字段
三元式
一个三元式(triple)有三个字段，分别是op, arg1, arg2。
运算x op y的位置用于存放结果
由于在优化时经常移动/删除/添加三元式，需要对引用的指令位置做出相应的修改。
表达式的DAG表示和三元式是等价的。
间接三元式
一个间接三元式(indirect triple)包含了一个指向三元式的指针列表，而不是列出三元式序列本身。
可以对这个列表进行操作，完成优化功能，操作 时不需要修改三元式中的参数
6.3 算数表达式的翻译
算术表达式的语法制导翻译定义
code表示代码
addr表示存放表达式结果的地址
new Temp()生成临时变量
gen()生成指令
6.3.1 增量翻译
和上一页翻译方案产生相同的三地址代码
gen不仅构造新的三地址指令，还要将它添加到至今为止已生成的指令序列之后
不需要code指令保存已有的代码，而是对gen的连续调用生成一个指令序列
6.3.2 带数组的算数表达式
假设数组元素被存放在连续的存储空间中，元素 从0到n1编号，第i个元素的地址为base + i * w
k维数组的寻址：假设数组按行存放，首先存放 A[0][i2]…[ik]，然后存放A[1][i2]…[ik]，…，那么A[i1][i2]…[ik]的地址为
base + i1 * w1 + i2 * w2 + … + ik * wk， 或 者
base + ((…((i1 * n2 + i2) * n3 + i3)…)*nk + ik)*w
其中base, w, n的值可以从符号表中找到
为数组引用生成代码要解决的主要问题：数组引用的文法和地址计算相关联
假定数组编号从0开始，基于宽度来计算相对地址
数组引用相关文法：非终结符号L生成数组名，加上一个下标表达式序列
6.3.3 数组引用生成代码的翻译方案
核心是确定数组引用的地址
L的代码只计算了偏移量
数组元素的存放地址应该根据偏移量进一步计算， 即L的数组基址加上偏移量
使用三地址指令x = a[i]
6.4 控制语句的翻译
控制流语句
S → if (B) S1
S → if (B) S1 else S2
S → while (B) S1
继承属性
因为值来自于父亲或兄弟节点的值
B.true：B为真时的跳转目标
B.false：B为假时的跳转目标
S.next：S执行完毕时的跳转目标
6.5 布尔表达式的翻译
6.5.1 布尔表达式
布尔表达式可以用于改变控制流/计算逻辑值
文法：
B → B ‖ B | B && B | ! B | ( B ) | E rel E | true | false
语义：
B1 ‖ B2中B1为真时，不计算B2，整个表达式为真，因此，当B1为真时应该跳过B2的代码
B1 && B2中B1为假时，不计算B2，整个表达式为假
6.5.2 短路代码/跳转代码
短路代码
通过跳转指令实现控制流，逻辑运算符本身不出现
语句
if (x < 100 ‖ x > 200 && x != y) x = 0;
代码
6.5.3 布尔表达式的翻译方案
生成的代码执行时跳转到两个标号之一
- 表达式的值为真时，跳转到B.true
- 表达式的值为假时，跳转到B.false
B.true和B.false是两个继承属性，根据B所在的上下文指向不同的位置
如果B是if语句条件表达式，分别指向then和else分支； 如果没有else分支，则B.false指向if语句的下一条指令
如果B是while语句的条件表达式，分别指向循环体的开头和循环出口处
if (x < 100 ‖ x > 200 && x != y ) x = 0;
程序中出现布尔表达式也可能是求值：x = a < b
处理方法：建立表达式的语法树，根据表达式的不同角色来处理
文法
S → id = E； | if (E) S | while (E) S | S S
E → E ‖ E | E && E | ! E | E rel E | …
根据E 的语法树结点所在的位置
S → while ( E ) S1中的E，生成跳转代码
对于S → id = E，生成计算右值的代码
6.6 回填技术
回填技术
生成跳转指令时不指定跳转目标，而是使用列表记录这些不完整指令的标号
当知道正确的跳转目标时再填写目标
列表中的每个指令都指向同一个目标
基本思想
记录B中跳转指令如goto S.next的标号，但不生成跳转目标，这些标号被记录到B的综合属性B.falselist中
当S.next的值成为已知时 (即S的代码生成完毕时)，把B.falselist中的所有指令的目标都填上这个
6.6.1 布尔表达式的回填
布尔表达式在取值true/false时分别跳转到某目标
综合属性
truelist：包含跳转指令标号的列表，这些指令在取值true时执行
falselist：包含跳转指令标号的列表，这些指令在取值false时执行
辅助函数
makelist(i)：创建一个包含跳转指令标号i的列表
merge(p1, p2)：将p1和p2指向的标号列表合并然后返回
backpatch(p, i)：将i作为跳转目标插入p的所有指令中
6.6.2 回填和非回填的翻译定义比较
比较
生成指令坯，然后加入相应的list
原来跳转到B.true的指令，现在加入到B.truelist中
原来跳转到B.false的指令，现在加入到B.falselist中
true/false属性的赋值，在回填方案中对应为相应的truelist/falselist的赋值或者merge
6.6.3 布尔表达式的翻译
x < 100 || x > 200 && x != y
最初始时不指定跳转目标，在确认后再回填
6.6.4 控制语句的回填
语句
S → if ( B ) S | if ( B ) S else S | while ( B ) S | { L } | A
L → L S | S
综合属性nextlist
nextlist 中跳转指令的目标是S 执行完毕后紧接着执行的下一条指令的标号
考虑S是if语句、while语句的子语句时，分别应该跳转到哪里？
M：用M.instr记录下一条指令的标号
N：生成goto指令坯，N.nextlist包含该指令标号
虽然break、continue在语法上是一个独立的句子， 但是它的代码和外围语句相关
方法：(break语句)
跟踪外围循环语句S
生成一个跳转指令坯
将这个指令坯的位置加入到S的nextlist中