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

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

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

3、型），的類型），X . cat（X的種的種別），別），X .val（X的值或地址）等的值或地址）等表示它表示它的屬性。的屬性。n用下標(biāo)（上角標(biāo)）區(qū)分同一產(chǎn)生式中相用下標(biāo)（上角標(biāo)）區(qū)分同一產(chǎn)生式中相同符號(hào)的多次出現(xiàn)。同符號(hào)的多次出現(xiàn)。例：例：簡(jiǎn)單臺(tái)式計(jì)算器的屬性文法簡(jiǎn)單臺(tái)式計(jì)算器的屬性文法產(chǎn)生式產(chǎn)生式L EnE E1+TE TT T1*FT FF (E)F digit語(yǔ)義規(guī)則語(yǔ)義規(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ān)于語(yǔ)言翻譯的高級(jí)規(guī)可以看作是關(guān)于語(yǔ)言翻譯的高級(jí)規(guī)范說(shuō)明，其中隱去了實(shí)現(xiàn)細(xì)節(jié)。范說(shuō)明，其中隱去了實(shí)現(xiàn)細(xì)節(jié)。n 翻譯模式翻譯模式是適合語(yǔ)法制導(dǎo)翻譯的另一種語(yǔ)言是適合語(yǔ)法制導(dǎo)翻譯的另一種語(yǔ)言翻譯的描述形式，它給出了使用語(yǔ)義規(guī)則進(jìn)行翻譯的描述形式，它給出了使用語(yǔ)義規(guī)則進(jìn)行計(jì)算的次序計(jì)算的次序，這樣就把某些這樣就把某些實(shí)現(xiàn)細(xì)節(jié)實(shí)現(xiàn)細(xì)節(jié)表示出來(lái)表示出來(lái)了。在翻譯模式中，和文法符號(hào)相關(guān)的屬性和了。在翻譯模式中，和文法符號(hào)相關(guān)的屬性和語(yǔ)義規(guī)則用語(yǔ)義規(guī)則用 括起來(lái)。也稱括起來(lái)。也稱語(yǔ)義動(dòng)作，語(yǔ)義子語(yǔ)義動(dòng)作，語(yǔ)義子程序程序 。2、語(yǔ)法制導(dǎo)翻譯方法、語(yǔ)法制導(dǎo)翻譯方法語(yǔ)法制導(dǎo)翻譯的基本思想語(yǔ)

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

6、Xm-1.VAL Xm-1.S0 / #.STATE VAL SYM語(yǔ)義棧語(yǔ)義棧語(yǔ)法制導(dǎo)翻譯方法的實(shí)現(xiàn)途徑語(yǔ)法制導(dǎo)翻譯方法的實(shí)現(xiàn)途徑1. 后綴式后綴式后綴式表示法又稱后綴式表示法又稱逆波蘭表示法逆波蘭表示法，是一種表示表達(dá)式的是一種表示表達(dá)式的方法，它把運(yùn)算量（操作數(shù)）寫(xiě)在前面，算符寫(xiě)在后面方法，它把運(yùn)算量（操作數(shù)）寫(xiě)在前面，算符寫(xiě)在后面例：中綴表示例：中綴表示: 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 特點(diǎn)特點(diǎn): : 運(yùn)算分量的個(gè)數(shù)與先后次序不變；運(yùn)算分量的個(gè)數(shù)與先后次序不變； 運(yùn)算符的個(gè)數(shù)不變運(yùn)算符的個(gè)數(shù)不變, , 但其出現(xiàn)順序即為執(zhí)行順序但其出現(xiàn)順序即為執(zhí)行順序 無(wú)括號(hào)；無(wú)括號(hào)；一個(gè)表達(dá)式一個(gè)表達(dá)式E的后綴式可如下定義：的后綴式可如下定義：n(1)如果如果E是一個(gè)是一個(gè)變量或常數(shù)變量或常數(shù)，則，則E的后綴式是的后綴式是E自身；自身；n(2)如果如果E是是E1opE2形式的表達(dá)式，形式的表達(dá)式，op是二元操是二元操作符，則作符，則E的的后綴式為后綴式為E1E2op, E1和和E2分分別為別為E1和和E2的后綴式；的后

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

