編譯原理第三版第七章語義和中間代碼產(chǎn)生

1、 n 任務任務: : 把語法單位翻譯為中間代碼把語法單位翻譯為中間代碼n 內(nèi)容內(nèi)容: : 屬性文法的屬性文法的概念概念、語法制導翻譯方法的語法制導翻譯方法的 基本思想?；舅枷?。 典型的典型的中間代碼中間代碼: : 逆波蘭式、三元式、四逆波蘭式、三元式、四 元式、樹等。元式、樹等。 基本語法單位的基本語法單位的翻譯翻譯。包括：說明語句、。包括：說明語句、 表達式、賦值語句、控制語句、數(shù)組元表達式、賦值語句、控制語句、數(shù)組元素素 引用、過程調(diào)用等的翻譯。引用、過程調(diào)用等的翻譯。 1、屬性文法、屬性文法在上下文無關文法的基礎上，在描述語義動作時，在上下文無關文法的基礎上，在描述語義動作時，為每個文

2、法符號（終結符和非終結符）配備若干相為每個文法符號（終結符和非終結符）配備若干相關的關的“值值”，如，如“類型類型”，“地址地址”等，等，稱為屬性稱為屬性。 對文法的對文法的每個產(chǎn)生式每個產(chǎn)生式配備一組屬性計算規(guī)則稱配備一組屬性計算規(guī)則稱為為語義規(guī)則語義規(guī)則，它的描述形式為，它的描述形式為b:=f(c1,c2,ck),其中其中b,c1,c2ck為文法符號的屬性，為文法符號的屬性，f是一個函數(shù)。是一個函數(shù)。 對每個產(chǎn)生式都給出其語義規(guī)則的對每個產(chǎn)生式都給出其語義規(guī)則的文法稱為文法稱為屬性屬性文法。文法。記號表示記號表示n對于某個文法符號對于某個文法符號XVT VN，用用 X . type（X的類

3、型），的類型），X . cat（X的種的種別），別），X .val（X的值或地址）等的值或地址）等表示它表示它的屬性。的屬性。n用下標（上角標）區(qū)分同一產(chǎn)生式中相用下標（上角標）區(qū)分同一產(chǎn)生式中相同符號的多次出現(xiàn)。同符號的多次出現(xiàn)。例：例：簡單臺式計算器的屬性文法簡單臺式計算器的屬性文法產(chǎn)生式產(chǎn)生式L EnE E1+TE TT T1*FT FF (E)F digit語義規(guī)則語義規(guī)則Print(E.val)E.val:=E1.val+T.valE.val:=T.valT.val:=T1.val*F.valT.val:=F.valF.val:=E.valF.val:=digit.lexvaln 屬

4、性文法屬性文法可以看作是關于語言翻譯的高級規(guī)可以看作是關于語言翻譯的高級規(guī)范說明，其中隱去了實現(xiàn)細節(jié)。范說明，其中隱去了實現(xiàn)細節(jié)。n 翻譯模式翻譯模式是適合語法制導翻譯的另一種語言是適合語法制導翻譯的另一種語言翻譯的描述形式，它給出了使用語義規(guī)則進行翻譯的描述形式，它給出了使用語義規(guī)則進行計算的次序計算的次序，這樣就把某些這樣就把某些實現(xiàn)細節(jié)實現(xiàn)細節(jié)表示出來表示出來了。在翻譯模式中，和文法符號相關的屬性和了。在翻譯模式中，和文法符號相關的屬性和語義規(guī)則用語義規(guī)則用 括起來。也稱括起來。也稱語義動作，語義子語義動作，語義子程序程序 。2、語法制導翻譯方法、語法制導翻譯方法語法制導翻譯的基本思想語

5、法制導翻譯的基本思想n在在語法分析過程語法分析過程中，隨著分析的步步進中，隨著分析的步步進展，在使用某個產(chǎn)生式進行推導或歸約展，在使用某個產(chǎn)生式進行推導或歸約時便時便執(zhí)行執(zhí)行相應的相應的語義子程序語義子程序，完成既定，完成既定的翻譯工作，生成中間代碼。的翻譯工作，生成中間代碼。 (1) (1) 擴大語法分析器的功能擴大語法分析器的功能, , 在使用某個產(chǎn)生式在使用某個產(chǎn)生式進行歸約進行歸約( (或推導或推導) )時時, ,調(diào)用相應的子程序進行翻譯調(diào)用相應的子程序進行翻譯( (生成中間代碼生成中間代碼) (2) ) (2) 分析棧改為分析棧改為語義棧語義棧 。Sm Xm.VAL Xm Sm-1

