第8章 語法制導(dǎo)翻譯及中間代碼生成(lly2)

1、第八章第八章 語法制導(dǎo)翻譯和中間代碼語法制導(dǎo)翻譯和中間代碼n中間代碼中間代碼：n常見語句的翻譯常見語句的翻譯（控制語句，控制語句，循循環(huán)，數(shù)組環(huán)，數(shù)組 語義分析語義分析語義分析的任務(wù)：語義分析的任務(wù)：在詞法分析和語法分析的基礎(chǔ)上，分析所寫源程序的含義，在理解含義的基礎(chǔ)上為生成相應(yīng)的目標(biāo)代碼作好準(zhǔn)備或直接生成目標(biāo)代碼。1）靜態(tài)語義檢查靜態(tài)語義檢查例：類型檢查、運(yùn)算、維數(shù)、越界2）語義翻譯語義翻譯（具體的動(dòng)作具體的動(dòng)作）例：語句的翻譯（中間代碼中間代碼或目標(biāo)代碼生成）語義分析方法：語義分析方法：大多編譯器采用語法制導(dǎo)翻譯語法制導(dǎo)翻譯方法語義分析工具：語義分析工具：在在語法制導(dǎo)翻譯方法中，常用屬性文

2、法屬性文法來說明程序設(shè)計(jì)語言語義 8.1 屬性文法屬性文法屬性文法屬性文法(attribute grammar)是一個(gè)三元是一個(gè)三元組組:A=(G,V,F)表達(dá)式文法表達(dá)式文法 ET+T| T or T T n | true|falsetruefalse類型檢查類型檢查的屬性文法：的屬性文法： （值的屬性值的屬性？ 設(shè)計(jì)?） 語 義 規(guī) 則 L EE E1+TE TT T1 * FT FF (E)F digitPrint(E.val) E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val F.val T.val:=F.valF.val:=E.valF.v

3、al:=digit.lexval產(chǎn) 生 式綜合屬性val綜合屬性綜合屬性n在分析樹中，如果一個(gè)結(jié)點(diǎn)的某一個(gè)屬性在分析樹中，如果一個(gè)結(jié)點(diǎn)的某一個(gè)屬性由其子結(jié)點(diǎn)的屬由其子結(jié)點(diǎn)的屬性確定性確定，則稱這種屬性為該結(jié)點(diǎn)的綜合屬性，則稱這種屬性為該結(jié)點(diǎn)的綜合屬性。過程過程Print打印打印E表達(dá)表達(dá)式式 的值。的值。以以3*5+4為例說明為例說明 在語法制導(dǎo)定義中，一條語義規(guī)則完成一個(gè)計(jì)算屬性在語法制導(dǎo)定義中，一條語義規(guī)則完成一個(gè)計(jì)算屬性值的動(dòng)作。值的動(dòng)作。digit是終結(jié)符，只使用綜合屬性，且其屬是終結(jié)符，只使用綜合屬性，且其屬性值由詞法分析器提供，通常不要計(jì)算屬性值性值由詞法分析器提供，通常不要計(jì)算屬

4、性值。LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的帶注釋的分析樹的帶注釋的分析樹如果一個(gè)語法制如果一個(gè)語法制導(dǎo)定義僅僅使用導(dǎo)定義僅僅使用綜合屬性，則稱綜合屬性，則稱這種語法制導(dǎo)定這種語法制導(dǎo)定義為義為S屬性定義屬性定義。通常采用通常采用自底向自底向上的方法上的方法對(duì)其分對(duì)其分析樹加注釋，即析樹加注釋，即從樹葉到樹根，從樹葉到樹根，按照語義規(guī)則計(jì)按照語義規(guī)則計(jì)算每個(gè)節(jié)點(diǎn)的屬算每個(gè)節(jié)點(diǎn)的屬性值。性值。繼承屬性繼承屬性n一個(gè)結(jié)

5、點(diǎn)的繼承屬性值是由此結(jié)點(diǎn)的父結(jié)點(diǎn)和父結(jié)點(diǎn)和/或或兄弟結(jié)點(diǎn)的某些屬性來決定兄弟結(jié)點(diǎn)的某些屬性來決定的。生 產(chǎn) 式語 義 規(guī) 則D TL T int T real L L1,idL idL.in:=T.typeT.type=integerT.type:=real L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)繼承屬性繼承屬性L.in以說明語句以說明語句real a1,a2,a3為例為例過程過程addtypeaddtype是把每個(gè)標(biāo)是把每個(gè)標(biāo)志符的類型志符的類型信息登錄在信息登錄在符號(hào)表中相符號(hào)表中相關(guān)項(xiàng)中。關(guān)項(xiàng)中。語句語句real

