五, 一类控制语句的翻译
1,文法及其分析
S→if B then S1
│if B then S1 else S2
│while B do S1
B
S1
if B then S1
B为假
B为真
S1的第一条四元式
用以“回填
B
S1
S2
if B then S1 else S2
B为假
B为真
S1,S2的第一条
四元式用以
“回填”
此处产生一无条件
转移语句
B
S1
B为假
B为真
while B do S1
B的第一条四元式需记录,S1的第一条四元式用以“回填”
此处产生一无条件
转移语句
由上面几个图可见,
(1)B具有真假出口
?B为真假时的转向不同
?在翻译 B时其真假出口有待“回填”
(2)因 if语句的嵌套,必须记录不确定转
移目标的四元式的地址 — 拉链技术
2,转移语句的四元式
?条件转移 (jrelop,P1,P2,0)
(jnz,P1,-,0)
?无条件转移 (j,-,-,0)
3,语句变量及过程
(1)B.truelist,B.falselist,B的真假出口链
(2)M.code,记录四元式地址
(3)N.nextlist,记录不确定转移目标的
四元式地址
(4)S.nextlist,记录 S中不确定转移目标的
且转向地址均相同的四元式 （ 这些四元
式形成一个链,S.nextlist为链头 ）
如,
(p) (j,-,-,0)
……
(q) (j,-,-,p)
……
(r) (j,-,-,q)
S.nextlist=r
(5)makelist(t),语义过程,建链 ; t为链头 ;
t空缺时建一空链 ;
(6)merge(t1,t2),语义函数,将 t1,t2合并,
返回合并后的链头 t2;
(7)backpatch(t1,code),语义过程,用 code
回填 t1;
(8)nextcode,全局量,下一条即将生成
但尚未生成四元式的地址 。 值同 ip
如,
(p) (j,-,-,0) (u) (j,-,-,0)
…… …..,
(q) (j,-,-,p) (v) (j,-,-,u)
…… …..,
(r) (j,-,-,q) (w) (j,-,-,v)
t1=r t2=w
执行 merge(t1,t2)后
得
(p) (j,-,-,0) (u) (j,-,-,r)
…… …..,
(q) (j,-,-,p) (v) (j,-,-,u)
…… …..,
(r) (j,-,-,q) (w) (j,-,-,v)
链头 t2=w
执行 backpatch(t2,120)后,
(p) (j,-,-,120) (u) (j,-,-,120)
…… …..,
(q) (j,-,-,120) (v) (j,-,-,120)
…… …..,
(r) (j,-,-,120) (w) (j,-,-,120)
4,翻译方案
?B→i
{ P:=lookup(i.name);
if P<>nil then
begin B.truelist:=makelist(nextcode);
emit(jnz,P,-,0);
B.falselist:=makelist(nextcode);
emit(j,-,-,0)
end
else error }
?B→i 1 relop i2
{ P1:=lookup(i1.name);
P2:=lookup(i2.name);
if P1<>nil and P2<>nil then
begin B.truelist:=makelist(nextcode);
emit (jrelop,P1,P2,0);
B.falselist:=makelist(nextcode);
emit(j,-,-,0)
end
else error }
?S→A
{ S.nextlist:=makelist() }
?M→ε
{ M.code:=ip }
?N→ε
{ N.nextlist:=makelist(nextcode);
emit (j,-,-,0) }
?S→ if B then M S1
{ backpatch(B.truelist,M.code);
S.nextlist:=merge(B.falselist,S1.nextlist) }
?S→ if B then M1 S1 N else M2 S2
{ backpatch(B.truelist,M1.code);
backpatch(B.falselist,M2.code);
S.nextlist:=merge(S1.nextlist,
merge(N.nextlist,S2.nextlist)) }
?S→ while M1 B do M2 S1
{ backpatch(B.truelist,M2.code);
backpatch(S1.nextlist,M1.code);
emit(j,-,-,M1.code);
S.nextlist:=B.falselist }
例 1,if a<b then a:=a+b 的翻译
if a<b
if B B.truelist=100 100:(j<,a,b,0)
B.falselist=104 104:(j,-,-,0)
if B then ?
if B then M M.code=108
if B then M a:=a+b
if B then M S1 S1.nextlist=0 108:(+,a,b,t1)
112:(:=,t1,-,a)
S backpatch(100,108)
S.nextlist=104
108
例 2,if a<b then a:=a+b else a:=a-b 的翻译
if a<b
if B B.truelist=100 100:(j<,a,b,0)
B.falselist=104 104:(j,-,-,0)
if B then ?
if B then M1 M1.code=108
if B then M1 a:=a+b
if B then M1 S1 S1.nextlist=0 108:(+,a,b,t1)
112:(:=,t1,-,a)
if B then M1 S1 ?
if B then M1 S1 N N.nextlist=116 116:(j,-,-,0)
if B then M1 S1 N else ?
if B then M1 S1 N else M2 M2.code=120
if B then M1 S1 N else M2 a:=a-b
if B then M1 S1 N else M2 S2 S2.nextlist=0 120:(-,a,b,t2)
124:(:=,t2,-,a)
S backpatch(100,108)
backpatch(104,120)
S.nextlist=merge(0,merge(116,0))=116
108
120
例 3,if a<b then a:=a+b
else while a>e do a:=a-b;的翻译
if a<b
if B1 B1.truelist=100
100:(j<,a,b,0)
B2.falselist=104
104:(j,-,-,0)
if B1 then ?
if B1 then M1 M1.code=108
if B1 then M1 a:=a+b
if B1 then M1 S1 S1.nextlist=0
108:(+,a,b,t1)
112:(:=,t1,-,a)
108
120
if B1 then M1 S1 ?
if B1 then M1 S1 N N.nextlist=116
116:(j,-,-,0)
if B1 then M1 S1 N else ?
if B1 then M1 S1 N else M2 M2.code=120
if B1 then M1 S1 N else M2 while ?
if B1 then M1 S1 N else M2 while M3 M3.code=120
if B1 then M1 S1 N else M2 while M3 a>e
if B1 then M1 S1 N else M2 while M3 B2
B.truelist=120
120:(j>,a,e,0)
B.falselist=124
124:(j,-,-,0)
128
116
140
140
if B1 then M1 S1 N else M2 while M3 B2 do ?
if B1 then M1 S1 N else M2 while M3 B2 do M4
M4.code=128
if B1 then M1 S1 N else M2 while M3 B2 do M4 a:=a-b
if B1 then M1 S1 N else M2 while M3 B2 do M4 S2
S2.nextlist=0
128,(-,a,b,t2)
132,(:=,t2,-,a)
if B1 then M1 S1 N else M2 S3 S3.nextlist=124
BP(B2.truelist,M4.code)
136,(j,-,-,120)
S4 BP(B1.truelist,M1.code)
BP(B1.falselist,M2.code)
S4.nextlist=merge(S1.nextlist,merge(N.nextlist,S3.nextlist))
=merge(0,merge(116,124))=124
S4; 140,
最终生成的四元式序列是,
100:(j<,a,b,108)
104:(j,-,-,120)
108:(+,a,b,t1)
112:(:=,t1,-,a)
116:(j,-,-,140)
120:(j>,a,e,128)
124:(j,-,-,140)
128,(-,a,b,t2)
132,(:=,t2,-,a)
136,(j,-,-,120)
140,
六．循环语句的翻译
1,文法及其语义
S→for i:=1 to N do S 1
其语义为
i:=1;
again, if i?N then begin
S1;
i:=i+1;
goto again
end
代码结构可为,
F+0:（,＝, ’ 1’,－, i）
F+4,(j<=,i,N,F+12)
F+8,(j,-,-,S.nextlist)
F+12,(S1的四元式序列 )
…,.,
D+0,(+,i,‘1’,i)
D+4,(j,-,-,F+4)
2,翻译方案
(1)为了在生成 S1的代码之前生成 i:=1
等三个语句,必须改写文法
F→for i:=1 to N do
S→F S1
(2)F具有三个语义值
?F.nextlist:记录前述 F+8的地址
?F.place:记录 i在符号表入口
?F.again:记录 F+4
(3)语义子程序
F→for i:=1 to N do
{ P:=lookup(i.name);
emit(:=,’1’,-,P);
F.again:=ip;
emit(j?,P,N,F.again+8);
F.nextlist:=ip;
emit(j,-,-,0);
F.place:=P }
S→F S1
{ backpatch(S1.nextlist,ip);
emit (+,F.place,’1’,F.place);
emit(j,-,-,F.again);
S.nextlist:=F.nextlist }
例, for I:=1 to N do M:=M+I的翻译
for I:=1 to N do
F F.again=104 100,(:=,’1’,-,I)
F.nextlist=108 104,(j?,I,N,112)
F.place=I 108,(j,-,-,0)
F M:=M+I
F S1 S1.nextlist=0 112,(+,M,I,t1)
116,(:=,t1,-,M)
S S.nextlist=108 120,(+,I,’1’,I)
124,(j,-,-,104)
七, 控制语句也可采用改写文法的方法
S→if B then S 1
│if B then S1 else S2
│while B do S1
可将上述文法改写为,
C→if B then
T→C S 1 else
W→while
R→W B do
S→C S 1 | T S1 | R S1
C→if B then
{ backpatch(B.truelist,ip);
C.nextlist:=B.falselist }
T→C S 1 else
{ q:=ip;
emit(j,-,-,0);
backpatch(C.nextlist,ip);
T.nextlist:=merge(q,S1.nextlist) }
W→while
{ W.code:=ip }
R→W B do
{ backpatch(B.truelist,ip);
R.nextlist:=B.falselist;
R.code:=W.code }
S→C S 1
{ S.nextlist:=merge(C.nxtlisrt,S1.nextlist) }
S→T S 1
{ S.nextlist:=merge(T.nxtlisrt,S1.nextlist) }
S→R S 1
{ backpatch(S1.nextlist,R.code);
emit(j,-,-,R.code);
S.nextlist:=R.nextlist }
八, 数组元素按列存放时的处理
D=a+(in-ln)*dn-1*dn-2*…*d 1
+(in-1-ln-1)*dn-2*dn-3*…*d 1
+…+(i 2-l2)*d1+(i1-l1)
D=CONSPART+VARPART
CONSPART=a-C
C=ln*dn-1*dn-2*…*d 1 +ln-1*dn-2*dn-3*…*d 1
+…+l 2*d1+l1
VARPART =in*dn-1*dn-2*…*d 1 +in-1*dn-2*dn-3*…*d 1 +…+i 2*d1+i1
=(.,,((in*dn-1+in-1)*dn-2+ in-2 )*dn-3 +.,,+i2)*d1+i1
方法,
?VARPART的值不能按下标式的出现顺序
从左到右进行累计，它必须待所有下标
式都处理完毕之后，再从右到左进行计
算。
?设置一个栈 STACK，记录每个下标式结
果值的存放单元。待到所有下标式都处
理完毕之后，再自栈顶而下，按
VARPART的算式，累计它的值。
?为 Elist赋予一个语义属性 STACK
?不用改写文法
A→V:=E
V→i[Elist]│i
Elist→Elist 1,E | E
E→E 1 op E2│-E1│(E1)│V
九, 自上而下语法制导翻译概说
方法,
·每个非终结符对应一个递归过程 （ 函数 ）
·有关语义值作为函数值返回
·在产生式的中间可以调用语义子程序
1,控制语句的翻译
S?if B then S1
?if B then S1 else S2
?while B do S1
?A
PROCEDURE S;
BEGIN
CASE lookahead OF
′if′,BEGIN
match(′if′);
(B.truelist,B.falselist):=B;
backpatch(B.truelist,ip);
IF lookahead=′then′
THEN BEGIN match(′then′);
S1.nextlist:=S
END
ELSE ERROR;
IF lookahead=′else′
THEN BEGIN
match(′else′);
q:=ip;
emit(j,?,?,0);
backpatch(B.falselist,ip);
S1.nextlist:=merge(S1.nextlist,q);
S2.nextlist:=S;
q:=merge(S1.nextlist,S2.nextlist);
RETURN(q)
END
ELSE RETURN(merge(S1.nextlist,B.falselist))
END;
′while′,BEGIN
q:=ip;
(B.truelist,B.falselist):=B;
backpatch(B.truelist,ip);
IF lookahead=′do′
THEN BEGIN match(′do′);
S1.nextlist:=S;
backpatch(S1.nextlist,q);
emit(j,?,?,q);
RETURN(B.falselist)
END
ELSE ERROR;
END;
′i′,BEGIN
A;
RETURN(makelist( ))
END;
OTHERWISE,ERROR
END OF CASE
END OF S;
2,算术表达式的翻译
E?T{+T}
T?F{*F}
F?i?(E)
PROCEDURE F;
IF lookahead=′i′
THEN BEGIN match(′i′);
RETURN(lookup(i.name))
END
ELSE IF lookahead=′(′
THEN BEGIN match(′(′);
PLACE:=E;
IF lookahead=′)′
THEN BEGIN match(′)′);
RETURN(PLACE)
END
ELSE ERROR
END
ELSE ERROR;
PROCEDURE T;
BEGIN
T1.PLACE:=F;
WHILE lookahead=′*′ DO
BEGIN
match(′*′);
T2.PLACE:=F;
T1:=newtemp;
emit(*,T1.PLACE,T2.PLACE,T1);
T1.PLACE:=T1
END;
RETURN(T1.PLACE)
END OF T;
PROCEDURE E;
BEGIN
E1.PLACE:=T;
WHILE lookahead=′+′ DO
BEGIN
match(′+′);
E2.PLACE:=T;
T1:=newtemp;
emit(+,E1.PLACE,E2.PLACE,T1);
E1.PLACE:=T1
END;
RETURN(E1.PLACE)
END OF T;
第三节 代码优化
一, 优化的定义
优化是一种等价的，有效的程序变换
?等价 —— 不改变程序运行结果
?有效 —— 时空效率要高
二, 不同阶段的优化
1,源程序阶段的优化
2,编译优化 —— 中间代码优化和目标代码
优化
3,中间代码优化 —— 局部优化和全局优化
?局部优化：在基本块内的优化
?全局优化：超越基本块，在基本块之间的优
化
三, 划分基本块和构造程序流图
1,划分基本块
(1)找入口语句
?程序的第一条语句
?能由条件或无条件转向语句转移到的语
句
?紧跟在条件转向语句后的那个语句
(2)确定基本块
入口语句 入口语句 入口语句
…… …… ……
入口语句 转向语句 停语句
(3)删除未被划入基本块的语句
(1)i:=m-1
(2)j:=n
(3)t1:=4*n
(4)v:=a[t1]
(5)i:=i+1
(6)t2:=4*i
(7)t3:=a[t2]
(8)if t3<v goto (5)
(9)j:=j-1
(10)t4:=4*j
(11)t5:=a[t4]
(12)if t5>v goto (9)
(13)if i>=j goto (23)
(14)t6:=4*i
(15)x:=a[t6]
(16)t7:=4*i
(17)t8:=4*j
(18)t9:=a[t8]
(19)a[t7]:=t9
(20)t10:=4*j
(21)a[t10]:=x
(22)goto (5)
(23)t11:=4*i
(24)x:=a[t11]
(25)t12:=4*i
(26)t13:=4*n
(27)t14:=a[t13]
(28)a[t12]:=t14
(29)t15:=4*n
(30)a[t15]:=x
1,文法及其分析
S→if B then S1
│if B then S1 else S2
│while B do S1
B
S1
if B then S1
B为假
B为真
S1的第一条四元式
用以“回填
B
S1
S2
if B then S1 else S2
B为假
B为真
S1,S2的第一条
四元式用以
“回填”
此处产生一无条件
转移语句
B
S1
B为假
B为真
while B do S1
B的第一条四元式需记录,S1的第一条四元式用以“回填”
此处产生一无条件
转移语句
由上面几个图可见,
(1)B具有真假出口
?B为真假时的转向不同
?在翻译 B时其真假出口有待“回填”
(2)因 if语句的嵌套,必须记录不确定转
移目标的四元式的地址 — 拉链技术
2,转移语句的四元式
?条件转移 (jrelop,P1,P2,0)
(jnz,P1,-,0)
?无条件转移 (j,-,-,0)
3,语句变量及过程
(1)B.truelist,B.falselist,B的真假出口链
(2)M.code,记录四元式地址
(3)N.nextlist,记录不确定转移目标的
四元式地址
(4)S.nextlist,记录 S中不确定转移目标的
且转向地址均相同的四元式 （ 这些四元
式形成一个链,S.nextlist为链头 ）
如,
(p) (j,-,-,0)
……
(q) (j,-,-,p)
……
(r) (j,-,-,q)
S.nextlist=r
(5)makelist(t),语义过程,建链 ; t为链头 ;
t空缺时建一空链 ;
(6)merge(t1,t2),语义函数,将 t1,t2合并,
返回合并后的链头 t2;
(7)backpatch(t1,code),语义过程,用 code
回填 t1;
(8)nextcode,全局量,下一条即将生成
但尚未生成四元式的地址 。 值同 ip
如,
(p) (j,-,-,0) (u) (j,-,-,0)
…… …..,
(q) (j,-,-,p) (v) (j,-,-,u)
…… …..,
(r) (j,-,-,q) (w) (j,-,-,v)
t1=r t2=w
执行 merge(t1,t2)后
得
(p) (j,-,-,0) (u) (j,-,-,r)
…… …..,
(q) (j,-,-,p) (v) (j,-,-,u)
…… …..,
(r) (j,-,-,q) (w) (j,-,-,v)
链头 t2=w
执行 backpatch(t2,120)后,
(p) (j,-,-,120) (u) (j,-,-,120)
…… …..,
(q) (j,-,-,120) (v) (j,-,-,120)
…… …..,
(r) (j,-,-,120) (w) (j,-,-,120)
4,翻译方案
?B→i
{ P:=lookup(i.name);
if P<>nil then
begin B.truelist:=makelist(nextcode);
emit(jnz,P,-,0);
B.falselist:=makelist(nextcode);
emit(j,-,-,0)
end
else error }
?B→i 1 relop i2
{ P1:=lookup(i1.name);
P2:=lookup(i2.name);
if P1<>nil and P2<>nil then
begin B.truelist:=makelist(nextcode);
emit (jrelop,P1,P2,0);
B.falselist:=makelist(nextcode);
emit(j,-,-,0)
end
else error }
?S→A
{ S.nextlist:=makelist() }
?M→ε
{ M.code:=ip }
?N→ε
{ N.nextlist:=makelist(nextcode);
emit (j,-,-,0) }
?S→ if B then M S1
{ backpatch(B.truelist,M.code);
S.nextlist:=merge(B.falselist,S1.nextlist) }
?S→ if B then M1 S1 N else M2 S2
{ backpatch(B.truelist,M1.code);
backpatch(B.falselist,M2.code);
S.nextlist:=merge(S1.nextlist,
merge(N.nextlist,S2.nextlist)) }
?S→ while M1 B do M2 S1
{ backpatch(B.truelist,M2.code);
backpatch(S1.nextlist,M1.code);
emit(j,-,-,M1.code);
S.nextlist:=B.falselist }
例 1,if a<b then a:=a+b 的翻译
if a<b
if B B.truelist=100 100:(j<,a,b,0)
B.falselist=104 104:(j,-,-,0)
if B then ?
if B then M M.code=108
if B then M a:=a+b
if B then M S1 S1.nextlist=0 108:(+,a,b,t1)
112:(:=,t1,-,a)
S backpatch(100,108)
S.nextlist=104
108
例 2,if a<b then a:=a+b else a:=a-b 的翻译
if a<b
if B B.truelist=100 100:(j<,a,b,0)
B.falselist=104 104:(j,-,-,0)
if B then ?
if B then M1 M1.code=108
if B then M1 a:=a+b
if B then M1 S1 S1.nextlist=0 108:(+,a,b,t1)
112:(:=,t1,-,a)
if B then M1 S1 ?
if B then M1 S1 N N.nextlist=116 116:(j,-,-,0)
if B then M1 S1 N else ?
if B then M1 S1 N else M2 M2.code=120
if B then M1 S1 N else M2 a:=a-b
if B then M1 S1 N else M2 S2 S2.nextlist=0 120:(-,a,b,t2)
124:(:=,t2,-,a)
S backpatch(100,108)
backpatch(104,120)
S.nextlist=merge(0,merge(116,0))=116
108
120
例 3,if a<b then a:=a+b
else while a>e do a:=a-b;的翻译
if a<b
if B1 B1.truelist=100
100:(j<,a,b,0)
B2.falselist=104
104:(j,-,-,0)
if B1 then ?
if B1 then M1 M1.code=108
if B1 then M1 a:=a+b
if B1 then M1 S1 S1.nextlist=0
108:(+,a,b,t1)
112:(:=,t1,-,a)
108
120
if B1 then M1 S1 ?
if B1 then M1 S1 N N.nextlist=116
116:(j,-,-,0)
if B1 then M1 S1 N else ?
if B1 then M1 S1 N else M2 M2.code=120
if B1 then M1 S1 N else M2 while ?
if B1 then M1 S1 N else M2 while M3 M3.code=120
if B1 then M1 S1 N else M2 while M3 a>e
if B1 then M1 S1 N else M2 while M3 B2
B.truelist=120
120:(j>,a,e,0)
B.falselist=124
124:(j,-,-,0)
128
116
140
140
if B1 then M1 S1 N else M2 while M3 B2 do ?
if B1 then M1 S1 N else M2 while M3 B2 do M4
M4.code=128
if B1 then M1 S1 N else M2 while M3 B2 do M4 a:=a-b
if B1 then M1 S1 N else M2 while M3 B2 do M4 S2
S2.nextlist=0
128,(-,a,b,t2)
132,(:=,t2,-,a)
if B1 then M1 S1 N else M2 S3 S3.nextlist=124
BP(B2.truelist,M4.code)
136,(j,-,-,120)
S4 BP(B1.truelist,M1.code)
BP(B1.falselist,M2.code)
S4.nextlist=merge(S1.nextlist,merge(N.nextlist,S3.nextlist))
=merge(0,merge(116,124))=124
S4; 140,
最终生成的四元式序列是,
100:(j<,a,b,108)
104:(j,-,-,120)
108:(+,a,b,t1)
112:(:=,t1,-,a)
116:(j,-,-,140)
120:(j>,a,e,128)
124:(j,-,-,140)
128,(-,a,b,t2)
132,(:=,t2,-,a)
136,(j,-,-,120)
140,
六．循环语句的翻译
1,文法及其语义
S→for i:=1 to N do S 1
其语义为
i:=1;
again, if i?N then begin
S1;
i:=i+1;
goto again
end
代码结构可为,
F+0:（,＝, ’ 1’,－, i）
F+4,(j<=,i,N,F+12)
F+8,(j,-,-,S.nextlist)
F+12,(S1的四元式序列 )
…,.,
D+0,(+,i,‘1’,i)
D+4,(j,-,-,F+4)
2,翻译方案
(1)为了在生成 S1的代码之前生成 i:=1
等三个语句,必须改写文法
F→for i:=1 to N do
S→F S1
(2)F具有三个语义值
?F.nextlist:记录前述 F+8的地址
?F.place:记录 i在符号表入口
?F.again:记录 F+4
(3)语义子程序
F→for i:=1 to N do
{ P:=lookup(i.name);
emit(:=,’1’,-,P);
F.again:=ip;
emit(j?,P,N,F.again+8);
F.nextlist:=ip;
emit(j,-,-,0);
F.place:=P }
S→F S1
{ backpatch(S1.nextlist,ip);
emit (+,F.place,’1’,F.place);
emit(j,-,-,F.again);
S.nextlist:=F.nextlist }
例, for I:=1 to N do M:=M+I的翻译
for I:=1 to N do
F F.again=104 100,(:=,’1’,-,I)
F.nextlist=108 104,(j?,I,N,112)
F.place=I 108,(j,-,-,0)
F M:=M+I
F S1 S1.nextlist=0 112,(+,M,I,t1)
116,(:=,t1,-,M)
S S.nextlist=108 120,(+,I,’1’,I)
124,(j,-,-,104)
七, 控制语句也可采用改写文法的方法
S→if B then S 1
│if B then S1 else S2
│while B do S1
可将上述文法改写为,
C→if B then
T→C S 1 else
W→while
R→W B do
S→C S 1 | T S1 | R S1
C→if B then
{ backpatch(B.truelist,ip);
C.nextlist:=B.falselist }
T→C S 1 else
{ q:=ip;
emit(j,-,-,0);
backpatch(C.nextlist,ip);
T.nextlist:=merge(q,S1.nextlist) }
W→while
{ W.code:=ip }
R→W B do
{ backpatch(B.truelist,ip);
R.nextlist:=B.falselist;
R.code:=W.code }
S→C S 1
{ S.nextlist:=merge(C.nxtlisrt,S1.nextlist) }
S→T S 1
{ S.nextlist:=merge(T.nxtlisrt,S1.nextlist) }
S→R S 1
{ backpatch(S1.nextlist,R.code);
emit(j,-,-,R.code);
S.nextlist:=R.nextlist }
八, 数组元素按列存放时的处理
D=a+(in-ln)*dn-1*dn-2*…*d 1
+(in-1-ln-1)*dn-2*dn-3*…*d 1
+…+(i 2-l2)*d1+(i1-l1)
D=CONSPART+VARPART
CONSPART=a-C
C=ln*dn-1*dn-2*…*d 1 +ln-1*dn-2*dn-3*…*d 1
+…+l 2*d1+l1
VARPART =in*dn-1*dn-2*…*d 1 +in-1*dn-2*dn-3*…*d 1 +…+i 2*d1+i1
=(.,,((in*dn-1+in-1)*dn-2+ in-2 )*dn-3 +.,,+i2)*d1+i1
方法,
?VARPART的值不能按下标式的出现顺序
从左到右进行累计，它必须待所有下标
式都处理完毕之后，再从右到左进行计
算。
?设置一个栈 STACK，记录每个下标式结
果值的存放单元。待到所有下标式都处
理完毕之后，再自栈顶而下，按
VARPART的算式，累计它的值。
?为 Elist赋予一个语义属性 STACK
?不用改写文法
A→V:=E
V→i[Elist]│i
Elist→Elist 1,E | E
E→E 1 op E2│-E1│(E1)│V
九, 自上而下语法制导翻译概说
方法,
·每个非终结符对应一个递归过程 （ 函数 ）
·有关语义值作为函数值返回
·在产生式的中间可以调用语义子程序
1,控制语句的翻译
S?if B then S1
?if B then S1 else S2
?while B do S1
?A
PROCEDURE S;
BEGIN
CASE lookahead OF
′if′,BEGIN
match(′if′);
(B.truelist,B.falselist):=B;
backpatch(B.truelist,ip);
IF lookahead=′then′
THEN BEGIN match(′then′);
S1.nextlist:=S
END
ELSE ERROR;
IF lookahead=′else′
THEN BEGIN
match(′else′);
q:=ip;
emit(j,?,?,0);
backpatch(B.falselist,ip);
S1.nextlist:=merge(S1.nextlist,q);
S2.nextlist:=S;
q:=merge(S1.nextlist,S2.nextlist);
RETURN(q)
END
ELSE RETURN(merge(S1.nextlist,B.falselist))
END;
′while′,BEGIN
q:=ip;
(B.truelist,B.falselist):=B;
backpatch(B.truelist,ip);
IF lookahead=′do′
THEN BEGIN match(′do′);
S1.nextlist:=S;
backpatch(S1.nextlist,q);
emit(j,?,?,q);
RETURN(B.falselist)
END
ELSE ERROR;
END;
′i′,BEGIN
A;
RETURN(makelist( ))
END;
OTHERWISE,ERROR
END OF CASE
END OF S;
2,算术表达式的翻译
E?T{+T}
T?F{*F}
F?i?(E)
PROCEDURE F;
IF lookahead=′i′
THEN BEGIN match(′i′);
RETURN(lookup(i.name))
END
ELSE IF lookahead=′(′
THEN BEGIN match(′(′);
PLACE:=E;
IF lookahead=′)′
THEN BEGIN match(′)′);
RETURN(PLACE)
END
ELSE ERROR
END
ELSE ERROR;
PROCEDURE T;
BEGIN
T1.PLACE:=F;
WHILE lookahead=′*′ DO
BEGIN
match(′*′);
T2.PLACE:=F;
T1:=newtemp;
emit(*,T1.PLACE,T2.PLACE,T1);
T1.PLACE:=T1
END;
RETURN(T1.PLACE)
END OF T;
PROCEDURE E;
BEGIN
E1.PLACE:=T;
WHILE lookahead=′+′ DO
BEGIN
match(′+′);
E2.PLACE:=T;
T1:=newtemp;
emit(+,E1.PLACE,E2.PLACE,T1);
E1.PLACE:=T1
END;
RETURN(E1.PLACE)
END OF T;
第三节 代码优化
一, 优化的定义
优化是一种等价的，有效的程序变换
?等价 —— 不改变程序运行结果
?有效 —— 时空效率要高
二, 不同阶段的优化
1,源程序阶段的优化
2,编译优化 —— 中间代码优化和目标代码
优化
3,中间代码优化 —— 局部优化和全局优化
?局部优化：在基本块内的优化
?全局优化：超越基本块，在基本块之间的优
化
三, 划分基本块和构造程序流图
1,划分基本块
(1)找入口语句
?程序的第一条语句
?能由条件或无条件转向语句转移到的语
句
?紧跟在条件转向语句后的那个语句
(2)确定基本块
入口语句 入口语句 入口语句
…… …… ……
入口语句 转向语句 停语句
(3)删除未被划入基本块的语句
(1)i:=m-1
(2)j:=n
(3)t1:=4*n
(4)v:=a[t1]
(5)i:=i+1
(6)t2:=4*i
(7)t3:=a[t2]
(8)if t3<v goto (5)
(9)j:=j-1
(10)t4:=4*j
(11)t5:=a[t4]
(12)if t5>v goto (9)
(13)if i>=j goto (23)
(14)t6:=4*i
(15)x:=a[t6]
(16)t7:=4*i
(17)t8:=4*j
(18)t9:=a[t8]
(19)a[t7]:=t9
(20)t10:=4*j
(21)a[t10]:=x
(22)goto (5)
(23)t11:=4*i
(24)x:=a[t11]
(25)t12:=4*i
(26)t13:=4*n
(27)t14:=a[t13]
(28)a[t12]:=t14
(29)t15:=4*n
(30)a[t15]:=x
