第7讲 语法制导翻译及中间代码生成(2)

1、布尔表达式到四元式的翻译 布尔表达式的作用布尔表达式的作用 布尔表达式的文法布尔表达式的文法 作为控制语句的条件表达式作为控制语句的条件表达式 用于逻辑计值用于逻辑计值EEE EE E (E) i rop i i注：注： rop 为关系运算符：为关系运算符：= =， ，=，=， 为为“与与”运算；运算；为为“或或”运算；运算； 为为“非非”运算运算 结合性为左结合性结合性为左结合性 优先级别为：优先级别为： rop ， ， 布尔表达式的计值方法布尔表达式的计值方法 方法一：方法一： 逐步计算逐步计算 方法二：方法二： 优化计算优化计算例如：例如：1 （ 0 0） 0= 1 （ 1 0） 0=

2、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-语句语句”中

3、布尔表达式的作用：中布尔表达式的作用：仅仅用于执行流程的控制仅仅用于执行流程的控制 if E then S1 else S2 while E do SE的四元式代码的四元式代码S1的四元式代码的四元式代码GOTO L E的四元式代码的四元式代码S2的四元式代码的四元式代码S的四元式代码的四元式代码 GOTO L T TR RU UE ET TR RU UE EF FA AL LS SE EF FA AL LS SE E返回 我们通过观察我们通过观察 “if-语句语句” 和和 “while-语句语句”中布尔表达式的作用可以知道：中布尔表达式的作用可以知道：E的四元式代码的四元式代码T TR RU

4、 UE EF FA AL LS SE EE的真出口，用的真出口，用 E.TC 表示表示E的假出口，用的假出口，用 E.FC 表示表示 （ jnz ，A， ， p） 若若A为真，则转到第为真，则转到第p号四元式去执行号四元式去执行（ jrop，A，B， p） 若若A rop B为真，则转到第为真，则转到第p号四元式去执行号四元式去执行（ j ， ， ， p） 无条件转到第无条件转到第p号四元式去执行号四元式去执行为了翻译布尔表达式，我们引入下面三种四元式：为了翻译布尔表达式，我们引入下面三种四元式：例如：将下面语句翻译成四元式的形式（编号从例如：将下面语句翻译成四元式的形式（编号从100开始）开

5、始） if ABD then x:=y+z else x := y-z100 （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

6、if ABD then x:=y+z else x := y-z100 （jnz，A， ，104） ； A的的“真出口真出口”101 （j ， ， ，102） ； A的的“假出口假出口”102 （j ，B ，D，104） ； BD的的“真出口真出口”103 （j ， ， ，107） ； BD 翻译成四元式（从翻译成四元式（从100号开始）号开始）100 （jnz，A，0）101 （j ， ， ，0）句句 型型: ABCD = EABCD 执执 行：行： Sub1； NXQ=102 属属 性：性： EA.TC = 100; EA.FC = 101; 102 查看语义子程序EA.TC EA.FC

7、NXQ E i E.TC = NXQ; E.FC = NXQ + 1; Gen(jnz, Lookup(), , 0); Gen(j, , ,0); 100 （jnz，A，0）101 （j ， ， ，102） 句句 型型: EABCD = EBCD 执执 行：行： Sub7； NXQ=102 属属 性：性： E.TC = 100; （EA.TC = 100; EA.FC = 101; ）102 查看语义子程序E.TC NXQ (7) E E1 BackPatch( E1.FC, NXQ ) ; E.TC = E1.TC ; 100 （jnz，A，0）101 （j ， ， ，102）

8、 句句 型型: EBCD = EEBCD 执执 行：行： Sub1； NXQ=104 属属 性：性： E.TC = 100; EB.TC = 102; EB.FC = 103; （ E.TC = 100; ）查看语义子程序E.TC NXQ E i E.TC = NXQ; E.FC = NXQ + 1; Gen(jnz, Lookup(), , 0); Gen(j, , ,0); 102 （jnz，B， ，0）103 （j ， ， ， 0）104 EB.TC EB.FC 100 （jnz，A，0）101 （j ， ， ，102） 句句 型型: EEBCD = EECD 执执 行：行：

