第讲-语法制导翻译和中间代码生成.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,布尔表达式的计值方法,方法一：逐步计算,方法二：优化计算,例如：1（0 0）0,=1（1 0）0,=1 0 0,=1 0,=1,A B,A B,A,解释为：if A then TRUE else B,解释为：if A then B else FALSE,解释为：if A then FALSE else TRUE,作为逻辑计值的布尔表达式的翻译,例如：将 ABC=D 翻译成四元式的形式,（=，C，D，T1）,（，B，T1，T2）,（，A，T2，T3）,作为控制条件的布尔表达式的翻译,下面我们来观察“if-语句”和“while-语句”中布尔表达式的作用：,仅仅用于执行流程的控制,if E then S1 else S2 while E do S,E的四元式代码,S1的四元式代码,GOTO,L,E的四元式代码,S2的四元式代码,S的四元式代码,GOTO,L,TRUE,TRUE,FALSE,FALSE,返回,我们通过观察“if-语句”和“while-语句”中布尔表达式的作用可以知道：,E的四元式代码,TRUE,FALSE,E的真出口，用 E.TC 表示,E的假出口，用 E.FC 表示,（jnz ，A，p）,若A为真，则转到第p号四元式去执行,（jrop，A，B，p）,若A rop B为真，则转到第p号四元式去执行,（j ，p）,无条件转到第p号四元式去执行,为了翻译布尔表达式，我们引入下面三种四元式：,例如：将下面语句翻译成四元式的形式（编号从100开始）,if ABD then x:=y+z else x:=y-z,100 （jnz，A，104）,；A的“真出口”,101 （j ，102）,；A的“假出口”,102 （j ，B，D，104）,；BD的“真出口”,103 （j ，107）,；BD的“假出口”,104 （+，y，z，T1）,；S1语句,105 （,:=,，T1，x）,；S1语句,106 （j ，109）,；跳过S2的代码,107 （-，y，z，T2）,；S2语句,108 （,:=,，T2，x）,；S2语句,109 ,if ABD then x:=y+z else x:=y-z,100 （jnz，A，104）,；A的“真出口”,101 （j ，102）,；A的“假出口”,102 （j ，B，D，104）,；BD的“真出口”,103 （j ，107）,；B，C，D，0）,（6)Wd W E do,Chain=101;C.,104 （j，C，D，0）,Place:=A.,数组元素的引用 用“变址取数”四元式：,TC=104;）,q (，0),104 （+，y，z，T1）,引入以下属性和子程序：,执 行：Sub5；,=（i1d2+i2）d3+i3）d4+in-1）dn+in,(j ,0),Chain:=0;,(2)C B E3),例1：把 ABCD 翻译成四元式（从100号开始）,100 （jnz，A，0）,101 （j ，0）,句 型:,A,BCD,=,E,A,BCD,执 行：Sub1；NXQ=102,属 性：E,A,.TC=100;E,A,.FC=101;,102,查看语义子程序,E,A,.TC,E,A,.FC,NXQ,E i,E.TC=NXQ;E.FC=NXQ+1;,Gen(jnz,Lookup(i.name),0);Gen(j,0);,100 （jnz，A，0）,101 （j ，,102,）,句 型:,E,A,BCD,=,E,BCD,执 行：Sub7；NXQ=102,属 性：E,.TC=100;,（E,A,.TC=100;E,A,.FC=101;）,102,查看语义子程序,E,.TC,NXQ,(7)E,E,1,BackPatch(E,1,.FC,NXQ);E,.TC=E,1,.TC;,100 （jnz，A，0）,101 （j ，102）,句 型:,E,B,CD,=,E,E,B,CD,执 行：Sub1；NXQ=104,属 性：E,.TC=100;E,B,.TC =102;E,B,.FC=103;,（E,.TC=100;,）,查看语义子程序,E,.TC,NXQ,E i,E.TC=NXQ;E.FC=NXQ+1;,Gen(jnz,Lookup(i.name),0);Gen(j,0);,102 （jnz，B，0）,103 （j ，0）,104,E,B,.TC,E,B,.FC,100 （jnz，A，0）,101 （j ，102）,句 型:,E,E,B,CD,=,E,E,CD,执 行：Sub5；NXQ=104,属 性：E,.TC=100;E,.FC=103;,（E,.TC=100;E,B,.TC =102;E,B,.FC=103;,）,查看语义子程序,E,.TC,NXQ,102 （jnz，B，,104,）,103 （j ，0）,104,E,.FC,(5)E,E,1,BackPatch(E,1,.TC,NXQ);E,.FC=E,1,.FC;,100 （jnz，A，0）,101 （j ，102）,句 型:,E,E,CD,=,E,E,E,2,执 行：Sub2；NXQ=106,属 性：,E,.TC=100;E,.FC=103;E,2,.TC=104;E,2,.FC=105;,（E,.TC=100;,E,.FC=103;,）,查看语义子程序,E,.TC,NXQ,102 （jnz，B，104）,103 （j ，0）,E,.FC,104 （j，C，D，0）,105 （j ，0）,106,E,2,.TC,E,2,.FC,(2)E i,1,rop i,2,E.TC=NXQ;E.FC=NXQ+1;,Gen(jnz,Lookup(i,1,.name),Lookup(i,2,.name),0);,Gen(j,0);,100 （jnz，A，0）,101 （j ，102）,句 型:,E,E,E,2,=,E,E,2,执 行：Sub6；NXQ=106,属 性：,E,.TC=100;E,2,.FC=103;E,2,.TC=104;,（E,.TC=100;,E,.FC=103;,E,2,.TC=104;E,2,.FC=105;,）,查看语义子程序,E,.TC,NXQ,102 （jnz，B，104）,103 （j ，,105,）,E,2,.FC,104 （j，C，D，0）,105 （j ，0）,106,E,2,.TC,(6)E E,E,2,E.TC=E,2,.TC;E.FC=Merge(E,.FC,E,2,.FC),100 （jnz，A，,104,）,101 （j ，102）,句 型:,E,E,2,=,E,执 行：Sub8；NXQ=106,属 性：,E.TC=100;E.FC=103;,（E,.TC=100;,E,2,.FC=103;,E,2,.TC=104;）,查看语义子程序,E.TC,NXQ,102 （jnz，B，104）,103 （j ，105）,E.FC,104 （j，C，D，0）,105 （j ，0）,106,(8)E E,E,2,E.FC=E,2,.FC;E.TC=Merge(E,.TC,E,2,.TC),100 （jnz，A，104）,101 （j ，102）,E.TC,NXQ,102 （jnz，B，104）,103 （j ，105）,E.FC,104 （j，C，D，0）,105 （j ，0）,106,100 （jnz，A，,106,）,101 （j ，102）,102 （jnz，B，104）,103 （j ，,108,）,104 （j，C，D，,106,）,105 （j ，,108,）,106 （+，x，1，x）,107 （j ，109）,108 （+，y，1，y）,109 ,if ABCD then x:=x+1 else y:=y+1,ABCD,例2：翻译布尔表达式 A B CD ，并把其值保存到一个临时变量中（用四元式表示，从100号开始）,100 （jnz，A，102）,101 （j ，104）,E.TC,102 （jnz，B，,104,）,103 （j ，104）,E.FC,104 （j,，C，D，,0,）,105 （j ，,0,）,106,100 （jnz，A，102）,101 （j ，104）,102 （jnz，B，,106,）,103 （j ，104）,104 （j,，C，D，,106,）,105 （j ，,108,）,106 （:=，1，x）,107 （j ，109）,108 （:=，0，x）,109 ,表达式 A B CD 的四元式,X:=A B CD 的四元式,(9)SE,T:=Newtemp;BackPatch(E.TC,NXQ);,BackPatch(E.FC,NXQ+2);Gen(:=,1,T);L=NXQ+2;,Gen(j,L);,Gen(:=,0,T);S.Place:=T;,在前面文法的基础上增加如下一条四元式：,标号语句和GOTO语句到四元式的翻译,标号语句和GOTO语句的文法,(1)S,g,goto Label,(2)S Label S,(3)Label i:,符号表,名 字,定 义,种 属,类 型,地 址,L,0,LAB,r,goto L1,goto L2,goto L2,L1:S1,goto L1,L2:S2,名字,定义,种属,类型,地址,L1,1,LAB,k,源代码：,四元式：,k (,),goto L2,符号表,goto L1,goto L2,goto L2,L1:S1,goto L1,L2:S2,名字,定义,种属,类型,地址,L1,1,LAB,k,源代码：,四元式：,k (,),m (j ,k),n (j ,k),goto L2,符号表,goto L1,goto L2,goto L2,L1:S1,goto L1,L2:S2,名字,定义,种属,类型,地址,L1,1,LAB,k,L2,0,LAB,p,源代码：,四元式：,k (,),m (j ,k),n (j ,k),goto L2,p (j ,0,),符号表,goto L1,goto L2,goto L2,L1:S1,goto L1,L2:S2,名字,定义,种属,类型,地址,L1,1,LAB,k,L2,0,LAB,q,源代码：,四元式：,k (,),m (j ,k),n (j ,k),goto L2,p (j ,0,),符号表,q (j ,p,),goto L1,goto L2,goto L2,L1:S1,goto L1,L2:S2,名字,定义,种属,类型,地址,L1,1,LAB,k,L2,0,LAB,r,源代码：,四元式：,k (,),m (j ,k),n (j ,k),goto L2,p (j ,0,),符号表,q (j ,p,),r (j ,q,),goto L1,goto L2,goto L2,L1:S1,goto L1,L2:S2,名字,定义,种属,类型,地址,L1,1,LAB,k,L2,1,LAB,t,源代码：,四元式：,k (,),m (j ,k),n (j ,k),goto L2,p (j ,t),符号表,q (j ,t),r (j ,t),t (,),标 号 语 句 和 GOTO 语 句 的 语 义 子 程 序,(1)S,g,goto Label,Enter:=Lookup(Label.Name);,if Enter=Null then,Begin Enter.Name:=Label.Name;Enter.Cat :=LAB;,Enter.Def :=0;Enter.Addr:=NXQ;,Gen(j,0);End,else if Enter.Def=1 then Gen(j,Enter.Addr);,else Begin N:=NXQ;Gen(j,Enter.Addr);,Enter.Addr:=N;End ,(2),S Label S,(3)Label i:,Enter:=Lookup(i.Name);,if Enter=Null then,Begin Enter.Name:=i.Name;Enter.Cat :=LAB;,Enter.Def :=1;Enter.Addr:=NXQ;End,else if Enter.Def=1 then Error;,else Begin Enter.Def :=1;BackPatch(Enter.Addr,NXQ);,Enter.Addr:=NXQ;End ,条件语句、while语句和复合语句到四元式的翻译,条件语句、while语句和复合语句的语法,（1）S if E then Sif E then S else S,while E do Sbegin L endA,（2）L L;SS,说明：S 表示语句；E 表示布尔表达式；A 表示赋值语句；L 表示语句串。,引入二个新的符号属性,S.Chain:转出内层语句S的各四元式所形成的链的链头。,X.Quad:相应于X符号的四元式串的第一个四元式编号。,为了在翻译过程中能及时地进行“拉链”和“回填”处理，我们将其文法改写成如下形式：,（,1）S if E then S,if E then S else S,while E do S,begin L end,A,（2）L L;S,S,(1)C if E then,(2)S C S,1,(3)T,P,C S,1,else,(4)S T,P,S,2,(5)W while,(6)W,d,W E do,(7)S W,d,S,1,(8)S A,(9)L S,(10)L,S,L;,(11)L L,S,S,1,(12)S begin L end,改写前的四元式：,查看语句,翻译模式,语 义 子 程 序 如 下：,(1)C if E then,(2)S C S,1,(3)T,P,C S,1,else,(4)S T,P,S,2,(5)W while,(6)W,d,W E do,(7)S W,d,S,1,(8)S A,(9)L S,(10)L,S,L;,(11)L L,S,S,1,(12)S begin L end,BackPatch(E.TC,NXQ);C.Chain:=E.FC;,S.Chain:=Merge(C.Chain,S,1,.Chain);,q:=NXQ;Gen(j,0);BackPatch(C.Chain,NXQ);,T,P,.Chain:=Merge(S,1,.Chain,q);,S.Chain:=Merge(T,P,.Chain,S,2,.Chain);,W.Quad:=NXQ;,BackPatch(E.TC,NXQ);,W,d,.Chain:=E.FC;W,d,.Quad:=W.Quad;,BackPatch(S,1,.Chain,W,d,.Quad);,Gen(j,W,d,.Quad);S.Chain:=W,d,.Chain;,S.Chain:=0;,L.Chain:=S.Chain;,BackPatch(L.Chain,NXQ);,L.Chain:=S,1,.Chain;,S.Chain:=L.Chain;,返回,查看翻译,框架,例3：将下列语句翻译成四元式的形式（假设编号从100 开始）,while (A D)then x:=y+z;,查看语义子程序,句 型:,while,(A D)then x:=y+z;,=,W,(A D)then x:=y+z;,执 行：Sub5；NXQ=100,属 性：W.Quad=100;,W.Quad,NXQ,100,(5)W while,W.Quad:=NXQ;,查看语义子程序,句 型:,W,(A D)then x:=y+z;,=,W,E,do if (CD)then x:=y+z;,执 行：归约布尔表达式；NXQ=102,属 性：W.Quad=100;E.TC=100;E.FC=101,(W.Quad=100;),NXQ,100 （jD)then x:=y+z;,=,W,d,if (CD)then x:=y+z;,执 行：Sub6；NXQ=102,属 性：W,d,.Quad=100;W,d,.Chain=101,(W.Quad=100;E.TC=100;E.FC=101),W,d,.Quad,NXQ,100 （jD),then x:=y+z;,=,W,d,if,E,then x:=y+z;,执 行：归约布尔表达式；NXQ=104,属 性：,W,d,.Quad=100;W,d,.Chain=101;E.TC=102;E.FC=103,(W,d,.Quad=100;W,d,.Chain=101),W,d,.Quad,NXQ,100 （j，C，D，0）,103 （j ，0）,104,E.TC,E.FC,查看语义子程序,句 型:,W,d,if E then,x:=y+z;,=,W,d,C,x:=y+z;,执 行：Sub1；NXQ=104,属 性：,W,d,.Quad=100;W,d,.Chain=101;C.Chain=103,(W,d,.Quad=100;W,d,.Chain=101;E.TC=102;E.FC=103),W,d,.Quad,NXQ,100 （j，C，D，,104,）,103 （j ，0）,104,C.Chain,(1)C if E then,BackPatch(E.TC,NXQ);,C.Chain:=E.FC;,句 型:,W,d,C,x:=y+z,;,=,W,d,C,A,;,执 行：归约赋值语句；NXQ=106,属 性：,W,d,.Quad=100;W,d,.Chain=101;C.Chain=103,(W,d,.Quad=100;W,d,.Chain=101;C.Chain=103),W,d,.Quad,NXQ,100 （j，C，D，104）,103 （j ，0）,C.Chain,104 （+，y，z，T1）,105 （:=，T1，x）,106,查看语义子程序,句 型:,W,d,C,A,;,=,W,d,C,S,1,;,执 行：Sub8；NXQ=106,属 性：,W,d,.Quad=100;W,d,.Chain=101;C.Chain=103;,S,1,.Chain=0,(W,d,.Quad=100;W,d,.Chain:=101;C.Chain=103),W,d,.Quad,NXQ,100 （j，C，D，104）,103 （j ，0）,C.Chain,104 （+，y，z，T1）,105 （:=，T1，x）,106,(8)S A,S.Chain:=0;,S,1,.Chain=0,查看语义子程序,句 型:,W,d,C S,1,;,=,W,d,S,2,;,执 行：Sub2；NXQ=106,属 性：,W,d,.Quad=100;W,d,.Chain=101;S,2,.Chain=103;,(W,d,.Quad=100;W,d,.Chain:=101;C.Chain=103;S,1,.Chain=0 ),W,d,.Quad,NXQ,100 （j，C，D，104）,103 （j ，0）,S,2,.Chain,104 （+，y，z，T1）,105 （:=，T1，x）,106,(2)S C S,1,S.Chain:=Merge(C.Chain,S,1,.Chain);,查看语义子程序,句 型:,W,d,S,2,;,=,S,;,执 行：Sub7；NXQ=107,属 性：,S.Chain=101;,(W,d,.Quad=100;W,d,.Chain:=101;C.Chain=103),NXQ,100 （j，C，D，104）,103 （j ，,100,）,104 （+，y，z，T1）,105 （:=，T1，x）,(7)S W,d,S,1,BackPatch(S,1,.Chain,W,d,.Quad);,Gen(j,W,d,.Quad);,S.Chain:=W,d,.Chain;,106 （j，100）,107,查看语义子程序,句 型:,S,;,=,L,;,执 行：Sub9；NXQ=107,属 性：,L.Chain=101;,(S.Chain:=101 ),NXQ,100 （j，C，D，104）,103 （j ，100）,104 （+，y，z，T1）,105 （:=，T1，x）,(9)L S,106 （j，100）,107,L.Chain:=S.Chain;,查看语义子程序,句 型:,L;,=,L,S,执 行：Sub10；NXQ=107,属 性：,(L.Chain:=101 ),NXQ,100 （j，C，D，104）,103 （j ，100）,104 （+，y，z，T1）,105 （:=，T1，x）,(10)L,S,L;,106 （j，100）,107,BackPatch(L.Chain,NXQ);,while (A D)then x:=y+z;,100 （j，C，D，104）,103 （j ，100）,104 （+，y，z，T1）,105 （:=，T1，x）,106 （j，100）,107,上面语句翻译成四元式的形式为：,思考题：上面语句后面少分号，结果有是如何呢？,例4：将下列语句翻译成四元式的形式（假设编号从100 开始）,while (A B C)do,begin,k:=k+1;,if (mn)then x:=x+y;,else x:=x-y;,y:=y*2;,end,思考题目：给出详细的翻译步骤？,while (A B C)do,begin,k:=k+1;,if (mn)then x:=x+y;,else x:=x-y;,y:=y*2;,end,100 (jnz,A ,102),101 (j ,104),102 (jnz,B ,106),103 (j ,104),104 (jnz,C ,106),105 (j ,0,),106 (+,k ,1,T1),107 (:=,T1,k ),108 (j ,m,n,110),109 (j ,113),110 (+,x ,y,T2),111 (:=,T2,x ),112 (j ,115),113 (-,x ,y,T3 ),114 (:=,T3,x ),115 (*,y,2,T4),116 (:=,T4,y ),117 (j ,100),118,S.Chain =105,总 结,如何分割一个产生式,如何为一个产生式编写语义子程序,理解语句的执行流程。,自左向右扫描，理解语句的翻译框架。,对后面四元式的转移目标（四元式编号）设置属性保存。,拉（并）链的时机。,回填的时机。,设置文法符号的属性值以便保存：后面四元式的转移,目标；待回填的四元式编号；需要继承的属性。,如果需要并链，则用Merge函数。,如果需要回填，则用BackPatch过程。,如果需要产生四元式，则用Gen过程。,返回,For 循 环 语 句 到 四 元 式 的 翻 译,三种for循环语句的文法：,S for i:=E,1,step E,2,until E,3,do S,1,S for i:=E,1,until E,2,step E,3,do S,1,S for(E,1,;E,2,;E,3,)S,1,语句,for i:=E,1,step E,2,until E,3,do S,1,的翻译,执行流程如下：,语义解释如下：,i:=E,1,S,i:=i+E,2,i E,3,Y,N,i:=E,1,goto over,again:i:=i+E,2,over:if iE,3,then,begin,S,1,;,goto again,end,总结,i:=E,1,goto over,again:i:=i+E,2,over:if iE,3,then,begin,S,1,;,goto again,end,语 句,for i:=E,1,step E,2,until E,3,do S,1,的翻译框架,E,1,的四元式代码,i:=E,1,(j,over),i:=i+E,2,(j,i,E,3,L),(j,again),(j,0),E,2,的四元式代码,again,E,3,的四元式代码,over,S,1,的四元式代码,L,总结,E,1,的四元式代码,i:=E,1,(j,over),i:=i+E,2,E,2,的四元式代码,(j,i,E,3,L),E,3,的四元式代码,(j,again),(j,0),S,1,的四元式代码,over,again,L,总结,(4)A for i:=E,1,step,(3)B A E,2,until,(2)C B E,3,do,(1)S C S,1,S.Chain,产生式,S for i:=E,1,step E,2,until E,3,do S,1,的分割,返回,E,1,的四元式代码,i:=E,1,(j,0),i:=i+E,2,E,2,的四元式代码,(j,i,E,3,L),E,3,的四元式代码,(j,again),(j,0),S,1,的四元式代码,总结,返回,(4)A for i:=E,1,step,语句,for i:=E,1,step E,2,until E,3,do S,1,的语义子程序,A.Place:=LookUp(i.Name);,Gen(:=,E,1,.Place,A.Place);,A.Chain:=NXQ;,Gen(j,0);,A.Quad:=NXQ;,A.Chain,A.Quad,NXQ,总结,返回,语句,for i:=E,1,step E,2,until E,3,do S,1,的语义子程序,(3)B A E,2,until,B.Quad:=A.Quad;,B.Place:=A.Place;,Gen(+,A.Place,E,2,.Place,A.Place);,BackPatch(A.Chain,NXQ);,E,1,的四元式代码,i:=E,1,(j,over,),i:=i+E,2,E,2,的四元式代码,(j,i,E,3,L),E,3,的四元式代码,(j,again),(j,0),S,1,的四元式代码,B.Quad,A.Quad,A.Chain,NXQ,总结,返回,语句,for i:=E,1,step E,2,until E,3,do S,1,的语义子程序,(2)C B E,3,do,C.Quad:=B.Quad;,q:=NXQ;,Gen(j,B.Place,E,3,.Place,q+2);,C.Chain:=NXQ;,Gen(j,0);,E,1,的四元式代码,i:=E,1,(j,over),i:=i+E,2,E,2,的四元式代码,(j,i,E,3,L),E,3,的四元式代码,(j,again),(j,0),S,1,的四元式代码,C.Quad,B.Quad,C.Chain,NXQ,总结,返回,语句,for i:=E,1,step E,2,until E,3,do S,1,的语义子程序,(1)S C S,1,Gen(j,C.Quad);,S.Chain:=C.Chain;,BackPatch(S1.Chain,C.Quad);,E,1,的四元式代码,i:=E,1,(j,over),i:=i+E,2,E,2,的四元式代码,(j,i,E,3,L),E,3,的四元式代码,(j,again),(j,0),S,1,的四元式代码,S.Chain,C.Chain,NXQ,C.Quad,(4)A for i:=E,1,step,(3)B A E,2,until,(2)C B E,3,do,(1)S C S,1,语句,for i:=E,1,step E,2,until E,3,do S,1,的语义子程序,A.Place:=LookUp(i.Name);,Gen(:=,E,1,.Place,A.Place);,A.Chain:=NXQ;Gen(j,0);,A.Quad:=NXQ;,B.Quad:=A.Quad;B.Place:=A.Place;,Gen(+,A.Place,E,2,.Place,A.Place);,BackPatch(A.Chain,NXQ);,C.Quad:=B.Quad;q:=NXQ;,Gen(j,B.Place,E,3,.Place,q+2);,C.Chain:=NXQ;Gen(j,0);,Gen(j,C.Quad);S.Chain:=C.Chain;,BackPatch(S1.Chain,C.Quad);,返回,例：将下列语句翻译成四元式的形式（编号从开始）,for I:=a+2*b step c+d until n+m do x:=y+z,查看语义子程序,句 型:,for I:=,a+2*b,step c+d until n+m do x:=y+z,=,for I:=,E,1,step c+d until n+m do x:=y+z,执 行：归约算术表达式；NXQ=102,属 性：,NXQ,100 （*，b，T1）,101 （+，a，T1，T2）,102,Enter:=Lookup(Label.,101 （j ，0）,name),Lookup(i2.,可按如下公式计算：,Quad;B.,(3)Label i:,Quad=104 ),Begin,Quad;q:=NXQ;,Quad1:=NXQ;,name),0);Gen(j,0);,while k,A,step c+d until n+m do x:=y+z,执 行：Sub4；NXQ=104,属 性：A.PlaceI;A.Chain=103;A.Quad=104,NXQ,100 （*，b，T1）,101 （+，a，T1，T2）,102（:=，T2，i）,(4)A for i:=E,1,Gen(:=,E,1,.Place,A.Place);A.Chain:=NXQ;Gen(j,0);A.Quad:=NXQ;,A.Place:=LookUp(i.Name);,103（j，0）,104,A.Chain,A.Quad,查看语义子程序,查看语义子程序,句 型:,A step,c+d,until n+m do x:=y+z,=,A step,E,2,until n+m do x:=y+z,执 行：归约算术表达式；NXQ=105,属 性：,(A.PlaceI;A.Chain=103;A.Quad=104),NXQ,100 （*，b，T1）,101 （+，a，T1，T2）,102（:=，T2，i）,103（j，0）,104 (+，c，d，T3),A.Chain,A.Quad,105,句 型:,A step E,2,until n+m do x:=y+z,=,B,until n+m do x:=y+z,执 行：Sub3；NXQ=105,属 性：B.Quad=104;B.Place I;,(A.PlaceI;A.Chain=103;A.Quad=104 ),NXQ,100 （*，b，T1）,101 （+，a，T1，T2）,102（:=，T2，I）,103（j，,106,）,104 (+，c，d，T3),B.Quad,105 (+，I，T3，I),(3)B A step E,2,B.Place:=A.Place;Gen(+,A.Place,E,2,.Place,A.Place);,BackPatch(A.Chain,NXQ);,B.Quad:=A.Quad;,106,查看语义子程序,查看语义子程序,句 型:,B until,n+m,do x:=y+z,=,B until,E,3,do x:=y+z,执 行：归约算术表达式；NXQ=107,属 性：,(B.PlaceI;B.Quad=104 ),NXQ,100（*，b，T1）,101（+，a，T1，T2）,102（:=，T2，I）,103（j，106）,104 (+，c，d，T3),B.Quad,105 (+，I，T3，I),106 (+，n，m，T4),107,查看语义子程序,句 型:,B until E,3,do x:=y+z,=,C,do x:=y+z,执 行：Sub2；,NXQ=109,属 性：,NXQ,100（*，b，T1）,101（+，a，T1，T2）,102（:=，T2，I）,103（j，106）,104 (+，c，d，T3),C.Quad,105 (+，I，T3，I),106 (+，n，m，T4),107 (j，I，T4，109),(2)C B until E,3,Gen(j,B.Place,E,3,.Place,q+2);,C.Chain:=NXQ;Gen(j,0);,C.Quad:=B.Quad;q:=NXQ;,(B.PlaceI;B.Quad=104 ),108 (j，0),109,C.Chain,C.Quad=104;C.Chain=108,查看语义子程序,句 型:,C do,x:=y+z,=,C do,S,1,执 行：归约赋值语句,NXQ=111,属 性：,NXQ,100（*，b，T1）,101（+，a，T1，T2）,102（:=，T2，I）,103（j，106）,104 (+，c，d，T3),C.Quad,105 (+，I，T3，I),106 (+，n，m，T4),107 (j，I，T4，109),(C.Quad=104;,C.Chain=108 ),108 (j，0),109 (+，y，z，T5),C.Chain,110 (:=，T5，x),111,句 型:,C do S,1,=,S,执 行：Sub1,NXQ=111,属 性：S.Chain=108,NXQ,100（*，b，T1）,101（+，a，T1，T2）,102（:=，T2，I）,103（j，106）,104 (+，c，d，T3),105 (+，I，T3，I),106 (+，n，m，T4),107 (j，I，T4，109),108 (j，0),109 (+，y，z，T5),S.Chain,110 (:=，T5，x),111 (j，104),(1)S C do S,1,Gen(j,C.Quad);,S.Chain:=C.Chain;BackPatch(S1.Chain,C.Quad);,112,查看语义,子程序,语句,for (E,1,；E,2,；E,3,)S,的翻译,执行流程如下：,语义解释如下：,E,1,S,E,3,E,2,0,Y,N,E,1,L1:if E,2,0 then goto L3,else goto L4,L2:E,3,goto L1,L3:S,goto L2,L4:,总结,语 句,for (E,1,；E,2,；E,3,)S,的 翻 译 框 架,E,1,的四元式代码,(j,L1),(jnz,E,2,L3),E,3,的四元式代码,(j ,L2),(j ,0),S,1,的四元式代码,L1,总结,E,1,L1:if E,2,0 then goto L3,else goto L4,L2:E,3,goto L1,L3:S,goto L2,L4:,E,2,的四元式代码,L2,L3,L4,产生式,S for (E,1,；E,2,；E,3,)S,1,的分割,E,1,的四元式代码,(j,L1),(jnz,E,2,L3),E,3,的四元式代码,(j ,L2),(j ,0),S,1,的四元式代码,L1,总结,E,2,的四元式代码,返回,L2,L3,(4)A for (E,1,;,(3)B A E,2,;,(2)C B E,3,),(1)S C S,1,S.Chain,E,1,的四元式代码,(j,L1),(jnz,E,2,L3),E,3,的四元式代码,(j ,L2),(j ,0),S,1,的四元式代码,A.Quad,总结,E,2,的四元式代码,返回,A.Quad:=NXQ;,(4)A for (E,1,;,语 句,for (E,1,；E,2,；E,3,)S,1,的 语 义 子 程 序,NXQ,E,1,的四元式代码,(j,L1),(jnz,E,2,L3),E,3,的四元式代码,(j ,L