最新【考研计算机专业课】天津大学 编译原理讲义 控制语句的翻译5.4(共24张PPT课件).pptx

《最新【考研计算机专业课】天津大学 编译原理讲义 控制语句的翻译5.4(共24张PPT课件).pptx》由会员分享，可在线阅读，更多相关《最新【考研计算机专业课】天津大学 编译原理讲义 控制语句的翻译5.4(共24张PPT课件).pptx（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、5.4.2 IF句与句与WHILE语句的翻译语句的翻译 (1) S if E then S(1) (2) | |if E then S(1) else S(2)(3) | |while E do S(1)(4) | |begin L end(5) | |A(6) L L(1); S(7) | |S 5.4控制语句控制语句(yj)的翻译的翻译第一页，共二十四页。考虑考虑(kol)(kol)语句语句: : if E then S1 else S2 (1) 非终结符非终结符E具有两项语义值具有两项语义值E.TC和和 E.FC，它们分别指出了尚需回，它们分别指出了尚需回填真、假出口的四元式串。填真、假

2、出口的四元式串。 E的的真真出口要扫描到出口要扫描到then才能才能(cinng)(cinng)知道，而知道，而假假出口要扫描出口要扫描到到else才能明确。为了能及时回填这些出口信息，须改写文法。才能明确。为了能及时回填这些出口信息，须改写文法。 S C S | |TP S C if E then TP C S else S if E then S(1) | |if E then S(1) else S(2)第二页，共二十四页。if E then S1 else S2(2) C if E then，当产生式进行规约时，当产生式进行规约时，E的的真真出口可以回填，出口可以回填，而而假假出口需要

3、继续等待，因此出口需要继续等待，因此(ync)要被传递下去。需要文法符号要被传递下去。需要文法符号C记录此信息。记录此信息。 对文法符号对文法符号C定义语义值定义语义值C.CHAIN，指向一条翻译完，指向一条翻译完C后需后需要进行转移目标回填要进行转移目标回填(hutin)的四元式链。的四元式链。 C.CHAIN = E.FC 可以对其它可以对其它(qt)文法符号文法符号 S、TP 同样定义语义值同样定义语义值S.CHAIN、TP.CHAIN。第三页，共二十四页。考虑考虑(kol)(kol)语句语句: : while E do S E 的代码的代码 S 的代码的代码真真出出口口假假出出口口第四

4、页，共二十四页。while E do S(1) S 代码执行之后应产生一条转向测试代码执行之后应产生一条转向测试 E 的无条件转移指令，因的无条件转移指令，因此在看到此在看到 while 时必须记住时必须记住(j zh) E 开始四元式的位置。开始四元式的位置。S Wd SWd W E doW whileS while E do S(1) E 的的真真出口要扫描到出口要扫描到 do 时才能知道。为了能及时时才能知道。为了能及时(jsh)(jsh)回回填这些信息，须改写文法。填这些信息，须改写文法。第五页，共二十四页。while E do S(2) W while 当产生式进行规约时，需要记录四

5、元当产生式进行规约时，需要记录四元(s yun)式位式位置置。引入语义值。引入语义值W.QUAD，记录，记录 while 语句所对应的第一个四语句所对应的第一个四元式的地址。元式的地址。 Wd W E do 当产生式进行规约时，当产生式进行规约时，E假假出口需要出口需要(xyo)继续继续等待，因此要被传递下去。也需要等待，因此要被传递下去。也需要(xyo)文法符号文法符号C的语义值的语义值C.CHAIN记录此信息。记录此信息。第六页，共二十四页。最终最终(zu zhn)(zu zhn)文法改写为文法改写为: : （1） S C S（2） | |TP S（3） | |Wd S（4） | |beg