6、 a1,a2,a3的分析樹，采用的分析樹，采用自上自上而下而下的分析方法的分析方法 產(chǎn) 生 式語 義 規(guī) 則D TL T int T real L L1,idL idL.in:=T.typeT.type=integerT.type:=real L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)DL.in= realL.in= realL.in= realT.type=realreala2a1a3.， 8.2 語法制導(dǎo)翻譯概論語法制導(dǎo)翻譯概論n在語法分析過程中，隨著分析的步步進(jìn)展，根據(jù)每個(gè)產(chǎn)在語法分析過程中，隨著分析的步步進(jìn)展，根據(jù)

7、每個(gè)產(chǎn)生式所對(duì)應(yīng)的生式所對(duì)應(yīng)的語義子程序語義子程序（或語義規(guī)則描述的（或語義規(guī)則描述的語義動(dòng)作語義動(dòng)作）進(jìn)行翻譯的辦法稱作進(jìn)行翻譯的辦法稱作語法制導(dǎo)翻譯語法制導(dǎo)翻譯。說明說明：定義理解：定義理解： 語法制導(dǎo)翻譯是在語法制導(dǎo)翻譯是在語法分析過程語法分析過程中同時(shí)進(jìn)行的；中同時(shí)進(jìn)行的； 一旦用到某個(gè)產(chǎn)生式一旦用到某個(gè)產(chǎn)生式推導(dǎo)推導(dǎo)/歸約歸約時(shí)，調(diào)用相應(yīng)的時(shí)，調(diào)用相應(yīng)的語義子語義子程序程序進(jìn)行翻譯。進(jìn)行翻譯。目的目的：用語法制導(dǎo)翻譯的方法來說明程序設(shè)計(jì)語言的結(jié)構(gòu)：用語法制導(dǎo)翻譯的方法來說明程序設(shè)計(jì)語言的結(jié)構(gòu)怎樣被翻譯成中間形式怎樣被翻譯成中間形式參見參見P.157-159對(duì)表達(dá)式對(duì)表達(dá)式2+3*5進(jìn)

8、行的分析進(jìn)行的分析8.3 中間代碼的形成中間代碼的形成中間代碼的常見形式：中間代碼的常見形式：逆波蘭記號(hào)逆波蘭記號(hào)三元式（樹形表示）三元式（樹形表示）四元式四元式逆波蘭記號(hào)（逆波蘭記號(hào)（后綴式后綴式）結(jié)構(gòu)特點(diǎn)結(jié)構(gòu)特點(diǎn)：將：將運(yùn)算對(duì)象運(yùn)算對(duì)象寫在寫在前面前面，把，把運(yùn)算符號(hào)運(yùn)算符號(hào)寫在寫在后面后面表達(dá)式逆波蘭式a+bab+a+b*cabc*+(a+b)*cab+c*a:=b*c+b*d？計(jì)算方法計(jì)算方法：自左向右掃描逆波蘭式，遇到運(yùn)算對(duì)象則：自左向右掃描逆波蘭式，遇到運(yùn)算對(duì)象則入棧，遇到算符則將相應(yīng)數(shù)目的運(yùn)算對(duì)象出棧計(jì)算后入棧，遇到算符則將相應(yīng)數(shù)目的運(yùn)算對(duì)象出棧計(jì)算后結(jié)果入棧結(jié)果入棧。特點(diǎn)特點(diǎn)：

9、1）不需要括號(hào)（已考慮結(jié)合性與優(yōu)先性）；）不需要括號(hào)（已考慮結(jié)合性與優(yōu)先性）； 2）適合計(jì)算機(jī)運(yùn)算，但不適合人。）適合計(jì)算機(jī)運(yùn)算，但不適合人。逆波蘭記號(hào)的擴(kuò)充用途逆波蘭記號(hào)的擴(kuò)充用途iiGotoLLjumpifEthenS1elseS2ES1S2￥AnmnmAsubs復(fù)雜性：壓棧的可能是地址（如變量賦值），不是值；棧中不一定產(chǎn)生結(jié)果。逆波蘭示例（逆波蘭示例（以算術(shù)表達(dá)式以算術(shù)表達(dá)式a+a a最左推導(dǎo)說明最左推導(dǎo)說明）把下述產(chǎn)生式定義的算術(shù)表達(dá)式映射到后綴波蘭表示：把下述產(chǎn)生式定義的算術(shù)表達(dá)式映射到后綴波蘭表示： EE+T E T T TF T F F (E) F a E=ET+ E=T T=T

