第八章 語(yǔ)法制導(dǎo)翻譯與中間代碼生成

1、第第8章章 語(yǔ)法制導(dǎo)翻譯和中間代碼語(yǔ)法制導(dǎo)翻譯和中間代碼生成生成提綱：提綱： 屬性文法屬性文法 翻譯模式翻譯模式 中間代碼中間代碼 語(yǔ)句翻譯語(yǔ)句翻譯n語(yǔ)法制導(dǎo)翻譯：語(yǔ)法制導(dǎo)翻譯：n在語(yǔ)法分析的同時(shí)，完成相應(yīng)的語(yǔ)義處理在語(yǔ)法分析的同時(shí)，完成相應(yīng)的語(yǔ)義處理n語(yǔ)義分析的任務(wù)：語(yǔ)義分析的任務(wù)：n檢查靜態(tài)語(yǔ)義：類型、越界、維數(shù)、運(yùn)算檢查靜態(tài)語(yǔ)義：類型、越界、維數(shù)、運(yùn)算n翻譯翻譯(生成生成)中間中間(目標(biāo)目標(biāo))代碼：變量的存儲(chǔ)分配、表代碼：變量的存儲(chǔ)分配、表達(dá)式的求值、語(yǔ)句的翻譯達(dá)式的求值、語(yǔ)句的翻譯8.1 屬性文法屬性文法n語(yǔ)義：語(yǔ)法成份的語(yǔ)義可以用文法符號(hào)的屬性來(lái)表示，語(yǔ)義：語(yǔ)法成份的語(yǔ)義可以用文法符

2、號(hào)的屬性來(lái)表示，通過(guò)屬性的計(jì)算來(lái)完成翻譯通過(guò)屬性的計(jì)算來(lái)完成翻譯n屬性文法：在上下文無(wú)關(guān)文法的基礎(chǔ)上，為每個(gè)文法屬性文法：在上下文無(wú)關(guān)文法的基礎(chǔ)上，為每個(gè)文法符號(hào)（終結(jié)符或非終結(jié)符）配備若干相關(guān)的符號(hào)（終結(jié)符或非終結(jié)符）配備若干相關(guān)的屬性屬性及一及一些附在產(chǎn)生式上的語(yǔ)義規(guī)則。些附在產(chǎn)生式上的語(yǔ)義規(guī)則。n屬性代表與文法符號(hào)相關(guān)信息，如類型、值、代碼屬性代表與文法符號(hào)相關(guān)信息，如類型、值、代碼序列、符號(hào)表內(nèi)容等序列、符號(hào)表內(nèi)容等n屬性可以進(jìn)行計(jì)算和傳遞屬性可以進(jìn)行計(jì)算和傳遞n語(yǔ)義規(guī)則語(yǔ)義規(guī)則：對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬：對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則性的計(jì)算規(guī)則l屬性文法的

3、形式化定義：屬性文法的形式化定義：l屬性文法屬性文法A是一個(gè)三元組是一個(gè)三元組:A=(G,V,F) lG:是一個(gè)上下文無(wú)關(guān)文法是一個(gè)上下文無(wú)關(guān)文法lV:有窮的屬性集有窮的屬性集lF:關(guān)于屬性的語(yǔ)義規(guī)則關(guān)于屬性的語(yǔ)義規(guī)則n屬性的設(shè)定：屬性的設(shè)定：n根據(jù)文法符號(hào)的語(yǔ)義，為文法符號(hào)設(shè)置屬性根據(jù)文法符號(hào)的語(yǔ)義，為文法符號(hào)設(shè)置屬性n例如：根據(jù)實(shí)際需要設(shè)置屬性n表達(dá)式表達(dá)式E：E.type E.valn屬性文法的例子：屬性文法的例子：n文法文法 語(yǔ)義規(guī)則語(yǔ)義規(guī)則nEE1+E2 E.val := E1.val +E2.val E(E1) E.val := E1.val En E.val := n.lexl屬

4、性文法的主要思想：屬性文法的主要思想：l首先對(duì)每個(gè)文法符號(hào)引進(jìn)相關(guān)的屬性符號(hào)；首先對(duì)每個(gè)文法符號(hào)引進(jìn)相關(guān)的屬性符號(hào)；l其次對(duì)每個(gè)產(chǎn)生式寫出屬性值計(jì)算的規(guī)則。其次對(duì)每個(gè)產(chǎn)生式寫出屬性值計(jì)算的規(guī)則。l說(shuō)明：說(shuō)明：l屬性有不同的類型，可以象變量一樣地被賦值屬性有不同的類型，可以象變量一樣地被賦值.l例：例：E.val := E1.val +E2.vall賦值過(guò)程就是語(yǔ)義處理過(guò)程賦值過(guò)程就是語(yǔ)義處理過(guò)程.l例：例：在推導(dǎo)語(yǔ)法樹的時(shí)候，諸屬性的值被計(jì)算并通過(guò)在推導(dǎo)語(yǔ)法樹的時(shí)候，諸屬性的值被計(jì)算并通過(guò)賦值規(guī)則層層傳遞賦值規(guī)則層層傳遞.l語(yǔ)法推導(dǎo)樹最后完成時(shí)，就得到開始符號(hào)的屬性值語(yǔ)法推導(dǎo)樹最后完成時(shí)，就得

5、到開始符號(hào)的屬性值.也就是整個(gè)程序的語(yǔ)義也就是整個(gè)程序的語(yǔ)義.n屬性的分類：屬性的分類：n綜合屬性綜合屬性：“自下而上自下而上”傳遞信息傳遞信息n繼承屬性繼承屬性：“自上而下自上而下”傳遞信息傳遞信息l在一個(gè)屬性文法中，對(duì)應(yīng)于每個(gè)產(chǎn)生式在一個(gè)屬性文法中，對(duì)應(yīng)于每個(gè)產(chǎn)生式A 都有都有一套一套與之相關(guān)聯(lián)的與之相關(guān)聯(lián)的語(yǔ)義規(guī)則語(yǔ)義規(guī)則，每條規(guī)則的形式為：，每條規(guī)則的形式為：lb:=f(c1,c2,ck)l這里，這里，f是一個(gè)函數(shù)，是一個(gè)函數(shù)， c1,c2,ck是產(chǎn)生式文法符號(hào)或是產(chǎn)生式文法符號(hào)或A的屬性的屬性lb為為A的綜合屬性：的綜合屬性：l如果如果b是是A的一個(gè)的一個(gè)屬性屬性，并且，并且c1,c