6、Xm-1.VAL Xm-1.S0 / #.STATE VAL SYM語義棧語義棧語法制導翻譯方法的實現(xiàn)途徑語法制導翻譯方法的實現(xiàn)途徑1. 后綴式后綴式后綴式表示法又稱后綴式表示法又稱逆波蘭表示法逆波蘭表示法，是一種表示表達式的是一種表示表達式的方法，它把運算量（操作數(shù)）寫在前面，算符寫在后面方法，它把運算量（操作數(shù)）寫在前面，算符寫在后面例：中綴表示例：中綴表示: a+b,a+b: a+b,a+b* *c,mc,m=1,(a+b)=1,(a+b)* *c, (a+b)c, (a+b)* *(c-d) (c-d) 后綴表示后綴表示: ab+, abc: ab+, abc* *+, m1=,ab+

7、c+, m1=,ab+c* *, ab+cd, ab+cd- -* *n 特點特點: : 運算分量的個數(shù)與先后次序不變；運算分量的個數(shù)與先后次序不變； 運算符的個數(shù)不變運算符的個數(shù)不變, , 但其出現(xiàn)順序即為執(zhí)行順序但其出現(xiàn)順序即為執(zhí)行順序 無括號；無括號；一個表達式一個表達式E的后綴式可如下定義：的后綴式可如下定義：n(1)如果如果E是一個是一個變量或常數(shù)變量或常數(shù)，則，則E的后綴式是的后綴式是E自身；自身；n(2)如果如果E是是E1opE2形式的表達式，形式的表達式，op是二元操是二元操作符，則作符，則E的的后綴式為后綴式為E1E2op, E1和和E2分分別為別為E1和和E2的后綴式；的后

8、綴式；n(3)如果如果E是是(E1)形式的表達式，則形式的表達式，則E1的后綴式的后綴式就是就是E的后綴式的后綴式 二叉樹遍歷法即后序遍歷二叉樹二叉樹遍歷法即后序遍歷二叉樹 例如：例如：(a+b) / (c-d)） e /+- ea b c d 中序遍歷中序遍歷( 左左 中中 右右 ): (a+b) / (c-d) e 后序遍歷后序遍歷( 左左 右右 中中): ab+cd- / e 中綴到后綴的轉(zhuǎn)換中綴到后綴的轉(zhuǎn)換后綴式的推廣后綴式的推廣例例 條件算術表達式條件算術表達式: if e then X else Y 三目運算三目運算 if - then - else : ￥ eXY ￥= X e0

9、 即即e為為. T.Y e =0 即即e為為. F. 轉(zhuǎn)移指令轉(zhuǎn)移指令: 無條件轉(zhuǎn)無條件轉(zhuǎn): p jump 小于轉(zhuǎn)小于轉(zhuǎn): e1 e2 p jlt 為零轉(zhuǎn)為零轉(zhuǎn): e p jeze p1 jez X p2 jump p1: Y P2: p1 p2 POST: e p1 jez X p2 jump Y . . . 例例 if (x+y)*z = 0 then (a+b)c else abc 后綴式后綴式: (1) xy+z*0 = ab+c abc ￥ (2) xy+z*0 = p1 jez ab+c p2 jump p1: abc p2: 2、樹、樹: 也可以用也可以用樹型結構樹型結構表示表達

10、式或語句。對表達式中表示表達式或語句。對表達式中的的每個子表達式表式為一棵子樹，每個子表達式表式為一棵子樹，即簡單變量或常即簡單變量或常數(shù)的樹就是該變量或常數(shù)自身。如果表示數(shù)的樹就是該變量或常數(shù)自身。如果表示e1和和e2的的樹為樹為T1和和T2，那么，那么，e1+e2,e1*e2,-e1的樹分別為：的樹分別為：+ * _(uminus)T1 T2 T1 T2 T1e1 + e2 e1 * e2 - e1+* *A B C D A*B+C*D的樹的樹雙目運算對應二叉子樹，多目運算對應雙目運算對應二叉子樹，多目運算對應多叉子樹。多叉子樹。后綴式是樹的后序遍歷序列。后綴式是樹的后序遍歷序列。3、三地

11、址代碼三地址代碼一般形式一般形式：x:=y op z如：如： x:=y op z二元賦值二元賦值 x:= op y一元賦值一元賦值 x:=y復制賦值復制賦值 goto L無條件轉(zhuǎn)移無條件轉(zhuǎn)移 if x relop y goto L條件轉(zhuǎn)移條件轉(zhuǎn)移 if a goto L 條件轉(zhuǎn)移條件轉(zhuǎn)移三地址代碼在具體實現(xiàn)時常表示為記錄結構，如四三地址代碼在具體實現(xiàn)時常表示為記錄結構，如四元式、三元式、間接三元式元式、三元式、間接三元式。u 四元式四元式一個四元式是一個帶有四個域的記錄結構一個四元式是一個帶有四個域的記錄結構( op, arg1, arg2, result )op 運算符，運算符，arg1,a

