《编译原理》控制流语句 if 和 while 语句的翻译 - 例题解析

《编译原理》控制流语句 if 和 while 语句的翻译 - 例题解析

将 if 和 while 语句翻译成四元式

注：不同教材会有小差异，使用 _ 或者 — ，如果是 —，请注意区分 — 和 - 减号

（一）四元式

四元式是普遍采用的一种中间代码形式，由于它便于优化处理，所以目前在很多编译程序中得到广泛应用。

形式	表示
一般形式	（op ，arg1 ，arg2 ，result）
一目运算	（op ，arg1 ，____ ，result）
0元运算	（op ，____ ，____，result）

如：a:= -b+c*d的四元式为：

（:= 表示赋值，用于区分 =）

(1) ( - , b , __ , T1 )
(2) ( * , c , d , T2 )
(3) ( + , T1 , T2 , T3 )
(4) ( := , T3 , __ , a )

T1 := -b
T2 := c * d
T3 := T1 + T2
a : = T3

四元式的最大优点：

在实现代码优化时，通常需要从现有的运算序列删去某些运算，或者需要挪动一些运算的位置，这对于四元式序列来说，是比较容易实现的。

因为四元式之间的联系是通过临时变量来实现的，所以更改其中一些四元式给整个序列带来的影响较小

（二）if 语句的翻译

描述 if 语句的文法如下：

if E then S₁

或者

if E then S₁ else S₂

其中 E 为布尔表达式
S₁，S₂ 本身也可以是 if 语句或者其他语句

控制语句中的回填技术

一些转移地址并不能不产生这些四元式的同时得知。

也就是说，一个布尔式的真假出口往往不能在产生四元式的同时就确定。
因此，要回填这些地址

拉链

为了记录需回填地址的四元式，采用 “拉链” 的方法。

把需回填 E.true 的四元式拉成一链，把需回填 E.false 的四元式拉成一链，分别称做“真”链和“假”链

IF 语句翻译过程

IF 语句翻译过程大致如下：

(1) 翻译 E，获得一组四元式；
(2) 扫描 E 的真出口，回填；
假出口尚不知；
(3) 翻译 S(1) ；
(4) 遇到 else，S(1) 结束，生成一条无条件转移四元式，但出口不明；
(5) 翻译 S(2) ，结束。

if 语句的翻译例题：

对下语句进行翻译：

if A > B or C then
   if D<E then F:=F+1 else F:=F-1
      else S2;

四元式从 100 开始编号：

100 ( j> , A , B , 104 )
101 ( j , _ , _ , 102 )
102 ( jnz, C , _ , 104 )
103 ( j , _ , _ , 112 )
104 ( j< , D , E , 106 )
105 ( j , _ , _ , 109 )
106 ( + , F , 1 , T₁ )
107 ( := , T₁ , _ , F )
108 ( j , _ , _ , 113 )
109 ( _ , F , 1 , T₂ )
110 ( := , T₂ , _ , F)
111 ( j , _ , _ , 113 )
112 ( := , 0 , _ , F )
113 …

解释：

（1）第 100 号 ( j> , A , B , 104 ) ，表式示如果满足 A > B，此时四元式第四个表示结果的是 104，就表示跳转到 104 号执行，是一个真出口；如果不满足就会继续走到下个序号的四元式 101 号。
（2）第 101 号 ( j , _ , _ , 102 )，表示直接到 102。虽然没有这一句也能到达 102，但是它表表示上面不满足的状态，也叫假出口，必须要写。
（3）所以写条件要一写一对，因为不满足就走到下一个序号的四元式，并且假出口只能在它相邻的下面。
（4）第 102 号 ( jnz, C , _ , 104 )，只有一个参数，操作符时 jnz，然后同样是满足则到 104，不满足走到下一个序号的四元式。
（5）第 106 号 ( + , F , 1 , T₁ )，T₁ 是 F + 1 的结果，此时不表示跳转，不跳转也就是走到下个序号的四元式。
（6）注意赋值语句的表示，第 107 号 ( := , T₁ , _ , F )，是将被赋值的元素放在结果的位置上，就是四元式第四个位置。

（三）while 语句的翻译

while 语句的翻译过程

while 语句的翻译过程大致如下：
(1) 翻译 E，待填 E 的真链、假链；
(2) 扫描 do 后，回填 E 的真链；
(3) 翻译 S 语句称代码段；
(4) 无条件转移到 E 代码段的第一条四元式，若 S 有语句链，也应转到 E 代码段的第一条四元式。

while 语句的翻译例题

对下语句进行翻译：

While (a<b) do
{ a=a+3;
  b=b-3;    
}

四元式从 100 开始编号：

101 (j<, a, b, 103) 真出口
102 (j, _, _, 108) 假出口
103 (+, a, 3, T1)
104 (:=, T1, _, a)
105 (-, b, 3, T2)
106 (:=, T2, _, b)
107 (j, _, _, 101)
108 …

解释：

（1）原理同上
（2）注意赋值语句的表示，例如第 104 号 (:=, T1, _, a)，是将被赋值的元素放在结果的位置上，就是四元式第四个位置。