6、2,ck是產(chǎn)生式右邊是產(chǎn)生式右邊文法符號(hào)的屬性或者文法符號(hào)的屬性或者A的其他屬性。的其他屬性。lb是文法符號(hào)是文法符號(hào)X的繼承屬性：的繼承屬性：l如果如果b是產(chǎn)生式右邊某個(gè)文法符號(hào)是產(chǎn)生式右邊某個(gè)文法符號(hào)X的一個(gè)的一個(gè)屬性，屬性，c1,c2,ck 是是A或產(chǎn)生式右邊任何文法符號(hào)的屬性?；虍a(chǎn)生式右邊任何文法符號(hào)的屬性。l兩種情況下，屬性兩種情況下，屬性b都依賴于屬性都依賴于屬性c1,c2,ck。l說(shuō)明：說(shuō)明：n終結(jié)符屬性為綜合屬性，由詞法分析器給出終結(jié)符屬性為綜合屬性，由詞法分析器給出n非終結(jié)符既可以有綜合屬性，也可以有繼承屬性非終結(jié)符既可以有綜合屬性，也可以有繼承屬性 產(chǎn)產(chǎn) 生生 式式 LEE

7、E1+T ETTT1*FTFF (E)Fdigit語(yǔ)語(yǔ) 義義 規(guī)規(guī) 則則print(E.val) E.val := E1.val+T.val E.val :=T.val T.val :=T1.val* F.val T.val :=F.val F.val :=E.val F.val :=digit.lexvalE、T、F的的Val屬性是？屬性是？綜合屬性綜合屬性例：簡(jiǎn)單算術(shù)表達(dá)式求值的語(yǔ)義描述（屬性文法）例：簡(jiǎn)單算術(shù)表達(dá)式求值的語(yǔ)義描述（屬性文法）產(chǎn)產(chǎn) 生生 式式 語(yǔ)語(yǔ) 義義 規(guī)規(guī) 則則 DTLL.in := T.type TintT.type := integer TrealT.type :=

8、 real LL1, idL1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in) T.type是綜合屬性是綜合屬性L.in是繼承屬性是繼承屬性例：說(shuō)明語(yǔ)句中各種變量的類型信息的語(yǔ)義規(guī)則（屬性文法）例：說(shuō)明語(yǔ)句中各種變量的類型信息的語(yǔ)義規(guī)則（屬性文法）n綜合屬性綜合屬性n在語(yǔ)法樹中，一個(gè)結(jié)點(diǎn)的在語(yǔ)法樹中，一個(gè)結(jié)點(diǎn)的綜合屬性綜合屬性的值由其的值由其子結(jié)點(diǎn)子結(jié)點(diǎn)的屬性值確定。的屬性值確定。n使用自底向上的方法在每一個(gè)結(jié)點(diǎn)處使用語(yǔ)義規(guī)則使用自底向上的方法在每一個(gè)結(jié)點(diǎn)處使用語(yǔ)義規(guī)則計(jì)算綜合屬性的值計(jì)算綜合屬性的值3*5+4的的帶語(yǔ)

9、義信息帶語(yǔ)義信息的語(yǔ)法樹的語(yǔ)法樹 digit.lexval=3F.val=3T.val=3*digit.lexval=5F.val=5T.val=15E.val=15+digit.lexval=4F.val=4T.val=4E.val=19L 產(chǎn)產(chǎn) 生生 式式 語(yǔ)語(yǔ) 義義 規(guī)規(guī) 則則 LE print(E.val) EE1+T E.val := E1.val+T.val ET E.val :=T.val TT1*F T.val :=T1.val* F.val TF T.val :=F.val F (E) F.val :=E.val Fdigit F.val :=digit.lexvaln繼承屬

10、性繼承屬性n在語(yǔ)法樹中，一個(gè)結(jié)點(diǎn)的在語(yǔ)法樹中，一個(gè)結(jié)點(diǎn)的繼承屬性繼承屬性由此結(jié)點(diǎn)的由此結(jié)點(diǎn)的父結(jié)父結(jié)點(diǎn)和點(diǎn)和/或兄弟結(jié)點(diǎn)或兄弟結(jié)點(diǎn)的某些屬性確定的某些屬性確定句子句子real id1，id2，id3的的帶語(yǔ)義信息帶語(yǔ)義信息的語(yǔ)法樹的語(yǔ)法樹 id1L,id2L,id3LrealTDT.type=realL.in=realL.in=realL.in=real產(chǎn)產(chǎn) 生生 式式 語(yǔ)語(yǔ) 義義 規(guī)規(guī) 則則 DTL L.in := T.type Tint T.type := integer Treal T.type := real LL1, id L1.in :=L.in addtype(id.entry,

11、 L.in) Lid addtype(id.entry, L.in) 8.2 語(yǔ)法制導(dǎo)翻譯概論語(yǔ)法制導(dǎo)翻譯概論n基于屬性文法的處理方法基于屬性文法的處理方法 n過(guò)程（一般情況）：過(guò)程（一般情況）：n對(duì)單詞符號(hào)串進(jìn)行語(yǔ)法分析，構(gòu)造語(yǔ)法分析樹對(duì)單詞符號(hào)串進(jìn)行語(yǔ)法分析，構(gòu)造語(yǔ)法分析樹n構(gòu)造屬性依賴圖構(gòu)造屬性依賴圖n獲得語(yǔ)義規(guī)則的計(jì)算順序獲得語(yǔ)義規(guī)則的計(jì)算順序n翻譯結(jié)果（語(yǔ)義規(guī)則的計(jì)算）翻譯結(jié)果（語(yǔ)義規(guī)則的計(jì)算）n產(chǎn)生代碼n在符號(hào)表中存放信息n給出錯(cuò)誤信息n執(zhí)行任何其它動(dòng)作n對(duì)輸入符號(hào)串的對(duì)輸入符號(hào)串的翻譯翻譯也就是根據(jù)語(yǔ)義規(guī)則進(jìn)行也就是根據(jù)語(yǔ)義規(guī)則進(jìn)行計(jì)算計(jì)算的結(jié)果。的結(jié)果。8.2.1 計(jì)算語(yǔ)義規(guī)則

