语义分析和中间代码生成

学习地址：
国防科技大学中国大学 MOOC

中间语言

特点：

独立于机器
复杂性介于源语言和目标语言之间

常用的中间语言：

后缀式，逆波兰式表示
图表示：抽象语法树（AST）、有向无环图（DAG）
三地址代码：三元式、四元式、间接三元式

后缀式

Lukasiewicz 发明的一种表达式的方法，又称逆波兰表示法。

一个表达式 E 的后缀形式可以如下定义：

如果 E 是一个常量或变量，则 E 的后缀式是 E 自身。
如果 E 是 $$E_1\ op\ E_2$$ 形式的表达式，其中 op 是任何二元操作符，则 E 的后缀形式为 $$E_1’ E_2’ op$$，其中 $$E_1’$$ 和 $$E_2’$$ 分别是 $$E_1$$ 和 $$E_2$$ 的后缀形式。
如果 E 是 $$(E_1)$$ 形式的表达式，那么 $$E_1$$ 的后缀式就是 E 的后缀式。

图表示

有向无环图（Directed acyclic Graph，简称 DAG）:

对表达式中的每个子表达式，DAG 中都有一个结点
一个内部结点代表一个操作符，它的孩子表示操作数
在一个 DAG 中代表公共子表达式的结点具有多个父节点。

与 AST 区别的一个简单示例：

三地址代码

基本形式：x := y op z

三地址代码可以看作是 AST 或 DAG 的一种线性表示。

对抽象语法树进行自下而上，自左而右的遍历

三地址的语句种类：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
x := y op z		# 双目运算符
x := op y		# 单目运算符
x := y			# 直接赋值
goto L			# 无条件跳转
if x relop y goto L
if a goto L		#条件跳转
param x			# 传参
call p, n		# 调用过程
return y		# 返回
x := y[i]
x[i] := y		# 索引赋值
x := &y
x := *y
*x := y			# 地址和指针赋值

四元式实现：

一个带有四个域的记录结构，这四个域分别为 op、arg1、arg2 以及 result。

三元式实现：

只用三个域表示 op、arg1 以及 arg2
计算结果引用：引用计算该值的语句的位置