【编译原理复习笔记】中间语言

中间语言

中间语言的特点和作用

（1）独立于机器
（2）复杂性介于源语言和目标语言之间
中间语言可以使编译程序的结构在逻辑上更为简单明确

常用的中间语言

后缀式
图表示：抽象语法树，有向无环图
三地址代码：三元式，四元式，间接三元式

后缀式

（1）若 E 为单独的变量或常量，则其自身就为后缀式
（2）若 E 为 E1 op E2 的形式，则其后缀式为 E1’ E2’ op，其中前两项对应了各自的后缀式
（3）若 E 为（E1）形式，则 E 的后缀式为 E1 的后缀式
优点：
后缀式不用使用括号
自左向右扫描后缀式，每碰到运算量就推进栈，遇到 k 目运算符时就计算栈顶的 k 个项目

图表示法

（1）抽象语法树
（2）有向无环图 DAG
对于表达式中的子表达式，DAG 中都有一个结点
一个内部结点表示一个操作符，其子节点代表操作数
在一个 DAG 中代表公共子表达式的节点有多个父节点

三地址代码

可以看作前两种方法的相线性表达方法
三地址：结果，第一操作数，第二操作数
而且三地址代码的复杂程度也与抽象语法树和有向无环图的复杂程度相关

三地址代码语句的种类

赋值语句
操作语句（双操作数，单操作数）
goto 语句
传参语句
返回语句
等等

四元式

将每个三元式都表示为带有四个域的记录结构，分别为 op，arg1，arg2，res

三元式

三元式不储存 res，用序号来表示 res

间接三元式

三元式表+间接码表
间接码表：一张指示器表，按运算的先后顺序列出有关三元式在三元式表中的位置，节省空间

在格外添加间接码表，此后再修改时只需要修改间接码表，这个三元式表就不用变动

赋值语句的属性文法

赋值语句的形式：
$id:=E$
赋诗语句的 S 属性文法
非终结符 S 有综合属性 S.code，代表赋值语句的三地址代码
E 有两个属性
E.place 表示存放 E 的单元的地址
E.code 表示对 E 求值的三地址语句

赋值语句的翻译模式

数组元素地址计算

设 A 为 n 维数组，按行存放，每个元素宽度为 w
$lo{w}_i$为第 i 维 的下界
$u{p}_i$为第 i 维的上界
$n_i$为第 i 维的个数
$base$为 A 的基准坐标（第一个元素地址）

红色为可变部分，蓝色为固定部分

带数组元素引用的赋值语句翻译

十分复杂，建议直接观看视频：
哈工大编译原理 P6-4

赋值语句中类型的转换

（1）在运算符中带上类型信息
（2）新增加类型转换运算符
（3）用 E.type 表示非终结符 E 的类型，并增加类型检查

如果两者类型不同时对应的语义动作：

布尔表达式

$$\begin{gathered} E\to E \\ or \\ E|E \\ and \\ E|not \\ E|(E)|i \\ relationop \\ i|i \end{gathered}$$均为布尔表达式
计算布尔表达式的两种办法：
（1）数值表示法
true 为 1，false 为 0
（2）带优化的翻译法、
可以节省计算过程
e.g.
$AandB=>ifAthenBelseFalse$
如果采用数值表示法，那么 B 的真伪是必须要进行计算的，但是采用这种方法时，A 一旦为 false 就不用在计算 B

按数值表示法进行翻译

a or b and not c
T1:=not c
T2:=b and T1
T3:=a or T2
nextstate 用来记录下一条三地址语句的位置，方便 emit 来输出三元式

带优化翻译布尔表达式

对于语义函数 newlabel，返回新的符号标号
对于一个布尔表达式，设置两个继承属性，E.true 是其为真时的控制流跳转符号
E.false 是其为假时控制流跳转符号
E.code 记录 E 生成三地址代码

一遍扫描的布尔表达式

以四元式为中间语言，使用 emit 将其送入输出数组
难点：产生四元式时转移地址无法立刻知道，只有知道了后续状态才能回填跳转状态
总的来说，一共有两种跳转可能，一种为“真”，一种为“假”，把这些未完成的四元式作为语义值保存，到合适的位置回填

引入语义变量：
nextquad：指向下一条产生四元式的地址
makelist：创建一条长度为 1 的链，对应四元式的下标
merge：合并两条链，指向合并后的链首
backpatch：回填

控制语句的属性文法

if-then

双分支 if then else

while