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

1、第六章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成學(xué)習(xí)目標(biāo)：掌握：常見(jiàn)語(yǔ)法成分的中間代碼形式；常見(jiàn)語(yǔ)法成分的屬性文法或翻譯方法理解：屬性文法、語(yǔ)法制導(dǎo)翻譯方法天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系主要內(nèi)容屬性文法和語(yǔ)法制導(dǎo)翻譯：屬性文法語(yǔ)法制導(dǎo)翻譯基本思想中間代碼的表示形式（逆波蘭式、四元式、三元式、間接三元式、樹(shù)結(jié)構(gòu)等等）簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯布爾表達(dá)式到四元式的翻譯控制結(jié)構(gòu)翻譯成四元式天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系目標(biāo)程序源程序詞法分析語(yǔ)法分析語(yǔ)義分析中間代碼生成代碼優(yōu)化目標(biāo)代碼生成表格管理出錯(cuò)處理天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系語(yǔ)義分析基礎(chǔ)語(yǔ)義分析的內(nèi)容主要是類型相容檢查，有以下幾種：各種條件表達(dá)式的類型是不是

2、boolean型？運(yùn)算符的分量類型是否相容？賦值語(yǔ)句的左右部的類型是否相容？形參和實(shí)參的類型是否相容?下標(biāo)表達(dá)式的類型是否為所允許的類型？函數(shù)說(shuō)明中的函數(shù)類型和返回值的類型是否一致？天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系語(yǔ)義分析基礎(chǔ)-語(yǔ)義分析的內(nèi)容（續(xù)）其它語(yǔ)義檢查：VE中的V是不是變量，而且是數(shù)組類型？V.i中的V是不是變量，而且是記錄類型？i是不是該記錄的域名？x+f()中的f是不是函數(shù)名？形參個(gè)數(shù)和實(shí)參個(gè)數(shù)是否一致？每個(gè)使用性標(biāo)識(shí)符是否都有聲明？有無(wú)標(biāo)識(shí)符的重復(fù)聲明？天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系語(yǔ)義分析基礎(chǔ)在語(yǔ)義分析同時(shí)產(chǎn)生中間代碼，在這種模式下，語(yǔ)義分析的主要功能如下：語(yǔ)義審查在掃描聲明部分時(shí)構(gòu)

3、造標(biāo)識(shí)符的符號(hào)表在掃描語(yǔ)句部分時(shí)產(chǎn)生中間代碼中間代碼：獨(dú)立于機(jī)器，復(fù)雜性介于源語(yǔ)言和機(jī)器語(yǔ)言之間，十分接近目標(biāo)機(jī)器指令的一種表示形式。對(duì)于中間代碼的產(chǎn)生，是很困難的，因?yàn)檎Z(yǔ)義形式化比語(yǔ)法形式化難得多。目前普遍采用的語(yǔ)義分析方法語(yǔ)法制導(dǎo)翻譯方法使用屬性文法為工具來(lái)說(shuō)明程序設(shè)計(jì)語(yǔ)言的語(yǔ)義。天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.1屬性文法(Attribute Grammar)屬性對(duì)文法的每一個(gè)符號(hào)，引進(jìn)一些屬性，這些屬性代表與文法符號(hào)相關(guān)的信息，如類型、值、存儲(chǔ)位置等。語(yǔ)義規(guī)則為文法的每一個(gè)產(chǎn)生式配備的計(jì)算屬性的計(jì)算規(guī)則，稱為語(yǔ)義規(guī)則。屬性文法是帶屬性的一種文法它的主要思想：首先對(duì)于每個(gè)文法符號(hào)引進(jìn)相關(guān)的