12、計(jì)算語(yǔ)義規(guī)則n在一棵語(yǔ)法樹中，結(jié)點(diǎn)的繼承屬性和綜合屬性之間的在一棵語(yǔ)法樹中，結(jié)點(diǎn)的繼承屬性和綜合屬性之間的相互依賴關(guān)系可以由稱作相互依賴關(guān)系可以由稱作依賴圖依賴圖的一個(gè)有向圖來(lái)描述的一個(gè)有向圖來(lái)描述n為每一個(gè)包含過(guò)程調(diào)用的語(yǔ)義規(guī)則引入一個(gè)為每一個(gè)包含過(guò)程調(diào)用的語(yǔ)義規(guī)則引入一個(gè)虛綜合屬虛綜合屬性性b，這樣把每一個(gè)語(yǔ)義規(guī)則都寫成，這樣把每一個(gè)語(yǔ)義規(guī)則都寫成b:=f(c1,c2,ck)的形式的形式n依賴圖中為每一個(gè)屬性設(shè)置一個(gè)結(jié)點(diǎn)，如果屬性依賴圖中為每一個(gè)屬性設(shè)置一個(gè)結(jié)點(diǎn)，如果屬性b依賴依賴于屬性于屬性c，則從屬性，則從屬性c的結(jié)點(diǎn)有一條有向邊連到屬性的結(jié)點(diǎn)有一條有向邊連到屬性b的結(jié)點(diǎn)。的結(jié)點(diǎn)。 E

13、E1E2 E.val:=E1.val+E2.val E1+E2Evalvalval語(yǔ)義規(guī)則的計(jì)算次序語(yǔ)義規(guī)則的計(jì)算次序 n一個(gè)一個(gè)依賴圖依賴圖的任何的任何拓?fù)渑判蛲負(fù)渑判蚨冀o出一個(gè)語(yǔ)法樹中結(jié)點(diǎn)都給出一個(gè)語(yǔ)法樹中結(jié)點(diǎn)的語(yǔ)義規(guī)則計(jì)算的有效順序的語(yǔ)義規(guī)則計(jì)算的有效順序n基于屬性文法的翻譯是很精確的基于屬性文法的翻譯是很精確的n基礎(chǔ)文法用于建立輸入符號(hào)串的語(yǔ)法分析樹基礎(chǔ)文法用于建立輸入符號(hào)串的語(yǔ)法分析樹n根據(jù)語(yǔ)義規(guī)則建立依賴圖根據(jù)語(yǔ)義規(guī)則建立依賴圖n從依賴圖的拓?fù)渑判蛑?，我們可以得到?jì)算語(yǔ)義規(guī)從依賴圖的拓?fù)渑判蛑?，我們可以得到?jì)算語(yǔ)義規(guī)則的順序則的順序 輸入串輸入串語(yǔ)法樹語(yǔ)法樹依賴圖依賴圖語(yǔ)義規(guī)則計(jì)算

14、次序語(yǔ)義規(guī)則計(jì)算次序?qū)傩杂?jì)算屬性計(jì)算n1）樹遍歷）樹遍歷n通過(guò)樹遍歷的方法計(jì)算屬性的值通過(guò)樹遍歷的方法計(jì)算屬性的值 n假設(shè)語(yǔ)法樹已建立，且樹中已帶有開始符號(hào)的繼承假設(shè)語(yǔ)法樹已建立，且樹中已帶有開始符號(hào)的繼承屬性和終結(jié)符的綜合屬性屬性和終結(jié)符的綜合屬性 n以某種次序遍歷語(yǔ)法樹，直至計(jì)算出所有屬性以某種次序遍歷語(yǔ)法樹，直至計(jì)算出所有屬性n深度優(yōu)先，從左到右的遍歷深度優(yōu)先，從左到右的遍歷 屬性計(jì)算屬性計(jì)算n2）一遍掃描的處理方法）一遍掃描的處理方法是在語(yǔ)法分析的同時(shí)計(jì)算屬性是在語(yǔ)法分析的同時(shí)計(jì)算屬性值值 n所采用的語(yǔ)法分析方法所采用的語(yǔ)法分析方法n屬性的計(jì)算次序?qū)傩缘挠?jì)算次序8.2.2 S-屬性文法

15、和自下而上翻譯屬性文法和自下而上翻譯nS-屬性文法屬性文法：只含有綜合屬性：只含有綜合屬性nS屬性文法適合于一遍掃描的屬性文法適合于一遍掃描的自下而上自下而上分析分析n綜合屬性可以在分析輸入符號(hào)串的同時(shí)由自下綜合屬性可以在分析輸入符號(hào)串的同時(shí)由自下而上的分析器來(lái)計(jì)算。而上的分析器來(lái)計(jì)算。n分析器可以保存與棧中文法符號(hào)有關(guān)的綜合屬分析器可以保存與棧中文法符號(hào)有關(guān)的綜合屬性值，每當(dāng)進(jìn)行歸約時(shí)，新的屬性值就由棧中性值，每當(dāng)進(jìn)行歸約時(shí)，新的屬性值就由棧中正在歸約的產(chǎn)生式右邊符號(hào)的屬性值來(lái)計(jì)算。正在歸約的產(chǎn)生式右邊符號(hào)的屬性值來(lái)計(jì)算。n在分析棧中使用一個(gè)附加的域來(lái)存放綜合屬性在分析棧中使用一個(gè)附加的域來(lái)