9、 即即e為為. T.Y e =0 即即e為為. F. 轉(zhuǎn)移指令轉(zhuǎn)移指令: 無(wú)條件轉(zhuǎn)無(wú)條件轉(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、樹(shù)、樹(shù): 也可以用也可以用樹(shù)型結(jié)構(gòu)樹(shù)型結(jié)構(gòu)表示表達(dá)

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

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

12、rg2 運(yùn)算數(shù)，運(yùn)算數(shù)，result 運(yùn)算結(jié)果運(yùn)算結(jié)果 例例 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)系通過(guò)四元式之間的聯(lián)系通過(guò)臨時(shí)變量臨時(shí)變量實(shí)現(xiàn)。實(shí)現(xiàn)。單目運(yùn)算只用單目運(yùn)算只用arg1域，轉(zhuǎn)移語(yǔ)句將目標(biāo)標(biāo)號(hào)放入域，轉(zhuǎn)移語(yǔ)句將目標(biāo)標(biāo)號(hào)放入 result域。域。 arg1,arg2,result通常為通常為指針指針，指向有關(guān)名字的符號(hào)，指

13、向有關(guān)名字的符號(hào)表入口，且臨時(shí)變量填入符號(hào)表。表入口，且臨時(shí)變量填入符號(hào)表。u 三元式三元式 一個(gè)三元式有三個(gè)域一個(gè)三元式有三個(gè)域 ( op, arg1, arg2 ),其中：其中：arg1,arg2為指向符號(hào)表的指針（對(duì)程序中的名字或常量）或者是指為指向符號(hào)表的指針（對(duì)程序中的名字或常量）或者是指向三元式表的指針（取代臨時(shí)變量）。向三元式表的指針（取代臨時(shí)變量）。 例：例：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 間接三元式間接三元式不直接使用三元式表，另設(shè)一張不直接使用三元式表，另設(shè)一張間接碼表間接碼表，按運(yùn)算的先后次，按運(yùn)算的先后次序列出有關(guān)三元式在三元式表中的位置，序列出有關(guān)三元式在三元式表中的位置，相同的三元式無(wú)需相同的三元式無(wú)需 重填重填三元式表。三元式表。 例：例： 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)化時(shí)修改較難。時(shí)修改較難。 間接三元式優(yōu)化只需要更改間接碼表，并間接三元式優(yōu)化只需要更改間接碼表，并節(jié)省三元式表存儲(chǔ)空間。節(jié)省三元式表存儲(chǔ)空間。 修改四元式表也較容易，只是臨時(shí)變量要修改四元式表也較容易，只是臨時(shí)變量要填入符號(hào)表，占據(jù)一定存儲(chǔ)空間。填入符號(hào)表，占據(jù)一定存儲(chǔ)空間。 四元式、三元式和間接三元式比較四元式、三元式和間接三元式比較 n說(shuō)明語(yǔ)句作用說(shuō)明語(yǔ)句作用: 用關(guān)鍵字定義名字的性質(zhì)用關(guān)鍵字定義名字的性質(zhì)（數(shù)據(jù)類型）（數(shù)據(jù)類型）n 簡(jiǎn)單類型說(shuō)明簡(jiǎn)單類型說(shuō)明n 數(shù)組、記錄說(shuō)明數(shù)組、記錄說(shuō)明n 語(yǔ)義動(dòng)作語(yǔ)義動(dòng)作: 填符號(hào)表、信息向量表、除填符號(hào)表

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

