[科普中国]-中间语言

中间语言的优点

1、中间语言与具体机器特性无关，一种中间语言可以为生成多种不同型号的目标机的目标代码服务。

2、可对中间语言进行与机器无关的优化，有利于提高目标代码的质量。

3、把源程序映射成中间代码表示，再映射成目标代码的工作分在几个阶段进行，使编译算法更加清晰。

对于中间语言，要求其不但与机器无关，而且有利于代码生成。

常用的中间语言逆波兰表示逆波兰表示又称后缀表示法，它是最简单的一种中间代码表示形式，早在编译程序出现之前，它就用于表示算术表达式。

只包含简单变量（包括常数）的表达式的逆波兰式定义如下：

①每个变量a是逆波兰式；

②如果E1和E2是逆波兰式，则E1E2ω也是逆波兰式，其中ω是任一运算符。

从上面的定义可以看出，逆波兰表示法是将运算对象写在前面，把运算符写在后面（后缀），例如，把a+b写成ab+，把a*b写成ab*。所以用这种表示法表示的表达式也称为后缀式。一般来说，若 θ 是一个k（≥1）目算符，它对后缀式e1，e2，...，ek作用的结果将被表示为e1e2...ek。

逆波兰表示法的特点是不再需要括号来明显地规定表达式运算的顺序。例如，表达式(x-y)*z将被表示为xy-z*。根据运算对象和运算符出现的先后位置，以及每个算符的目数，就完全决定了一个表达式的分解。表达式和它的逆波兰式中的运算对象顺序是完全一致的，即，表达式中的所有运算对象，均按原序排在其逆波兰式中。1

四元式四元式也是一种比较普遍采用的中间代码形式，

其形式为：（OP，ARG1，ARG2，RESULT）

其中：OP为运算符，ARG1为第一运算对象，ARG2为第二运算对象，RESULT为运算结果。

运算对象和运算结果有时指用户自定义的变量，有时指编译程序引进的临时变量。我们很容易将一个表达式或一个语句表示为一组四元式。例如表达式a+b的四元式为：（ +，a，b，T）在四元式表示法中，特别规定，对于单目运算符（单目减、逻辑非、类型转换等），其四元式中的ARG2为空，一般用符号“/”或“ -”表示。例如表达式-a的四元式为：（ -，a，/，T）

三元式三元式表示是与四元式类似的一种表示法，所不同的仅是三元式中没有表示运算结果的部分，凡要涉及到运算结果的均用三元式的位置或序号来代替。

三元式的形式为：（OP，ARG1，ARG2）

其中，OP为运算符，ARG1为第一运算对象，ARG2为第二运算对象。运算对象ARG1，ARG2可以是变量名，也可以是三元式的编号。

例如，表达式a+b*c的三元式表示为：

①（*，b，c）

②（ +，a，①）

其中，三元式中的元素①表示第一个三元式的结果。

树表示树形表示是三元式的翻版。在树的表示中，树叶均为运算对象，即常量或变量，其他结点表示运算符。表达式的树形表示很容易实现：简单变量或常量的树就是该变量或常量自身，如果表达式

e1和e2的树分别为T1和T2，那么e1+e2，e1* e2，-e的树分别为图1，表达式a* b+c* d树形表示为图2，后序遍历上述二叉树便可得到该表达式的逆波兰表示ab*cd*+。

我们很容易把三元式表示成树形表示。每个三元式（OP，ARG1，ARG2）对应一棵二叉子树，OP为子树的根，ARG1和ARG2为子树的两棵子树，它们或为末端结点（终结符）或为下代子树的根，最后一个三元式③对应树的根。下图给出了三元式和树形表示的对应关系。

一般而言，双目运算对应二叉子树，多目运算对应多叉子树。但是，为了便于安排存储空间，一棵多叉子树可以通过引进新结点而表示成一棵二叉子树。2