16、存放綜合屬性值值 n假設(shè)語(yǔ)義規(guī)則假設(shè)語(yǔ)義規(guī)則A.a:=f(X.x,Y.y,Z.z)是對(duì)應(yīng)于產(chǎn)是對(duì)應(yīng)于產(chǎn)生式生式AXYZ的的 Sm Z.z Z Sm-1 Y.y Y Sm-2 X.x X S0 # TOP Sm-2 A.a A S0 # TOP 表達(dá)式文法的表達(dá)式文法的SLR（1）分析表）分析表ACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5文法文法 0:LE 1: EE+T 2:ET 3:TT*F 4:TF 5

17、:F (E) 6:Fi 產(chǎn)產(chǎn) 生生 式式 LEEE1+T ETTT1*FTFF (E)Fdigit語(yǔ)語(yǔ) 義義 規(guī)規(guī) 則則print(E.val) E.val := E1.val+T.val E.val :=T.val T.val :=T1.val* F.val T.val :=F.val F.val :=E.val F.val :=digit.lexvaln3*5+4的分析和值計(jì)算過(guò)程的分析和值計(jì)算過(guò)程n 輸入輸入 state sym val用到的產(chǎn)生式用到的產(chǎn)生式n 3*5+4# 0 # -n *5+4# 05#3 -n *5+4# 03 #F -3 Fdigitn *5+4# 02 #T

18、-3 TFn 5+4# 027#T* -3 -n +4# 0275 #T*5 -3 - -ACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S11文法文法 0:LE 1: EE+T 2:ET 3:TT*F 4:TF 5:F (E) 6:Fin3*5+4的分析和值計(jì)算過(guò)程的分析和值計(jì)算過(guò)程輸入輸入 statesym val 用到的產(chǎn)生式用到的產(chǎn)生式+4# 0275 #T*5 -3 - -+4# 02710#T*F -3 - 5 FdigitACTIONGOTOi+*()#ETF

19、0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S11文法文法 0:LE 1: EE+T 2:ET 3:TT*F 4:TF 5:F (E) 6:Fin3*5+4的分析和值計(jì)算過(guò)程的分析和值計(jì)算過(guò)程輸入輸入 statesym val 用到的產(chǎn)生式用到的產(chǎn)生式+4# 0275 #T*5 -3 - -+4# 02710#T*F -3 - 5 Fdigit+4# 02 #T -15 TT*F+4# 01 #E -15 ET4# 016 #E+ -15- # 0165 #E+4 -15- 4ACTIONGOTOi+*()

20、#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S11文法文法 0:LE 1: EE+T 2:ET 3:TT*F 4:TF 5:F (E) 6:Fin3*5+4的分析和值計(jì)算過(guò)程的分析和值計(jì)算過(guò)程 輸入輸入 statesym val 用到的產(chǎn)生式用到的產(chǎn)生式 # 0165 #E+4 -15- - # 0163 #E+F -15- 4Fdigit # 0169 #E+T -15- 4TF # 01 #E -19 EE+T #L -19 LEACTIONGOTOi+*()#ETF0S5S41231S6acc

21、2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S11文法文法 0:LE 1: EE+T 2:ET 3:TT*F 4:TF 5:F (E) 6:Fi8.2.3 L-屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯n一個(gè)屬性文法稱為一個(gè)屬性文法稱為L(zhǎng)-L-屬性文法屬性文法，如果對(duì)于每個(gè)產(chǎn)，如果對(duì)于每個(gè)產(chǎn)生式生式AXAX1 1X X2 2X Xn n，其每個(gè)語(yǔ)義規(guī)則中的每個(gè)屬性，其每個(gè)語(yǔ)義規(guī)則中的每個(gè)屬性或者是綜合屬性，或者是或者是綜合屬性，或者是X Xj j(1(1 j j n)n)的一個(gè)繼承屬的一個(gè)繼承屬性且這個(gè)繼承屬性僅依賴于：性且這個(gè)繼承

22、屬性僅依賴于：(1)(1)產(chǎn)生式產(chǎn)生式X Xj j的左邊符號(hào)的左邊符號(hào)X X1 1，X X2 2，X Xj-1j-1的屬性；的屬性；(2)A(2)A的繼承屬性。的繼承屬性。nS-S-屬性文法一定是屬性文法一定是L-L-屬性文法屬性文法不是不是L-屬性文法屬性文法產(chǎn)產(chǎn) 生生 式式 語(yǔ)語(yǔ) 義義 規(guī)規(guī) 則則 ALM M.i :=m(L.s) AQR Q.i :=q(R.s) A.s :=f(Q.s) 例：將中綴表達(dá)式翻譯成后綴表達(dá)式的屬性文法例：將中綴表達(dá)式翻譯成后綴表達(dá)式的屬性文法nE-E addop T print(addop.lexeme)|TnT-num print(num.val)n其中，

23、其中，addop為為+或或-n是是L-屬性文法屬性文法n如果用如果用LR分析，很容易實(shí)現(xiàn)在語(yǔ)法分析時(shí)進(jìn)行翻譯分析，很容易實(shí)現(xiàn)在語(yǔ)法分析時(shí)進(jìn)行翻譯n例：將例：將2+3-5轉(zhuǎn)換成中綴表達(dá)式轉(zhuǎn)換成中綴表達(dá)式2Tprint 2E3Tprint +ETprint -E5print 5說(shuō)明語(yǔ)義動(dòng)作的語(yǔ)法樹說(shuō)明語(yǔ)義動(dòng)作的語(yǔ)法樹print 3例：將例：將2+3-5轉(zhuǎn)換成中綴表達(dá)式轉(zhuǎn)換成中綴表達(dá)式LR分析分析8.2.3 L-屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯n對(duì)對(duì)L-屬性文法進(jìn)行自頂向下翻譯屬性文法進(jìn)行自頂向下翻譯nLL(1)文法適合自頂向下分析文法適合自頂向下分析nLL(1)文法不包含左遞歸文法不包