17、類型說(shuō)明namelistnamelistnamelist. . .DDDD(3) 語(yǔ)義變量與語(yǔ)義過(guò)程語(yǔ)義變量與語(yǔ)義過(guò)程 D.att: 記錄說(shuō)明語(yǔ)句記錄說(shuō)明語(yǔ)句D規(guī)定的類型；規(guī)定的類型； fill (p, a):填表過(guò)程填表過(guò)程, 把屬性把屬性a填入符號(hào)表入口填入符號(hào)表入口p的有關(guān)欄中；的有關(guān)欄中； entry(i): 回送標(biāo)識(shí)符回送標(biāo)識(shí)符i在符號(hào)表中的入口（在符號(hào)表中的入口（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ù)組說(shuō)明數(shù)組說(shuō)明(1) 文法文法 Darray i l1 :u1 , l2: u2 , . . . , ln:un (2) 信息向量表信息向量表 l 1 u1 d1. . . ln un dn n Ctype aA array . . . 符號(hào)表符號(hào)表信息向量表信息向量表說(shuō)明說(shuō)明: : 對(duì)于固定數(shù)組對(duì)于固定數(shù)組, , 將有關(guān)說(shuō)明信息依次填入符號(hào)表信息向?qū)⒂嘘P(guān)說(shuō)明

19、信息依次填入符號(hào)表信息向量表；對(duì)于可變數(shù)組，需要形成中間代碼量表；對(duì)于可變數(shù)組，需要形成中間代碼 。(3) 可變數(shù)組的處理可變數(shù)組的處理 編譯時(shí)編譯時(shí): 分配信息向量表區(qū)。分配信息向量表區(qū)。 產(chǎn)生運(yùn)行時(shí)建立信息向量表和分配數(shù)組空間的四元式。產(chǎn)生運(yùn)行時(shí)建立信息向量表和分配數(shù)組空間的四元式。 運(yùn)行時(shí)運(yùn)行時(shí): 填寫(xiě)信息向量表。填寫(xiě)信息向量表。 分配數(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;申請(qǐng)申請(qǐng)N個(gè)單元的數(shù)組空間個(gè)單元的數(shù)組空間,令其首址為令其首址為a;把把n, C, type, a 填入信息向量表填入信息向量表END 3. 記錄說(shuō)明的翻譯記錄說(shuō)明的翻譯(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 簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯只含整型變量的簡(jiǎn)單算術(shù)表達(dá)式，并符合運(yùn)只含整型變量的簡(jiǎn)單算術(shù)表達(dá)式，并符合運(yùn)算符的結(jié)合規(guī)則和優(yōu)先級(jí)規(guī)定。算符的結(jié)合規(guī)則和優(yōu)先級(jí)規(guī)定。1. . 文法描述文法描述(1) Si := E (2) EE1 + E2(3) EE1 * E2(4) E - E1 (5) E(E1 )(6) Ei 2. . 語(yǔ)義變量和語(yǔ)義過(guò)程語(yǔ)義變量和語(yǔ)義過(guò)程 E. place : 存放存放E值的變量名在符號(hào)表的入口值的變量名在符號(hào)表的入口 或臨時(shí)變量的編

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

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. 語(yǔ)義子程序語(yǔ)義子程序 產(chǎn)生式產(chǎn)生式語(yǔ)義動(dòng)作語(yǔ)義動(dòng)作例例: : a:= - b*(c+d) 的語(yǔ)法制導(dǎo)翻譯過(guò)程的語(yǔ)法制導(dǎo)翻譯過(guò)程棧棧輸入串輸入串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)換 運(yùn)算符運(yùn)算符: 實(shí)型實(shí)型 +r , r , r 整型整型 +i , i , i 語(yǔ)義變量語(yǔ)義變量E. type = 轉(zhuǎn)換指令轉(zhuǎn)換指令( itr,A1, _ , T )intrealEE1 op E2 的語(yǔ)義子程序的語(yǔ)義子程序( ( 帶有語(yǔ)義轉(zhuǎn)換功能帶有語(yǔ)義轉(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 布爾表達(dá)式的翻譯布爾表達(dá)式的翻譯1. 布爾表達(dá)式的定義布爾表達(dá)式的定義(1)構(gòu)成構(gòu)成:用用布爾運(yùn)算符布爾運(yùn)算符把把布爾量布爾量、關(guān)系表達(dá)式關(guān)系表達(dá)式聯(lián)結(jié)起聯(lián)結(jié)起 來(lái)的式子。來(lái)的式子。布爾運(yùn)算符：布爾運(yùn)算符：and, or, not ；關(guān)系運(yùn)算符關(guān)系運(yùn)算符 , ， ,(2) 作用作用: 控制語(yǔ)句的條件控制語(yǔ)句的條件 計(jì)算邏輯值計(jì)算邏輯值(3) 文法文法: EE and EE or Enot E(E)i i1 re

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

31、, b, 103) 101 (:= , 0, _ ,T) 102 (j , _ ,_ , 104) 103 (:=, 1,_ , T)104例例:布爾表達(dá)式布爾表達(dá)式a or b and not c翻譯為四元式翻譯為四元式:(not , c, _ , T1)(and , b , T1 , T2)(or , a , T2, T3)產(chǎn)生以上結(jié)果的語(yǔ)義子程序?yàn)楫a(chǎn)生以上結(jié)果的語(yǔ)義子程序?yàn)椋篍 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為四元式序?yàn)樗脑叫蛄兄?/p>