10、F T=F F=E F=a 產(chǎn)生式 翻譯成分n確定輸入確定輸入a+a a的輸出：的輸出：(E,E)(E+T,ET+)(T+T,TT+)(F+T,FT+)(a+T,aT+)(a+TF,aFF+)(a+FF,aFF+)(a+aF,aaF+)(a+aa,aaa+)三元式和樹形表示三元式和樹形表示n格式格式：( (算符算符, , 第一運(yùn)算對(duì)象第一運(yùn)算對(duì)象, , 第二運(yùn)算對(duì)象第二運(yùn)算對(duì)象) )注意注意：運(yùn)算結(jié)果用三元式編號(hào)表示。：運(yùn)算結(jié)果用三元式編號(hào)表示。n如如：a:=b*c+b*d(1) (*,b,c)(2) (*,b,d)(3) (+,(1),(2)(4) (:=,(3),a):=a+*bcbd三元

11、式表示三元式表示樹形表示樹形表示四元式四元式n格式格式：( (算符算符, , 第一運(yùn)算對(duì)象第一運(yùn)算對(duì)象, , 第二運(yùn)算對(duì)象第二運(yùn)算對(duì)象, , 結(jié)果結(jié)果) )注意注意：運(yùn)算結(jié)果用臨時(shí)變量表示。n如：a:=ba:=b* *c+bc+b* *d d (1) (1)( (* *,b,c,t1),b,c,t1) (2) (2)( (* *,b,d,t2),b,d,t2) (3) (3)(+,t1,t2,t3)(+,t1,t2,t3) (4) (4)(:=,t3,a)(:=,t3,a)n特點(diǎn)特點(diǎn):類似于三地址指令類似于三地址指令利于優(yōu)化和代碼生成利于優(yōu)化和代碼生成四元式的直觀表示四元式的直觀表示na:=b

12、a:=b* *c+bc+b* *d d (1) (1)( (* *,b,c,t1),b,c,t1) (2) (2)( (* *,b,d,t2),b,d,t2) (3) (3)(+,t1,t2,t3)(+,t1,t2,t3) (4) (4)(:=,t3, ,a)(:=,t3, ,a)注意注意：x:=b*c的四元式表示（三元式，后綴式）四元式表示（三元式，后綴式）？四元式的擴(kuò)展四元式的擴(kuò)展n(jump, , ,L)(jump, , ,L) goto L goto Ln(jrop,B,C,L)(jrop,B,C,L) if B rop C goto L if B rop C goto Ln(jnz,

13、A, ,L) if A then L(jnz,A, ,L) if A then L思考思考：if A then L0 else L1 if A then L0 else L1 四元式四元式？t1:=b*ct2:=b*dt3:=t1+t2a:=t38.4 簡單賦值語句的翻譯簡單賦值語句的翻譯四元式形式四元式形式 : : t :=arg1 op arg2t :=arg1 op arg2語義屬性語義屬性：, E.place函數(shù)函數(shù)：lookup() ;過程過程：emit(t := arg1 op arg2);函數(shù)函數(shù)： newtemp;返回指向id的指針輸出四元式生成臨時(shí)

14、變量，返回指針E.place:值E的位置(1) S id := E P:=lookup () ; if P nil then emit( P“:=”E.place) else error (2) EE1+E2 / -，* ，/ E.place:= newtemp; emit(E.place“:=” E1.place“+”E2.place) (3) E - E1 E.place:=newtemp; emit(E.place“:=”“uminus” E1.place)(4) E( E1) E.place:= E1.place(5) Eid P:=lookup(); if

15、 P nil then E.place:=P else errorx=a+b-c 例（例（有二義，設(shè)有二義，設(shè)+優(yōu)先，自下而上分析優(yōu)先，自下而上分析）思考思考：人如何處理？人的思維與語義子程序設(shè)計(jì)關(guān)系？人如何處理？人的思維與語義子程序設(shè)計(jì)關(guān)系？產(chǎn)生式和語義描述產(chǎn)生式和語義描述（簡單算術(shù)表達(dá)式賦值語句四元式）翻譯簡單算術(shù)表達(dá)式賦值語句四元式）翻譯語法制導(dǎo)翻譯思想語法制導(dǎo)翻譯思想8.5 布爾表達(dá)式到四元式的翻譯 布爾表達(dá)式的作用布爾表達(dá)式的作用 作為控制語句的條件表達(dá)式作為控制語句的條件表達(dá)式 用于邏輯計(jì)值用于邏輯計(jì)值EEE EE E (E) i rop j i注：注： rop 為關(guān)系運(yùn)算符：為關(guān)

16、系運(yùn)算符：= =， ，=，=， 為為“與與”運(yùn)算；運(yùn)算；為為“或或”運(yùn)算；運(yùn)算； 為為“非非”運(yùn)算運(yùn)算 結(jié)合性為左結(jié)合性結(jié)合性為左結(jié)合性 優(yōu)先級(jí)別為：優(yōu)先級(jí)別為： , rop ， 布爾表達(dá)式的計(jì)值方法布爾表達(dá)式的計(jì)值方法 方法一：方法一： 逐步計(jì)算逐步計(jì)算 方法二：方法二： 優(yōu)化計(jì)算優(yōu)化計(jì)算例如：例如：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 思考思考：

17、 優(yōu)化后如何翻譯為四元式？優(yōu)化后如何翻譯為四元式？ 作為作為邏輯計(jì)值邏輯計(jì)值的布爾表達(dá)式的翻譯的布爾表達(dá)式的翻譯例如例如：將：將 ABC!=D 翻譯成四元式的形式翻譯成四元式的形式 （逐步計(jì)算）逐步計(jì)算）（ !=， C， D， T1 ）（ ， B， T1， T2 ）（ ， A， T2， T3 ）思考思考： 優(yōu)化法如何翻譯為四元式？優(yōu)化法如何翻譯為四元式？ 布爾表達(dá)式布爾表達(dá)式的翻譯的翻譯 下面我們來觀察下面我們來觀察 “if-語句語句” 和和 “while-語句語句”中布爾表達(dá)式的作用：中布爾表達(dá)式的作用：僅僅用于執(zhí)行流程的控制僅僅用于執(zhí)行流程的控制 if E then S1 else S2

18、while E do SE的四元式代碼的四元式代碼S1的四元式代碼的四元式代碼GOTO L S2的四元式代碼的四元式代碼T TR RU UE EF FA AL LS SE EE的四元式代碼的四元式代碼S的四元式代碼的四元式代碼 GOTO L T TR RU UE EF FA AL LS SE E返回思考思考：若無：若無GOTO L，結(jié)果會(huì)如何？，結(jié)果會(huì)如何？ 我們通過觀察我們通過觀察 “if-語句語句” 和和 “while-語句語句”中布爾表達(dá)式的作用可以知道：中布爾表達(dá)式的作用可以知道：E的四元式代碼的四元式代碼T TR RU UE EF FA AL LS SE EE的真出口，用的真出口，用

19、 E.true 表示表示E的假出口，用的假出口，用 E.false 表示表示說明說明：在控制語句中：在控制語句中布爾表達(dá)式布爾表達(dá)式常采用常采用優(yōu)化法優(yōu)化法進(jìn)行翻譯進(jìn)行翻譯優(yōu)優(yōu)化化計(jì)計(jì)算算 A B A B A解釋為：解釋為： if A then TRUE else B解釋為：解釋為： if A then B else FALSE解釋為：解釋為： if A then FALSE else TRUE EE1E2 E1的的“真出口真出口”就是就是E2的第一個(gè)四元式編號(hào)；的第一個(gè)四元式編號(hào)； E1的的“假出口假出口”就是就是E的的“假出口假出口”； E2的的“真真/假出口假出口”就是就是E的的“真真/

20、假出口假出口”E E1E2 E1的的“真出口真出口”就是就是E的的“真出口真出口” ； E1的的“假出口假出口”就是就是E2的第一個(gè)四元式編號(hào)；的第一個(gè)四元式編號(hào)； E2的的“真真/假出口假出口”就是就是E的的“真真/假出口假出口” E E1 E1的的“真出口真出口”就是就是E的的“假出口假出口” ； E1的的“假出口假出口”就是就是E的的“真出口真出口” ； （ jnz ，A， ， p）若若A為真，則轉(zhuǎn)到第為真，則轉(zhuǎn)到第p號(hào)四元式去執(zhí)行號(hào)四元式去執(zhí)行（ jrop，A，B， p）若若A rop B為真，則到第為真，則到第p號(hào)四元式去執(zhí)行號(hào)四元式去執(zhí)行（ j ， ， ， p） 無條件轉(zhuǎn)到第無條件

21、轉(zhuǎn)到第p號(hào)四元式去執(zhí)行號(hào)四元式去執(zhí)行為了翻譯布爾表達(dá)式，我們引入下面三種四元式：為了翻譯布爾表達(dá)式，我們引入下面三種四元式：思考思考：if ABD then x:=y+z else x := y-z 如如何翻譯為四元式？何翻譯為四元式？E的四元式代碼的四元式代碼S1的四元式代碼的四元式代碼GOTO L S2的四元式代碼的四元式代碼T TR RU UE EF FA AL LS SE E if E then S1 else S2if ABD then x:=y+z else x := y-z100 （jnz，A， ，104） ； A的的“真出口真出口”101 （j ， ， ，102） ； A的的“

22、假出口假出口”102 （j ，B，D，104） ； BD的的“真出口真出口”103 （j ， ， ，107） ； Bn ) then x := x + y; else x := x-y; y := y*2; end思考題目：給出詳細(xì)的翻譯步驟？思考題目：給出詳細(xì)的翻譯步驟？while E do SE的四元式代碼的四元式代碼S的四元式代碼的四元式代碼 GOTO L T TR RU UE EF FA AL LS SE Ewhile ( A B C ) do begin k := k+1; if ( mn ) then x := x + y; else x := x-y; y := y*2; end