24、含左遞歸n文法：文法：nE-E addop T print(addop.lexeme)|TnT-num print(num.val)n此文法含有左遞歸此文法含有左遞歸n為了利用為了利用LL(1)方法分析，必須去除左遞歸方法分析，必須去除左遞歸 ETR Raddop T print(addop.lexeme) R1 | Tnum print(num.val) 例：例：9-5+2語(yǔ)義動(dòng)作的語(yǔ)法樹語(yǔ)義動(dòng)作的語(yǔ)法樹-ETR9print(9)TR5print(5)print(-)+T2print(2)Rprint(+) 改寫后：改寫后：E-E addop T print(addop.lexeme)|TT

25、-num print(num.val)這種語(yǔ)義處理的描述形這種語(yǔ)義處理的描述形式稱為翻譯模式式稱為翻譯模式8.2.3 L-屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯n翻譯模式翻譯模式：是適合語(yǔ)法制導(dǎo)翻譯的另一種描：是適合語(yǔ)法制導(dǎo)翻譯的另一種描述形式，給出了使用語(yǔ)義規(guī)則進(jìn)行計(jì)算的次述形式，給出了使用語(yǔ)義規(guī)則進(jìn)行計(jì)算的次序序 n在翻譯模式中，和文法符號(hào)相關(guān)的屬性和語(yǔ)在翻譯模式中，和文法符號(hào)相關(guān)的屬性和語(yǔ)義規(guī)則用花括號(hào)義規(guī)則用花括號(hào) 括起來(lái)，插入到產(chǎn)生式右括起來(lái)，插入到產(chǎn)生式右部的合適位置上部的合適位置上設(shè)計(jì)翻譯模式的原則設(shè)計(jì)翻譯模式的原則n設(shè)計(jì)翻譯模式時(shí)，必須保證當(dāng)某個(gè)動(dòng)作引用一設(shè)計(jì)翻譯模式時(shí)，

26、必須保證當(dāng)某個(gè)動(dòng)作引用一個(gè)屬性時(shí)它必須是有定義的。個(gè)屬性時(shí)它必須是有定義的。nL-屬性文法本身就能確保每個(gè)動(dòng)作不會(huì)引用尚屬性文法本身就能確保每個(gè)動(dòng)作不會(huì)引用尚未計(jì)算出來(lái)的屬性。未計(jì)算出來(lái)的屬性。 當(dāng)消除一個(gè)翻譯模式的基本文法的左遞歸時(shí)同時(shí)考慮當(dāng)消除一個(gè)翻譯模式的基本文法的左遞歸時(shí)同時(shí)考慮屬屬性性 8.2.4 L-屬性文法的自下而上的翻譯屬性文法的自下而上的翻譯n方法：方法：n1）從翻譯模式中去掉嵌入在產(chǎn)生式中間的動(dòng)作，把所有的語(yǔ)）從翻譯模式中去掉嵌入在產(chǎn)生式中間的動(dòng)作，把所有的語(yǔ)義動(dòng)作都放在產(chǎn)生式的末尾義動(dòng)作都放在產(chǎn)生式的末尾n2）用綜合屬性代替繼承屬性）用綜合屬性代替繼承屬性n1）轉(zhuǎn)換方法：

27、）轉(zhuǎn)換方法：n加入新的產(chǎn)生式加入新的產(chǎn)生式M n把嵌入在產(chǎn)生式中的每個(gè)語(yǔ)義動(dòng)作用不同的標(biāo)記非終結(jié)符把嵌入在產(chǎn)生式中的每個(gè)語(yǔ)義動(dòng)作用不同的標(biāo)記非終結(jié)符M代替，并把這個(gè)動(dòng)作放在產(chǎn)生式代替，并把這個(gè)動(dòng)作放在產(chǎn)生式M 的末尾的末尾 n翻譯模式翻譯模式 E TRR T print () R | T print () R | T num print (num.val)n轉(zhuǎn)換為轉(zhuǎn)換為 E TRR TMR | TNR | T num print (num.val)M print ()N print ()8.3 中間代碼的形式中間代碼的形式n中間代碼：中間代碼：是源程序的一種內(nèi)部表示，復(fù)雜性介于源是源程序的一種

28、內(nèi)部表示，復(fù)雜性介于源語(yǔ)言和目標(biāo)機(jī)語(yǔ)言之間語(yǔ)言和目標(biāo)機(jī)語(yǔ)言之間n中間代碼的作用：中間代碼的作用：n使編譯程序的邏輯結(jié)構(gòu)更加簡(jiǎn)單明確使編譯程序的邏輯結(jié)構(gòu)更加簡(jiǎn)單明確n利于進(jìn)行與目標(biāo)機(jī)無(wú)關(guān)的優(yōu)化利于進(jìn)行與目標(biāo)機(jī)無(wú)關(guān)的優(yōu)化n利于在不同目標(biāo)機(jī)上實(shí)現(xiàn)同一種語(yǔ)言利于在不同目標(biāo)機(jī)上實(shí)現(xiàn)同一種語(yǔ)言n中間代碼的形式：中間代碼的形式：n逆波蘭式、四元式、三元式、樹逆波蘭式、四元式、三元式、樹8.3.1 逆波蘭式逆波蘭式n逆波蘭逆波蘭表示法：一種表示表達(dá)式的方法，又稱表示法：一種表示表達(dá)式的方法，又稱后綴式后綴式表示法。表示法。n4+5*2-3n后綴式：后綴式：452*+3-n后綴式的計(jì)算后綴式的計(jì)算n要知道每個(gè)算

