,
.
,
何谓中间代码 ( Intermediate code )
( Intermediate representation )
( Intermediate language )
源程序的一种内部表示，不依赖目标机的结构，易于机械生成目 标代码的中间表示。
为什麽要此阶段逻辑结构清楚；利于不同目标机上实现同一种语言；
利于进行与机器无关的优化 ；这些内部形式也能用于解释。
中间代码的几种形式逆波兰 四元式 三元式 间接三元式 树
7.3 中间代码生成中间代码生成
中间代码的形式
中间代码生成
7.3.1中间代码 de形式
中间代码：
是源程序的一种内部表示
复杂性介于源语言和目标机语言之间
中间代码的作用：
使编译程序的逻辑结构更加简单明确
利于进行与目标机无关的优化
利于在不同目标机上实现同一种语言
中间代码的形式：
逆波兰式、四元式、三元式、间接三元式,抽象语法树和 DAG
中间代码的层次中间代码按照其与高级语言和机器语言的接近程度，可以分成以下三个层次：
高级：最接近高级语言，保留了大部分源语言的结构。
中级：介于二者之间，与源语言和机器语言都有一定差异。
低级：最接近机器语言，能够反映目标机的系统结构，因而经常依赖于目标机。
不同层次的中间代码源语言
（高级语言）
中间代码
（高级）
中间代码
（中级）
中间代码
（低级）
float a[10][20];
a[i][j+2];
t1 = a[i,j+2] t1 = j + 2
t2 = i * 20
t3 = t1 + t2
t4 = 4 * t3
t5 = addr a
t6 = t5 + t4
t7 = *t6
r1 = [fp - 4]
r2 = [r1 + 2]
r3 = [fp - 8]
r4 = r3 * 20
r5 = r4 + r2
r6 = 4 * r5
r7 = fp – 216
f1 = [r7 + r6]
逆波兰,A B C D - * + E C D – N ^ / +
四元式,( 1 ) ( - C D T1 )
( 2 ) ( * B T1 T2)
( 3 ) ( + A T2 T3)
( 4 ) ( - C D T4)
( 5 ) ( ^ T4 N T5)
( 6 ) ( / E T5 T6)
( 7 ) ( + T3 T6 T7)
例,A + B * ( C - D ) + E / ( C - D ) ^N
三元式,( 1) ( - C D )
(2) ( * B (1 ) )
(3) ( + A (2 ) )
(4) ( - C D )
(5) ( ^ (4) N )
(6) ( / E (5 ) )
(7) ( + (3 ) (6 ) )
例,A + B * ( C - D ) + E / ( C - D ) ^N
间接三元式,间接三元式序列 间接码表
( 1) ( - C D ) （ 1 ）
( 2) ( * B ( 1) ) （ 2 ）
( 3) ( + A ( 2) ) （ 3 ）
( 4 ) ( ^ ( 1 ) N ) （ 1 ）
( 5) ( / E ( 4) ) （ 4 ）
( 6) ( + ( 3) (5 ) ) （ 5 ）
（ 6 ）
例,A + B * ( C - D ) + E / ( C - D ) ^N
抽象语法树和 DAG图语法树可以作为一种合适的中间语言形式。在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种经变换后的语法树称之为抽象语法树（ Abstract Syntax Tree）。
在抽象语法树中，操作符和关键字都不作为叶结点出现，而是把它们作为内部结点，即这些叶结点的父结点如产生式 S→if B then S 1 else S2抽象语法树表示
if-then-else
B S1 S2
语法树和抽象语法树
directed acyclic graph (DAG).
b*c+b*c
+
*
b c
7.3.2 简单赋值语句的 (四元式）翻译四元式形式,
result,= arg1 op arg2
语义属性,id.name,E.place
函数,lookup( id.name) ;
过程,emit(t,= arg1 op arg2);
newtemp;
产生式和语义描述：
(1) S?id,= E
{ P:=lookup (id.name) ;
if P? nil then emit( P ―,=‖ E.place)
else error }
(op,arg1,arg2,result) 或
(2) E?E1+E2
{E.place:= newtemp;
emit(E.place―:=‖ E1.place―+‖E2.place)}
(3) E? - E1
{ E.place:=newtemp;
emit(E.place―:=‖―uminus‖ E1.place)}
(4) E?( E1)
{ E.place:= E1.place}
(5) E?id
{E.place:=newtemp;
P:=lookup(id.name);
if P?nil then E.place:=P
else error}
7.3.3简单说明句的翻译 -翻译是指在符号表中登录名字和性质。
最简单的说明句的语法：
Ｄ → integer〈 namelist〉 ｜ real〈 namelist〉
〈 namelist〉 → 〈 namelist〉,id｜ id
用自下而上翻译 文法改写：
Ｄ → Ｄ 1,id
｜ integer id
| real id
(1)Ｄ → integer id｛ enter(id,int） ;D.att:=int}
(2)Ｄ → real id｛ enter(id,real） ;D.att:=real}
(3)Ｄ → Ｄ １,id｛ enter(id，Ｄ １,att）；
D.att:=Ｄ １,att｝
过程中的说明语句 —用全程变量 offset表示变量在本过程的数据区的相对位置,增加的量为数据对象的宽度,用属性 width
表示,
P→D ｛ offset:=0}
Ｄ → ….
Ｄ → real id
｛ enter(id,real,offset） ;D.att:=real;
D.width:=8; offset:=offset+D.width}
…
如 i f B t h e n S 1 e l s e S 2
B 的 代 码条 件 假转
S1的 代 码转 移
S2的 代 码
B
S1 S2
N
Y
7.3.4控制语句的翻译 -结构的翻译
E.false
控制语句的结构翻译控制语句 S?if E then S 1
E 的代码 E.true
E.true,S1 的代码
E.false,
S? 1 2
E 的代码 E
E S1 的代码
2 的代码
E.false
控制语句的结构翻译控制语句 if E then S else S
.true
.true,
goto S.next
E.false,S
S.next:
E.false
控制语句的结构翻译控制语句 S?while E do S1
E 的代码 E.true
E S1 的代码
…
.true,
goto S.begin
E.false,
S.begin,
S?if E then S1
{E.true:=nemlable;
E.false:=S.next;
S1,next:=S.next;
S.code:=E.code||gen(E.true’:’)|| S1.code}
S?if E then S1 elseS2
{E.true:=nemlable;
E.false:= nemlable;
S1,next:=S.next;
S2,next:=S.next
S.code:=E.code||gen(E.true’:’)|| S1.code ||gen(‘goto’
S.next)||gen(E.false’:’)||S2.code}
S?while E do S1
{….,}
E.false
7.3.5控制语句中布尔表达式的翻译控制语句 S?if E then S 1 else S 2
E 的代码 E.true
E.true,S1 的代码
goto out
E.false,S2 的代码
out:
,把条件转移的布尔表达式 翻译成仅含
E
条件真 转 (jrop,B,C,L) 和无条件 转 (jump,_,_,L)的四元式
=a rop b
if a rop b goto E.true
goto E.false
如,a<b or c<d and e<f
可 翻译成如下四元式：
(1) if a<b goto E.true
(2) goto (3)
(3) if c<d goto (5)
(4) goto E.false
(5) if e<f goto E.true
(6) goto E.false
(翻译 不是最优 )
语句 if a<b or c<d and e<f then S1 else S2的四元式
(1) if a<b goto (7) //转移至 (E.true )
(2) goto (3)
(3) if c<d goto (5)
(4) goto (p+1) //转移至 (E.false)
(5) if e<f goto (7)
(6) goto (p+1)
(7)( S1的四元式
……
(p-1) …… ）
(p) goto (q)
(p+1) (S2的四元式
……
(q-1) …… ）
(q)
//转移至 (E.true )
//转移至 (E.false)
//(E.false)入口
// (E.true ) 入口拉链技术 －记录需回填地址的四元式，把需回填
Ｅ．ｔｒｕｅ的四元式拉成一链，把需回填Ｅ．ｆａ
ｌｓｅ的四元式拉成一链，分别称做“真”链和“假”
链 （１０） … ｇ oｔｏ Ｅ．ｔｒｕｅ
…
（２０） … ｇｏｔｏ Ｅ．ｔｒｕｅ
…
（３０） … ｇｏｔｏ Ｅ．ｔｒｕｅ
则链成
（１０） … ｇｏｔｏ （０）
…
（２０） … ｇｏｔｏ （１０）
…
（３０） … ｇｏｔｏ （２０）
把地址（３０）称作“真”链链首，０为链尾标志，即地址（１
０）为“真”链链尾。
语义描述使用的变量和过程：
E.true,―真,链,E.false,―假,链
E.codebegin,E 的第一个四元式
Nextstat,下一四元式地址过程,emit( ) 输出一条四元式，而 nextstat+1
merge(p1,p2) 把 p1 的链首填在 p2 的链尾例,merge(p1,p2)
(p10) goto ( 0)
……
p1 链 (p100) goto (p10)
…… `
(p1) goto (p100)
(p20) goto( 0) (p1)
……
p2 链 (p200) goto (p20)
……
(p2) goto (p200)
backpatch(p,t) 把 链首 p 所链接的每个四元式的第四区段都填为 t
语句 i f a < b o r c<d a n d e<f t h en S
1
el s e S
2
的四元式
(1 ) i f a < b g o t o ( 7 ) ( E,t ru e ) ( 1 ) 和 ( 5 ）
( 2 ) g o t o ( 3 ) 拉链 （真）
( 3 ) i f c<d g o t o ( 5 )
( 4 ) g o t o ( p + 1 ) ( E,f a l se) ( 4 ) 和 ( 6 )
( 5 ) i f e<f g o t o ( 7 ) 拉链 （假）
( 6 ) g o t o ( p + 1 )
( 7 ) ( S
1
的四元式
( p - 1 )）
( p ) g o t o (q)
( p + 1 ) ( S
2
的四元式
( q - 1 )）
(q)
自下而上分析中的一种翻译方案：
(1) E→ E1 or E 2 { backpatch(E 1.false,E 2.Codebegin);
E.Codebegin:= E 1.codebegin;
E.true:=merge(E 1.true,E 2.true)
E.false:= E 2.false}
(2)E→ E1 and E 2 { backpatch(E 1.true,E 2.codebegin);
E.Codebegin:= E 1.codebegin;
E.true:= E 2.true;
E.false:= merge(E 1.false,E 2false);}
(3) E→ not E1 { E.true:= E 1.false;
E.Codebegin:= E 1.codebegin;
E.false:= E 1.true
( 4 ) E → (E
1
) { E,t r u e,= E
1
,t r u e ;
E,C o d e b e g i n,= E
1
,c o d e b e g i n ;
E,f a l se,= E
1
,f a l se }
( 5 ) E → i d 1 r o p i d 2 { E,t r u e,=n e x t st a t ;
E,C o d e b e g i n,=n e x t st a t ;
E,f a l se,=n e x t st a t + 1 ;
e m it (? if ‘ id 1,p la c e? r o p ‘ id 2,p la c e?g o to ‘– ) ;
em it (? g o t o ‘ - ) }
( 6 ) E → i d { E,t r u e,=n e x t st a t ;
E,c o d e b e g i n,=n e x t st a t ;
E,f a l se,=n e x t st a t + 1 ;
e m it (? if ‘ id,p la c e?g o to ‘ – ) ;
e m it (? g o t o ‘ - ) }
GOTO语句翻译 —拉链返填
……
（ 10） goto L （ 10） goto 0
…… …… 链尾 （ 10）
（ 20） goto L （ 20） goto 10
…… ……
（ 30） goto L (30) goto 20
…… …… 链首 30）
（ 40） L,…… （ 40） L,….
符号表
name type def add
…
L label not r
(p) goto 0
…
(q) goto p
…
(r) goto q
建链的方法是：若ｇｏｔｏ Ｌ中的标号Ｌ尚未在符号表中出现，则把Ｌ填入表中，置Ｌ的,定义否,标志为,未,,把ｎｅｘｔｓｔａｔ填进Ｌ
的地址栏中 作为新链首，然后，产生四元式（ｇ
ｏｔｏ ０），其中０为链尾标志。若Ｌ已在符号表中出现（但,定义否,标志为,未,），则把它的地址栏中的编号（记为ｑ）取出，把
nextstat填进该栏作新链首，然后，产生四元式
（ｇｏｔｏ ｑ）。
定义标号语句的产生式
Ｓ → <label> Ｓ
<label>→ ｉ：
那么，当用 <label>→ ｉ：进行归约时，应做如下的语义动作：
1.若ｉ所指的标识符（假定为Ｌ）不在符号表中，则把它填入，置,类型,为,标号,,,定义否,为
,已,,,地址,为 nextstat。
2.若Ｌ已在符号表中但,类型,不为,标号,或,定义否,为,已,,则报告出错。
3.若Ｌ已在符号表中，则把标志,未,改为,已,,
然后，把地址栏中的链首（设为ｑ）取出，同时把
nextstat填在其中，最后，执行 backpatch（ｑ，
nextstat）。
翻译ｇｏｔｏ语句时，还有两点必须注意第一：相同名字的标号可以在不同名字作用域中定义。如：
（１） ｂｅｇｉｎ
（２） Ｌ：ｂｅｇｉｎ
（３） ｇｏｔｏ Ｌ； //延迟使用
（４） ……
（５） Ｌ,…
（６） ｅｎｄ
（７） ｅｎｄ
第二，转移标号是非法的
（１） for ｉ ∶ =１ to 10 do
（２） begin gotoＬ；
（３） for ｊ ∶ =１ to 20 do
（４） begin goto Ｌ；
… …
（ｎ） L,end ｛ forｊ｝
end ｛ for i｝
处理到第（ｎ）行后，第（４）行的 goto目标得以解决。而第（２）行的 goto Ｌ是非法的，但只有当循环关闭时才能确定。
7.3.6 过程调用的四元式产生
过程调用的实质是把程序控制转移到子程序 (过程段 )。
在转子之前必须用某种办法把实在参数的信息传给被调用的子程序，并且应该告诉子程序在它工作完毕后返回到什么地方。
传递实在参数,
过程调用
ＣＡＬＬ Ｓ（Ａ＋Ｂ,Ｚ）
将被翻译成：
Ｔ ∶ =
ｐａｒ
ｐａｒ
ｃａｌｌ
如何产生反映这种模式的四元式过程调用语句的文法：
（１） S→call ｉ （ 〈 arglist〉 ）
（２） <arglist>→<arglist> １ E
（３） <arglist>→E
arglist.QUEUE
在处理实在参数串的过程中记住每个实参的地址
（１） S→call ｉ （ 〈 arglist〉 ）
｛ For 队列 argulist.QUEUE 的每一项ｐ Do
Gen(par _,_,p)；
Gen(call,_,_,entry(i))}
（２） <arglist>→<arglist> １ E
｛把Ｅ,PLACE 排在 arglist１,QUEUE 的末端；
arglist.QUEUE:= arglist１,QUEUE ｝
（３） <arglist>→E
｛建立一个 arglist.QUEUE,它只包含一项 E.PLACE｝
记录实在参数个数
7.3.7 数组的翻译数组说明和数组元素的引用
数组内情向量,
编译中，将数组的有关信息记录在一些单元中，称为,内情向量”，确定数组，放在符号表中；可变数组，运行时建立相应的内情向量。
A [ l
1
,u
1
,l
2
,u
2
,,l
n
,u
n
]
l
1
u
1
l
2
u
2
,
,
t y pe a （首地址）
n C
例：按行 A 是 10? 20 的二维数组
A[1,1]
A[1,2]
.,第一行
.,
A [ 1,2 0 ]
A [ 2,1 ]
.,第二行
.,
.,
.,
.,
A [ 1 0,2 0 ] 第十行数组元素的地址计算设 A [ 1,1] 的地址为 a,每个元素占一个字
A[ i,j] 的地址,a + （ i - 1 ）? 2 0 + （ j-1 ）
= （ a - 2 1 ） + （ 2 0 i +j ）
一般,a r r a y A [ l
1
,u
1
,l
2
,u
2
，,l
n
,u
n
]
令 d
i
=u
i
-l
i
+1
元素 A [ i
1
,i
2
，,i
n
] 的地址 D
D = a + （ i
1
-l
1
） d
2
d
3
d
n
+ （ i
2
-l
2
） d
3
d
4
d
n
+ + （ i
n - 1
-l
n - 1
） d
n
+ （ i
n
- l
n
）
经因子分解后得 D =C ON S PAR T +V A R PAR T
其中 CO NSPART=a - C
C= （（（ l
1
d
2
+l
2
） d
3
+ l
3
） d
4
+ + l
n - 1
） d
n
+ l
n
VARP ART= （（（ i
1
d
2
+i
2
） d
3
+ i
3
） d
4
+ + i
n - 1
） d
n
+ i
n
将产生两组计算数组元素地址的四元式一组计算ＶＡＲＰＡＲＴ，将它放在某个临时单元 Ｔ 中；
一组计算ＣＯＮＳＰＡＲＴ，放在另一个临时单元 T1中。
同时用表示数组元素的地址。
对应“数组元素引用”（引用其值）和“对数组元素赋值”
有两个相应的四元式：“变址取数”和“变址存数”。
“变址取数”的四元式是：
（ ＝［ ］,T1[ T ],Ｘ ∶ =
T1[ T ] ／
“变址存数”的四元式是：
（ ［ ］＝，,T1[ T ]
T1[ T ],=x ／
.
,
何谓中间代码 ( Intermediate code )
( Intermediate representation )
( Intermediate language )
源程序的一种内部表示，不依赖目标机的结构，易于机械生成目 标代码的中间表示。
为什麽要此阶段逻辑结构清楚；利于不同目标机上实现同一种语言；
利于进行与机器无关的优化 ；这些内部形式也能用于解释。
中间代码的几种形式逆波兰 四元式 三元式 间接三元式 树
7.3 中间代码生成中间代码生成
中间代码的形式
中间代码生成
7.3.1中间代码 de形式
中间代码：
是源程序的一种内部表示
复杂性介于源语言和目标机语言之间
中间代码的作用：
使编译程序的逻辑结构更加简单明确
利于进行与目标机无关的优化
利于在不同目标机上实现同一种语言
中间代码的形式：
逆波兰式、四元式、三元式、间接三元式,抽象语法树和 DAG
中间代码的层次中间代码按照其与高级语言和机器语言的接近程度，可以分成以下三个层次：
高级：最接近高级语言，保留了大部分源语言的结构。
中级：介于二者之间，与源语言和机器语言都有一定差异。
低级：最接近机器语言，能够反映目标机的系统结构，因而经常依赖于目标机。
不同层次的中间代码源语言
（高级语言）
中间代码
（高级）
中间代码
（中级）
中间代码
（低级）
float a[10][20];
a[i][j+2];
t1 = a[i,j+2] t1 = j + 2
t2 = i * 20
t3 = t1 + t2
t4 = 4 * t3
t5 = addr a
t6 = t5 + t4
t7 = *t6
r1 = [fp - 4]
r2 = [r1 + 2]
r3 = [fp - 8]
r4 = r3 * 20
r5 = r4 + r2
r6 = 4 * r5
r7 = fp – 216
f1 = [r7 + r6]
逆波兰,A B C D - * + E C D – N ^ / +
四元式,( 1 ) ( - C D T1 )
( 2 ) ( * B T1 T2)
( 3 ) ( + A T2 T3)
( 4 ) ( - C D T4)
( 5 ) ( ^ T4 N T5)
( 6 ) ( / E T5 T6)
( 7 ) ( + T3 T6 T7)
例,A + B * ( C - D ) + E / ( C - D ) ^N
三元式,( 1) ( - C D )
(2) ( * B (1 ) )
(3) ( + A (2 ) )
(4) ( - C D )
(5) ( ^ (4) N )
(6) ( / E (5 ) )
(7) ( + (3 ) (6 ) )
例,A + B * ( C - D ) + E / ( C - D ) ^N
间接三元式,间接三元式序列 间接码表
( 1) ( - C D ) （ 1 ）
( 2) ( * B ( 1) ) （ 2 ）
( 3) ( + A ( 2) ) （ 3 ）
( 4 ) ( ^ ( 1 ) N ) （ 1 ）
( 5) ( / E ( 4) ) （ 4 ）
( 6) ( + ( 3) (5 ) ) （ 5 ）
（ 6 ）
例,A + B * ( C - D ) + E / ( C - D ) ^N
抽象语法树和 DAG图语法树可以作为一种合适的中间语言形式。在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种经变换后的语法树称之为抽象语法树（ Abstract Syntax Tree）。
在抽象语法树中，操作符和关键字都不作为叶结点出现，而是把它们作为内部结点，即这些叶结点的父结点如产生式 S→if B then S 1 else S2抽象语法树表示
if-then-else
B S1 S2
语法树和抽象语法树
directed acyclic graph (DAG).
b*c+b*c
+
*
b c
7.3.2 简单赋值语句的 (四元式）翻译四元式形式,
result,= arg1 op arg2
语义属性,id.name,E.place
函数,lookup( id.name) ;
过程,emit(t,= arg1 op arg2);
newtemp;
产生式和语义描述：
(1) S?id,= E
{ P:=lookup (id.name) ;
if P? nil then emit( P ―,=‖ E.place)
else error }
(op,arg1,arg2,result) 或
(2) E?E1+E2
{E.place:= newtemp;
emit(E.place―:=‖ E1.place―+‖E2.place)}
(3) E? - E1
{ E.place:=newtemp;
emit(E.place―:=‖―uminus‖ E1.place)}
(4) E?( E1)
{ E.place:= E1.place}
(5) E?id
{E.place:=newtemp;
P:=lookup(id.name);
if P?nil then E.place:=P
else error}
7.3.3简单说明句的翻译 -翻译是指在符号表中登录名字和性质。
最简单的说明句的语法：
Ｄ → integer〈 namelist〉 ｜ real〈 namelist〉
〈 namelist〉 → 〈 namelist〉,id｜ id
用自下而上翻译 文法改写：
Ｄ → Ｄ 1,id
｜ integer id
| real id
(1)Ｄ → integer id｛ enter(id,int） ;D.att:=int}
(2)Ｄ → real id｛ enter(id,real） ;D.att:=real}
(3)Ｄ → Ｄ １,id｛ enter(id，Ｄ １,att）；
D.att:=Ｄ １,att｝
过程中的说明语句 —用全程变量 offset表示变量在本过程的数据区的相对位置,增加的量为数据对象的宽度,用属性 width
表示,
P→D ｛ offset:=0}
Ｄ → ….
Ｄ → real id
｛ enter(id,real,offset） ;D.att:=real;
D.width:=8; offset:=offset+D.width}
…
如 i f B t h e n S 1 e l s e S 2
B 的 代 码条 件 假转
S1的 代 码转 移
S2的 代 码
B
S1 S2
N
Y
7.3.4控制语句的翻译 -结构的翻译
E.false
控制语句的结构翻译控制语句 S?if E then S 1
E 的代码 E.true
E.true,S1 的代码
E.false,
S? 1 2
E 的代码 E
E S1 的代码
2 的代码
E.false
控制语句的结构翻译控制语句 if E then S else S
.true
.true,
goto S.next
E.false,S
S.next:
E.false
控制语句的结构翻译控制语句 S?while E do S1
E 的代码 E.true
E S1 的代码
…
.true,
goto S.begin
E.false,
S.begin,
S?if E then S1
{E.true:=nemlable;
E.false:=S.next;
S1,next:=S.next;
S.code:=E.code||gen(E.true’:’)|| S1.code}
S?if E then S1 elseS2
{E.true:=nemlable;
E.false:= nemlable;
S1,next:=S.next;
S2,next:=S.next
S.code:=E.code||gen(E.true’:’)|| S1.code ||gen(‘goto’
S.next)||gen(E.false’:’)||S2.code}
S?while E do S1
{….,}
E.false
7.3.5控制语句中布尔表达式的翻译控制语句 S?if E then S 1 else S 2
E 的代码 E.true
E.true,S1 的代码
goto out
E.false,S2 的代码
out:
,把条件转移的布尔表达式 翻译成仅含
E
条件真 转 (jrop,B,C,L) 和无条件 转 (jump,_,_,L)的四元式
=a rop b
if a rop b goto E.true
goto E.false
如,a<b or c<d and e<f
可 翻译成如下四元式：
(1) if a<b goto E.true
(2) goto (3)
(3) if c<d goto (5)
(4) goto E.false
(5) if e<f goto E.true
(6) goto E.false
(翻译 不是最优 )
语句 if a<b or c<d and e<f then S1 else S2的四元式
(1) if a<b goto (7) //转移至 (E.true )
(2) goto (3)
(3) if c<d goto (5)
(4) goto (p+1) //转移至 (E.false)
(5) if e<f goto (7)
(6) goto (p+1)
(7)( S1的四元式
……
(p-1) …… ）
(p) goto (q)
(p+1) (S2的四元式
……
(q-1) …… ）
(q)
//转移至 (E.true )
//转移至 (E.false)
//(E.false)入口
// (E.true ) 入口拉链技术 －记录需回填地址的四元式，把需回填
Ｅ．ｔｒｕｅ的四元式拉成一链，把需回填Ｅ．ｆａ
ｌｓｅ的四元式拉成一链，分别称做“真”链和“假”
链 （１０） … ｇ oｔｏ Ｅ．ｔｒｕｅ
…
（２０） … ｇｏｔｏ Ｅ．ｔｒｕｅ
…
（３０） … ｇｏｔｏ Ｅ．ｔｒｕｅ
则链成
（１０） … ｇｏｔｏ （０）
…
（２０） … ｇｏｔｏ （１０）
…
（３０） … ｇｏｔｏ （２０）
把地址（３０）称作“真”链链首，０为链尾标志，即地址（１
０）为“真”链链尾。
语义描述使用的变量和过程：
E.true,―真,链,E.false,―假,链
E.codebegin,E 的第一个四元式
Nextstat,下一四元式地址过程,emit( ) 输出一条四元式，而 nextstat+1
merge(p1,p2) 把 p1 的链首填在 p2 的链尾例,merge(p1,p2)
(p10) goto ( 0)
……
p1 链 (p100) goto (p10)
…… `
(p1) goto (p100)
(p20) goto( 0) (p1)
……
p2 链 (p200) goto (p20)
……
(p2) goto (p200)
backpatch(p,t) 把 链首 p 所链接的每个四元式的第四区段都填为 t
语句 i f a < b o r c<d a n d e<f t h en S
1
el s e S
2
的四元式
(1 ) i f a < b g o t o ( 7 ) ( E,t ru e ) ( 1 ) 和 ( 5 ）
( 2 ) g o t o ( 3 ) 拉链 （真）
( 3 ) i f c<d g o t o ( 5 )
( 4 ) g o t o ( p + 1 ) ( E,f a l se) ( 4 ) 和 ( 6 )
( 5 ) i f e<f g o t o ( 7 ) 拉链 （假）
( 6 ) g o t o ( p + 1 )
( 7 ) ( S
1
的四元式
( p - 1 )）
( p ) g o t o (q)
( p + 1 ) ( S
2
的四元式
( q - 1 )）
(q)
自下而上分析中的一种翻译方案：
(1) E→ E1 or E 2 { backpatch(E 1.false,E 2.Codebegin);
E.Codebegin:= E 1.codebegin;
E.true:=merge(E 1.true,E 2.true)
E.false:= E 2.false}
(2)E→ E1 and E 2 { backpatch(E 1.true,E 2.codebegin);
E.Codebegin:= E 1.codebegin;
E.true:= E 2.true;
E.false:= merge(E 1.false,E 2false);}
(3) E→ not E1 { E.true:= E 1.false;
E.Codebegin:= E 1.codebegin;
E.false:= E 1.true
( 4 ) E → (E
1
) { E,t r u e,= E
1
,t r u e ;
E,C o d e b e g i n,= E
1
,c o d e b e g i n ;
E,f a l se,= E
1
,f a l se }
( 5 ) E → i d 1 r o p i d 2 { E,t r u e,=n e x t st a t ;
E,C o d e b e g i n,=n e x t st a t ;
E,f a l se,=n e x t st a t + 1 ;
e m it (? if ‘ id 1,p la c e? r o p ‘ id 2,p la c e?g o to ‘– ) ;
em it (? g o t o ‘ - ) }
( 6 ) E → i d { E,t r u e,=n e x t st a t ;
E,c o d e b e g i n,=n e x t st a t ;
E,f a l se,=n e x t st a t + 1 ;
e m it (? if ‘ id,p la c e?g o to ‘ – ) ;
e m it (? g o t o ‘ - ) }
GOTO语句翻译 —拉链返填
……
（ 10） goto L （ 10） goto 0
…… …… 链尾 （ 10）
（ 20） goto L （ 20） goto 10
…… ……
（ 30） goto L (30) goto 20
…… …… 链首 30）
（ 40） L,…… （ 40） L,….
符号表
name type def add
…
L label not r
(p) goto 0
…
(q) goto p
…
(r) goto q
建链的方法是：若ｇｏｔｏ Ｌ中的标号Ｌ尚未在符号表中出现，则把Ｌ填入表中，置Ｌ的,定义否,标志为,未,,把ｎｅｘｔｓｔａｔ填进Ｌ
的地址栏中 作为新链首，然后，产生四元式（ｇ
ｏｔｏ ０），其中０为链尾标志。若Ｌ已在符号表中出现（但,定义否,标志为,未,），则把它的地址栏中的编号（记为ｑ）取出，把
nextstat填进该栏作新链首，然后，产生四元式
（ｇｏｔｏ ｑ）。
定义标号语句的产生式
Ｓ → <label> Ｓ
<label>→ ｉ：
那么，当用 <label>→ ｉ：进行归约时，应做如下的语义动作：
1.若ｉ所指的标识符（假定为Ｌ）不在符号表中，则把它填入，置,类型,为,标号,,,定义否,为
,已,,,地址,为 nextstat。
2.若Ｌ已在符号表中但,类型,不为,标号,或,定义否,为,已,,则报告出错。
3.若Ｌ已在符号表中，则把标志,未,改为,已,,
然后，把地址栏中的链首（设为ｑ）取出，同时把
nextstat填在其中，最后，执行 backpatch（ｑ，
nextstat）。
翻译ｇｏｔｏ语句时，还有两点必须注意第一：相同名字的标号可以在不同名字作用域中定义。如：
（１） ｂｅｇｉｎ
（２） Ｌ：ｂｅｇｉｎ
（３） ｇｏｔｏ Ｌ； //延迟使用
（４） ……
（５） Ｌ,…
（６） ｅｎｄ
（７） ｅｎｄ
第二，转移标号是非法的
（１） for ｉ ∶ =１ to 10 do
（２） begin gotoＬ；
（３） for ｊ ∶ =１ to 20 do
（４） begin goto Ｌ；
… …
（ｎ） L,end ｛ forｊ｝
end ｛ for i｝
处理到第（ｎ）行后，第（４）行的 goto目标得以解决。而第（２）行的 goto Ｌ是非法的，但只有当循环关闭时才能确定。
7.3.6 过程调用的四元式产生
过程调用的实质是把程序控制转移到子程序 (过程段 )。
在转子之前必须用某种办法把实在参数的信息传给被调用的子程序，并且应该告诉子程序在它工作完毕后返回到什么地方。
传递实在参数,
过程调用
ＣＡＬＬ Ｓ（Ａ＋Ｂ,Ｚ）
将被翻译成：
Ｔ ∶ =
ｐａｒ
ｐａｒ
ｃａｌｌ
如何产生反映这种模式的四元式过程调用语句的文法：
（１） S→call ｉ （ 〈 arglist〉 ）
（２） <arglist>→<arglist> １ E
（３） <arglist>→E
arglist.QUEUE
在处理实在参数串的过程中记住每个实参的地址
（１） S→call ｉ （ 〈 arglist〉 ）
｛ For 队列 argulist.QUEUE 的每一项ｐ Do
Gen(par _,_,p)；
Gen(call,_,_,entry(i))}
（２） <arglist>→<arglist> １ E
｛把Ｅ,PLACE 排在 arglist１,QUEUE 的末端；
arglist.QUEUE:= arglist１,QUEUE ｝
（３） <arglist>→E
｛建立一个 arglist.QUEUE,它只包含一项 E.PLACE｝
记录实在参数个数
7.3.7 数组的翻译数组说明和数组元素的引用
数组内情向量,
编译中，将数组的有关信息记录在一些单元中，称为,内情向量”，确定数组，放在符号表中；可变数组，运行时建立相应的内情向量。
A [ l
1
,u
1
,l
2
,u
2
,,l
n
,u
n
]
l
1
u
1
l
2
u
2
,
,
t y pe a （首地址）
n C
例：按行 A 是 10? 20 的二维数组
A[1,1]
A[1,2]
.,第一行
.,
A [ 1,2 0 ]
A [ 2,1 ]
.,第二行
.,
.,
.,
.,
A [ 1 0,2 0 ] 第十行数组元素的地址计算设 A [ 1,1] 的地址为 a,每个元素占一个字
A[ i,j] 的地址,a + （ i - 1 ）? 2 0 + （ j-1 ）
= （ a - 2 1 ） + （ 2 0 i +j ）
一般,a r r a y A [ l
1
,u
1
,l
2
,u
2
，,l
n
,u
n
]
令 d
i
=u
i
-l
i
+1
元素 A [ i
1
,i
2
，,i
n
] 的地址 D
D = a + （ i
1
-l
1
） d
2
d
3
d
n
+ （ i
2
-l
2
） d
3
d
4
d
n
+ + （ i
n - 1
-l
n - 1
） d
n
+ （ i
n
- l
n
）
经因子分解后得 D =C ON S PAR T +V A R PAR T
其中 CO NSPART=a - C
C= （（（ l
1
d
2
+l
2
） d
3
+ l
3
） d
4
+ + l
n - 1
） d
n
+ l
n
VARP ART= （（（ i
1
d
2
+i
2
） d
3
+ i
3
） d
4
+ + i
n - 1
） d
n
+ i
n
将产生两组计算数组元素地址的四元式一组计算ＶＡＲＰＡＲＴ，将它放在某个临时单元 Ｔ 中；
一组计算ＣＯＮＳＰＡＲＴ，放在另一个临时单元 T1中。
同时用表示数组元素的地址。
对应“数组元素引用”（引用其值）和“对数组元素赋值”
有两个相应的四元式：“变址取数”和“变址存数”。
“变址取数”的四元式是：
（ ＝［ ］,T1[ T ],Ｘ ∶ =
T1[ T ] ／
“变址存数”的四元式是：
（ ［ ］＝，,T1[ T ]
T1[ T ],=x ／