4、屬性符號(hào)；其次對(duì)于每個(gè)產(chǎn)生式寫(xiě)出計(jì)算屬性值的語(yǔ)義規(guī)則天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.1 屬性文法(續(xù))屬性文法的形式定義一個(gè)屬性文法是一個(gè)三元組,A(G, V, F)G是一個(gè)上下文無(wú)關(guān)文法；V是屬性的有窮集；F是關(guān)于屬性的斷言的有窮集。說(shuō)明：每個(gè)屬性與文法符號(hào)相聯(lián)，N.t表示文法符號(hào)N的屬性t。屬性值又稱語(yǔ)義值。存儲(chǔ)屬性值的變量又稱語(yǔ)義變量。每個(gè)斷言與文法的某個(gè)產(chǎn)生式相聯(lián)，寫(xiě)在 內(nèi)。屬性的斷言又稱語(yǔ)義規(guī)則，它所描述的工作可以包括屬性計(jì)算、靜態(tài)語(yǔ)義檢查、符號(hào)表的操作、代碼生成等，有時(shí)寫(xiě)成函數(shù)或過(guò)程段。天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.1 屬性文法(續(xù))例 完成類型檢查的屬性文法ET1+T2T1.t

5、int AND T2.tintET1 or T2T1.tbool AND T2.tboolTnumT.t :intTtrueT.t :boolTfalseT.t :bool天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.1 屬性文法(續(xù))屬性的分類：綜合屬性：從語(yǔ)法樹(shù)的角度來(lái)看，如果一個(gè)結(jié)點(diǎn)的某一屬性值是由該結(jié)點(diǎn)的子結(jié)點(diǎn)的屬性值計(jì)算來(lái)的，則稱該屬性為綜合屬性。內(nèi)在屬性是綜合屬性。用于“自下而上”傳遞信息天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.1 屬性文法(續(xù))繼承屬性從語(yǔ)法樹(shù)的角度來(lái)看，若一個(gè)結(jié)點(diǎn)的某一屬性值是由該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)和（或）父結(jié)點(diǎn)的屬性值計(jì)算來(lái)的，則稱該屬性為繼承屬性。用于“自上而下”傳遞信息特別說(shuō)明：終

6、結(jié)符只有綜合屬性，它們由詞法分析器提供非終結(jié)符既有綜合屬性也有繼承屬性，但文法開(kāi)始符沒(méi)有繼承屬性天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.1 屬性文法(續(xù))例 簡(jiǎn)單算術(shù)表達(dá)式求值的屬性文法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.lexval E.val、T.val、F.val都是綜合屬性終結(jié)符digit只有綜合屬性lexval ，它的值由詞法分析器提供天津財(cái)經(jīng)大學(xué)信

7、息科學(xué)與技術(shù)系6.2 語(yǔ)法制導(dǎo)翻譯概論語(yǔ)法制導(dǎo)翻譯基本思想：在語(yǔ)法分析過(guò)程中，隨著分析的步步進(jìn)展，每當(dāng)使用一條產(chǎn)生式進(jìn)行推導(dǎo)（對(duì)于自上而下分析）或歸約（對(duì)于自下而上分析），就執(zhí)行該產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義動(dòng)作（語(yǔ)義子程序），完成相應(yīng)的翻譯工作（產(chǎn)生中間代碼）。語(yǔ)法制導(dǎo)翻譯法不論對(duì)自上而下分析或自下而上分析都適用。天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系例 簡(jiǎn)單算術(shù)表達(dá)式求值的屬性文法EE1+T E.val :E1.val +T.val ET E.val :T.val TT1*digit T.val :T1.val * digit.lexval Tdigit T.val :digit.lexval 2+3*5的語(yǔ)

8、法樹(shù)：EE1+TT1*5T23T.val=2T.val=3T.val=15E.val=2E.val=17自下而上語(yǔ)法制導(dǎo)翻譯過(guò)程：一旦語(yǔ)法分析確認(rèn)輸入符號(hào)串是一個(gè)句子，它的值也同時(shí)由語(yǔ)義規(guī)則計(jì)算出來(lái)天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.3 中間代碼的形式定義：中間代碼是獨(dú)立于機(jī)器，復(fù)雜性介于源語(yǔ)言和機(jī)器語(yǔ)言之間，十分接近目標(biāo)機(jī)器指令的一種表示形式。使用中間代碼的好處：中間代碼與具體機(jī)器無(wú)關(guān)，便于編譯程序改變目標(biāo)機(jī)便于對(duì)中間代碼進(jìn)行與機(jī)器無(wú)關(guān)的優(yōu)化表示形式：逆波蘭式、四元式、三元式、間接三元式和樹(shù)形表示天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.3.1 逆波蘭表示法（后綴式） 逆波蘭表示法將運(yùn)算對(duì)象寫(xiě)在前面，把運(yùn)