12、rg2 運算數(shù)，運算數(shù)，result 運算結果運算結果 例例 a:= b*-c+b*-c 的四元式序列的四元式序列: : op arg1 arg2 result(1) ( c _ T1 )(2) ( * b T1 T2 )(3) ( c _ T3 )(4) ( * b T3 T4 )(5) (+ T2 T4 T5)(6) (:= T5 _ a) 四元式之間的聯(lián)系通過四元式之間的聯(lián)系通過臨時變量臨時變量實現(xiàn)。實現(xiàn)。單目運算只用單目運算只用arg1域，轉(zhuǎn)移語句將目標標號放入域，轉(zhuǎn)移語句將目標標號放入 result域。域。 arg1,arg2,result通常為通常為指針指針，指向有關名字的符號，指

13、向有關名字的符號表入口，且臨時變量填入符號表。表入口，且臨時變量填入符號表。u 三元式三元式 一個三元式有三個域一個三元式有三個域 ( op, arg1, arg2 ),其中：其中：arg1,arg2為指向符號表的指針（對程序中的名字或常量）或者是指為指向符號表的指針（對程序中的名字或常量）或者是指向三元式表的指針（取代臨時變量）。向三元式表的指針（取代臨時變量）。 例：例：a:= b*-c+b*-c 的三元式序列的三元式序列： op arg1 arg2(1) ( c _ ) (2) ( * b (1) ) (3) ( c _ )(4) (* b (3) )(5) (+ (2) (4) )(6

14、) (:= a (5) )u 間接三元式間接三元式不直接使用三元式表，另設一張不直接使用三元式表，另設一張間接碼表間接碼表，按運算的先后次，按運算的先后次序列出有關三元式在三元式表中的位置，序列出有關三元式在三元式表中的位置，相同的三元式無需相同的三元式無需 重填重填三元式表。三元式表。 例：例： a:= b*-c+b*-c 的間接三的間接三 元式為元式為：間接碼表間接碼表 op arg1 arg2 （1） (1) ( c _ ) （2） (2) ( * b (1) ) （1） (3) (+ (1) (2) ) （2) (4) (:= a (3) ) (3) (4) 三元式中使用了指向三元式的

15、指針，優(yōu)化三元式中使用了指向三元式的指針，優(yōu)化時修改較難。時修改較難。 間接三元式優(yōu)化只需要更改間接碼表，并間接三元式優(yōu)化只需要更改間接碼表，并節(jié)省三元式表存儲空間。節(jié)省三元式表存儲空間。 修改四元式表也較容易，只是臨時變量要修改四元式表也較容易，只是臨時變量要填入符號表，占據(jù)一定存儲空間。填入符號表，占據(jù)一定存儲空間。 四元式、三元式和間接三元式比較四元式、三元式和間接三元式比較 n說明語句作用說明語句作用: 用關鍵字定義名字的性質(zhì)用關鍵字定義名字的性質(zhì)（數(shù)據(jù)類型）（數(shù)據(jù)類型）n 簡單類型說明簡單類型說明n 數(shù)組、記錄說明數(shù)組、記錄說明n 語義動作語義動作: 填符號表、信息向量表、除填符號表

16、、信息向量表、除動態(tài)數(shù)組外不生成四元式。動態(tài)數(shù)組外不生成四元式。 (1) 文法文法 integer i1 , i2, . . . , inDinteger namelist real namelist namelistnamelist, i i 問題問題: : 必須把所有名字都歸約為必須把所有名字都歸約為namelist后才能把各個名字的后才能把各個名字的 類型填入符號表類型填入符號表, ,需要使用隊列或棧保存這些名字需要使用隊列或棧保存這些名字(2) 改寫文法改寫文法integer i1 , i2 , . . . , inDinteger i real i D, i D1. 簡單類型說明簡單