29、符的目數(shù)要知道每個(gè)算符的目數(shù)n用一個(gè)棧實(shí)現(xiàn)。用一個(gè)棧實(shí)現(xiàn)。n一般的計(jì)算過(guò)程是：自左至右掃描后綴式，每碰到一般的計(jì)算過(guò)程是：自左至右掃描后綴式，每碰到運(yùn)算量就把它推進(jìn)棧。每碰到運(yùn)算量就把它推進(jìn)棧。每碰到k目運(yùn)算符就把它作目運(yùn)算符就把它作用于棧頂?shù)挠糜跅ｍ數(shù)膋個(gè)項(xiàng)，并用運(yùn)算結(jié)果代替這個(gè)項(xiàng)，并用運(yùn)算結(jié)果代替這k個(gè)項(xiàng)個(gè)項(xiàng)。8.3.1 逆波蘭式逆波蘭式n可將可將逆波蘭表示擴(kuò)充逆波蘭表示擴(kuò)充到表達(dá)式以外的范圍到表達(dá)式以外的范圍n例如：例如：n賦值語(yǔ)句賦值語(yǔ)句 a:=b*c+b*dn表示：表示：abc*bd*+:=n條件語(yǔ)句條件語(yǔ)句 if E then S1 else S2n表示：表示：ES1S2 n為三目

30、運(yùn)算符為三目運(yùn)算符8.3.2 三元式和樹形表示三元式和樹形表示n三元式三元式 n通過(guò)計(jì)算臨時(shí)變量值的語(yǔ)句的位置來(lái)引用這個(gè)臨時(shí)變通過(guò)計(jì)算臨時(shí)變量值的語(yǔ)句的位置來(lái)引用這個(gè)臨時(shí)變量量n三個(gè)域：三個(gè)域：op（運(yùn)算符）、（運(yùn)算符）、arg1(運(yùn)算對(duì)象運(yùn)算對(duì)象)和和arg2（運(yùn)算對(duì)象）（運(yùn)算對(duì)象）oparg1arg2(0)- c(1)*b(0)(2)- c(3)*b(2)(4)+(1)(3)(5)：= a(4)例如：例如：a:=b*(-c)+b*(-c)n例如，語(yǔ)句例如，語(yǔ)句X:=(A+B)*C;Y:=D(A+B)的三元式表示如下表所示。的三元式表示如下表所示。 三元式表示三元式表示 OP ARG1 AR

31、G2 (1) + A B (2) * (1) C (3) := X (2) (4) D (1) (5) := Y (4) 三元式也可以表示成樹三元式也可以表示成樹：=a+*b-c*b-c例如例如 a:=b*(-c)+b*(-c)的樹表示法的樹表示法8.3.3 四元式四元式n四元式四元式(普遍采用的中間代碼形式普遍采用的中間代碼形式)n一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域分別稱為一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域分別稱為op, arg1, arg2及及resultoparg1arg2result(0)- cT1(1)*bT1T2(2)- cT3(3)*bT3T4(4)+T2T4T5(5):=T5a

32、 例如：例如：a:=b*(-c)+b*(-c)8.3.3 四元式四元式n為了更直觀，也把四元式的形式寫成簡(jiǎn)單賦值形式為了更直觀，也把四元式的形式寫成簡(jiǎn)單賦值形式n(1)T1:=-cn(2)T2:=b*T1n(3) T3:=-cn(4)T4:=b*T3n(5)T5:=T2+T4n(6)a:=T5把（把（jump,-,-,L）寫成）寫成goto L把把(jrop,B,C,L)寫成寫成if B rop C goto L例如：例如：a:=b*(-c)+b*(-c)8.4 簡(jiǎn)單賦值語(yǔ)句的翻譯簡(jiǎn)單賦值語(yǔ)句的翻譯n在上面的四元式中，使用變量名字本身表示運(yùn)算對(duì)象在上面的四元式中，使用變量名字本身表示運(yùn)算對(duì)象n

33、在實(shí)際實(shí)現(xiàn)中，它們是在實(shí)際實(shí)現(xiàn)中，它們是n指針：指向符號(hào)表的某一登陸項(xiàng)指針：指向符號(hào)表的某一登陸項(xiàng)n或臨時(shí)變量的整數(shù)碼或臨時(shí)變量的整數(shù)碼n翻譯的一般要求：翻譯的一般要求：n充分了解各種語(yǔ)法成分的語(yǔ)義充分了解各種語(yǔ)法成分的語(yǔ)義n目標(biāo)語(yǔ)言的語(yǔ)義目標(biāo)語(yǔ)言的語(yǔ)義簡(jiǎn)單賦值語(yǔ)句的翻譯：翻譯成四元式簡(jiǎn)單賦值語(yǔ)句的翻譯：翻譯成四元式n下面為翻譯中用到的信息：下面為翻譯中用到的信息：n語(yǔ)義屬性：語(yǔ)義屬性： nE.place：存儲(chǔ)位置或整數(shù)碼：存儲(chǔ)位置或整數(shù)碼nlookup() ：子程序，在符號(hào)表中查找：子程序，在符號(hào)表中查找nemit(t:=arg1 op arg2)：子程序，生成

34、四元式：子程序，生成四元式nnewtemp：產(chǎn)生新的臨時(shí)變量：產(chǎn)生新的臨時(shí)變量產(chǎn)生賦值語(yǔ)句的四元式翻譯模式產(chǎn)生賦值語(yǔ)句的四元式翻譯模式 Sid:=E p:=lookup(); if p nil thenemit(p := E.place) else error EE1+E2 E.place:=newtemp; emit(E.place := E1.place + E2.place)EE1*E2 E.place:=newtemp; emit(E.place := E 1.place * E 2.place)產(chǎn)生賦值語(yǔ)句的四元式翻譯模式（續(xù)）產(chǎn)生賦值語(yǔ)句的四元式翻譯模式（續(xù)）E-E1

35、 E.place:=newtemp; emit(E.place:= -E 1.place)E(E1) E.place:=E1.placeEid p:=lookup(); if p nil then E.place:=p else error 例如：將例如：將x:=y+i*j翻譯成四元式翻譯成四元式Sid:=E p:=lookup(); if p nil then emit(p := E.place) else error EE1+E2 E.place:=newtemp; emit(E.place := E1.place + E2.place)EE1*E2 E.pla