9、算符寫(xiě)在后面，因而也稱后綴式。例如：程序設(shè)計(jì)語(yǔ)言中的表示逆波蘭表示a+bab+a+b*c abc * +(a+b)*cab+c *天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系bt1dct1t2t1t3t1= - bt2= c*dt3= t1+t2例：表達(dá)式bc*d的后綴式 bcd*+的計(jì)值過(guò)程后綴式的計(jì)算機(jī)處理后綴式的最大優(yōu)點(diǎn)是易于計(jì)算機(jī)處理處理過(guò)程：從左到右掃描后綴式，每碰到運(yùn)算對(duì)象就推進(jìn)棧；碰到運(yùn)算符就從棧頂彈出相應(yīng)目數(shù)的運(yùn)算對(duì)象施加運(yùn)算，并把結(jié)果推進(jìn)棧。最后的結(jié)果留在棧頂。天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系逆波蘭表示法的擴(kuò)充逆波蘭表示法很容易擴(kuò)充到表達(dá)式以外的范圍 例如：語(yǔ)句逆波蘭表示備注a:=b+cabc+

10、:=:=看作二目運(yùn)算符GOTO LL jumpjump看成一目運(yùn)算符，表示GOTOIf E then S1 else S2ES1S2￥把￥ 看成三目運(yùn)算符，表示if then else天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.3.2 三元式三元式(算符op，第一個(gè)運(yùn)算對(duì)象ARG1,第二個(gè)運(yùn)算對(duì)象ARG2)說(shuō)明：三元式的某些運(yùn)算對(duì)象是另一個(gè)三元式的編號(hào)（代表其結(jié)果）一目算符只需選用一個(gè)運(yùn)算對(duì)象（ARG1）多目算符可用連續(xù)幾個(gè)三元式表示例： a :b*c+b*d表示為 (1) (* ,b,c)(2) (* ,b,d)(3) (+ ,(1),(2)(4) (:,(3),a)天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.3.

11、3 樹(shù)形表示樹(shù)形表示二目運(yùn)算對(duì)應(yīng)二叉子樹(shù)，多目運(yùn)算對(duì)應(yīng)多叉子樹(shù)，但通常通過(guò)引入新結(jié)點(diǎn)表示成二叉子樹(shù)。例如：a:b*c+b*d 表示成:=a+*bcbd葉子結(jié)點(diǎn)代表運(yùn)算量，非葉子結(jié)點(diǎn)代表運(yùn)算符天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.3.4 四元式四元式四元式是一種比較普遍采用的中間代碼形式(算符op，ARG1，ARG2，運(yùn)算結(jié)果RESULT）例如：a:b*c+b*d的四元式表示如下： (*,b,c,t1 )(*,b,d,t2 )(+,t1,t2,t3 )(:,t3 ,a ) 其中t i（i1,2,3）是編譯程序引入的臨時(shí)變量天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.3.4 四元式（續(xù)）四元式的優(yōu)點(diǎn)：四元式比三元式

12、更便于優(yōu)化優(yōu)化要求改變運(yùn)算順序或刪除某些運(yùn)算，引起編號(hào)的變化。三元式通過(guò)編號(hào)引用中間結(jié)果，編號(hào)的變化引起麻煩；四元式通過(guò)臨時(shí)變量引用中間結(jié)果，編號(hào)變化無(wú)影響。四元式對(duì)生成目標(biāo)代碼有利四元式表示很類似于三地址指令，很容易轉(zhuǎn)換成機(jī)器代碼。天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.3.4 四元式（續(xù)）四元式的另一種表示有時(shí)為了更直觀，把四元式寫(xiě)成簡(jiǎn)單賦值形式或更易理解的形式(三地址碼)四元式直觀形式（1）（ * , b , c , t1）（1） t1:b*c（2）（ * , b , d , t2）（2） t2:b*d（3）（ +, t1 , t2 , t3）（3） t3:t1+t2（4）（:, t3 , a）

13、（4） a:t3天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.3.5 間接三元式為了便于優(yōu)化處理，不直接使用三元式，而是另設(shè)一張指示器表（稱為間接碼表），它按照運(yùn)算的先后順序列出有關(guān)三元式在三元式表中的位置。即：用一張間接碼表輔以三元式表的方法來(lái)表示中間代碼。四元式、間接三元式的優(yōu)化同樣方便，三元式的優(yōu)化十分困難。天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系舉例：給出A+B*(C-D)+E/(C-D)N的逆波蘭式、四元式、三元式、間接三元式的表示1、逆波蘭式：ABCD-*+ECD-N/+2、四元式：(-,C,D,T1)(*,B,T1,T2)(+,A, T2, T3)(-,C,D, T4)(, T4,N, T5)(/,E,

14、T5, T6)(+, T3, T6, T7)天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系舉例：給出A+B*(C-D)+E/(C-D)N的逆波蘭式、四元式、三元式、間接三元式的表示3、三元式：(-,C,D)(*,B,1)(+,A, 2)(-,C,D)(, 4),N)(/,E,5)(+, 3),6)4、間接三元式：(-,C,D)(*,B,1)(+,A, 2)(, 1),N)(/,E,4)(+, 3),5)間接碼表1)2)3)1)4)5)6)天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.4 語(yǔ)法制導(dǎo)翻譯主要討論自下而上的語(yǔ)法制導(dǎo)翻譯在一個(gè)產(chǎn)生式進(jìn)行歸約時(shí)，執(zhí)行相應(yīng)的語(yǔ)義動(dòng)作進(jìn)行翻譯（產(chǎn)生中間代碼）天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.

