U7 源程序的中间形式

一、中间表示IR

1、概念

广义上讲，编译的运行过程中任何形式的中间表示都可以称为“IR”。
一般编译程序都生成中间代码，然后再生成目标代码，主要优点是可移植 (与具体目标程序无关)，且易于共性的、目标平台无关的代码优化。

2、拓展

现代编译器设计实践：多层IR：

不同层次的IR代表了不同层次的抽象（类型、操作）通过分层抽象，实现最大限度的重用。

3、表示形式

1. 波兰表示
   前缀表示（波兰表达）：<操作符><操作数序列> + 3 5
   后缀表示（逆波兰表达） ：<操作数序列><操作符> 3 5 +
2. N-元组表示
3. 抽象机代码

二、波兰表示

1、概念

从语法树的角度，逆波兰表示可以看成后续遍历。
前序：根左右（波兰表示）
中序：左根右
后序：左右根（逆波兰表示）

2、生成波兰表示

1. 根据生成树后续遍历
2. 构造一个算法生成
   设一个操作符栈；当读到操作数时，立即输出该操作数，当扫描到操作符时，与栈顶操作符比较优先级，若栈顶操作符优先级高于栈外，则输出该栈顶操作符，反之，则栈外操作符入栈。
   

3、if语句的波兰表示

三、N元表示

1、概念

在该表示中，每条指令由n个域组成，通常第一个域表示操作符，其余为操作数。
常用的n元表示是： 三元式 四元式。

2、三元式

条件语句的三元式

缺点：使用三元式不便于代码优化，因为优化要删除一些三元式，或对某些三元式的位置要进行变更，由于三元式的结果(表示为编号)，可以是某个三元式的操作数，随着三元式位置的变更也将作相应的修改，很费事。

3、间接三元式

为了便于在三元式上作优化处理，可使用间接三元式。
三元式的执行次序用另一张表表示,这样在优化时，三元式可以不变，而仅仅改变其执行顺序表。

4、四元式（三地址表示/TAC）

结果：通常是由编译引入的临时变量，可由编译程序分配一个（虚拟）寄存器或主存单元。

5、SSA

Single Static Assignment form(SSA form) 静态单一赋值形式的 IR 主要特征是每个变量只赋值一次。
优点：可以简化很多优化的过程；可以获得更好的优化结果。

四、抽象语法树（AST）

1、概念

用树型图的方式表示中间代码，操作数出现在叶节点上，操作符出现在中间结点。
上述波兰表示的树即抽象语法树。

DAG图：Directed Acyclic Graphs 有向无环图，语法树的一种归约表达方式。

有方向：从下往上的方向是边的方向