語法制導(dǎo)翻譯和中間代碼生成()

1、布爾表達(dá)式到四元式的翻譯 布爾表達(dá)式的作用布爾表達(dá)式的作用 布爾表達(dá)式的文法布爾表達(dá)式的文法 作為控制語句的條件表達(dá)式作為控制語句的條件表達(dá)式 用于邏輯計值用于邏輯計值EEE EE E (E) i rop i i注：注： rop 為關(guān)系運(yùn)算符：為關(guān)系運(yùn)算符：= =， ，=，=， 為為“與與”運(yùn)算；運(yùn)算；為為“或或”運(yùn)算；運(yùn)算； 為為“非非”運(yùn)算運(yùn)算 結(jié)合性為左結(jié)合性結(jié)合性為左結(jié)合性 優(yōu)先級別為：優(yōu)先級別為： rop ， ， 布爾表達(dá)式的計值方法布爾表達(dá)式的計值方法 方法一：方法一： 逐步計算逐步計算 方法二：方法二： 優(yōu)化計算優(yōu)化計算例如：例如：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 作為邏輯計值的布爾表達(dá)式的翻譯作為邏輯計值的布爾表達(dá)式的翻譯例如：將例如：將 ABC=D 翻譯成四元式的形式翻譯成四元式的形式（ =， C， D， T1 ）（ ， B， T1， T2 ）（ ， A， T2， T3 ） 作為控制條件的布爾表達(dá)式的翻譯作為控制條件的布爾表達(dá)式的翻譯 下面我們來觀察下面我們來觀察 “if-語句語句” 和和 “while-語句語句”中

3、布爾表達(dá)式的作用：中布爾表達(dá)式的作用：僅僅用于執(zhí)行流程的控制僅僅用于執(zhí)行流程的控制 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-語句語句”中布爾表達(dá)式的作用可以知道：中布爾表達(dá)式的作用可以知道：E的四元式代碼的四元式代碼T TR RU

4、 UE EF FA AL LS SE EE的真出口，用的真出口，用 E.TC 表示表示E的假出口，用的假出口，用 E.FC 表示表示 （ jnz ，A， ， p） 若若A為真，則轉(zhuǎn)到第為真，則轉(zhuǎn)到第p號四元式去執(zhí)行號四元式去執(zhí)行（ jrop，A，B， p） 若若A rop B為真，則轉(zhuǎn)到第為真，則轉(zhuǎn)到第p號四元式去執(zhí)行號四元式去執(zhí)行（ j ， ， ， p） 無條件轉(zhuǎn)到第無條件轉(zhuǎn)到第p號四元式去執(zhí)行號四元式去執(zhí)行為了翻譯布爾表達(dá)式，我們引入下面三種四元式：為了翻譯布爾表達(dá)式，我們引入下面三種四元式：例如：將下面語句翻譯成四元式的形式（編號從例如：將下面語句翻譯成四元式的形式（編號從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 執(zhí)執(zhí) 行：行： 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 執(zhí)執(zhí) 行：行： 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 執(zhí)執(zhí) 行：行： 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 執(zhí)執(zhí) 行：行：

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 執(zhí)執(zhí) 行：行： 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 執(zhí)執(zhí) 行：行： 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 執(zhí)執(zhí) 行：行： 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：翻譯布爾表達(dá)式：翻譯布爾表達(dá)式 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 表達(dá)式表達(dá)式 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; 在前面文法的基礎(chǔ)上增加如下一條四元式：在前面文法的基礎(chǔ)上增加如下一條四元式：標(biāo)號語句和標(biāo)號語句和GOTO語句到四元式的翻譯語句到四元式的翻譯 標(biāo)號語句和標(biāo)號語句和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 (,)標(biāo)標(biāo) 號號 語語 句句 和和 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語句和復(fù)合語句到四元式的翻譯語句和復(fù)合語句到四元式的翻譯 條件語句、while語句和復(fù)合語句的語法（1）S if E then Sif E then S else S while E do Sbegin L endA（2）L L ; SS說明：說明： S 表示語句；表示語句； E 表示布爾表達(dá)式；表示布爾表達(dá)式； A 表示賦值語句；表示賦值語句； L 表示語句串。表示語句串。 引入二個新的符號屬性 S.Chain : 轉(zhuǎn)出內(nèi)層語句轉(zhuǎn)出內(nèi)層語句S的各四元式所形成的鏈的

22、鏈頭。的各四元式所形成的鏈的鏈頭。 X.Quad : 相應(yīng)于相應(yīng)于X符號的四元式串的第一個四元式編號。符號的四元式串的第一個四元式編號。 為了在翻譯過程中能及時地進(jìn)行為了在翻譯過程中能及時地進(jìn)行“拉鏈拉鏈”和和“回填回填”處理，我們將處理，我們將其文法改寫成如下形式：其文法改寫成如下形式：（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：將下列語句翻譯成四元式的形式（假設(shè)編號從：將下列語句翻譯成四元式的形式（假設(shè)編號從100 開始）開始）while ( A D) then x := y + z;查看語義子程序句句 型型: while ( A D) then x := y + z; = W ( A D) then x := y + z; 執(zhí)執(zhí) 行：行： 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; 執(zhí)執(zhí) 行：行： 歸約布爾表達(dá)式；歸約布爾表達(dá)式； 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; 執(zhí)執(zhí)

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; 執(zhí)執(zhí) 行：行： 歸約布爾表達(dá)式；歸約布爾表達(dá)式； 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; 執(zhí)執(zhí) 行：行： 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; 執(zhí)執(zhí) 行：歸約賦值語句；行：歸約賦值語句； 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; 執(zhí)執(zhí) 行：行： 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; 執(zhí)執(zhí) 行：行： 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; 執(zhí)執(zhí) 行：行： 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; 執(zhí)