33、下一條四元式地列中下一條四元式地址索引，每產(chǎn)生一條址索引，每產(chǎn)生一條四元式，過(guò)程四元式，過(guò)程gen將將nextstart加加1例例：布爾表達(dá)式布爾表達(dá)式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. 作為條件控制的布爾表達(dá)式的翻譯作為條件控制的布爾表達(dá)式的翻譯(1) 考察考察條件語(yǔ)句條件語(yǔ)句: : if E then S1 else S2 E E的作用的作用: : 控制對(duì)控制對(duì)S1和和S2 的選擇的選擇, 其值無(wú)需保留。其值無(wú)需保留。(2) 代碼結(jié)構(gòu)代碼結(jié)構(gòu): :E的代碼的代碼S1的代碼的代碼S2的代碼的代碼(3) E的四元式形式的四元式形式: 全部為條件或無(wú)條件轉(zhuǎn)移指令全部為條件或無(wú)條件轉(zhuǎn)移指令 ( jnz, A1, _ , p )A1為真轉(zhuǎn)為真轉(zhuǎn)p ( j , A1, A2, p ) A

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

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

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

38、的跳轉(zhuǎn)四元式的標(biāo)號(hào)。記錄需要回填的跳轉(zhuǎn)四元式的標(biāo)號(hào)。鏈表的組織方式鏈表的組織方式設(shè)鏈表的頭指針為設(shè)鏈表的頭指針為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)語(yǔ)義變量和過(guò)程、函數(shù)語(yǔ)義變量和過(guò)程、函數(shù) nextquad: 變量，下一個(gè)將形成的四元式地址，變量，下一個(gè)將形成的四元式地址， 初值為初值為1, 每執(zhí)行一次每執(zhí)行一次GEN 自動(dòng)加自動(dòng)加1. m

