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

1、源語言程序源語言程序中間代碼中間代碼匯編代碼匯編代碼詞法分析詞法分析語義分析語義分析語法分析語法分析中間代碼生成中間代碼生成代碼生成代碼生成在編譯中的邏輯階段在編譯中的邏輯階段前端處理前端處理后端處理后端處理語義處理語義處理1、使邏輯結(jié)、使邏輯結(jié)構(gòu)簡單明確構(gòu)簡單明確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)化源語言程序源語言程序匯編代碼匯編代碼詞法分析詞法分析語義分析語義分析語法分析語法分析代碼生成代碼生成前端處理前端處理后端處理后端處理 語義處理語義處理類型檢查的屬性文法：類型檢查的屬性文法： 語 義 規(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左部符號的左部符號的綜合屬性綜合屬性是從該產(chǎn)生式右部文法符號的屬性值計(jì)算出來的；是從該產(chǎn)生式右部文法符號的屬性值計(jì)算出來的；n在分析樹中，如果一個結(jié)點(diǎn)的某一個屬性由其子結(jié)點(diǎn)的屬性確定，則稱在分析樹中，如果一個結(jié)點(diǎn)的某一個屬性由其子結(jié)點(diǎn)的屬性確定，則稱這種屬性為該結(jié)點(diǎn)的這

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

4、合屬性，則稱綜合屬性，則稱這種語法制導(dǎo)定這種語法制導(dǎo)定義為義為S屬性定義屬性定義。通常采用通常采用自底向自底向上的方法上的方法對其分對其分析樹加注釋，即析樹加注釋，即從樹葉到樹根，從樹葉到樹根，按照語義規(guī)則計(jì)按照語義規(guī)則計(jì)算每個節(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過程調(diào)用：過程調(diào)用：將每個標(biāo)識將每個標(biāo)識

5、符的類型信符的類型信息登錄到符息登錄到符號表的相關(guān)號表的相關(guān)項(xiàng)中項(xiàng)中 產(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=realrealid2id1id3.，addtype(id3.entry,L.in)addtype(id2.entry,L.in)addtype(id1.entry,L.in)計(jì)算

6、方法計(jì)算方法：自左向右掃描逆波蘭式，遇到運(yùn)算對象則入棧，：自左向右掃描逆波蘭式，遇到運(yùn)算對象則入棧，遇到算符則將相應(yīng)數(shù)目的運(yùn)算對象出棧計(jì)算后結(jié)果入棧遇到算符則將相應(yīng)數(shù)目的運(yùn)算對象出棧計(jì)算后結(jié)果入棧。復(fù)雜性：復(fù)雜性：壓棧的可能是地址（如變量賦值），不是值；壓棧的可能是地址（如變量賦值），不是值；棧中不一定產(chǎn)生結(jié)果。棧中不一定產(chǎn)生結(jié)果。例例a:=b*c+b*c將表達(dá)式將表達(dá)式b*c+b*c的值送到變量的值送到變量a(地址地址)，棧中無結(jié)果值。棧中無結(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)生式 翻譯成分將下列語句翻譯成后綴式：后綴式： if xy then y=y+z else x=x+z錯誤的翻譯：錯誤的翻譯： （ 翻譯成：翻譯成：xyyzy+ =z+xx=正確的翻譯：正確的翻譯：x yy zy+=z +x x=L1JzJzL2JmpJmp L1 L2:=a+*bcbd三元式表示三元式表示樹形表示樹形表示返回指向返回指向id的指針的指針

8、輸出四元式輸出四元式生成臨時變量生成臨時變量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)#查看語意義子程序查看語意義子程序13查看語意義子程序查看語意義子程序46 棧棧 余留輸入字符余留輸入字符 語意義動作語意義動作 產(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)#查看語意義子程序查看語意義子程序13查看語意義子程序查看語意義子程序46 棧棧 余留輸入字符余留輸入字符 語意義動作語意義動作 產(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控制語

11、句控制語句 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) 和和 無條件無條件 轉(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: ?語句語句 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)語義描述使用的變量和過程：語義描述使用的變量和過程： E.true ： “真真”鏈，鏈， E.false ： “假假”鏈鏈 。 E.codebegin ： E 的第一個四元式的第一個四元式 Nextstat： 下一四元式地址下一四元式地址 過程：過程： 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 所鏈接的每個四元式所鏈接的每個四元式的第四區(qū)段都填為的第四區(qū)段都填為t語義描述使用的變量和過程：語義描述使用的變量和過程： E.true ： “真真”鏈，鏈， E.false ： “假假”鏈鏈 。 E.codebegin ： E 的第一個四元式的第一個四元式 Nextstat： 下一四元式地址下一四元式地址 過程：過程： 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 所鏈接的每個四元式所鏈接的每個四元式的第四區(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