36、ce:=newtemp; emit(E.place := E 1.place * E 2.place)E-E1 E.place:=newtemp; emit(E.place:=-E 1.place)E(E1) E.place:=E1.placeEid p:=lookup(); if p nil then E.place:=p else error 在翻譯中有時(shí)需要類型轉(zhuǎn)換在翻譯中有時(shí)需要類型轉(zhuǎn)換用用E.type表示非終結(jié)符表示非終結(jié)符E的類型屬性的類型屬性 n假設(shè)只有整型和實(shí)型，對(duì)應(yīng)產(chǎn)生式假設(shè)只有整型和實(shí)型，對(duì)應(yīng)產(chǎn)生式EE1 op E2的語(yǔ)義動(dòng)作的語(yǔ)義動(dòng)作中關(guān)于中關(guān)于E.type

37、的語(yǔ)義規(guī)則可定義為：的語(yǔ)義規(guī)則可定義為： if E1.type=integer and E2.type=integer E.type:=integer else E.type:=real n算符區(qū)分為整型算符算符區(qū)分為整型算符int op和實(shí)型算符和實(shí)型算符real opnx:=yi*j 其中其中x、y為實(shí)型；為實(shí)型；i、j為整型。這個(gè)賦值句產(chǎn)生的四元為整型。這個(gè)賦值句產(chǎn)生的四元式代碼（簡(jiǎn)寫）為：式代碼（簡(jiǎn)寫）為： T1:=i int* j T3:=inttoreal T1 T2:=y real+ T3 x:=T2關(guān)于產(chǎn)生式關(guān)于產(chǎn)生式EE1 E2 的語(yǔ)義動(dòng)作的語(yǔ)義動(dòng)作 E.place:=new

38、temp; if E1.type=integer and E2.type=integer then begin emit (E.place := E 1.place int+ E 2.place); E.type:=integer end else if E1.type=real and E2.type=real then begin emit (E.place := E 1.place real+ E 2.place); E.type:=real endelse if E1.type=integer and E2.type=real then beginu:=newtemp;emit (u

39、:= inttoreal E 1.place);emit (E.place := u real+ E 2.palce);E.type:=realendelse if E1.type=real and E1.type=integer then beginu:=newtemp;emit (u := inttoreal E 2.place);emit (E.place := E 1.place real+ u);E.type:=realend else E.type:=type_error8.5 布爾表達(dá)式的翻譯布爾表達(dá)式的翻譯布爾表達(dá)式的兩個(gè)基本作用布爾表達(dá)式的兩個(gè)基本作用:n計(jì)算邏輯值：計(jì)算邏輯

40、值：a&b|c (C語(yǔ)言語(yǔ)言)n控制語(yǔ)句的條件表達(dá)式：控制語(yǔ)句的條件表達(dá)式： (C語(yǔ)言語(yǔ)言)nif (a5) t-;n產(chǎn)生布爾表達(dá)式的文法產(chǎn)生布爾表達(dá)式的文法nEE or E | E and E | not E|(E) | i rop i | true|falsen約定布爾算符的優(yōu)先順序從高到低為約定布爾算符的優(yōu)先順序從高到低為not,and,or，并且，并且and和和or服從左結(jié)合服從左結(jié)合8.5.1 布爾表達(dá)式的翻譯方法布爾表達(dá)式的翻譯方法n通常計(jì)算布爾表達(dá)式的值有兩種方法通常計(jì)算布爾表達(dá)式的值有兩種方法:1. 如同計(jì)算算術(shù)表達(dá)式一樣，一步步算（計(jì)算值）如同計(jì)算算術(shù)表達(dá)式一樣，一步

41、步算（計(jì)算值） 1 or (not 0 and 0) or 0 =1 or (1 and 0) or 0 =1 or 0 or 0 =1 or 0 =12. 采用某種優(yōu)化措施（控制語(yǔ)句中的條件表達(dá)式）采用某種優(yōu)化措施（控制語(yǔ)句中的條件表達(dá)式） 計(jì)算計(jì)算A or B，若，若A為為1，可以不計(jì)算，可以不計(jì)算B 8.5.1 布爾表達(dá)式的翻譯方法布爾表達(dá)式的翻譯方法n若按第一種辦法計(jì)算布爾表達(dá)式，則若按第一種辦法計(jì)算布爾表達(dá)式，則a or b and not c 翻譯成的四元式序列翻譯成的四元式序列為：為：（1）t1:=not c（2）t2:=b and t1（3）t3:=a or t2n對(duì)于關(guān)系表達(dá)

42、式對(duì)于關(guān)系表達(dá)式ab可看成等價(jià)的條件語(yǔ)句可看成等價(jià)的條件語(yǔ)句nif ab then 1 else 0 n翻譯成的四元式序列為：翻譯成的四元式序列為：n（1）if ab goto （4） （2）t:=0（3）goto （5）（4）t:=1（5）關(guān)于布爾表達(dá)式的翻譯模式關(guān)于布爾表達(dá)式的翻譯模式n過(guò)程過(guò)程emit生成四元式生成四元式nnextstat給出輸出序列中下一個(gè)四元式的地址給出輸出序列中下一個(gè)四元式的地址na or b and not c 翻譯成的四元式序列為：翻譯成的四元式序列為：（1）t1:=not c 生成四元式（生成四元式（1）之后，）之后，nextstat的值為的值為2（2）t2:

43、=b and t1（3）t3:=a or t2n每產(chǎn)生一個(gè)四元式后，過(guò)程每產(chǎn)生一個(gè)四元式后，過(guò)程emit便把便把nextstat加加1 布爾表達(dá)式的翻譯模式布爾表達(dá)式的翻譯模式 EE1 or E2 E.place:=newtemp;emit(E.place := E 1.place or E2.place)EE1 and E2 E.place:=newtemp;emit(E.place := E 1.place and E2.place)Enot E1 E.place:=newtemp; emit(E.place := not E 1.place)E(E1) E.place:=E1.place