17、類型說明namelistnamelistnamelist. . .DDDD(3) 語義變量與語義過程語義變量與語義過程 D.att: 記錄說明語句記錄說明語句D規(guī)定的類型；規(guī)定的類型； fill (p, a):填表過程填表過程, 把屬性把屬性a填入符號表入口填入符號表入口p的有關欄中；的有關欄中； entry(i): 回送標識符回送標識符i在符號表中的入口（在符號表中的入口（lookup(); ( (4) 翻譯模式翻譯模式 (1) Dinteger i (2) Dreal i (3) DD1, i p:=entry(i); fill (p , int );D.att := int

18、p:=entry(i); fill (p , real ); D.att := real p:=entry(i); fill (p ,D1.att); D.att :=D1.att例：例： integer i1 , i2 , i32. 數(shù)組說明數(shù)組說明(1) 文法文法 Darray i l1 :u1 , l2: u2 , . . . , ln:un (2) 信息向量表信息向量表 l 1 u1 d1. . . ln un dn n Ctype aA array . . . 符號表符號表信息向量表信息向量表說明說明: : 對于固定數(shù)組對于固定數(shù)組, , 將有關說明信息依次填入符號表信息向?qū)⒂嘘P說明

19、信息依次填入符號表信息向量表；對于可變數(shù)組，需要形成中間代碼量表；對于可變數(shù)組，需要形成中間代碼 。(3) 可變數(shù)組的處理可變數(shù)組的處理 編譯時編譯時: 分配信息向量表區(qū)。分配信息向量表區(qū)。 產(chǎn)生運行時建立信息向量表和分配數(shù)組空間的四元式。產(chǎn)生運行時建立信息向量表和分配數(shù)組空間的四元式。 運行時運行時: 填寫信息向量表。填寫信息向量表。 分配數(shù)組存貯空間。分配數(shù)組存貯空間。 子程序子程序: 功能功能: 建立信息向量表和分配數(shù)組空間建立信息向量表和分配數(shù)組空間 參數(shù)參數(shù): n, type, li, ui, 信息向量表首址信息向量表首址BEGINi := 1; N := 1; C :=0; /*

20、i為維數(shù)為維數(shù),N為體積為體積, C為為a - C中的中的C*/WHILE i n DOBEGINdi := ui - li + 1; N := N * di ; C := C * di + li ;把把 li, ui , di 填入信息向量表填入信息向量表; i := i + 1END;申請申請N個單元的數(shù)組空間個單元的數(shù)組空間,令其首址為令其首址為a;把把n, C, type, a 填入信息向量表填入信息向量表END 3. 記錄說明的翻譯記錄說明的翻譯(1) ftype i (2) ftype I n(3) f1f(4) f1f1(1); f (5) typerecord(6) typec

21、har(7) typenteger(8) typepointer f. NAME := i .NAME; f.LEN:=type.LEN; FILN ( i . NAME, f. LEN) f. NAME := i .NAME; f . LEN := type. LEN * n .VAL; FILN ( i . NAME, f . LEN) FILO ( f . NAME, 0 ); f1 . LEN := f . LEN FILO ( f . NAME, f1(1). LEN ); f1 . LEN := f1(1). LEN+ f . LEN type . LEN := f1.LEN ty

22、pe . LEN := 1 type . LEN := 4 type . LEN := 4 #7.4 7.4 簡單算術表達式和賦值語句的翻譯簡單算術表達式和賦值語句的翻譯只含整型變量的簡單算術表達式，并符合運只含整型變量的簡單算術表達式，并符合運算符的結合規(guī)則和優(yōu)先級規(guī)定。算符的結合規(guī)則和優(yōu)先級規(guī)定。1. . 文法描述文法描述(1) Si := E (2) EE1 + E2(3) EE1 * E2(4) E - E1 (5) E(E1 )(6) Ei 2. . 語義變量和語義過程語義變量和語義過程 E. place : 存放存放E值的變量名在符號表的入口值的變量名在符號表的入口 或臨時變量的編

23、號或臨時變量的編號 ； :表示表示i所代表的名字本身，或直接用所代表的名字本身，或直接用i表示；表示； newtemp: 函數(shù)過程函數(shù)過程, 生成一個新的臨時單元生成一個新的臨時單元, 返回其編號；返回其編號；entry (i) : 函數(shù)過程函數(shù)過程, 返回返回i 在符號表的入口（或在符號表的入口（或lookup() ； gen ( op, arg1, arg2, result ) :語義過程，語義過程， 生成一個四元式并將它送到四元式表中；生成一個四元式并將它送到四元式表中；或或emit(x,”:=“, y, op, z):語義過程，把三地址語句語義過程，把三地址語句

