編譯原理總復(fù)習(xí)chap8

1、第 1 頁(yè)u沒有標(biāo)準(zhǔn)的方法來說明語(yǔ)言的靜態(tài)語(yǔ)義沒有標(biāo)準(zhǔn)的方法來說明語(yǔ)言的靜態(tài)語(yǔ)義u對(duì)于各種語(yǔ)言，靜態(tài)語(yǔ)義分析的種類和總量的變對(duì)于各種語(yǔ)言，靜態(tài)語(yǔ)義分析的種類和總量的變化范圍很大?；秶艽?。屬性文法屬性文法u確定語(yǔ)言實(shí)體的屬性，寫成屬性等式進(jìn)行計(jì)算，確定語(yǔ)言實(shí)體的屬性，寫成屬性等式進(jìn)行計(jì)算，并描述屬性的計(jì)算如何與語(yǔ)言的文法規(guī)則相關(guān)。并描述屬性的計(jì)算如何與語(yǔ)言的文法規(guī)則相關(guān)。u應(yīng)用比較廣的應(yīng)用比較廣的：語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)翻譯u編譯的語(yǔ)義分析編譯的語(yǔ)義分析第 2 頁(yè)靜態(tài)語(yǔ)義分析的環(huán)境靜態(tài)語(yǔ)義分析的環(huán)境符號(hào)表符號(hào)表第 3 頁(yè)8.1 屬性及屬性文法屬性及屬性文法8.2 語(yǔ)法制導(dǎo)翻譯概論語(yǔ)法制導(dǎo)翻譯概

2、論8.3 中間代碼的形式中間代碼的形式第 4 頁(yè)8.1 屬性及屬性文法屬性及屬性文法第 5 頁(yè)定義定義 屬性文法屬性文法(Attribute Grammar) 既描述程序設(shè)計(jì)語(yǔ)言的語(yǔ)法既描述程序設(shè)計(jì)語(yǔ)言的語(yǔ)法, ,又描述語(yǔ)義。又描述語(yǔ)義。1968年由年由D.E.Knuth 提出提出第 6 頁(yè)例例 關(guān)于表達(dá)式的文法關(guān)于表達(dá)式的文法 ：ET+T| T or T Tnum|true|false規(guī)定：規(guī)定：參加參加”運(yùn)算的：運(yùn)算的：int型；參加型；參加 “or”運(yùn)算的運(yùn)算的: bool型型寫出寫出表達(dá)式類型的屬性文法表達(dá)式類型的屬性文法P P156屬性文法的思想：屬性文法的思想：n對(duì)每個(gè)文法符號(hào)引進(jìn)

3、相關(guān)的屬性符號(hào)；對(duì)每個(gè)文法符號(hào)引進(jìn)相關(guān)的屬性符號(hào)；n對(duì)每個(gè)產(chǎn)生式寫出屬性值計(jì)算的規(guī)則。對(duì)每個(gè)產(chǎn)生式寫出屬性值計(jì)算的規(guī)則。第 7 頁(yè)例例 8.1 簡(jiǎn)單算術(shù)表達(dá)式求值的屬性文法。簡(jiǎn)單算術(shù)表達(dá)式求值的屬性文法。值屬性值屬性val ：每個(gè)非終結(jié)符有一個(gè)。：每個(gè)非終結(jié)符有一個(gè)。數(shù)字?jǐn)?shù)字digit的值：由詞法分析程序提供。的值：由詞法分析程序提供。P P156語(yǔ)語(yǔ) 義義 規(guī)規(guī) 則則 L E E E1+TE T T 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.v

4、alF.val:=E.valF.val:=digit.lexval產(chǎn)產(chǎn) 生生 式式打印打印E的值的值第 8 頁(yè)屬性分類屬性分類第 9 頁(yè)屬性計(jì)算屬性計(jì)算n將屬性等式轉(zhuǎn)化為計(jì)算規(guī)則。將屬性等式轉(zhuǎn)化為計(jì)算規(guī)則。n為賦值和屬性分配尋找一個(gè)順序?yàn)橘x值和屬性分配尋找一個(gè)順序，確保每次計(jì)算時(shí)，確保每次計(jì)算時(shí)要使用的所有屬性值都是有效的。要使用的所有屬性值都是有效的。n屬性等式屬性等式本身指示了屬性計(jì)算時(shí)的約束順序本身指示了屬性計(jì)算時(shí)的約束順序A的綜合屬性的綜合屬性Xj的繼承屬性的繼承屬性 產(chǎn)生式左邊的繼承屬性和右邊的綜合屬性產(chǎn)生式左邊的繼承屬性和右邊的綜合屬性 不由該產(chǎn)生式計(jì)算，不由該產(chǎn)生式計(jì)算，由其它產(chǎn)