39、akelist(i): 函數(shù)，創(chuàng)建一個(gè)僅含函數(shù)，創(chuàng)建一個(gè)僅含i的新鏈表，的新鏈表，i為四元式地為四元式地址（標(biāo)號(hào)）址（標(biāo)號(hào)）.merge(p1, p2 ): 函數(shù)過(guò)程函數(shù)過(guò)程, 把以把以p1,p2 為為 鏈?zhǔn)椎膬蓚€(gè)鏈合并回送合并后的鏈?zhǔn)祖準(zhǔn)椎膬蓚€(gè)鏈合并回送合并后的鏈?zhǔn)?backpatch ( p, t ) : 過(guò)程過(guò)程,把鏈?zhǔn)装焰準(zhǔn)譸 所指所指鏈中的四元式第鏈中的四元式第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) 語(yǔ)義子程序語(yǔ)義子程序?qū)ξ姆óa(chǎn)生式稍作修改，引入對(duì)文法產(chǎn)生式稍作修改，引入標(biāo)記非終結(jié)符標(biāo)記非終結(jié)符M，以便在適當(dāng)?shù)臅r(shí)候，以便在適當(dāng)?shù)臅r(shí)候執(zhí)行一個(gè)語(yǔ)義動(dòng)作，記下下一個(gè)要產(chǎn)生四元式標(biāo)號(hào)。執(zhí)行一個(gè)語(yǔ)義動(dòng)作，記下下一個(gè)要產(chǎn)生四元式標(biāo)號(hào)。(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 控制語(yǔ)句的翻譯控制語(yǔ)句的翻譯 1.控制流語(yǔ)句控制流語(yǔ)句

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

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

46、句多增加了一條跳轉(zhuǎn)語(yǔ)句多增加了一條跳轉(zhuǎn)指令指令goto S.next.while-do語(yǔ)句增加了一條語(yǔ)句增加了一條goto S.begin指令指令.兩條語(yǔ)句所做的其他工作也是回填布爾式兩條語(yǔ)句所做的其他工作也是回填布爾式E或其或其它語(yǔ)句中指令地址它語(yǔ)句中指令地址.對(duì)于語(yǔ)句也需要一個(gè)未填寫(xiě)目標(biāo)標(biāo)號(hào)而以后需對(duì)于語(yǔ)句也需要一個(gè)未填寫(xiě)目標(biāo)標(biāo)號(hào)而以后需要回填的轉(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:語(yǔ)句語(yǔ)句 L:語(yǔ)句串語(yǔ)句串 A:賦值語(yǔ)句賦值語(yǔ)句E:布爾表達(dá)式布爾表達(dá)式(3)語(yǔ)義子程序語(yǔ)義子程序( (翻譯模式翻譯模式) )使用有關(guān)鏈表操作的使用有關(guān)鏈表操作的語(yǔ)義變量、函數(shù)和過(guò)程語(yǔ)義變量、函數(shù)和過(guò)程（ nextquad, makelist（）（）, merge( ), backpatch( ) ),E.truelist,E.falselist,S.nextlist,L.nextlist指向需回填的指向需回填的指令鏈表指令鏈表。對(duì)文法稍做修改：對(duì)文法稍做修改：1 1）引入標(biāo)記非終結(jié)符）引入標(biāo)記非終結(jié)符M M，以記錄某些位，以記錄某些位置的四元式標(biāo)號(hào)；置的四

48、元式標(biāo)號(hào)；2 2）引入標(biāo)記非終結(jié)符）引入標(biāo)記非終結(jié)符N N，以生成一條跳轉(zhuǎn)，以生成一條跳轉(zhuǎn)指令和一個(gè)鏈。指令和一個(gè)鏈。 改寫(xiě)后的文法及語(yǔ)義動(dòng)作改寫(xiě)后的文法及語(yǔ)義動(dòng)作 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 時(shí)時(shí) Sn-1 的的 代代 碼碼 Sn 的的 代代 碼碼計(jì)算計(jì)算T：=E的代碼的代碼S1 的的 代代 碼碼S2 的的 代代 碼碼判斷判斷T 的的 代代 碼碼T=C1 L1:T=C2 L2:T=Cn-1 Ln-1:T=其它其它 Ln:TEST:NEXT:(4) 代碼生成過(guò)程代碼生成過(guò)程: 遇到遇到case遇到遇到E of遇到遇到Ci 遇到遇到Si 遇到遇到end利用隊(duì)列利用隊(duì)列QUEUE4. for語(yǔ)句語(yǔ)句(1) 文法文法: : Sfor i := E(1) step E(2) until E(3) do S(1)(2) 代

52、碼結(jié)構(gòu)代碼結(jié)構(gòu): :增量部分增量部分: i:= i + E(2)測(cè)試部分測(cè)試部分: 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) 改寫(xiě)文法與語(yǔ)