24、x:=y op z發(fā)送到輸出文件。發(fā)送到輸出文件。(1) Si := E gen(:=, E.place, _ , entry(i) (2) EE1 + E2 T:= newtemp; gen( +, E1. place, E2. place, T); E. place:=T (3) EE1 * E2 T:= newtemp; gen(* , E1. place, E2. place, T);E. place:=T (4) E - E1 T:= newtemp; gen( , E1. place, _ , T);E. place:=T (5) E(E1 ) E.place:= E1. plac

25、e(6) Ei E. place:= entry (i)3. 語義子程序語義子程序 產(chǎn)生式產(chǎn)生式語義動作語義動作例例: : a:= - b*(c+d) 的語法制導翻譯過程的語法制導翻譯過程棧棧輸入串輸入串i.place 四元式四元式 #a:= -b*(c+d)# #i := -b*(c+d)# a #i:= -b*(c+d)# a_ #i:=- b*(c+d)# a_ _ #i:=- i *(c+d)# a_ _ b #i:= - E *(c+d)# a_ _ b #i:= E *(c+d)# a_ T1 #i:= E* (c+d)# a_ T1_ #i:= E*( c+d)# a_ T1_

26、_ #i:= E*(i +d)# a_ T1_ _ c #i:= E*(E +d)# a_ T1_ _ c #i:= E*(E+ d)# a_ T1_ _ c _ #i:= E*(E+i )# a_ T1_ _ c _ d #i:= E*(E+E )# a_ T1_ _ c _ d #i:= E*(E )# a_ T1_ _ T2 #i:= E*(E ) # a_ T1_ _ T2_ #i:= E*E # a_ T1_ T2 #i:= E # a_ T3 #S # (, b, _ ,T1)(+, c , d, T2)(*, T1, T2 ,T3)(:=, T3 ,_ , a )4. 類型轉(zhuǎn)換類

27、型轉(zhuǎn)換 若若i i 的類型不同的類型不同, ,則拒絕或做類型轉(zhuǎn)換則拒絕或做類型轉(zhuǎn)換 運算符運算符: 實型實型 +r , r , r 整型整型 +i , i , i 語義變量語義變量E. type = 轉(zhuǎn)換指令轉(zhuǎn)換指令( itr,A1, _ , T )intrealEE1 op E2 的語義子程序的語義子程序( ( 帶有語義轉(zhuǎn)換功能帶有語義轉(zhuǎn)換功能 ) ) T:= NEWTEMP；IF E1.type=int AND E2.type=int THEN BEGIN GEN(opi , E1.PLACE, E2.PLACE, T ); E. type:= int ENDELSE IF E1.type

28、=real AND E2.type=real THEN BEGIN GEN(opr , E1.PLACE, E2.PLACE, T ); E. type:= real ENDELSE IF E1.type=int /*and E2.type=real*/ THEN BEGIN U:= NEWTEMP GEN(itr , E1. PLACE, _ , U ); GEN(opr , U , E2. PLACE, T ); E. type:= real ENDELSE /* E1.type=real and E2.type=int*/ THEN BEGIN U:= NEWTEMP; GEN(itr

29、, E2. PLACE, _ , U ); GEN(opr, E1. PLACE, U, T ); E. type:= real END ； E. PLACE:= T7. 5 7. 5 布爾表達式的翻譯布爾表達式的翻譯1. 布爾表達式的定義布爾表達式的定義(1)構成構成:用用布爾運算符布爾運算符把把布爾量布爾量、關系表達式關系表達式聯(lián)結起聯(lián)結起 來的式子。來的式子。布爾運算符：布爾運算符：and, or, not ；關系運算符關系運算符 , ， ,(2) 作用作用: 控制語句的條件控制語句的條件 計算邏輯值計算邏輯值(3) 文法文法: EE and EE or Enot E(E)i i1 re

30、lop i2 運算符優(yōu)先級運算符優(yōu)先級:布爾運算由高到低布爾運算由高到低:not and or ,同級左結合同級左結合.關系運算符同級關系運算符同級,且高于布爾運算符且高于布爾運算符(4) 計值計值: 按優(yōu)先級按優(yōu)先級 (與算術表達式相同與算術表達式相同) 2. 數(shù)值表示法的布爾式翻譯數(shù)值表示法的布爾式翻譯： 與算術表達式翻譯相同與算術表達式翻譯相同 將將 and or not 看作運算符看作運算符關系表達式翻譯為含轉(zhuǎn)移語句的序列關系表達式翻譯為含轉(zhuǎn)移語句的序列: 即：即：ab表示表示if ab then 1 else 0例例：關系表達式關系表達式ab 翻譯為翻譯為四元式四元式:100（j,a

31、, b, 103) 101 (:= , 0, _ ,T) 102 (j , _ ,_ , 104) 103 (:=, 1,_ , T)104例例:布爾表達式布爾表達式a or b and not c翻譯為四元式翻譯為四元式:(not , c, _ , T1)(and , b , T1 , T2)(or , a , T2, T3)產(chǎn)生以上結果的語義子程序為產(chǎn)生以上結果的語義子程序為：E E1 or E2 T:=newtemp; gen( or E1.place, E2.place,T); E.place:=T E E1 and E2 T:=newtemp; gen( and E1.place,

32、E2.place, T);E.place:=TE not E1 T:=newtemp; gen( not E1.place, _, T);E.place:=TE ( E1) E.place:= E1.placeE id1 relop id2 T:=newtemp; gen(jrelop, id1.place, id2.place,nextstart+3); gen (:=, 0, _ , T); gen (j, _, _,nextstart+2); gen (:=, 1, _ , T);E.place:=T;E id E.place:=id.placenextstart為四元式序為四元式序列中

