中间代码生成

源程序的中间代码表现可以有多种形式，常见的是 三地址码 (Three-address Code) 和 语法结构树 (Syntax Trees)，语法结构树简称语法树。在这里我们只介绍一下三地址码。

三地址码由类似于汇编语言的指令序列组成，每个指令最多有三个操作数 (operand)，因此叫三地址码。

常用的三地址指令

不解释，自己体会。

// x = op z 其实就是这一类一元运算符
x = ++z

在 数组赋值 和 数组引用 中，i 表示的是数组的偏移地址而不是数组的下标，而 x[i] 和 y[i] 中的 x 和 y 是数组的基地址。

为了方便起见，像 x 、y、z 等之类的地址我们可以用源程序中的名字，也就是标识符，来作为三地址指令中的地址，因为标识符对应的地址都存放在符号表中，因此通过这些名字就可以找到对应的地址。另外，像是常量或者编译器生成的临时变量也可以作为三地址指令的地址。

三地址指令的表示

三地址指令的表现形式有一下几种：

• 四元式 (Quadruples)
• 三元式 (Triples)
• 间接三元式

以四元式为例，它由四个分量构成，其中第一个分量表示三地址指令中的操作符，后边三个分量对应与三个操作数。

(op,y,z,x)

三地址指令的四元式表示

在四元式中，第二个分量和第三个分量为源操作数，第四个分量为目标操作数，如果第二个源操作数为空，那么第三个分量也为空。

三地址指令序列唯一确定了运算完成的顺序

Example : 中间代码生成

假入输入这样一个程序片段:

while a < b do
  if c < 5 then
    while x > y do
      z = x + 1;
  else x = y;

那么它对应的分析树就是这样的(敲这棵树累死我了):

graph TD
	S --- Text7[while]
	S --- B1[B]
	S --- do
	S --- S1[S]
	B1 --- E1[E]
	E1 --- Text1["id ( a )"]
	B1 --- Text2["relop ( < )"]
	B1 --- E2[E]
	E2 --- Text3["id ( b )"]
	S1 --- if
	S1 --- B2[B]
	S1 --- then
	S1 --- S2[S]
	S1 --- else
	S1 --- S3[S]
	B2 --- E3[E]
	E3 --- Text4["id ( e )"]
	B2 --- Text5["relop ( < )"]
	B2 --- E4[E]
	E4 --- Text6["num ( 5 )"]
	S2 --- Text8[while]
	S2 --- B3[B]
	S2 --- Text9[do]
	S2 --- S4[S]
	B3 --- E5[E]
	E5 --- Text10["id ( x )"]
	B3 --- Text11["relop ( > )"]
	B3 --- E6[E]
	E6 --- Text12["id ( y )"]
	S4 --- Text13["id ( z )"]
	S4 --- Text14[=]
	S4 --- E7[E]
	S4 --- Text15[";"]
	E7 --- E8[E]
	E7 --- Text16["+"]
	E7 --- E9[E]
	E8 --- Text17["id ( x )"]
	E9 --- Text18["num ( 1 )"]
	S3 --- Text19["id ( x )"]
	S3 --- Text20["="]
	S3 --- E10[E]
	S3 --- Text21[";"]
	E10 --- Text22["id ( y )"]

他对应的中间代码应该是这样的:

100: ( j< , a  , b , 102 )
101: ( j  , -  , - , 112 )
102: ( j< , c  , 5 , 104 )
103: ( j  , -  , - , 110 )
104: ( j> , x  , y , 106 )
105: ( j  , -  , - , 100 )
106: ( +  , x  , 1 , t1  )
107: ( =  , t1 , - , z   )
108: ( j  , -  , - , 104 )
109: ( j  , -  , - , 100 )
110: ( =  , y  , - , x   )
111: ( j  , -  , - , 100 )
112:

这里，冒号前面的数字表示代码的标号，这里我们从 100 取到 112。

第 100 条指令是条件跳转指令，这条指令表示如果 a 小于 b 就跳转到 102 号指令，否则的话就继续执行 101 行指令，101 号指令是一条无条件跳转指令，也就是跳转到 112 号指令，也就是跳出整个 while 循环。

按照上面给出的伪代码，对照四元式，试着分析这段三地址指令的操作。

目标代码生成

目标代码生成以源程序的中间表示形式作为输入，并把它映射到目标语言。

目标代码生成的一个重要任务就是为程序中使用的变量合理分配寄存器

代码优化

代码优化就是为改进代码所进行的等价的程序变换，使其拥有更好的时空占用。

代码优化分为机器无关代码优化和机器相关代码优化，前者是在中间代码中优化，后者是对目标语言进行优化，优化的内容包括很多方面，比如说自动识别代码中的重复运算，并将他们删除，再比如将代价较高的运算替换为代价较低的等价的运算等等。

graph TD
	Start-- 字符流 -->词法分析器
	词法分析器-- 词法字节流 -->语法分析器
	语法分析器-- 语法树 -->语义分析器
	语义分析器-- 语法树 -->中间代码生成器
	中间代码生成器-- 中间表示形式 -->机器无关代码优化器
	机器无关代码优化器-- 中间表示形式 -->目标代码生成器
	目标代码生成器-- 目标机器语言 -->机器相关代码优化器
	机器相关代码优化器-- 目标机器语言 -->Fin

第一章 结束