23、100 ( jnz , A , , 102 )101 ( j , , , 104 )102 ( jnz , B , , 106 )103 ( j , , , 104 )104 ( jnz , C , , 106 )105 ( j , , , 118 )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 ( :

24、= , T3, , x )115 ( * , y , 2 , T4 )116 ( := , T4, , y )117 ( j , , , 100 )118FOR循環(huán)翻譯C/C+語言語言 語句語句 for (E1；E2；E3) S 的翻譯的翻譯執(zhí)行流程如下執(zhí)行流程如下：語義解釋如下：語義解釋如下： E1SE3 E20YN E1L1: if E20 then goto L3 else goto L4 L2: E3 goto L1L3: S goto L2L4: 總結(jié)注意注意：語句翻譯框架語句翻譯框架由語句由語句執(zhí)行流程執(zhí)行流程與與從左到右掃描從左到右掃描決定決定C/C+語言語言語語 句句 for

25、(E1；E2；E3) S 的的 翻翻 譯譯 框框 架架 E1 的四元式代碼的四元式代碼(j , , , L1 )(jnz, E2, , L3 )E3 的四元式代碼的四元式代碼(j , , , L2 )(j , , , L4 )S1 的四元式代碼的四元式代碼L1總結(jié) E1L1: if E20 then goto L3 else goto L4 L2: E3 goto L1L3: S goto L2L4: E2 的四元式代碼的四元式代碼L2L3L4例例： for (i=0;i5; i=i+1) x=x+10; x=x-100;其他語言其他語言 forfor語句的翻譯語句的翻譯例例(BASIC：翻譯

26、過程與具體語言語義相關(guān)） P:=0 P:=0 for i:=1 to 20 do P:=P+10 for i:=1 to 20 do P:=P+10例例(ALGOL ：翻譯過程與具體語言語義相關(guān)）for i:=1 step 1 until 20 do P:=P+10for i:=1 step 1 until 20 do P:=P+10參見參見:174 :174 注意注意：語句翻譯框架語句翻譯框架由語句由語句執(zhí)行流程執(zhí)行流程與與從左到右掃描從左到右掃描決定決定數(shù)組元素到四元式的翻譯數(shù)組元素到四元式的翻譯下標(biāo)變量（數(shù)組元素）的地址計(jì)算下標(biāo)變量（數(shù)組元素）的地址計(jì)算數(shù)組的存貯方式有兩種： 按行存貯。

27、 例如：C/C+；PASCLA；ALGOL等 按列存貯 。 例如： FORTRAN 我們假定我們假定按行存貯按行存貯，每個(gè)，每個(gè)數(shù)組元素占一個(gè)字?jǐn)?shù)組元素占一個(gè)字，且機(jī)，且機(jī)器是按器是按字編址字編址的，下標(biāo)從的，下標(biāo)從1開始開始思考思考:A20, AiA20, Ai 元素的地址元素的地址? ?A1020, Ai, jA1020, Ai, j 元素的地址元素的地址? ? 對(duì)于一個(gè)對(duì)于一個(gè)d1d2dn的的n維數(shù)組維數(shù)組A的數(shù)組元素的數(shù)組元素A i1, i2, , in 的地址計(jì)算如下的地址計(jì)算如下(其中其中a為數(shù)組的起地為數(shù)組的起地) ：D = a + (i1 1)d2d3dn + (i2 1)d3d4dn + (in-1 - 1)dn + (in 1) = a - (d2d3dn + d3d4dn + + dn + 1) + (i1d2d3dn + i2d3d4dn + + in-1dn + in )令：令： C = d2d3dn +