5、生式的屬性規(guī)則計(jì)算由其它產(chǎn)生式的屬性規(guī)則計(jì)算n相關(guān)依賴圖相關(guān)依賴圖 (associated dependency graph)。n描述分析樹中的屬性之間的相互依賴關(guān)系描述分析樹中的屬性之間的相互依賴關(guān)系n明確約束的順序。明確約束的順序。第 10 頁(yè) 從祖先到子孫的繼承從祖先到子孫的繼承屬性值經(jīng)過父結(jié)點(diǎn)屬性值經(jīng)過父結(jié)點(diǎn)在兄弟中傳遞在兄弟中傳遞繼承屬性的相關(guān)依賴圖繼承屬性的相關(guān)依賴圖屬性值直接沿著屬性值直接沿著兄弟鏈傳遞兄弟鏈傳遞重疊在相應(yīng)語(yǔ)法樹中的相關(guān)圖重疊在相應(yīng)語(yǔ)法樹中的相關(guān)圖第 11 頁(yè)屬性計(jì)算方式屬性計(jì)算方式第 12 頁(yè)綜合屬性的計(jì)算綜合屬性的計(jì)算對(duì)語(yǔ)法樹進(jìn)行簡(jiǎn)單的對(duì)語(yǔ)法樹進(jìn)行簡(jiǎn)單的自底向

6、上自底向上或或后序遍歷后序遍歷。屬性賦值程序?qū)傩再x值程序第 13 頁(yè)例例 定義表達(dá)式值的屬性文法定義表達(dá)式值的屬性文法EE1+E2 E.val := E1.val +E2.valE(E1) E.val := E1.val En E.val := n.lexE.Val：綜合屬性綜合屬性句子句子2（31）帶注釋的語(yǔ)法樹帶注釋的語(yǔ)法樹第 14 頁(yè)繼承屬性的計(jì)算繼承屬性的計(jì)算語(yǔ)法樹的語(yǔ)法樹的前序遍歷前序遍歷或或前序前序/中序遍歷中序遍歷的組合。的組合。屬性賦值程序?qū)傩再x值程序計(jì)算的順序計(jì)算的順序在子孫的屬性中繼承屬性可能有依賴關(guān)系。在子孫的屬性中繼承屬性可能有依賴關(guān)系。T T的每個(gè)子孫的每個(gè)子孫C C

7、的訪問順序必須滿足這些依賴的要求。的訪問順序必須滿足這些依賴的要求。第 15 頁(yè)產(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)例例8.2 描述說明語(yǔ)句中變量的類型屬性描述說明語(yǔ)句中變量的類型屬性(type)的文法的文法in：繼承屬性：繼承屬性int id1,id2的語(yǔ)法樹的語(yǔ)法樹P P157把標(biāo)志符的類型信息把標(biāo)志符的類型信息記錄在符號(hào)表中記錄在符號(hào)表中DLTintid2

8、id1,Ltype：綜合屬性：綜合屬性第 16 頁(yè)語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)翻譯(syntax-directed semantics)n以屬性文法為基礎(chǔ)，以屬性文法為基礎(chǔ)，分析屬性的依賴關(guān)系；分析屬性的依賴關(guān)系； n遍歷語(yǔ)法樹，在各結(jié)點(diǎn)按語(yǔ)義規(guī)則進(jìn)行計(jì)算遍歷語(yǔ)法樹，在各結(jié)點(diǎn)按語(yǔ)義規(guī)則進(jìn)行計(jì)算。8.2 語(yǔ)法制導(dǎo)翻譯概論語(yǔ)法制導(dǎo)翻譯概論綜合屬性綜合屬性繼承屬性繼承屬性自底向上自底向上傳遞信息傳遞信息自頂向下（自左自頂向下（自左向右）向右）傳遞信息傳遞信息第 17 頁(yè)S S屬性文法的自下而上計(jì)算屬性文法的自下而上計(jì)算第 18 頁(yè)例例 8.1_2 算術(shù)表達(dá)式求值的屬算術(shù)表達(dá)式求值的屬性文法，性文法，對(duì)對(duì)2+