9、 Sub5； NXQ=104 属属 性：性： E.TC = 100; E.FC = 103; （ E.TC = 100; EB.TC = 102; EB.FC = 103; ）查看语义子程序E.TC NXQ 102 （jnz，B， ，104）103 （j ， ， ， 0）104 E.FC (5) E E1 BackPatch( E1.TC, NXQ ) ; E .FC = E1.FC ; 100 （jnz，A，0）101 （j ， ， ，102） 句句 型型: EECD = EE E2 执执 行：行： Sub2； NXQ=106 属属 性：性： E.TC = 100; E.FC = 103;

10、E2.TC = 104; E2.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）106E2.TCE2.FC(2) E i1 rop i2 E.TC = NXQ; E.FC = NXQ + 1; Gen( jnz, Lookup(), Lookup() , 0 ) ; Gen( j, , ,0 ); 100 （jnz，A，0）101 （j ， ， ，102） 句句 型型: EE E2

11、 = E E2 执执 行：行： Sub6； NXQ=106 属属 性：性： E.TC = 100; E2.FC = 103; E2.TC = 104; （ E.TC = 100; E.FC = 103; E2.TC = 104; E2.FC = 105; ）查看语义子程序E.TC NXQ 102 （jnz，B， ，104）103 （j ， ， ， 105）E2.FC 104 （j，C，D，0）105 （j ， ， ， 0）106E2.TC(6) E EE2 E .TC = E2.TC ; E.FC = Merge( E.FC, E2.FC ) 100 （jnz，A，104）101 （j ， ，

12、 ，102） 句句 型型: E E2 = E 执执 行：行： Sub8； NXQ=106 属属 性：性： E.TC = 100; E.FC = 103; （ E.TC = 100; E2.FC = 103; E2.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 E2 E .FC = E2.FC ; E.TC = Merge( E.TC, E2.TC ) 100 （jnz，A，104）101 （j ， ， ，102）E.TC NXQ 1

13、02 （jnz，B， ，104）103 （j ， ， ， 105）E.FC 104 （j，C，D，0）105 （j ， ， ， 0）106100 （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+1ABCD例例2：翻译布尔表达式：翻译布尔表达式 A B CD ，并把其值保存到一个临时变量中，并把其值保存

14、到一个临时变量中（用四元式表示，从（用四元式表示，从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）106100 （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

15、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) Sg goto Label(2) S Label S(3) Labe

16、l i: 符号表符号表名名 字字 定定 义义 种种 属属 类类 型型 地地 址址 L 0 LAB r goto L1goto L2goto L2L1 : S1goto L1L2 : S2名字名字定义定义种属种属类型类型 地址地址 L1 1LAB k源代码：四元式：k (,)goto L2符号表goto L1goto L2goto L2L1 : S1goto L1L2 : S2名字名字定义定义种属种属类型类型 地址地址 L1 1LAB k源代码：四元式：k (,)m (j , , , k )n (j , , , k )goto L2符号表goto L1goto L2goto L2L1 : S1g

17、oto L1L2 : S2名字名字定义定义种属种属类型类型 地址地址 L1 1LAB k L2 0LAB p 源代码：四元式：k (,)m (j , , , k )n (j , , , k )goto L2p (j , , , 0 )符号表goto L1goto L2goto L2L1 : S1goto L1L2 : S2名字名字定义定义种属种属类型类型 地址地址 L1 1LAB k L2 0LAB q 源代码：四元式：k (,)m (j , , , k )n (j , , , k )goto L2p (j , , , 0 )符号表q (j , , , p )goto L1goto L2got

18、o L2L1 : S1goto L1L2 : S2名字名字定义定义种属种属类型类型 地址地址 L1 1LAB k L2 0LAB r 源代码：四元式：k (,)m (j , , , k )n (j , , , k )goto L2p (j , , , 0 )符号表q (j , , , p )r (j , , , q )goto L1goto L2goto L2L1 : S1goto L1L2 : S2名字名字定义定义种属种属类型类型 地址地址 L1 1LAB k L2 1LAB t 源代码：四元式：k (,)m (j , , , k )n (j , , , k )goto L2p (j , ,

19、 , t )符号表q (j , , , t )r (j , , , t )t (,)标标 号号 语语 句句 和和 GOTO 语语 句句 的的 语语 义义 子子 程程 序序(1) Sg 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 , , , E