33、下一條四元式地列中下一條四元式地址索引，每產(chǎn)生一條址索引，每產(chǎn)生一條四元式，過程四元式，過程gen將將nextstart加加1例例：布爾表達式布爾表達式ab or cd and ef 的四元的四元式序列：式序列：100（j,a,b,103)101 ( :=,0,_, T1)102 (j, _, _, 104)103 (:=, 1, _, T1)104（j,c,d,107)105 ( :=,0,_, T2)106 (j, _, _, 108)107 (:=, 1, _, T2)108（j,e,f,111)109 ( :=,0,_, T3)110 (j, _, _, 112)111 (:=, 1,

34、 _, T3)112 (and, T2,T3,T4)113(or , T1, T4, T5)#3. 作為條件控制的布爾表達式的翻譯作為條件控制的布爾表達式的翻譯(1) 考察考察條件語句條件語句: : if E then S1 else S2 E E的作用的作用: : 控制對控制對S1和和S2 的選擇的選擇, 其值無需保留。其值無需保留。(2) 代碼結構代碼結構: :E的代碼的代碼S1的代碼的代碼S2的代碼的代碼(3) E的四元式形式的四元式形式: 全部為條件或無條件轉(zhuǎn)移指令全部為條件或無條件轉(zhuǎn)移指令 ( jnz, A1, _ , p )A1為真轉(zhuǎn)為真轉(zhuǎn)p ( j , A1, A2, p ) A

35、1A2為真轉(zhuǎn)為真轉(zhuǎn)p （為關系運算符）為關系運算符）( j, _ , _ , p ) 無條件轉(zhuǎn)無條件轉(zhuǎn)p真出口真出口假出口假出口(4) (4) E的真、假出口的確定的真、假出口的確定E 形如形如ab時，時， 生成四元式生成四元式 (j, a, b,E.true)(j,_, _, E.false)E形如形如E1or E2 E1 為真為真: E1 的真出口即為的真出口即為E的真出口，不必求的真出口，不必求E2； E1 為假為假: E2 需要計值需要計值, 其第一個四元式為其第一個四元式為E1 的假出口；的假出口； E2 的真假出口為的真假出口為E的真假出口。的真假出口。 E形如形如E1and E2

36、 E1 為假為假: E1 的假出口即為的假出口即為E的假出口的假出口,不必求不必求E2； E1 為真為真: E2 需要計值需要計值, 其第一個四元式為其第一個四元式為E1 的真出口；的真出口； E2 的真假出口為的真假出口為E的真假出口。的真假出口。 E形如形如not E1 E1 的真出口為的真出口為E的假出口；的假出口； E1 的假出口為的假出口為E的真出口。的真出口。(5) 回填技術回填技術 問題問題: 在自下而上語法分析中在自下而上語法分析中, 真假出口往往不能在真假出口往往不能在生成四元式的同時填上。生成四元式的同時填上。解決：解決：一種一種解決方法解決方法是兩遍掃描；另一種是兩遍掃描

37、；另一種解決方法解決方法是是采用一遍掃描，這時需要把相應四元式的地址保存采用一遍掃描，這時需要把相應四元式的地址保存, 到到適當?shù)臅r機再填入。這就是適當?shù)臅r機再填入。這就是回填回填技術。技術。 實現(xiàn)：實現(xiàn)：建立一個建立一個鏈表鏈表，把跳轉(zhuǎn)到相同目標的四元式，把跳轉(zhuǎn)到相同目標的四元式標號鏈在同一個表中，當目標確定后，再將它回填到標號鏈在同一個表中，當目標確定后，再將它回填到有關的指令中。有關的指令中。 可以有可以有兩種方式組織鏈表兩種方式組織鏈表：利用需要回填的跳轉(zhuǎn)四：利用需要回填的跳轉(zhuǎn)四元式的第四個域元式的第四個域(result)構造鏈表；或者建立單獨鏈表構造鏈表；或者建立單獨鏈表記錄需要回填