9、3*5進(jìn)行語(yǔ)法制導(dǎo)翻譯。進(jìn)行語(yǔ)法制導(dǎo)翻譯。P P174產(chǎn)產(chǎn) 生生 式式 語(yǔ)語(yǔ) 義義 規(guī)規(guī) 則則（0）L E Print(E.val)（1）E E1+T E.val:=E1.val+T.val（2）E T E.val:=T.val（3）T T1* F T.val:=T1.val F.val（4）T F T.val:=F.val（5）F (E) F.val:=E.val（6）F digit F.val:=digit.lexvalSLR(1)SLR(1)分析表見分析表見P142 表表7.8第 19 頁(yè) 中間代碼中間代碼( Intermediate code/ representation/ lang

10、uage) 源程序的一種內(nèi)部表示源程序的一種內(nèi)部表示, 復(fù)雜性介于源語(yǔ)言和目復(fù)雜性介于源語(yǔ)言和目標(biāo)機(jī)語(yǔ)言之間標(biāo)機(jī)語(yǔ)言之間從語(yǔ)法樹生成的更接近目標(biāo)代碼的中間表示形式，從語(yǔ)法樹生成的更接近目標(biāo)代碼的中間表示形式，代表了語(yǔ)法樹的某種線性化代表了語(yǔ)法樹的某種線性化 ( linearization )形式，將語(yǔ)形式，將語(yǔ)法樹用順序形式表示。法樹用順序形式表示。8.3 中間代碼的形式中間代碼的形式第 20 頁(yè)中間代碼的形式中間代碼的形式n逆波蘭式、四元式、三元式、間接三元式、逆波蘭式、四元式、三元式、間接三元式、樹樹P-機(jī)器機(jī)器( P - machine )的假想棧機(jī)器的代碼。的假想棧機(jī)器的代碼。Pasc

11、al編譯器產(chǎn)生的標(biāo)準(zhǔn)目標(biāo)匯編代碼編譯器產(chǎn)生的標(biāo)準(zhǔn)目標(biāo)匯編代碼PL/0偽代碼偽代碼第 21 頁(yè)逆波蘭表示逆波蘭表示運(yùn)算對(duì)象在前，運(yùn)算符號(hào)在后。運(yùn)算對(duì)象在前，運(yùn)算符號(hào)在后。ab+abc*+a-b+ac*bd*+a+ba+b*c-a+b a*c+b*d特點(diǎn)特點(diǎn)1、運(yùn)算對(duì)象出現(xiàn)的順序和原有順序（從左到右）相同、運(yùn)算對(duì)象出現(xiàn)的順序和原有順序（從左到右）相同2、運(yùn)算符按實(shí)際計(jì)算順序（從左到右）出現(xiàn)、運(yùn)算符按實(shí)際計(jì)算順序（從左到右）出現(xiàn)3、運(yùn)算符緊跟在運(yùn)算對(duì)象的后面出現(xiàn)，且沒有括號(hào)、運(yùn)算符緊跟在運(yùn)算對(duì)象的后面出現(xiàn)，且沒有括號(hào)優(yōu)點(diǎn)：簡(jiǎn)明、便于計(jì)值優(yōu)點(diǎn)：簡(jiǎn)明、便于計(jì)值第 22 頁(yè)三元式表示三元式表示(算符算符o

12、p，第一運(yùn)算對(duì)象，第一運(yùn)算對(duì)象arg1，第二運(yùn)算對(duì)象，第二運(yùn)算對(duì)象arg2)a:=a*c+b*d第 23 頁(yè)四元式表示四元式表示(算符算符op，第一運(yùn)算對(duì)象，第一運(yùn)算對(duì)象arg1，第二運(yùn)算對(duì)象，第二運(yùn)算對(duì)象arg2，運(yùn)算結(jié)果運(yùn)算結(jié)果result)a:=a*c+b*d第 24 頁(yè)例例 A + B * ( C - D ) + E / ( C - D ) NA B C D - * + E C D N / +逆波蘭逆波蘭(1) ( - C D T1 ) (2) ( * B T1 T2) (3) ( + A T2 T3) (4) ( - C D T4) (5) ( T4 N T5) (6) ( / E

13、T5 T6) (7) ( + T3 T6 T7) 四元式四元式第 25 頁(yè) (1) ( - C D ) (2) ( * B (1) ) (3) ( + A (2) ) (4) ( - C D ) (5) ( (4) N ) (6) ( / E (5) ) (7) ( + (3) (6) ) 三元式三元式例例 A + B * ( C - D ) + E / ( C - D ) N第 26 頁(yè)if E then s1 else s2ES1S2NYE的代碼的代碼S1的代碼的代碼goto outS2的代碼的代碼out:E.trueE.falseE.trueE.falseout:布爾表達(dá)式布爾表達(dá)式 E