20、nter.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; Ba

21、ckPatch (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的各四元式所形成的链的

22、链头。的各四元式所形成的链的链头。 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 S1(3) TP C S1 else(4) S TP S2(5) W while(6) Wd W E do(7) S

23、 Wd S1(8) S A(9) L S(10) LS L ; (11) L LS S1(12) S begin L end改写前的四元式：改写前的四元式：查看语句翻译模式 语语 义义 子子 程程 序序 如如 下：下：(1) C if E then(2) S C S1(3) TP C S1 else(4) S TP S2(5) W while(6) Wd W E do(7) S Wd S1(8) S A(9) L S(10) LS L ; (11) L LS S1(12) S begin L end BackPatch(E.TC, NXQ); C.Chain := E.FC; S.Chain

24、:= Merge ( C.Chain, S1.Chain ); q := NXQ; Gen( j, , , 0); BackPatch(C.Chain, NXQ); TP.Chain := Merge ( S1.Chain, q ); S.Chain := Merge ( TP.Chain, S2.Chain ); W.Quad := NXQ; BackPatch ( E.TC, NXQ ); Wd.Chain := E.FC; Wd.Quad := W.Quad ; BackPatch ( S1.Chain, Wd.Quad ); Gen ( j, , ,Wd.Quad ); S.Chain

25、 := Wd.Chain; S.Chain := 0; L.Chain := S.Chain ; BackPatch(L.Chain , NXQ); L.Chain := S1.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=

26、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; = Wd if (CD) then x := y + z; 执执

27、行：行： Sub6； NXQ=102 属属 性：性： Wd.Quad = 100; Wd. Chain = 101 ( W.Quad = 100; E.TC = 100; E.FC = 101)Wd.Quad NXQ 100 （jD) then x := y + z; = Wd if E then x := y + z; 执执 行：行： 归约布尔表达式；归约布尔表达式； NXQ=104 属属 性：性： Wd.Quad = 100; Wd. Chain = 101; E.TC=102; E.FC=103 (Wd.Quad = 100; Wd. Chain = 101)Wd.Quad NXQ 10

28、0 （j，C，D ，0）103 （j ， ， ， 0）104E.TCE.FC查看语义子程序 句句 型型: Wd if E then x := y + z; = Wd C x := y + z; 执执 行：行： Sub1； NXQ=104 属属 性：性： Wd.Quad = 100; Wd. Chain = 101; C.Chain =103 (Wd.Quad = 100; Wd. Chain = 101 ; E.TC=102; E.FC=103)Wd.Quad NXQ 100 （j，C，D ，104）103 （j ， ， ， 0）104C.Chain(1) C if E then BackPa

29、tch(E.TC, NXQ); C.Chain := E.FC; 句句 型型: Wd C x := y + z; = Wd C A; 执执 行：归约赋值语句；行：归约赋值语句； NXQ=106 属属 性：性： Wd.Quad = 100; Wd. Chain = 101; C.Chain=103 (Wd.Quad = 100; Wd. Chain = 101 ; C.Chain = 103)Wd.Quad NXQ 100 （j，C，D ，104）103 （j ， ， ， 0）C.Chain104 （+ ，y，z， T1）105 （:=，T1 ， ，x）106查看语义子程序 句句 型型: Wd

30、C A; = Wd C S1; 执执 行：行： Sub8； NXQ=106 属属 性：性： Wd.Quad = 100; Wd. Chain = 101; C.Chain=103; S1.Chain = 0 (Wd.Quad = 100; Wd. Chain := 101 ; C.Chain=103)Wd.Quad NXQ 100 （j，C，D ，104）103 （j ， ， ， 0）C.Chain104 （+ ，y，z， T1）105 （:=，T1 ， ，x）106(8) S A S.Chain := 0; S1.Chain = 0查看语义子程序 句句 型型: Wd C S1; = Wd S

31、2; 执执 行：行： Sub2； NXQ=106 属属 性：性： Wd.Quad = 100; Wd. Chain = 101; S2.Chain=103; (Wd.Quad = 100; Wd. Chain := 101 ; C.Chain=103; S1.Chain = 0 )Wd.Quad NXQ 100 （j，C，D ，104）103 （j ， ， ， 0）S2.Chain104 （+ ，y，z， T1）105 （:=，T1 ， ，x）106(2) S C S1 S.Chain := Merge ( C.Chain, S1.Chain ); 查看语义子程序 句句 型型: Wd S2;