38、的跳轉(zhuǎn)四元式的標號。記錄需要回填的跳轉(zhuǎn)四元式的標號。鏈表的組織方式鏈表的組織方式設鏈表的頭指針為設鏈表的頭指針為E.truelist（需回填（需回填E的真值的的真值的的鏈），的鏈），E.falselist（需要回填（需要回填E的假值的鏈）的假值的鏈）E.truelist(r) (x, x, x, q)(q) (x, x, x, p)(p) (x, x, x, 0)E.truelistrqpnull(5)語義變量和過程、函數(shù)語義變量和過程、函數(shù) nextquad: 變量，下一個將形成的四元式地址，變量，下一個將形成的四元式地址， 初值為初值為1, 每執(zhí)行一次每執(zhí)行一次GEN 自動加自動加1. m

39、akelist(i): 函數(shù)，創(chuàng)建一個僅含函數(shù)，創(chuàng)建一個僅含i的新鏈表，的新鏈表，i為四元式地為四元式地址（標號）址（標號）.merge(p1, p2 ): 函數(shù)過程函數(shù)過程, 把以把以p1,p2 為為 鏈首的兩個鏈合并回送合并后的鏈首鏈首的兩個鏈合并回送合并后的鏈首.backpatch ( p, t ) : 過程過程,把鏈首把鏈首p 所指所指鏈中的四元式第鏈中的四元式第4域回填為域回填為 t。merge ( p1, p2 ); if p2 = 0 then merge= p1 else p := p2; while p.result0 do p=p.result; p.result=p1;

40、merge= P2; 00p2p1p1 (6) 語義子程序語義子程序?qū)ξ姆óa(chǎn)生式稍作修改，引入對文法產(chǎn)生式稍作修改，引入標記非終結符標記非終結符M，以便在適當?shù)臅r候，以便在適當?shù)臅r候執(zhí)行一個語義動作，記下下一個要產(chǎn)生四元式標號。執(zhí)行一個語義動作，記下下一個要產(chǎn)生四元式標號。(1)E i E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); gen(jnz, i.place,_,0); gen(j, _, _, 0) (2) E i1 relop i 2 E.truelist:=makelist(nextquad);

41、E.falselist:=makelist(nextquad+1); gen(jnz, i.place,_,0); gen(j, _, _, 0) (3) E(E1) E.truelist:=E1.truelist; E.falselist:=E1.falselist (4) Enot E1 E.truelist:=E1.falselist; E.falselist:=E1.truelist (5) E E1 and ME2 backpatch(E1.truelist,M.quad);E.truelist:=E2.truelist;E.falselist:=merge(E1.falselist

42、,E2.falselist) (6) EE1 or ME2 backpatch(E1.falselist, M.quad); E.truelist:=merge(E1.truelist,E2.truelist);E.falselist:=E2.falselist) (7) M M.quad:=nextquad例：例：將布爾式將布爾式ab or cd and ef 翻譯為四元式翻譯為四元式EE1orM1E4i1i2E2 and M E3i1i1i1 i1100 (j, a, b, 0)101 (j, _, _,0 )102 (j, c , d, 0)103 (j, _, _,0)104 (j,

43、e, f, 0)105 (j,_ ,_ ,0)鏈表鏈表：E1.truelist=100,E1.falselist=101Nextquad=102M1.quad=102E2.truelist=102,E2.falselist=103nextquad=104M.quad=104E3.truelist=104,E3.falselist=105nextquad=106E4.truelist=104E4.falselist=103,105E.truelist=100,104E.falselist=103,105104102四元式：四元式：#7.6 控制語句的翻譯控制語句的翻譯 1.控制流語句控制流語句

44、考察考察if - then , if - then - else ,while do 語句的翻譯語句的翻譯, 三種語句的形式三種語句的形式為為:if E then S1, if E then S1 else S2, While E do S1, 其中其中E為布爾表達式為布爾表達式.(1)三種語句的代碼結構三種語句的代碼結構 If-then 語句代碼結構語句代碼結構 E.codeS1.codeE.trueE.falseIf-then語句的代碼就是語句的代碼就是E的代碼的代碼后跟后跟S1的代碼。的代碼。 If-then語句只是語句只是控制了控制了這些代這些代碼中的碼中的轉(zhuǎn)移目標轉(zhuǎn)移目標。即。即E為

45、為”真真”時時,執(zhí)行執(zhí)行S1第一條語句第一條語句,E的真出的真出口口E.true為為S1的第一條指令的第一條指令,E中中某些四元式得到回填某些四元式得到回填;E為為”假假”時時,執(zhí)行執(zhí)行IF語句后的第一條指語句后的第一條指令令,設用設用S.next表示表示,該值待定。該值待定。S.next: while-do 語句的代碼結構語句的代碼結構If-then-else語句代碼結構語句代碼結構E.codeS1.codegoto S.nextS2.codeE.trueE.falseE.codeS1.codegoto S.beginE.trueE.false由分析可知由分析可知,if-then-else語