6、in L end（5） | |A（6） L LS S （7） | |S（8） C if E then（9） TP C S else（10）Wd W E do（11）W while（12）LS L； 第七页，共二十四页。文法的各个产生文法的各个产生(chnshng)(chnshng)式相应的语义动作式相应的语义动作 :(1) S C S(1) S.CHAIN = MERG( C.CHAIN , S(1).CHAIN ) (2) S TP S(2) S.CHAIN = MERG( TP.CHAIN , S(2).CHAIN ) (8) C if E then BACKPATCH ( E.TC ,

7、NXQ ) ; C.CHAIN = E.FC (9) TP C S(1) else q = NXQ；GEN ( j , 0 ) ; BACKPATCH ( C.CHAIN , NXQ ) ; TP.CHAIN = MERG ( S(1).CHAIN , q ) 第八页，共二十四页。(10) Wd W E do BACKPATCH ( E.TC , NXQ ) ; Wd.CHAIN =E.FC ; Wd.QUAD = W.QUAD (11) W while W.QUAD = NXQ (3) S Wd S(1) BACKPATCH ( S(1).CHAIN , Wd.QUAD ); GEN ( j

8、 , , Wd.QUAD ); S.CHAIN =Wd.CHAIN 第九页，共二十四页。(4) S begin L end S.CHAIN = L.CHAIN (5) S A S.CHAIN = 0 /* 空链空链 */ (6) L LS S(1) L.CHAIN = S(1).CHAIN (7) L S L.CHAIN = S.CHAIN (12) LS L； BACKPATCH ( L.CHAIN , NXQ ) 第十页，共二十四页。例例，有语句有语句: : while ( A B ) do if ( C D ) then x := y+z ；读入读入while，规约，规约(guyu)为为

9、W， W.QUAD = 100，NXQ = 100 读入读入( A B )，规约，规约(guyu)为为E， 100 ( j , A , B , 0 )，真真，NXQ = 101 101 ( j , , , 0 )，假假，NXQ = 102 读入读入do， 规约规约(guyu)为为Wd， 对对E.TC回填，回填，100 ( j , A , B ,102 ) Wd.CHAIN = E.FC = 101 Wd.QUAD = W.QUAD = 100 第十一页，共二十四页。读入读入then，规约，规约(guyu)为为C， 对对E.TC回填，回填，102 ( j , C , D , 104) C.CHA

10、IN = E.FC = 103 读入读入( C D )，规约，规约(guyu)为为E， 102 ( j , C , D , 0 )，NXQ = 103 103 ( j , , , 0 )，NXQ = 104 读入读入 if ，读入读入 x := y+z，规约，规约(guyu)为为A， 104 ( + , y , z , T1 )，NXQ = 105 105 ( := , T1 , x )，NXQ = 106 第十二页，共二十四页。WDS(1)规约为规约为S， 用用WD.QUAD回填回填(hutin)S(1).CHAIN， 103 ( j , 100 ) 生成生成106 ( j , 100 )

11、，NXQ = 107 S.CHAIN = WD.CHAIN = 101 A规约规约(guyu)为为S， S.CHAIN = 0 CS(1)规约规约(guyu)为为S， S.CHAIN = MERG( C.CHAIN , S(1).CHAIN ) = 103 S归约为归约为L， L.CHAIN = S.CAHIN = 101 读入读入；，规约为，规约为LS， 回填回填L.CHAIN，101 ( j , 107 ) 第十三页，共二十四页。翻译翻译(fny)(fny)结果为结果为: :100 ( j , A , B , 102 )101 ( j , , , 107 )102 ( j , C , D

12、, 104 )103 ( j , , , 100 )104 ( + , y , z , T )105 ( := , T , , x )106 ( j , , , 100 )107 第十四页，共二十四页。5.4.3 FOR语句语句(yj)(yj)的翻译的翻译 文法文法: S for i := E(1) step E(2) until E(3) do S(1) 按按ALGOL语言语言(yyn)(yyn)的语义可理解为的语义可理解为:i = E(1)；goto OVER；AGAIN:i = i + E(2)；OVER: if (iE(3) ) S(1)；goto AGAIN 第十五页，共二十四页。i