32、= S; 执执 行：行： Sub7； NXQ=107 属属 性：性： S.Chain = 101; (Wd.Quad = 100; Wd. Chain := 101 ; C.Chain=103)NXQ 100 （j，C，D ，104）103 （j ， ， ， 100）104 （+ ，y，z， T1）105 （:=，T1 ， ，x）(7) S Wd S1 BackPatch ( S1.Chain, Wd.Quad ); Gen ( j, , ,Wd.Quad ); S.Chain := Wd. Chain; 106 （j ， ， ，100） 107查看语义子程序 句句 型型: S; = L; 执

33、执 行：行： 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 S106 （j ， ， ，100） 107 L.Chain := S.Chain ; 查看语义子程序 句句 型型: L; = LS 执执 行：行： Sub10； NXQ=107 属属 性：性： ( L. Chain := 101 )NXQ 100 （j，C，D ，104）103 （j ， ， ， 100）104 （+ ，

34、y，z， T1）105 （:=，T1 ， ，x）(10) LS 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：将下列语句翻译成四元式的形式（假设编号从：将下列语句

35、翻译成四元式的形式（假设编号从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; end100 ( jnz , A , , 102 )101 ( j , , , 104 )102 ( jnz , B , , 106 )

36、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 , ,

37、, 100 )118S.Chain = 105总总 结结 如何分割一个产生式如何分割一个产生式 如何为一个产生式编写语义子程序如何为一个产生式编写语义子程序 理解语句的执行流程。理解语句的执行流程。 自左向右扫描，理解语句的翻译框架。自左向右扫描，理解语句的翻译框架。 对后面四元式的转移目标（四元式编号）设置属性保存。对后面四元式的转移目标（四元式编号）设置属性保存。 拉（并）链的时机。拉（并）链的时机。 回填的时机。回填的时机。 设置文法符号的属性值以便保存：设置文法符号的属性值以便保存： 后面四元式的转移后面四元式的转移 目标；目标； 待回填的四元式编号；待回填的四元式编号； 需要继承的属

38、性。需要继承的属性。 如果需要并链，则用如果需要并链，则用Merge函数。函数。 如果需要回填，则用如果需要回填，则用BackPatch过程。过程。 如果需要产生四元式，则用如果需要产生四元式，则用Gen过程。过程。返回For 循循 环环 语语 句句 到到 四四 元元 式式 的的 翻翻 译译三种for循环语句的文法：S for i:= E1 step E2 until E3 do S1S for i:= E1 until E2 step E3 do S1S for ( E1 ; E2 ; E3 ) S1 语句语句 for i:= E1 step E2 until E3 do S1 的翻译的翻译

39、执行流程如下：语义解释如下：i := E1Si := i + E2i E3 YN i := E1 goto overagain: i := i + E2over: if iE3 then begin S1; goto again end 总结 i := E1 goto overagain: i := i + E2over: if iE3 then begin S1; goto again end 语语 句句 for i:= E1 step E2 until E3 do S1 的翻译框架的翻译框架E1 的四元式代码的四元式代码i := E1(j, , , over )i := i + E2(j,

40、 i, E3, L )(j, , , again )(j, , , 0 )E2 的四元式代码的四元式代码againE3 的四元式代码的四元式代码overS1 的四元式代码的四元式代码L总结E1 的四元式代码的四元式代码i := E1(j, , , over )i := i + E2E2 的四元式代码的四元式代码(j, i, E3, L )E3 的四元式代码的四元式代码(j, , , again )(j, , , 0 )S1 的四元式代码的四元式代码overagainL总结(4) A for i:= E1 step(3) B A E2 until(2) C B E3 do(1) S C S1S.