46、句多增加了一條跳轉(zhuǎn)語句多增加了一條跳轉(zhuǎn)指令指令goto S.next.while-do語句增加了一條語句增加了一條goto S.begin指令指令.兩條語句所做的其他工作也是回填布爾式兩條語句所做的其他工作也是回填布爾式E或其或其它語句中指令地址它語句中指令地址.對于語句也需要一個未填寫目標標號而以后需對于語句也需要一個未填寫目標標號而以后需要回填的轉(zhuǎn)移指令鏈要回填的轉(zhuǎn)移指令鏈,用用S.nextlist指示指示.S.next:S.begin:S.next:(2)(2)文法描述文法描述 Sif E then S if E then S else S while E do S begin L en

47、d A LL;S S其中其中, S:語句語句 L:語句串語句串 A:賦值語句賦值語句E:布爾表達式布爾表達式(3)語義子程序語義子程序( (翻譯模式翻譯模式) )使用有關鏈表操作的使用有關鏈表操作的語義變量、函數(shù)和過程語義變量、函數(shù)和過程（ nextquad, makelist（）（）, merge( ), backpatch( ) ),E.truelist,E.falselist,S.nextlist,L.nextlist指向需回填的指向需回填的指令鏈表指令鏈表。對文法稍做修改：對文法稍做修改：1 1）引入標記非終結符）引入標記非終結符M M，以記錄某些位，以記錄某些位置的四元式標號；置的四

48、元式標號；2 2）引入標記非終結符）引入標記非終結符N N，以生成一條跳轉(zhuǎn)，以生成一條跳轉(zhuǎn)指令和一個鏈。指令和一個鏈。 改寫后的文法及語義動作改寫后的文法及語義動作 1) Sif E then M S1 backpatch(E.truelist,M.quad);S.nextlist:=merge(E.falselist,S1.nextlist)2) Sif E then M1 S1 N else M2 S2 backpatch(E.truelist,M1.quad); backpatch(E.falselist,M2.quad); S.nextlist:=merge(S1.nextlist,N

49、.nextlist,S2.next)3) N N.nextlist:=makelist(nextquad); gen( j,_ ,_ ,0)4) M M.quad:= nextquad5) Swhile M1 E do M2 S1 backpatch(S1.nextlist, M1.quad); backpatch (E.truelist, M2.quad); S.nextlist:=E.falselist; gen( j, _ ,_ ,M1.quad)6)S begin L end S.nextlist:=L.nextlist7) S A S.nextlist:=makelist()8) L

50、 L1;MS backpatch(L1.nextlist, M.quad); L.nextlist:= S.nextlist9) L S L.nextlist:=S.nextlist例例: :while a b do if c d then x:= y+z 翻譯為四元式翻譯為四元式100 ( j, a, b, 0 )101 ( j , _ , _ , 0 )102 ( j, c, d, 0 )103 ( j , _ , _ , 0 )104 ( +, y, z, T1 )105 ( := , T1, _ , x )106 ( j, _ , _ , 100 )S1whileM1E1 doM2S2

51、i1 i2ifE2 then M3 S3Ai:= Ei+ ii1 10 時時 Sn-1 的的 代代 碼碼 Sn 的的 代代 碼碼計算計算T：=E的代碼的代碼S1 的的 代代 碼碼S2 的的 代代 碼碼判斷判斷T 的的 代代 碼碼T=C1 L1:T=C2 L2:T=Cn-1 Ln-1:T=其它其它 Ln:TEST:NEXT:(4) 代碼生成過程代碼生成過程: 遇到遇到case遇到遇到E of遇到遇到Ci 遇到遇到Si 遇到遇到end利用隊列利用隊列QUEUE4. for語句語句(1) 文法文法: : Sfor i := E(1) step E(2) until E(3) do S(1)(2) 代

52、碼結構代碼結構: :增量部分增量部分: i:= i + E(2)測試部分測試部分: i = E(3)循環(huán)體循環(huán)體: S(1)初值部分初值部分: i := E(1) 例例 for i := 1 step 1 until N do M:=M+1AGAIN:OVER:假出口假出口真出口真出口100 (:= , 1 , _ , I ) 101 ( j, _ , _ , 0 103 )102 ( +, I, 1 , I ) 103 ( j, I , N , 0 105 )104 ( j , _ , _ , 0 108)105 (+, M , 1 , T )106 (:= , T , _ , M )107 ( j , _ , _ , 102)AGAIN:OVER:(3) (3) 改寫文法與語