14、：B rop C無條件轉(zhuǎn)無條件轉(zhuǎn) (jmp , -, -, L)條件真轉(zhuǎn)條件真轉(zhuǎn) (jrop, B, C, L)四元式四元式goto Lif B rop C goto L第 27 頁(yè)例例 8.5 布爾表達(dá)式布爾表達(dá)式ab or cf的翻譯的翻譯 P183E E的的“真真”出口轉(zhuǎn)移目出口轉(zhuǎn)移目標(biāo)標(biāo)E E的的“假假”出口轉(zhuǎn)移目標(biāo)出口轉(zhuǎn)移目標(biāo)第 28 頁(yè)(7)(p-1) u goto (p+1) (q-1)(q)語(yǔ)句語(yǔ)句if ab or cf then S1 else S2 的四元式的四元式S1的四元式的四元式S2的四元式的四元式轉(zhuǎn)移地址在產(chǎn)生四元式時(shí)無法確定，需要轉(zhuǎn)移地址在產(chǎn)生四元式時(shí)無法確定，需

15、要回填回填。E.trueE.false(7)(7)(p+1)(p+1)(q)ES1S2NYqE.trueE.false第 29 頁(yè)（10） goto L （20） goto L （30） goto L （40）L：拉鏈返填拉鏈返填（10）goto 0（20）goto 10（30） goto 20鏈尾鏈尾鏈?zhǔn)祖準(zhǔn)祖溛矘?biāo)志鏈尾標(biāo)志第 30 頁(yè)(E.true )： (1)和和( (5 ) )拉鏈拉鏈(E.false)：(4) 和和(6)拉鏈拉鏈語(yǔ)句語(yǔ)句if ab or cf then S1 else S2 的四元式的四元式(7)(p-1) u goto (p+1) (q-1)(q)S1的四元式的四元

16、式S2的四元式的四元式(7)(7)(p+1)(p+1)(q)第 31 頁(yè)語(yǔ)義描述使用的變量語(yǔ)義描述使用的變量 P P184E.true ： “真真”鏈鏈 E.false ： “假假”鏈鏈 E.Codebegin：E的第一個(gè)四元式序號(hào)的第一個(gè)四元式序號(hào) nextstat：輸出序列中下一四元式的序號(hào)：輸出序列中下一四元式的序號(hào)emit( ) ：輸出一條四元式，而后：輸出一條四元式，而后nextstat+1backpach(p,t)：把所鏈接的每個(gè)四元式的第四字段都填為：把所鏈接的每個(gè)四元式的第四字段都填為tE.place: : 存放存放E值的變量名在符號(hào)表中的登錄項(xiàng)值的變量名在符號(hào)表中的登錄項(xiàng),或

17、一整數(shù)碼或一整數(shù)碼merge(p1,p2) ：把：把p1和和p2為鏈?zhǔn)椎膬蓷l鏈合并為一條，返回合并為鏈?zhǔn)椎膬蓷l鏈合并為一條，返回合并 后的鏈?zhǔn)字岛蟮逆準(zhǔn)字?p1)第 32 頁(yè)第 33 頁(yè)(5)Eid E.true:=nextstat; E.codebegin:=nextstat; E.false:=nextstat+1; emit(if id.place goto); emit(goto-)(4)E(E1) E.true:= E1.true; E.Codebegin:= E1.codebegin; E.false:= E1.false(5)Eid1 rop id2 E.true:=nextst

18、at; E.Codebegin:=nextstat; E.false:=nextstat+1; emit(if id1.place rop id2.place goto); emit(goto-)第 34 頁(yè)EEEaborEcf(100) if ab goto _ (101) goto _ 例例 8.5 ab or cf的自底向上翻譯的自底向上翻譯 P185(5)Eid1 rop id2 E.true:=nextstat; E.Codebegin:=nextstat; E.false:=nextstat+1; emit(if id1.place rop id2.place goto); emi

19、t(goto-)E.true=100E.false=101E.codebegin=100第 35 頁(yè)EEEorEcf(100) if ab goto _ (101) goto _ E.true=100E.false=101E.codebegin=100例例 8.5 ab or cf的自底向上翻譯的自底向上翻譯 P185(5)Eid1 rop id2 E.true:=nextstat; E.Codebegin:=nextstat; E.false:=nextstat+1; emit(if id1.place rop id2.place goto); emit(goto-)(102) if cfE

20、.true=100E.false=101E.codebegin=100E.true=102E.false=103E.codebegin=102例例 8.5 ab or cf的自底向上翻譯的自底向上翻譯 P185(5)Eid1 rop id2 E.true:=nextstat; E.Codebegin:=nextstat; E.false:=nextstat+1; emit(if id1.place rop id2.place goto); emit(goto-)(100) if ab goto _ (101) goto _ (102) if cf goto _ (105) goto _E.true=104E.false=105E.codebegin=104第 37 頁(yè)EEEorEandEE.true=100E.false=101E.codebegin=100E.true=102E.false=103E.codebegin=102例例 8.5 ab or cf的自底向上翻譯的自底向上翻譯 P185(100) if ab goto _ (101) goto _ (102) if cf goto _ (1