編譯原理課件 第 7 講 語(yǔ)法制導(dǎo)翻譯和中間代碼生成(1)

1、源語(yǔ)言程序源語(yǔ)言程序中間代碼中間代碼匯編代碼匯編代碼詞法分析詞法分析語(yǔ)義分析語(yǔ)義分析語(yǔ)法分析語(yǔ)法分析中間代碼生成中間代碼生成代碼生成代碼生成在編譯中的邏輯階段在編譯中的邏輯階段前端處理前端處理后端處理后端處理語(yǔ)義處理語(yǔ)義處理1、使邏輯結(jié)、使邏輯結(jié)構(gòu)簡(jiǎn)單明確構(gòu)簡(jiǎn)單明確2、與機(jī)器相、與機(jī)器相關(guān)的某些實(shí)現(xiàn)關(guān)的某些實(shí)現(xiàn)細(xì)節(jié)放在代碼細(xì)節(jié)放在代碼生成階段生成階段3、可進(jìn)行代、可進(jìn)行代碼優(yōu)化碼優(yōu)化源語(yǔ)言程序源語(yǔ)言程序匯編代碼匯編代碼詞法分析詞法分析語(yǔ)義分析語(yǔ)義分析語(yǔ)法分析語(yǔ)法分析代碼生成代碼生成前端處理前端處理后端處理后端處理 語(yǔ)義處理語(yǔ)義處理類(lèi)型檢查的屬性文法：類(lèi)型檢查的屬性文法： 語(yǔ) 義 規(guī) 則L EE

2、 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.val:=digit.lexval產(chǎn) 生 式綜合屬性綜合屬性val綜合屬性綜合屬性n左部符號(hào)的左部符號(hào)的綜合屬性綜合屬性是從該產(chǎn)生式右部文法符號(hào)的屬性值計(jì)算出來(lái)的；是從該產(chǎn)生式右部文法符號(hào)的屬性值計(jì)算出來(lái)的；n在分析樹(shù)中，如果一個(gè)結(jié)點(diǎn)的某一個(gè)屬性由其子結(jié)點(diǎn)的屬性確定，則稱(chēng)在分析樹(shù)中，如果一個(gè)結(jié)點(diǎn)的某一個(gè)屬性由其子結(jié)點(diǎn)的屬性確定，則稱(chēng)這種屬性為該結(jié)點(diǎn)的這

3、種屬性為該結(jié)點(diǎn)的綜合屬性綜合屬性。產(chǎn)生副作用產(chǎn)生副作用的語(yǔ)義規(guī)則的語(yǔ)義規(guī)則，如打印一個(gè)如打印一個(gè)值、向符號(hào)值、向符號(hào)表中插入信表中插入信息或更新一息或更新一個(gè)全程變量個(gè)全程變量等。等。語(yǔ)義規(guī)則函數(shù)都不具有副作用的語(yǔ)法語(yǔ)義規(guī)則函數(shù)都不具有副作用的語(yǔ)法制導(dǎo)定義稱(chēng)為制導(dǎo)定義稱(chēng)為屬性文法。屬性文法。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的帶注釋的分析樹(shù)的帶注釋的分析樹(shù)如果一個(gè)語(yǔ)法制如果一個(gè)語(yǔ)法制導(dǎo)定義僅僅使用導(dǎo)定義僅僅使用綜