13、 = E(1)的代码的代码i = i + E(2)的代码的代码i E(3)的代码的代码S(1)的代码的代码AGAIN:OVER:(i E(3).TC(i E(3).FC(1) 改写改写(gixi)文法文法:第十六页，共二十四页。S for i := E(1) step E(2) until E(3) do S(1) F1 for i := E(1)F2 F1 step E(2)F3 F2 until E(3)S F3 do S(1) 第十七页，共二十四页。(2) 引入语义值方便记录各种引入语义值方便记录各种( zhn)信息信息i = E(1)的代码的代码(di m)i = i + E(2)的代

14、码的代码(di m)i E(3)的代码的代码S(1)的代码的代码AGAIN:OVER:(i E(3).TC(i E(3).FCF1.CHAINF1.QUADF2.QUADF3.QUADF3.CHAINS(1).CHAINS.CHAINF1.PLACEF2.PLACE第十八页，共二十四页。(1) F1 for i := E(1) GEN ( := , E(1).PLACE, , ENTRY(i) ); F1.PLACE = ENTRY(i); /*保留控制变量在符号表中的位置保留控制变量在符号表中的位置(wi zhi)*/ F1.CHAIN = NXQ; GEN( j, 0 ); /* goto

15、 OVER */ F1.QUAD = NXQ; /* 保留保留 AGAIN 的地址的地址 */ (2) F2 F1 step E(2) F2.QUAD =F1.QUAD; /* 保留保留(boli) AGAIN 的地址的地址 */ F2.PLACE = F1.PLACE; /*保留控制变量在符号表中的位置保留控制变量在符号表中的位置*/ GEN ( + , F1.PLACE，E(2).PLACE, F1.PLACE); BACKPATCH( F1.CHAIN, NXQ); /* 完成上面的完成上面的goto OVER */ 第十九页，共二十四页。(3) F3 F2 until E(3) F3.

16、QUAD = F2.QUAD; q = NXQ; GEN ( j, F2.PLACE，E(3).PLACE, q+2); /* 若若 iE(3) 转去执行循环体的第一个四元转去执行循环体的第一个四元(s yun)式式 */ F3.CHAIN =NXQ; GEN( j, 0 ); /* 转离循环转离循环 */ (4) S F3 do S GEN( j, F3.QUAD ); /* goto AGAIN */ BACKPATCH( S(1).CHAIN, F3.QUAD); S.CHAIN =F3.CHAIN; /* 转离循环的转移目标留待处理转离循环的转移目标留待处理(chl)(chl)外层外层

17、S时再回填时再回填 */ 第二十页，共二十四页。例例，for i:= 1 step 1 until n do M := M+i 读入读入step 1，归约为，归约为F2， F2.QUAD = F1.QUAD = 102 F2.PLACE = F1.PLACE = i 102 ( +, i , “1”, i ) NXQ = 103 回填回填(hutin)F1.CHAIN， ( 101 ( j , 103 ) );读入读入for i:= 1， 归约为归约为F1， 100 (:=,“1”, i ) NXQ = 101 101 ( j , , , 0 ) NXQ = 102 F1.PLACE = i

18、F1.QUAD = 102 F1.CHAIN = 101第二十一页，共二十四页。读入读入 until n，归约为，归约为F3， F3.QUAD = F2.QUAD = 102 103 ( j, I, N, 105 ) NXQ = 104 104 ( j , , , 0 ) NXQ = 105 F3.CHAIN =104 读入读入M:=M+i，规约为，规约为S，形成，形成(xngchng)M:=M+i的代码的代码 105 ( + , M , i , T1 ) NXQ = 106 106 ( :=, T1 , , M ) NXQ = 107读入读入 dodo S(1)归约为归约为S， 107 (

19、j , , , 102) NXQ = 108 回填回填(hutin)S(1).CHAIN，此时，此时S(1).CHAIN=0，不需要，不需要 S.CHAIN = F3.CHAIN = 104 第二十二页，共二十四页。翻译翻译(fny)(fny)结果结果:100 (:= ,“1”, i )101 ( j ,103)102 ( + , i, “1”, i ) 103 ( j, i, n,105)104 ( j , , , )105 ( +, M , i , T )106 (:=, T , , M )107 ( j , , 102)S.CHAIN = 104需要等到整个语句翻译需要等到整个语句翻译(fny)完后回填。完后回填。第二十三页，共二十四页。内容(nirng)总结5.4.2 IF句与WHILE语句的翻译。Wd.CHAIN =E.FC。/*保留控制变量在符号表中的位置*/。S.CHAIN =F3.CHAIN。do S(1)归约为S，。回填S(1).CHAIN，此时S(1).CHAIN=0，不需要(xyo)。翻译结果:第二十四页，共二十四页。