41、Chain产生式产生式 S for i:= E1 step E2 until E3 do S1 的分割的分割返回E1 的四元式代码的四元式代码i := E1(j, , , 0 )i := i + E2E2 的四元式代码的四元式代码(j, i, E3, L )E3 的四元式代码的四元式代码(j, , , again )(j, , , 0 )S1 的四元式代码的四元式代码总结返回(4) A for i:= E1 step语句语句 for i:= E1 step E2 until E3 do S1 的语义子程序的语义子程序 A.Place := LookUp(i.Name); Gen(:=, E1.

42、Place, ,A.Place); A.Chain := NXQ; Gen(j, , ,0); A.Quad := NXQ; A.ChainA.QuadNXQ总结返回语句语句 for i:= E1 step E2 until E3 do S1 的语义子程序的语义子程序(3) B A E2 until B.Quad := A.Quad; B.Place := A.Place; Gen(+, A.Place, E2.Place ,A.Place); BackPatch( A.Chain, NXQ); E1 的四元式代码的四元式代码i := E1(j, , , over )i := i + E2E2

43、 的四元式代码的四元式代码(j, i, E3, L )E3 的四元式代码的四元式代码(j, , , again )(j, , , 0 )S1 的四元式代码的四元式代码B.QuadA.QuadA.ChainNXQ总结返回语句语句 for i:= E1 step E2 until E3 do S1 的语义子程序的语义子程序(2) C B E3 do C.Quad := B.Quad; q := NXQ; Gen(j, B.Place, E3.Place , q+2); C.Chain := NXQ; Gen(j, , , 0); E1 的四元式代码的四元式代码i := E1(j, , , over

44、 )i := i + E2E2 的四元式代码的四元式代码(j, i, E3, L )E3 的四元式代码的四元式代码(j, , , again )(j, , , 0 )S1 的四元式代码的四元式代码C.QuadB.QuadC.ChainNXQ总结返回语句语句 for i:= E1 step E2 until E3 do S1 的语义子程序的语义子程序(1) S C S1 Gen( j, , , C.Quad ); S.Chain := C.Chain; BackPatch( S1.Chain, C.Quad ); E1 的四元式代码的四元式代码i := E1(j, , , over )i :=

45、i + E2E2 的四元式代码的四元式代码(j, i, E3, L )E3 的四元式代码的四元式代码(j, , , again )(j, , , 0 )S1 的四元式代码的四元式代码S.ChainC.ChainNXQC.Quad(4) A for i:= E1 step(3) B A E2 until(2) C B E3 do(1) S C S1语句语句 for i:= E1 step E2 until E3 do S1 的语义子程序的语义子程序 A.Place := LookUp(i.Name); Gen(:=, E1.Place, ,A.Place); A.Chain := NXQ; Ge

46、n(j, , ,0); A.Quad := NXQ; B.Quad := A.Quad; B.Place := A.Place; Gen(+, A.Place, E2.Place ,A.Place); BackPatch( A.Chain, NXQ); C.Quad := B.Quad; q := NXQ; Gen(j, B.Place, E3.Place , q+2); C.Chain := NXQ; Gen(j, , , 0); Gen( j, , , C.Quad ); S.Chain := C.Chain; BackPatch( S1.Chain, C.Quad ); 返回例：将下列语

47、句翻译成四元式的形式（编号从开始）例：将下列语句翻译成四元式的形式（编号从开始）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 := E1 step c+d until n+m do x := y+z 执执 行：行： 归约算术表达式；归约算术表达式； NXQ=102 属属 性：性：NXQ 100 （* ，b，T1）101 （+ ，a ，T1 ，T2）102 句句 型型: for I := E1 step c+

48、d until n+m do x := y+z = A step c+d until n+m do x := y+z 执执 行：行： Sub4； NXQ=104 属属 性：性： A.PlaceI ; A.Chain=103; A.Quad=104NXQ 100 （* ，b，T1）101 （+ ，a ，T1 ，T2）102 （:=，T2 ， ，i）(4) A for i:= E1Gen(:=, E1.Place, ,A.Place); A.Chain := NXQ; Gen(j, , ,0); A.Quad := NXQ; A.Place := LookUp(i.Name); 103 （j， ，

49、 ，0）104 A.Chain A.Quad 查看语义子程序查看语义子程序 句句 型型: A step c+d until n+m do x := y+z = A step E2 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

50、E2 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 E2B.Place := A.Place; Gen(+, A.Place, E2.Pl

51、ace ,A.Place); BackPatch( A.Chain, NXQ); B.Quad := A.Quad; 106 查看语义子程序查看语义子程序 句句 型型: B until n+m do x := y+z = B until E3 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

