第八章 語法制導翻譯與中間代碼生成

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

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

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

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

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

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

7、E1+T ETTT1*FTFF (E)Fdigit語語 義義 規(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屬性是？屬性是？綜合屬性綜合屬性例：簡單算術表達式求值的語義描述（屬性文法）例：簡單算術表達式求值的語義描述（屬性文法）產產 生生 式式 語語 義義 規(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是繼承屬性是繼承屬性例：說明語句中各種變量的類型信息的語義規(guī)則（屬性文法）例：說明語句中各種變量的類型信息的語義規(guī)則（屬性文法）n綜合屬性綜合屬性n在語法樹中，一個結點的在語法樹中，一個結點的綜合屬性綜合屬性的值由其的值由其子結點子結點的屬性值確定。的屬性值確定。n使用自底向上的方法在每一個結點處使用語義規(guī)則使用自底向上的方法在每一個結點處使用語義規(guī)則計算綜合屬性的值計算綜合屬性的值3*5+4的的帶語

9、義信息帶語義信息的語法樹的語法樹 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 產產 生生 式式 語語 義義 規(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在語法樹中，一個結點的在語法樹中，一個結點的繼承屬性繼承屬性由此結點的由此結點的父結父結點和點和/或兄弟結點或兄弟結點的某些屬性確定的某些屬性確定句子句子real id1，id2，id3的的帶語義信息帶語義信息的語法樹的語法樹 id1L,id2L,id3LrealTDT.type=realL.in=realL.in=realL.in=real產產 生生 式式 語語 義義 規(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 語法制導翻譯概論語法制導翻譯概論n基于屬性文法的處理方法基于屬性文法的處理方法 n過程（一般情況）：過程（一般情況）：n對單詞符號串進行語法分析，構造語法分析樹對單詞符號串進行語法分析，構造語法分析樹n構造屬性依賴圖構造屬性依賴圖n獲得語義規(guī)則的計算順序獲得語義規(guī)則的計算順序n翻譯結果（語義規(guī)則的計算）翻譯結果（語義規(guī)則的計算）n產生代碼n在符號表中存放信息n給出錯誤信息n執(zhí)行任何其它動作n對輸入符號串的對輸入符號串的翻譯翻譯也就是根據(jù)語義規(guī)則進行也就是根據(jù)語義規(guī)則進行計算計算的結果。的結果。8.2.1 計算語義規(guī)則

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

13、E1E2 E.val:=E1.val+E2.val E1+E2Evalvalval語義規(guī)則的計算次序語義規(guī)則的計算次序 n一個一個依賴圖依賴圖的任何的任何拓撲排序拓撲排序都給出一個語法樹中結點都給出一個語法樹中結點的語義規(guī)則計算的有效順序的語義規(guī)則計算的有效順序n基于屬性文法的翻譯是很精確的基于屬性文法的翻譯是很精確的n基礎文法用于建立輸入符號串的語法分析樹基礎文法用于建立輸入符號串的語法分析樹n根據(jù)語義規(guī)則建立依賴圖根據(jù)語義規(guī)則建立依賴圖n從依賴圖的拓撲排序中，我們可以得到計算語義規(guī)從依賴圖的拓撲排序中，我們可以得到計算語義規(guī)則的順序則的順序 輸入串輸入串語法樹語法樹依賴圖依賴圖語義規(guī)則計算

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

15、和自下而上翻譯屬性文法和自下而上翻譯nS-屬性文法屬性文法：只含有綜合屬性：只含有綜合屬性nS屬性文法適合于一遍掃描的屬性文法適合于一遍掃描的自下而上自下而上分析分析n綜合屬性可以在分析輸入符號串的同時由自下綜合屬性可以在分析輸入符號串的同時由自下而上的分析器來計算。而上的分析器來計算。n分析器可以保存與棧中文法符號有關的綜合屬分析器可以保存與棧中文法符號有關的綜合屬性值，每當進行歸約時，新的屬性值就由棧中性值，每當進行歸約時，新的屬性值就由棧中正在歸約的產生式右邊符號的屬性值來計算。正在歸約的產生式右邊符號的屬性值來計算。n在分析棧中使用一個附加的域來存放綜合屬性在分析棧中使用一個附加的域來

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

17、:F (E) 6:Fi 產產 生生 式式 LEEE1+T ETTT1*FTFF (E)Fdigit語語 義義 規(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的分析和值計算過程的分析和值計算過程n 輸入輸入 state sym val用到的產生式用到的產生式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的分析和值計算過程的分析和值計算過程輸入輸入 statesym val 用到的產生式用到的產生式+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的分析和值計算過程的分析和值計算過程輸入輸入 statesym val 用到的產生式用到的產生式+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的分析和值計算過程的分析和值計算過程 輸入輸入 statesym val 用到的產生式用到的產生式 # 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一個屬性文法稱為一個屬性文法稱為L-L-屬性文法屬性文法，如果對于每個產，如果對于每個產生式生式AXAX1 1X X2 2X Xn n，其每個語義規(guī)則中的每個屬性，其每個語義規(guī)則中的每個屬性或者是綜合屬性，或者是或者是綜合屬性，或者是X Xj j(1(1 j j n)n)的一個繼承屬的一個繼承屬性且這個繼承屬性僅依賴于：性且這個繼承

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

23、其中，addop為為+或或-n是是L-屬性文法屬性文法n如果用如果用LR分析，很容易實現(xiàn)在語法分析時進行翻譯分析，很容易實現(xiàn)在語法分析時進行翻譯n例：將例：將2+3-5轉換成中綴表達式轉換成中綴表達式2Tprint 2E3Tprint +ETprint -E5print 5說明語義動作的語法樹說明語義動作的語法樹print 3例：將例：將2+3-5轉換成中綴表達式轉換成中綴表達式LR分析分析8.2.3 L-屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯n對對L-屬性文法進行自頂向下翻譯屬性文法進行自頂向下翻譯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語義動作的語法樹語義動作的語法樹-ETR9print(9)TR5print(5)print(-)+T2print(2)Rprint(+) 改寫后：改寫后：E-E addop T print(addop.lexeme)|TT

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

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

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

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

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

30、運算符為三目運算符8.3.2 三元式和樹形表示三元式和樹形表示n三元式三元式 n通過計算臨時變量值的語句的位置來引用這個臨時變通過計算臨時變量值的語句的位置來引用這個臨時變量量n三個域：三個域：op（運算符）、（運算符）、arg1(運算對象運算對象)和和arg2（運算對象）（運算對象）oparg1arg2(0)- c(1)*b(0)(2)- c(3)*b(2)(4)+(1)(3)(5)：= a(4)例如：例如：a:=b*(-c)+b*(-c)n例如，語句例如，語句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一個帶有四個域的記錄結構，這四個域分別稱為一個帶有四個域的記錄結構，這四個域分別稱為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為了更直觀，也把四元式的形式寫成簡單賦值形式為了更直觀，也把四元式的形式寫成簡單賦值形式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 簡單賦值語句的翻譯簡單賦值語句的翻譯n在上面的四元式中，使用變量名字本身表示運算對象在上面的四元式中，使用變量名字本身表示運算對象n

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

34、四元式：子程序，生成四元式nnewtemp：產生新的臨時變量：產生新的臨時變量產生賦值語句的四元式翻譯模式產生賦值語句的四元式翻譯模式 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)產生賦值語句的四元式翻譯模式（續(xù)）產生賦值語句的四元式翻譯模式（續(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 在翻譯中有時需要類型轉換在翻譯中有時需要類型轉換用用E.type表示非終結符表示非終結符E的類型屬性的類型屬性 n假設只有整型和實型，對應產生式假設只有整型和實型，對應產生式EE1 op E2的語義動作的語義動作中關于中關于E.type

37、的語義規(guī)則可定義為：的語義規(guī)則可定義為： if E1.type=integer and E2.type=integer E.type:=integer else E.type:=real n算符區(qū)分為整型算符算符區(qū)分為整型算符int op和實型算符和實型算符real opnx:=yi*j 其中其中x、y為實型；為實型；i、j為整型。這個賦值句產生的四元為整型。這個賦值句產生的四元式代碼（簡寫）為：式代碼（簡寫）為： T1:=i int* j T3:=inttoreal T1 T2:=y real+ T3 x:=T2關于產生式關于產生式EE1 E2 的語義動作的語義動作 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 布爾表達式的翻譯布爾表達式的翻譯布爾表達式的兩個基本作用布爾表達式的兩個基本作用:n計算邏輯值：計算邏輯

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

41、步算（計算值） 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ōu)化措施（控制語句中的條件表達式） 計算計算A or B，若，若A為為1，可以不計算，可以不計算B 8.5.1 布爾表達式的翻譯方法布爾表達式的翻譯方法n若按第一種辦法計算布爾表達式，則若按第一種辦法計算布爾表達式，則a or b and not c 翻譯成的四元式序列翻譯成的四元式序列為：為：（1）t1:=not c（2）t2:=b and t1（3）t3:=a or t2n對于關系表達

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

43、=b and t1（3）t3:=a or t2n每產生一個四元式后，過程每產生一個四元式后，過程emit便把便把nextstat加加1 布爾表達式的翻譯模式布爾表達式的翻譯模式 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; 對于關系表達式對于關系表達式ab可看成等價的條件語句可看成等價的條件語句if ab then 1 else 0 翻譯成的四元式序列為：翻譯成的四元式序列為： （1）if ab

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

46、果（假設（假設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 這些語句的代碼結構示意圖：這些語句的代碼結構示意圖：E的代碼的代碼S1的代碼的代碼真真假假E的代碼的代碼S1的代碼的代碼真真假假S2的代碼的代碼goto outout：begin：E的代碼的代碼S1的代碼的代碼真真假假goto begin8.5.2 控制語句中布爾表達式的翻譯控制語句中布爾表達式的翻譯n布爾表達式布爾表達式E有兩個出口：真出口和假出口有兩個出口：真出口和假出口n

49、E.true是是E為為真真時控制流轉向的標號時控制流轉向的標號nE.false是是E為為假假時控制流轉向的標號時控制流轉向的標號n當當E為為a rop b（E-a rop b）作為條件轉移時，僅把）作為條件轉移時，僅把E翻譯成兩條代碼：條件轉和無條件轉翻譯成兩條代碼：條件轉和無條件轉n代碼為代碼為nif a rop b goto E.true ngoto E.false8.5.2 控制語句中布爾表達式的翻譯控制語句中布爾表達式的翻譯n對于對于E為為E1 or E2的形式的形式n若若E1為真，則可知道為真，則可知道E為真為真nE1的真出口與的真出口與E的真出口一樣的真出口一樣n若若E1為假，則必

50、須計算為假，則必須計算E2nE1的假出口是的假出口是E2的第一個四元式標號的第一個四元式標號nE2的真出口和假出口與的真出口和假出口與E的真出口和假出口一樣的真出口和假出口一樣n對于對于E為為E1and E2的形式的形式n若若E1為假，則可知道為假，則可知道E為假為假nE1的假出口與的假出口與E的假出口一樣的假出口一樣n若若E1為真，則必須計算為真，則必須計算E2nE1的真出口是的真出口是E2的第一個四元式標號的第一個四元式標號nE2的真出口和假出口與的真出口和假出口與E的真出口和假出口一樣的真出口和假出口一樣8.5.2 控制語句中布爾表達式的翻譯控制語句中布爾表達式的翻譯n例如：布爾表達式例如：布爾表達式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的值有時不能在產生四元式的同時知道的值有時不能在產生四元式的同時知道語語句句 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