44、Eid1 rop id2 E.place:=newtemp; emit(if id1.place rop id2. place goto nextstat+3); emit(E.place := 0); emit(goto nextstat+2); emit(E.place:= 1) Etrue E.place:=newtemp;E.place=1; Efalse E.place:=newtemp;E.place=0; 對(duì)于關(guān)系表達(dá)式對(duì)于關(guān)系表達(dá)式ab可看成等價(jià)的條件語(yǔ)句可看成等價(jià)的條件語(yǔ)句if ab then 1 else 0 翻譯成的四元式序列為：翻譯成的四元式序列為： （1）if ab

45、goto （4） （2）t:=0（3）goto （5）（4） t:=1（5）產(chǎn)生布爾表達(dá)式的文法產(chǎn)生布爾表達(dá)式的文法EE or E | E and E | not E|(E) | i rop i | true|false 約定布爾算符的優(yōu)先順序從高到低為約定布爾算符的優(yōu)先順序從高到低為not,and,or，并且，并且and和和or服從左結(jié)合服從左結(jié)合給出布爾表達(dá)式給出布爾表達(dá)式ab or cd and ef的語(yǔ)法樹（的語(yǔ)法樹（根據(jù)算符優(yōu)先根據(jù)算符優(yōu)先關(guān)系，采用自下向上分析關(guān)系，采用自下向上分析）abEcdEefEandEorE布爾表達(dá)式布爾表達(dá)式ab or cd and ef的翻譯結(jié)果的翻譯結(jié)

46、果（假設(shè)（假設(shè)nextstat從從0開始）開始）0: if ab goto 31: T1:=02: goto 43: T1:=14: if cd goto 75: T2:=06: goto 87: T2:=18: if ef goto 119: T3:=010: goto 1211: T3:=112: T4:=T2 and T313: T5:=T1 or T4EE1 or E2 E.place:=newtemp;emit(E.place := E 1.place or E2.place)EE1 and E2 E.place:=newtemp;emit(E.place := E 1.place

47、and E2.place)Enot E1 E.place:=newtemp; emit(E.place := not E 1.place)E(E1) E.place:=E1.placeEid1 rop id2 E.place:=newtemp;emit(if id1.place rop id2. place goto nextstat+3); emit(E.place := 0); emit(goto nextstat+2); emit(E.place:= 1) Etrue E.place:=newtemp;E.place=1; Efalse E.place:=newtemp;E.place=

48、0; abEcdEeif E then S1| if E then S1 else S2|while E do S1 S-if E then S1| if E then S1 else S2|while E do S1 這些語(yǔ)句的代碼結(jié)構(gòu)示意圖：這些語(yǔ)句的代碼結(jié)構(gòu)示意圖：E的代碼的代碼S1的代碼的代碼真真假假E的代碼的代碼S1的代碼的代碼真真假假S2的代碼的代碼goto outout：begin：E的代碼的代碼S1的代碼的代碼真真假假goto begin8.5.2 控制語(yǔ)句中布爾表達(dá)式的翻譯控制語(yǔ)句中布爾表達(dá)式的翻譯n布爾表達(dá)式布爾表達(dá)式E有兩個(gè)出口：真出口和假出口有兩個(gè)出口：真出口和假出口n

49、E.true是是E為為真真時(shí)控制流轉(zhuǎn)向的標(biāo)號(hào)時(shí)控制流轉(zhuǎn)向的標(biāo)號(hào)nE.false是是E為為假假時(shí)控制流轉(zhuǎn)向的標(biāo)號(hào)時(shí)控制流轉(zhuǎn)向的標(biāo)號(hào)n當(dāng)當(dāng)E為為a rop b（E-a rop b）作為條件轉(zhuǎn)移時(shí)，僅把）作為條件轉(zhuǎn)移時(shí)，僅把E翻譯成兩條代碼：條件轉(zhuǎn)和無(wú)條件轉(zhuǎn)翻譯成兩條代碼：條件轉(zhuǎn)和無(wú)條件轉(zhuǎn)n代碼為代碼為nif a rop b goto E.true ngoto E.false8.5.2 控制語(yǔ)句中布爾表達(dá)式的翻譯控制語(yǔ)句中布爾表達(dá)式的翻譯n對(duì)于對(duì)于E為為E1 or E2的形式的形式n若若E1為真，則可知道為真，則可知道E為真為真nE1的真出口與的真出口與E的真出口一樣的真出口一樣n若若E1為假，則必

50、須計(jì)算為假，則必須計(jì)算E2nE1的假出口是的假出口是E2的第一個(gè)四元式標(biāo)號(hào)的第一個(gè)四元式標(biāo)號(hào)nE2的真出口和假出口與的真出口和假出口與E的真出口和假出口一樣的真出口和假出口一樣n對(duì)于對(duì)于E為為E1and E2的形式的形式n若若E1為假，則可知道為假，則可知道E為假為假nE1的假出口與的假出口與E的假出口一樣的假出口一樣n若若E1為真，則必須計(jì)算為真，則必須計(jì)算E2nE1的真出口是的真出口是E2的第一個(gè)四元式標(biāo)號(hào)的第一個(gè)四元式標(biāo)號(hào)nE2的真出口和假出口與的真出口和假出口與E的真出口和假出口一樣的真出口和假出口一樣8.5.2 控制語(yǔ)句中布爾表達(dá)式的翻譯控制語(yǔ)句中布爾表達(dá)式的翻譯n例如：布爾表達(dá)式例如：布爾表達(dá)式ab or cf的翻譯的翻譯n(1) if ab goto E.truen(2) goto 3n(3) if cf goto E.truen(6) goto E.false注意：注意：E.true與與E.false的值有時(shí)不能在產(chǎn)生四元式的同時(shí)知道的值有時(shí)不能在產(chǎn)生四元式的同時(shí)知道語(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 goto (5)(4) goto (p+1)(E.fals