52、) 106 (+，n，m，T4) 107 查看语义子程序句句 型型: B until E3 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 E3Gen(j, B.Place, E3.Place , q+2); C.Chain := NXQ

53、; 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 S1 执执 行：归约赋值语句行：归约赋值语句 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 (+，

54、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 S1 = S 执执 行：行：Sub1 NXQ=111 属属 性：性： S.Chain=108NXQ 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) 1

55、09 (+，y，z，T5)S.Chain 110 (:=，T5，x) 111 (j，104) (1) S C do S1 Gen( j, , , C.Quad ); S.Chain := C.Chain; BackPatch( S1.Chain, C.Quad ); 112 查看语义子程序 语句语句 for (E1；E2；E3) S 的翻译的翻译执行流程如下：语义解释如下： E1SE3 E20YN E1L1: if E20 then goto L3 else goto L4 L2: E3 goto L1L3: S goto L2L4: 总结语语 句句 for (E1；E2；E3) S 的的 翻

56、翻 译译 框框 架架 E1 的四元式代码的四元式代码(j , , , L1 )(jnz, E2, , L3 )E3 的四元式代码的四元式代码(j , , , L2 )(j , , , 0 )S1 的四元式代码的四元式代码L1总结 E1L1: if E20 then goto L3 else goto L4 L2: E3 goto L1L3: S goto L2L4: E2 的四元式代码的四元式代码L2L3L4产生式产生式 S for (E1；E2；E3) S1 的分割的分割E1 的四元式代码的四元式代码(j , , , L1 )(jnz, E2, , L3 )E3 的四元式代码的四元式代码(j

57、 , , , L2 )(j , , , 0 )S1 的四元式代码的四元式代码L1总结E2 的四元式代码的四元式代码返回L2L3(4) A for ( E1 ;(3) B A E2 ;(2) C B E3 )(1) S C S1S.ChainE1 的四元式代码的四元式代码(j , , , L1 )(jnz, E2, , L3 )E3 的四元式代码的四元式代码(j , , , L2 )(j , , , 0 )S1 的四元式代码的四元式代码A.Quad总结E2 的四元式代码的四元式代码返回 A.Quad := NXQ; (4) A for ( E1 ;语语 句句 for (E1；E2；E3) S1

58、的的 语语 义义 子子 程程 序序NXQE1 的四元式代码的四元式代码(j , , , L1 )(jnz, E2, , L3 )E3 的四元式代码的四元式代码(j , , , L2 )(j , , , 0 )S1 的四元式代码的四元式代码B.Quad总结E2 的四元式代码的四元式代码返回语语 句句 for (E1；E2；E3) S1 的的 语语 义义 子子 程程 序序 B.TC := NXQ; Gen( jnz, E2.Place, ,0 ); B.FC := NXQ; Gen( j, , ,0 ) ; B.Quad := A.Quad; B.Quad1 := NXQ; (3) B A E2

59、;A.QuadB.TCB.FCB.Quad1NXQ总结返回语语 句句 for (E1；E2；E3) S1 的的 语语 义义 子子 程程 序序 Gen(j，B.Quad); BackPatch(B.TC，NXQ); C.Chain := B.FC; C.Quad := B.Quad1; (2) C B E3 )E1 的四元式代码的四元式代码(j , , , L1 )(jnz, E2, , L3 )E3 的四元式代码的四元式代码(j , , , L2 )(j , , , 0 )S1 的四元式代码的四元式代码B.QuadE2 的四元式代码的四元式代码B.TCC.ChainC.QuadB.FCB.Qu

60、ad1NXQ总结返回语语 句句 for (E1；E2；E3) S1 的的 语语 义义 子子 程程 序序E1 的四元式代码的四元式代码(j , , , L1 )(jnz, E2, , L3 )E3 的四元式代码的四元式代码(j , , , L2 )(j , , , 0 )S1 的四元式代码的四元式代码E2 的四元式代码的四元式代码S.ChainC.QuadNXQ Gen( j, , , C.Quad ); S.Chain := Merge(C.Chain，S1.Chain); (1) S C S1总结语语 句句 for (E1；E2；E3) S1 的的 语语 义义 子子 程程 序序 A.Quad