4、合屬性，則稱(chēng)綜合屬性，則稱(chēng)這種語(yǔ)法制導(dǎo)定這種語(yǔ)法制導(dǎo)定義為義為S屬性定義屬性定義。通常采用通常采用自底向自底向上的方法上的方法對(duì)其分對(duì)其分析樹(shù)加注釋?zhuān)次鰳?shù)加注釋?zhuān)磸臉?shù)葉到樹(shù)根，從樹(shù)葉到樹(shù)根，按照語(yǔ)義規(guī)則計(jì)按照語(yǔ)義規(guī)則計(jì)算每個(gè)節(jié)點(diǎn)的屬算每個(gè)節(jié)點(diǎn)的屬性值。性值。生 產(chǎn) 式語(yǔ) 義 規(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(fǎng).in過(guò)程調(diào)用：過(guò)程調(diào)用：將每個(gè)標(biāo)識(shí)將每個(gè)標(biāo)識(shí)

5、符的類(lèi)型信符的類(lèi)型信息登錄到符息登錄到符號(hào)表的相關(guān)號(hào)表的相關(guān)項(xiàng)中項(xiàng)中 產(chǎn) 生 式語(yǔ) 義 規(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=realrealid2id1id3.，addtype(id3.entry,L.in)addtype(id2.entry,L.in)addtype(id1.entry,L.in)計(jì)算

6、方法計(jì)算方法：自左向右掃描逆波蘭式，遇到運(yùn)算對(duì)象則入棧，：自左向右掃描逆波蘭式，遇到運(yùn)算對(duì)象則入棧，遇到算符則將相應(yīng)數(shù)目的運(yùn)算對(duì)象出棧計(jì)算后結(jié)果入棧遇到算符則將相應(yīng)數(shù)目的運(yùn)算對(duì)象出棧計(jì)算后結(jié)果入棧。復(fù)雜性：復(fù)雜性：壓棧的可能是地址（如變量賦值），不是值；壓棧的可能是地址（如變量賦值），不是值；棧中不一定產(chǎn)生結(jié)果。棧中不一定產(chǎn)生結(jié)果。例例a:=b*c+b*c將表達(dá)式將表達(dá)式b*c+b*c的值送到變量的值送到變量a(地址地址)，棧中無(wú)結(jié)果值。棧中無(wú)結(jié)果值。 把下述產(chǎn)生式定義的算術(shù)表達(dá)式映射到后綴式把下述產(chǎn)生式定義的算術(shù)表達(dá)式映射到后綴式表示：表示： EE+T E T T T F T F F (E)

7、 F a E = ET+ E = T T = TF T = F F = E F = a 產(chǎn)生式 翻譯成分 EE+T E T T T F T F F (E) F a E = ET+ E = T T = TF T = F F = E F = a 產(chǎn)生式 翻譯成分將下列語(yǔ)句翻譯成后綴式：后綴式： if xy then y=y+z else x=x+z錯(cuò)誤的翻譯：錯(cuò)誤的翻譯： （ 翻譯成：翻譯成：xyyzy+ =z+xx=正確的翻譯：正確的翻譯：x yy zy+=z +x x=L1JzJzL2JmpJmp L1 L2:=a+*bcbd三元式表示三元式表示樹(shù)形表示樹(shù)形表示返回指向返回指向id的指針的指針

8、輸出四元式輸出四元式生成臨時(shí)變量生成臨時(shí)變量E.place:值值E的位置的位置(2) (3) 返回返回(4) E - E1 E.place:=newtemp; emit(E.place“:=”“uminus” E1.place)(5) E( E1) E.place:= E1.place(6) Eid P:=lookup(); if P nil then E.place:=P else error返回返回# A:=-B*(C+D)#查看語(yǔ)意義子程序查看語(yǔ)意義子程序13查看語(yǔ)意義子程序查看語(yǔ)意義子程序46 棧棧 余留輸入字符余留輸入字符 語(yǔ)意義動(dòng)作語(yǔ)意義動(dòng)作 產(chǎn)生的四元式產(chǎn)生的四元式

9、#idA :=-B*(C+D)#idA := -B*(C+D)#idA :=- B*(C+D)#idA :=-idB *(C+D)#idA :=-EB *(C+D)# Sub6#idA :=ET1 *(C+D)# Sub4 (，B， ，T1）#idA := ET1 * (C+D)#idA := ET1 * ( C+D)#idA := ET1 * (idC +D)#idA := ET1 * (EC +D)# Sub6#idA := ET1 * (EC+ D)#查看語(yǔ)意義子程序查看語(yǔ)意義子程序13查看語(yǔ)意義子程序查看語(yǔ)意義子程序46 棧棧 余留輸入字符余留輸入字符 語(yǔ)意義動(dòng)作語(yǔ)意義動(dòng)作 產(chǎn)生的四元

10、式產(chǎn)生的四元式#idA := ET1 * (EC+ D)#idA := ET1 * (EC+idD )#idA := ET1 * (EC+ED )# Sub6#idA := ET1 * (ET2 )# Sub2 (+，C，D，T2）#idA := ET1 * (ET2) #idA := ET1 * ET2 # Sub5#idA := ET3 # Sub3 (*，T1，T2，T3）#S # Sub1 (:=，T3， ，A）(1) （ ， B ， ， T1 ）(2) （ +， C ， D， T2 ）(3) （ *， T1 ，T2， T3 ）(4) （ :=，T3 ， ， A ）E.false控制語(yǔ)

11、句控制語(yǔ)句 Sif E then S1 else S2 E 的代碼的代碼 E.true E.true: S1的代碼的代碼 goto outE.false: S2的代碼的代碼out:1 . 把條件轉(zhuǎn)移的布爾表達(dá)式把條件轉(zhuǎn)移的布爾表達(dá)式 E 翻譯成僅含翻譯成僅含 條件真條件真 轉(zhuǎn)轉(zhuǎn) 和和 無(wú)條件無(wú)條件 轉(zhuǎn)轉(zhuǎn) 的四元式的四元式 E：a rop b ?if a rop b goto E.true goto E.false如如 ：ab or cd and ef 可可 翻譯成如下四元式：翻譯成如下四元式：(1) if ab goto E.true(2) goto (3)(3) if cd goto (5)

12、(4) goto E.false(5) if ef goto E.true(6) goto E.false (翻譯翻譯 不是最優(yōu)不是最優(yōu))2拉鏈返填拉鏈返填 （10） goto L （10）goto 0 鏈尾鏈尾 （10）（20） goto L （20）goto 10 （30） goto L (30) goto 20 鏈頭鏈頭（30）（40）L： （40）L: ?語(yǔ)句語(yǔ)句 if ab or cd and ef then S1 else S2的四元式的四元式(1) if ab goto (7) (E.true ) (1)和和(5）(2) goto (3) 拉鏈拉鏈（真）（真）(3) if cd

13、goto (5)(4) goto (p+1)(E.false)(4) 和和(6)(5) if ef goto (7)拉鏈拉鏈（假）（假）(6) goto (p+1)(7)( S1的四元式的四元式 (p-1) ）(p) goto (q)(p+1) (S2的四元式的四元式(q-1) ）(q)(1) if ab goto (E.true )(2) goto (3)(3) if cd goto (5)(4) goto (E.false)(5) if ef goto (E.true ) (6) goto (E.false) (E.true)( S1的四元式序列的四元式序列 ）(p) goto (q)(E

14、.false) (S2的四元式序列的四元式序列(q-1) ）(q)語(yǔ)義描述使用的變量和過(guò)程：語(yǔ)義描述使用的變量和過(guò)程： E.true ： “真真”鏈，鏈， E.false ： “假假”鏈鏈 。 E.codebegin ： E 的第一個(gè)四元式的第一個(gè)四元式 Nextstat： 下一四元式地址下一四元式地址 過(guò)程：過(guò)程： emit( ) 輸出一條四元式輸出一條四元式 merge(p1, p2) 把把 p1的鏈頭填在的鏈頭填在p2 的鏈尾的鏈尾例：例： merge(p1, p2)(p10) 0 p1 鏈鏈 (p100) p10(p1) p100(p20) 0p2 鏈鏈 (p200) p20(p2)

15、p200 backpatch(p,t) 把把 p 所鏈接的每個(gè)四元式所鏈接的每個(gè)四元式的第四區(qū)段都填為的第四區(qū)段都填為t語(yǔ)義描述使用的變量和過(guò)程：語(yǔ)義描述使用的變量和過(guò)程： E.true ： “真真”鏈，鏈， E.false ： “假假”鏈鏈 。 E.codebegin ： E 的第一個(gè)四元式的第一個(gè)四元式 Nextstat： 下一四元式地址下一四元式地址 過(guò)程：過(guò)程： emit( ) 輸出一條四元式輸出一條四元式 merge(p1, p2) 把把 p1的鏈頭填在的鏈頭填在p2 的鏈尾的鏈尾例：例： merge(p1, p2)(p10) 0 p1 鏈鏈 (p100) p10(p1) p100(

16、p20) p100p2 鏈鏈 (p200) p20(p2) p200 backpatch(p,t) 把把 p 所鏈接的每個(gè)四元式所鏈接的每個(gè)四元式的第四區(qū)段都填為的第四區(qū)段都填為t自下而上分析中的一種翻譯方案：自下而上分析中的一種翻譯方案：(1) EE1 or E2 backpatch(E1.false, E2.Codebegin); E.Codebegin:= E1.codebegin; E.true:=merge(E1.true, E2.true) E.false:= E2.false(2) EE1 and E2 backpatch(E1.true, E2.codebegin); E.Codebegin:= E1.codebegin; E.true:= E2.true; E.false:= merge(E1.false, E2false);(3) Enot E1 E.true:= E1.false; E.Codebegin:= E1.codebegin; E.false:= E1.true(4) E(E1) E.true:= E1.true; E.Codebegin:= E1.co