15、4.1簡(jiǎn)單賦值語(yǔ)句到四元式的翻譯簡(jiǎn)單賦值語(yǔ)句是指不含復(fù)雜數(shù)據(jù)類型（如數(shù)組，記錄等）的賦值語(yǔ)句。賦值語(yǔ)句的語(yǔ)義檢查包括：每個(gè)使用性標(biāo)識(shí)符是否都有聲明？運(yùn)算符的分量類型是否相容？賦值語(yǔ)句的左右部的類型是否相容？賦值語(yǔ)句的翻譯目標(biāo)：在賦值語(yǔ)句右部表達(dá)式產(chǎn)生的四元式序列后加一條賦值四元式天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.4.1簡(jiǎn)單賦值語(yǔ)句到四元式的翻譯考慮如下文法描述的簡(jiǎn)單賦值句的翻譯：Ai:=E EE+E|E*E|-E|(E)|i (6.1)A代表賦值語(yǔ)句，設(shè)只含整型變量的運(yùn)算1、需要定義一系列的語(yǔ)義變量和語(yǔ)義過(guò)程：NEWTEMP：函數(shù)，生成臨時(shí)變量，每次調(diào)用生成一個(gè)新的臨時(shí)變量，如t1, t2 ,

16、返回一個(gè)整數(shù)碼作為函數(shù)值。ENTRY(i)：函數(shù)過(guò)程，查找并取得與i相對(duì)應(yīng)的標(biāo)識(shí)符在符號(hào)表中的位置（入口），簡(jiǎn)稱i值。E.PLACE：與E相聯(lián)系的語(yǔ)義變量，表示存放E值的變量名在符號(hào)表的入口。GEN(OP,ARG1,ARG1,RESULT)：語(yǔ)義過(guò)程，將四元式(OP,ARG1,ARG1,RESULT)填進(jìn)四元式表中。 天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系使用上述變量和過(guò)程，對(duì)文法6.1所定義的賦值語(yǔ)句的翻譯算法可由下述語(yǔ)義動(dòng)作予以描述6.4.1簡(jiǎn)單賦值語(yǔ)句到四元式的翻譯產(chǎn)生式語(yǔ)義動(dòng)作Ai:=E GEN(:=,E.PLACE,-,ENTRY(i) EE(1)+E (2) E.PLACE:=NEWTEMP

17、; GEN(+,E(1).PLACE,E(2).PLACE,E.PLACE) EE(1)*E (2) E.PLACE:=NEWTEMP; GEN(*,E(1).PLACE,E(2).PLACE,E.PLACE) E-E(1) E.PLACE:=NEWTEMP; GEN(,E(1).PLACE,-,E.PLACE) E(E(1) E.PLACE:=E(1).PLACE Ei E.PLACE:=ENTRY(i) 天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系輸入串棧PLACE四元式A:=-B*(C+D):=-B*(C+D)iA-B*(C+D)i:=A_B*(C+D)i:= -A_ _*(C+D)i:= -iA_ _

18、B*(C+D)i:= -EA_ _B(,B,-,T1)*(C+D)i:= EA_T1(C+D)i:= E*A_T1 _C+D)i:= E*(A_T1 _ _+D)i:= E*( iA_T1 _ _C+D)i:= E*( EA_T1 _ _CD)i:= E*( E+A_T1 _ _C_)i:= E*( E+iA_T1 _ _C_D)i:= E*( E+EA_T1 _ _C_D(+,C,D,T2)i:= E*( EA_T1 _ _T2i:= E*( E)A_T1 _ _T2 _i:= E* EA_T1 _T2(*, T1 ,T2,T3)i:=EA_ T3(:=, T3, - ,A)A2例：寫(xiě)出下面

19、賦值語(yǔ)句A:=-B*(C+D)的自下而上語(yǔ)法制導(dǎo)翻譯的過(guò)程，及生成的四元式。Ai:=E EE+E|E*E|-E|(E)|i 四元式為:(1)(,B,-,T1) (2) (+,C,D,T2) (3)(*, T1 ,T2,T3) (4) (:=, T3, - ,A)天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系3、類型轉(zhuǎn)換表達(dá)式中可能出現(xiàn)不同類型的變量和常量若不接受不同類型的運(yùn)算對(duì)象混合運(yùn)算，則應(yīng)指出錯(cuò)誤；若接受混合運(yùn)算則要進(jìn)行類型轉(zhuǎn)換處理。例：假定表達(dá)式可以有混合運(yùn)算，變量可以是整型和實(shí)型，且當(dāng)兩個(gè)不同類型的變量進(jìn)行運(yùn)算時(shí)先把整型變量轉(zhuǎn)換成實(shí)型，再進(jìn)行運(yùn)算。用 +i , *i , i 表示整型運(yùn)算，用 +r ,

20、*r, r表示實(shí)型運(yùn)算，用一目算符 itr 表示將整型量轉(zhuǎn)換成實(shí)型量的運(yùn)算令文法6.1中的 i 既可以是整型也可以是實(shí)型用E.MODE表示E的類型信息，其值為int或r，則產(chǎn)生式EE(1) op E(2)的語(yǔ)義動(dòng)作中，關(guān)于E.MODE的語(yǔ)義規(guī)則可定義為： if E1. MODE int AND E2. MODE int then E. MODE :=int else E. MODE :=r 天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系3、類型轉(zhuǎn)換（續(xù)）EE(1) op E(2) 的語(yǔ)義程序應(yīng)該修改，必要時(shí)產(chǎn)生對(duì)運(yùn)算量進(jìn)行類型轉(zhuǎn)換的四元式：(itr,A,-,T)，表示把整型A轉(zhuǎn)換成實(shí)型量，結(jié)果存于T中。例：假定

21、輸入串為X:=Y+I*J，其中X,Y為實(shí)型，I,J為整型，則其產(chǎn)生的四元式為：(1) (*i ,I,J,T1) (2)(itr,T1,-,T2) (3) (+r ,Y,T2,T3) (4) (:=,T3,-,X)例：關(guān)于產(chǎn)生式EE(1) op E(2) 的語(yǔ)義子程序更為具體的描述為：天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系T:=NEWTEMP;IF E1.MODE=int AND E2.MODE=int THEN BEGIN GEN(opi , E1.PLACE, E2.PLACE,T); E.MODE:=int ENDELSE IF E1.MODE=r AND E2.MODE=r THEN BEGIN

22、GEN(opr , E1.PLACE, E2.PLACE,T); E.MODE:=r ENDELSE IF E1.MODE=int /*AND E2.MODE=r */ THEN BEGIN U:=NEWTEMP; GEN(itr, E1.PLACE,-,U);GEN(opr , U,E2.PLACE,T); E.MODE:=r ENDELSE /* E1.MODE=r AND E2.MODE=int */ BEGINU:=NEWTEMP; GEN(itr, E2.PLACE,-,U);GEN(opr , E2.PLACE, U, T); E.MODE:=r ENDE.PLACE:=TEE(1

23、) op E(2)天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系布爾表達(dá)式的兩個(gè)作用：用于邏輯運(yùn)算，計(jì)算邏輯值作為控制語(yǔ)句(如if-then,while)的條件表達(dá)式布爾表達(dá)式由布爾算符（not,and,or）作用于布爾變量（或常數(shù)）或關(guān)系表達(dá)式而形成的。關(guān)系表達(dá)式的形式：E1 rop E2，rop是關(guān)系算符(如, , =)6.4.2布爾表達(dá)式到四元式的翻譯天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系為簡(jiǎn)單起見(jiàn)，只考慮如下形式的布爾表達(dá)式的翻譯，文法(6.2)EE or E | E and E | not E | (E ) | id rop id |id布爾算符的優(yōu)先順序（從高到低）為：not,and,or，且and和or都服

24、從左結(jié)合，not服從右結(jié)合關(guān)系算符的優(yōu)先級(jí)都相同，而且高于任何布爾算符，低于任何算術(shù)算符6.4.2布爾表達(dá)式到四元式的翻譯-續(xù)天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系1.布爾表達(dá)式的計(jì)算方法： 采用兩種方法：數(shù)值表示的直接計(jì)算與邏輯表示的短路計(jì)算直接計(jì)算與算術(shù)表達(dá)式計(jì)算方法基本相同如：1 or 0 and 1=1 or 0 的結(jié)果為：1短路計(jì)算即布爾表達(dá)式計(jì)算到某一部分就可以得到結(jié)果，而無(wú)需對(duì)布爾表達(dá)式進(jìn)行完全計(jì)算?？梢杂胕f-then-else來(lái)解釋A or B if A then true else BA and Bif A then B else falsenot Aif A then false

25、else true天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系2、直接計(jì)算的語(yǔ)法制導(dǎo)翻譯布爾表達(dá)式有兩種翻譯方法。（視計(jì)算機(jī)硬件條件來(lái)確定，如果執(zhí)行條件轉(zhuǎn)移效率較低，就用第一種方法）直接計(jì)算的語(yǔ)法制導(dǎo)翻譯 如同翻譯算術(shù)表達(dá)式一樣來(lái)翻譯布爾表達(dá)式如：A or B and not C被翻譯成：(1) (not,C,- ,T1)(2) (and,B,T1,T2)(3) (or,A,T2,T3)天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系3.作為條件控制的布爾式翻譯基本翻譯方法當(dāng)布爾表達(dá)式用于控制條件時(shí)，并不需要計(jì)算表達(dá)式的值，而是一旦確定了表達(dá)式為真或?yàn)榧伲蛯⒖刂妻D(zhuǎn)向相應(yīng)的代碼序列。S2 的代碼S1 的代碼E的代碼E.false

26、 E.true if E then S1 else S2為布爾表達(dá)式E引入兩個(gè)新的屬性：E.true：表達(dá)式的真出口，它指向表達(dá)式為真時(shí)的轉(zhuǎn)向E.false：表達(dá)式的假出口，它指向表達(dá)式為假時(shí)的轉(zhuǎn)向天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系把布爾表達(dá)式E翻譯成下述形式的條件轉(zhuǎn)移和無(wú)條件轉(zhuǎn)移的四元式序列：( jnz , A , - , p )若A為真，則轉(zhuǎn)向四元式p( jrop , A , B , p )若A rop B為真，則轉(zhuǎn)向四元式p( j , - , - , p )無(wú)條件轉(zhuǎn)向四元式p3.作為條件控制的布爾式翻譯-續(xù)天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系(1) ( jnz , A , - , 5 )A的真出口為5

27、(2) ( j , - , - , 3 )A的假出口為3(3) ( j , B , D , 5 )BD的真出口為5(4) ( j , - , - , p+1 ) BD的假出口為(p+1)(5) (關(guān)于S1的四元式序列)(p)( j , - , - , q )跳過(guò)S2的代碼段(p+1)(關(guān)于S2的四元式序列)(q)(1) - (4)是布爾式A or BD 翻譯產(chǎn)生的代碼，全部是條件轉(zhuǎn)移和無(wú)條件轉(zhuǎn)移四元式，沒(méi)有布爾運(yùn)算。例：if A or BD then S1 else S2翻譯成如下四元式序列天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系具體說(shuō)明如下：用E.true和E.false 分別表示E的“真”和“假”出口

28、轉(zhuǎn)移目標(biāo)，在翻譯E時(shí)并未能確定。對(duì)于E為 a rop b 形式，生成代碼如下：( jrop , a , b , E.true )( j , E.false )以結(jié)構(gòu)圖表示：E的代碼E.falseE.true天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系對(duì)于E為 E1 or E2的形式，生成代碼結(jié)構(gòu)如下：E1.的代碼E2.的代碼E1.falseE2.falseE.falseE1.trueE2.trueE.true若E1為真，則可知E為真，即E1的真出口和E的真出口一樣；若E1為假，則必須計(jì)算E2，因此E1的假出口應(yīng)是E2代碼的第一個(gè)四元式序號(hào)；E2的真出口和假出口分別與E的真出口和假出口一樣天津財(cái)經(jīng)大學(xué)信息科學(xué)與

29、技術(shù)系E1.的代碼E2.的代碼E1.falseE2.falseE.falseE1.trueE2.trueE.true對(duì)于E為 E1 and E2的形式，生成代碼結(jié)構(gòu)如下：對(duì)于E為 not E1形式，只需調(diào)換E1的真假出口，即可得到E的真假出口。天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系例：E 為 ab or cf ，翻譯為四元式序列：（1） (j, a,b,E.true)（2） (j, - ,- ,(3)（3） (j, e ,f ,E.true)（6） (j, - ,- ,E.false)舉例真假出口的拉鏈與回填在把布爾式翻譯成一串條件轉(zhuǎn)和無(wú)條件轉(zhuǎn)四元式時(shí)，真假出口未能在生成四元式時(shí)確定；而且多個(gè)四元式可能

30、有相同的出口天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系說(shuō)明：E.true和E.false不能在產(chǎn)生四元式的同時(shí)確定，要等將來(lái)目標(biāo)明確時(shí)再回填，為此要記錄這些要回填的四元式。通常采用“拉鏈”的辦法，把需要回填E.true的四元式拉成一條“真”鏈，把需要回填E.false的四元式拉成一條“假”鏈。if ab or cf then S1 else S2翻譯為四元式序列：（1） (j , a ,b ,(7)（2） (jump, - ,- ,(3)（3） (j , e ,f ,(7)（6） (jump, - ,- ,(p+1) （7）(關(guān)于S1的四元式)（p）(jump, - ,- ,q)(p+1)(關(guān)于S2的四元式

31、) (q)天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系練習(xí)：把下面的語(yǔ)句翻譯成四元式序列：If AB or CD then X:=Y else X:=Y=1100 (j,A,B,104)101 (j,-,-,102)102 (j,C,D,104)103 (j,-,-,106)104 (:=,Y,-,X)105 (j,-,-,108)106 (+,Y,1,T)107 (:=,T,-,X)108說(shuō)明：產(chǎn)生是100103是對(duì)應(yīng)布爾式AB or C=,C,D,106)。但這些是下一階段代碼優(yōu)化要討論的問(wèn)題，暫不討論。天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.4.3 控制語(yǔ)句的翻譯以if 語(yǔ)句，while語(yǔ)句為例說(shuō)明控制語(yǔ)句的翻譯方法S if E then S1 if語(yǔ)句| if E then S1 else S2if語(yǔ)句| while E do Swhile語(yǔ)句其中：E:布爾表達(dá)式， S，S1 , S2 為語(yǔ)句天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系E1=1E2=1S1S2S3endstartYesNoYesNo條件轉(zhuǎn)移語(yǔ)句的共同特點(diǎn)是：根據(jù)布爾表達(dá)式取值，分別執(zhí)行不同的語(yǔ)句序列。問(wèn)題：不同的語(yǔ)句序列結(jié)束后，如何使控制轉(zhuǎn)向語(yǔ)句的結(jié)束。例如：if E1