33、執(zhí) 行：行： 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 執(zhí)執(zhí) 行：行： 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上面語句翻譯成四元式的形式為：上面語句翻譯成四元式的形式為：思考題：上面語句后面少分號，結(jié)果有是如何呢？思考題：上面語句后面少分號，結(jié)果有是如何呢？例例4：將下列語句翻譯成四元式的形式（假設(shè)編號從：將下列語句

35、翻譯成四元式的形式（假設(shè)編號從100 開始）開始）while ( A B C ) do begin k := k+1; if ( mn ) then x := x + y; else x := x-y; y := y*2; end思考題目：給出詳細(xì)的翻譯步驟？思考題目：給出詳細(xì)的翻譯步驟？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總總 結(jié)結(jié) 如何分割一個產(chǎn)生式如何分割一個產(chǎn)生式 如何為一個產(chǎn)生式編寫語義子程序如何為一個產(chǎn)生式編寫語義子程序 理解語句的執(zhí)行流程。理解語句的執(zhí)行流程。 自左向右掃描，理解語句的翻譯框架。自左向右掃描，理解語句的翻譯框架。 對后面四元式的轉(zhuǎn)移目標(biāo)（四元式編號）設(shè)置屬性保存。對后面四元式的轉(zhuǎn)移目標(biāo)（四元式編號）設(shè)置屬性保存。 拉（并）鏈的時機(jī)。拉（并）鏈的時機(jī)。 回填的時機(jī)?；靥畹臅r機(jī)。 設(shè)置文法符號的屬性值以便保存：設(shè)置文法符號的屬性值以便保存： 后面四元式的轉(zhuǎn)移后面四元式的轉(zhuǎn)移 目標(biāo)；目標(biāo)； 待回填的四元式編號；待回填的四元式編號； 需要繼承的屬

38、性。需要繼承的屬性。 如果需要并鏈，則用如果需要并鏈，則用Merge函數(shù)。函數(shù)。 如果需要回填，則用如果需要回填，則用BackPatch過程。過程。 如果需要產(chǎn)生四元式，則用如果需要產(chǎn)生四元式，則用Gen過程。過程。返回For 循循 環(huán)環(huán) 語語 句句 到到 四四 元元 式式 的的 翻翻 譯譯三種for循環(huán)語句的文法：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、執(zhí)行流程如下：語義解釋如下：i := E1Si := i + E2i E3 YN i := E1 goto overagain: i := i + E2over: if iE3 then begin S1; goto again end 總結(jié) 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總結(jié)E1 的四元式代碼的四元式代碼i := E1(j, , , over )i := i + E2E2 的四元式代碼的四元式代碼(j, i, E3, L )E3 的四元式代碼的四元式代碼(j, , , again )(j, , , 0 )S1 的四元式代碼的四元式代碼overagainL總結(jié)(4) A for i:= E1 step(3) B A E2 until(2) C B E3 do(1) S C S1S.

41、Chain產(chǎn)生式產(chǎn)生式 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 的四元式代碼的四元式代碼總結(jié)返回(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總結(jié)返回語句語句 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總結(jié)返回語句語句 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總結(jié)返回語句語句 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 執(zhí)執(zhí) 行：行： 歸約算術(shù)表達(dá)式；歸約算術(shù)表達(dá)式； 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 執(zhí)執(zhí) 行：行： 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 執(zhí)執(zhí) 行：歸約算術(shù)表達(dá)式；行：歸約算術(shù)表達(dá)式； 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 執(zhí)執(zhí) 行：行：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 執(zhí)執(zhí) 行：歸約算術(shù)表達(dá)式；行：歸約算術(shù)表達(dá)式； 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 執(zhí)執(zhí) 行：行：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 執(zhí)執(zhí) 行：歸約賦值語句行：歸約賦值語句 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 執(zhí)執(zhí) 行：行：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 的翻譯的翻譯執(zhí)行流程如下：語義解釋如下： E1SE3 E20YN E1L1: if E20 then goto L3 else goto L4 L2: E3 goto L1L3: S goto L2L4: 總結(jié)語語 句句 for (E1；E2；E3) S 的的 翻

56、翻 譯譯 框框 架架 E1 的四元式代碼的四元式代碼(j , , , L1 )(jnz, E2, , L3 )E3 的四元式代碼的四元式代碼(j , , , L2 )(j , , , 0 )S1 的四元式代碼的四元式代碼L1總結(jié) E1L1: if E20 then goto L3 else goto L4 L2: E3 goto L1L3: S goto L2L4: E2 的四元式代碼的四元式代碼L2L3L4產(chǎn)生式產(chǎn)生式 S for (E1；E2；E3) S1 的分割的分割E1 的四元式代碼的四元式代碼(j , , , L1 )(jnz, E2, , L3 )E3 的四元式代碼的四元式代碼(j

57、 , , , L2 )(j , , , 0 )S1 的四元式代碼的四元式代碼L1總結(jié)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總結(jié)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總結(jié)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總結(jié)返回語語 句句 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總結(jié)返回語語 句句 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總結(jié)語語 句句 for (E1；E2；E3) S1 的的 語語 義義 子子 程程 序序 A.Quad