第八章語法制導(dǎo)和中間代碼生成

1、第八章第八章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成學(xué)習(xí)目標(biāo)：學(xué)習(xí)目標(biāo)：v掌握：掌握：常見語法成分的中間代碼形式；常見語法成分的中間代碼形式；常見語法成分的屬性文法或翻譯方案常見語法成分的屬性文法或翻譯方案v理解：理解：屬性文法、語法制導(dǎo)翻譯方法屬性文法、語法制導(dǎo)翻譯方法目標(biāo)程序目標(biāo)程序源程序源程序詞法分析詞法分析語法分析語法分析語義分析語義分析中間代碼生成中間代碼生成代碼優(yōu)化代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成表格管理表格管理出錯處理出錯處理語義分析基礎(chǔ)語義分析基礎(chǔ)語義分析的內(nèi)容語義分析的內(nèi)容 主要是類型相容檢查，有以下幾種：主要是類型相容檢查，有以下幾種：1) 各種條件表達(dá)式的類

2、型是不是各種條件表達(dá)式的類型是不是boolean型？型？2) 運(yùn)算符的分量類型是否相容？運(yùn)算符的分量類型是否相容？3) 賦值語句的左右部的類型是否相容？賦值語句的左右部的類型是否相容？4) 形參和實(shí)參的類型是否相容形參和實(shí)參的類型是否相容?5) 下標(biāo)表達(dá)式的類型是否為所允許的類型？下標(biāo)表達(dá)式的類型是否為所允許的類型？6) 函數(shù)說明中的函數(shù)類型和返回值的類型是否一函數(shù)說明中的函數(shù)類型和返回值的類型是否一致？致？其它語義檢查：其它語義檢查：1)VE中的中的V是不是變量，而且是數(shù)組類型？是不是變量，而且是數(shù)組類型？2)V.i中的中的V是不是變量，而且是記錄類型？是不是變量，而且是記錄類型？i是不是不

3、是該記錄的域名？是該記錄的域名？3)x+f()中的中的f是不是函數(shù)名？形參個數(shù)和實(shí)參個是不是函數(shù)名？形參個數(shù)和實(shí)參個數(shù)是否一致？數(shù)是否一致？4)每個使用性標(biāo)識符是否都有聲明？有無標(biāo)識符每個使用性標(biāo)識符是否都有聲明？有無標(biāo)識符的重復(fù)聲明？的重復(fù)聲明？在語義分析同時產(chǎn)生中間代碼，在這種模式下，在語義分析同時產(chǎn)生中間代碼，在這種模式下，語義分析的主要功能如下：語義分析的主要功能如下：語義審查語義審查在掃描聲明部分時構(gòu)造標(biāo)識符的符號表在掃描聲明部分時構(gòu)造標(biāo)識符的符號表在掃描語句部分時產(chǎn)生中間代碼在掃描語句部分時產(chǎn)生中間代碼語義分析方法語義分析方法語法制導(dǎo)翻譯語法制導(dǎo)翻譯方法方法使用使用屬性文法屬性文法

4、為工具來說明程序設(shè)計(jì)語言的語義。為工具來說明程序設(shè)計(jì)語言的語義。8.1屬性文法屬性文法8.2語法制導(dǎo)翻譯概論語法制導(dǎo)翻譯概論8.3中間代碼形式中間代碼形式8.4基本語言成分的自下而上語法制導(dǎo)翻譯基本語言成分的自下而上語法制導(dǎo)翻譯8.5自上而下的語法制導(dǎo)翻譯自上而下的語法制導(dǎo)翻譯8.1 8.1 屬性文法屬性文法( (Attribute Grammar)Attribute Grammar)屬性屬性對文法的每一個符號，引進(jìn)一些屬性，這些屬性對文法的每一個符號，引進(jìn)一些屬性，這些屬性代表與文法符號相關(guān)的信息，如類型、值、存儲代表與文法符號相關(guān)的信息，如類型、值、存儲位置等。位置等。語義規(guī)則語義規(guī)則為文

5、法的每一個產(chǎn)生式配備的計(jì)算屬性的計(jì)算規(guī)為文法的每一個產(chǎn)生式配備的計(jì)算屬性的計(jì)算規(guī)則，稱為語義規(guī)則。則，稱為語義規(guī)則。屬性文法是帶屬性的一種文法屬性文法是帶屬性的一種文法它的主要思想：它的主要思想：首先對于每個文法符號引進(jìn)相關(guān)的屬性符號；首先對于每個文法符號引進(jìn)相關(guān)的屬性符號；其次對于每個產(chǎn)生式寫出計(jì)算屬性值的語義規(guī)則其次對于每個產(chǎn)生式寫出計(jì)算屬性值的語義規(guī)則屬性文法的形式定義屬性文法的形式定義一個屬性文法是一個三元組一個屬性文法是一個三元組, ,A A(G, V, F)(G, V, F) G G是一個上下文無關(guān)文法；是一個上下文無關(guān)文法； V V是屬性的有窮集；是屬性的有窮集； F F是關(guān)于屬

6、性的斷言的有窮集。是關(guān)于屬性的斷言的有窮集。說明：說明：1.1. 每個每個屬性屬性與文法符號相聯(lián)，與文法符號相聯(lián)，N.tN.t表示文法符號表示文法符號N N的的屬性屬性t t。屬性值屬性值又稱又稱語義值語義值。存儲屬性值的變量。存儲屬性值的變量又稱又稱語義變量語義變量。2.2. 每個斷言與文法的某個產(chǎn)生式相聯(lián)，寫在每個斷言與文法的某個產(chǎn)生式相聯(lián)，寫在 內(nèi)。內(nèi)。屬性的斷言又稱屬性的斷言又稱語義規(guī)則語義規(guī)則，它所描述的工作可以，它所描述的工作可以包括屬性計(jì)算、靜態(tài)語義檢查、符號表的操作、包括屬性計(jì)算、靜態(tài)語義檢查、符號表的操作、代碼生成等，有時寫成函數(shù)或過程段。代碼生成等，有時寫成函數(shù)或過程段。例

7、例 完成類型檢查的屬性文法完成類型檢查的屬性文法1)1) E ET T1 1+T+T2 2TT1 1.t.tint AND Tint AND T2 2.t.tintint2)2) E ET T1 1 or T or T2 2TT1 1.t.tbool AND Tbool AND T2 2.t.tboolbool3)3) T TnumnumT.t :T.t :intint4)4) T TtruetrueT.t :T.t :boolbool5)5) T TfalsefalseT.t :T.t :boolbool 屬性的分類：屬性的分類：1.1. 綜合屬性綜合屬性： 從語法樹的角度來看，如果一個結(jié)點(diǎn)

8、的某一從語法樹的角度來看，如果一個結(jié)點(diǎn)的某一屬性值是由該結(jié)點(diǎn)的子結(jié)點(diǎn)的屬性值計(jì)算來屬性值是由該結(jié)點(diǎn)的子結(jié)點(diǎn)的屬性值計(jì)算來的，則稱該屬性為綜合屬性。的，則稱該屬性為綜合屬性。 內(nèi)在屬性是綜合屬性。內(nèi)在屬性是綜合屬性。 用于用于“自下而上自下而上”傳遞信息傳遞信息2.2. 繼承屬性繼承屬性 從語法樹的角度來看，若一個結(jié)點(diǎn)的某一屬從語法樹的角度來看，若一個結(jié)點(diǎn)的某一屬性值是由該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)和（或）父結(jié)點(diǎn)性值是由該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)和（或）父結(jié)點(diǎn)的屬性值計(jì)算來的，則稱該屬性為繼承屬性。的屬性值計(jì)算來的，則稱該屬性為繼承屬性。 用于用于“自上而下自上而下”傳遞信息傳遞信息說明：說明：v終結(jié)符終結(jié)符只有綜合

9、屬性，它們由詞法分析器提供只有綜合屬性，它們由詞法分析器提供v非終結(jié)符非終結(jié)符既有綜合屬性也有繼承屬性，但既有綜合屬性也有繼承屬性，但文法開文法開始符始符沒有繼承屬性沒有繼承屬性例例 簡單算術(shù)表達(dá)式求值的屬性文法簡單算術(shù)表達(dá)式求值的屬性文法1) LE Print(E.val) 2) EE1+T E.val :E1.val +T.val 3) ET E.val :T.val 4) TT1*F T.val :T1.val * F.val 5) TF T.val :F.val 6) F(E) F.val :E.val 7) Fdigit F.val :digit.lexval E.val、T.val

10、、F.val都是綜合屬性都是綜合屬性終結(jié)符終結(jié)符digit只有綜合屬性，它的值由詞法分析提供只有綜合屬性，它的值由詞法分析提供例例 描述變量類型說明的屬性文法描述變量類型說明的屬性文法1) DTL L.type:T.type 2) Tint T.type:int 3) Treal T.type:real 4) LL1,id L1.type:L.type；addtype( id.entry，L.type )5) Lid addtype( id.entry，L.type ) id1DTLL1id2，intL.type是繼承屬性是繼承屬性T.type是綜合屬性是綜合屬性 int id1,id2的語法

11、樹的語法樹:用用表示屬性的傳遞情況表示屬性的傳遞情況8.2 語法制導(dǎo)翻譯概論語法制導(dǎo)翻譯概論1.語法制導(dǎo)翻譯語法制導(dǎo)翻譯基本思想：基本思想：在語法分析過程中，隨著分析的步步進(jìn)展，每當(dāng)在語法分析過程中，隨著分析的步步進(jìn)展，每當(dāng)使用一條產(chǎn)生式進(jìn)行使用一條產(chǎn)生式進(jìn)行推導(dǎo)推導(dǎo)（對于自上而下分析）（對于自上而下分析）或或歸約歸約（對于自下而上分析），就執(zhí)行該產(chǎn)生式（對于自下而上分析），就執(zhí)行該產(chǎn)生式所對應(yīng)的所對應(yīng)的語義動作語義動作，完成相應(yīng)的翻譯工作。，完成相應(yīng)的翻譯工作。語法制導(dǎo)翻譯法不論對語法制導(dǎo)翻譯法不論對自上而下分析自上而下分析或或自下而上自下而上分析分析都適用都適用例例 簡單算術(shù)表達(dá)式求值的屬

12、性文法簡單算術(shù)表達(dá)式求值的屬性文法1)EE1+T E.val :E1.val +T.val 2)ET E.val :T.val 3)TT1*digit T.val :T1.val * digit.lexval 4)Tdigit T.val :digit.lexval 2+3*5的語法樹：的語法樹：EE1+TT1*5T23T.val=2T.val=3T.val=15E.val=2E.val=17自下而上語法制導(dǎo)翻譯過程：自下而上語法制導(dǎo)翻譯過程：一旦語法分析確認(rèn)輸入符號串是一個句子，它的值也同時由一旦語法分析確認(rèn)輸入符號串是一個句子，它的值也同時由語義規(guī)則計(jì)算出來語義規(guī)則計(jì)算出來2. 語法制導(dǎo)翻

13、譯的實(shí)現(xiàn)途徑語法制導(dǎo)翻譯的實(shí)現(xiàn)途徑以自下而上（以自下而上（ LR分析）的語法制導(dǎo)翻譯來說明分析）的語法制導(dǎo)翻譯來說明 將將LR分析器能力擴(kuò)大，增加在歸約后調(diào)用語義規(guī)分析器能力擴(kuò)大，增加在歸約后調(diào)用語義規(guī)則的功能則的功能 增加語義棧，語義值放到與符號棧同步操作的語增加語義棧，語義值放到與符號棧同步操作的語義棧中，多項(xiàng)語義值可設(shè)多個語義棧義棧中，多項(xiàng)語義值可設(shè)多個語義棧 ，棧結(jié)構(gòu)為：棧結(jié)構(gòu)為：狀態(tài)棧狀態(tài)棧符號棧符號棧語義棧語義棧SmXmXm.valS1X1X1.valS0#-例例 簡單算術(shù)表達(dá)式求值的屬性文法簡單算術(shù)表達(dá)式求值的屬性文法1)L Eprint(E.val)2)EE1+T E.val

14、:E1.val +T.val 3)ET E.val :T.val 4)TT1*digit T.val :T1.val * digit.lexval 5)Tdigit T.val :digit.lexval 狀態(tài)狀態(tài)ACTION GOTO d+*#ET0S3 12 1S4 acc2r3 S5r3 33r5r5 r54S3 75S6 6 r4r4 r47r2S5r2S5*5#E+-2-0146acc#-0101r2#E+-2-01497712GOTOr4S6r5S3S4r3r5S3Action#E+T*5- 2-3-501475685#E+T*-2-3-014757*5#E+3-2- 301435

15、3*5#E+-2-01443*5#-033*5#-023*5#2- 203123*5#-00剩余輸入串剩余輸入串符號棧符號棧語義棧語義棧狀態(tài)棧狀態(tài)棧步驟步驟分析并計(jì)算分析并計(jì)算23*5的過程如下的過程如下:22T12E73T7T15117EL E EE1+T ETTT1*digit Tdigit8.3 中間代碼的形式中間代碼的形式定義：定義：中間代碼是一種復(fù)雜性介于源程序語言和機(jī)器中間代碼是一種復(fù)雜性介于源程序語言和機(jī)器語言之間的一種表示形式。語言之間的一種表示形式。使用中間代碼的好處：使用中間代碼的好處：中間代碼與具體機(jī)器無關(guān)中間代碼與具體機(jī)器無關(guān)對中間代碼進(jìn)行與機(jī)器無關(guān)的優(yōu)化對中間代碼進(jìn)行

16、與機(jī)器無關(guān)的優(yōu)化形式：形式：逆波蘭記號、三元式、間接三元式、四元式和逆波蘭記號、三元式、間接三元式、四元式和樹形表示樹形表示8.3.1 逆波蘭記號逆波蘭記號 逆波蘭表示法逆波蘭表示法將運(yùn)算對象寫在前面，把運(yùn)算符寫在后面，將運(yùn)算對象寫在前面，把運(yùn)算符寫在后面，因而也稱后綴式。因而也稱后綴式。例如：例如：程序設(shè)計(jì)語言中的表示程序設(shè)計(jì)語言中的表示 逆波蘭表示逆波蘭表示a+bab+a+b*c abc * +(a+b)*cab+c *后綴式的計(jì)算機(jī)處理后綴式的計(jì)算機(jī)處理后綴式的最大優(yōu)點(diǎn)是易于計(jì)算機(jī)處理后綴式的最大優(yōu)點(diǎn)是易于計(jì)算機(jī)處理處理過程：處理過程：從左到右掃描后綴式，每碰到運(yùn)算對象就推進(jìn)棧；從左到右

17、掃描后綴式，每碰到運(yùn)算對象就推進(jìn)棧；碰到運(yùn)算符就從棧頂彈出相應(yīng)目數(shù)的運(yùn)算對象施碰到運(yùn)算符就從棧頂彈出相應(yīng)目數(shù)的運(yùn)算對象施加運(yùn)算，并把結(jié)果推進(jìn)棧。最后的結(jié)果留在棧加運(yùn)算，并把結(jié)果推進(jìn)棧。最后的結(jié)果留在棧頂。頂。 bt1dct1t2t1t3t1= - bt2= c*dt3= t1+t2例：表達(dá)式例：表達(dá)式bc*d的后綴式的后綴式 bcd*+的計(jì)值過程的計(jì)值過程逆波蘭表示法的擴(kuò)充逆波蘭表示法的擴(kuò)充逆波蘭表示法很容易擴(kuò)充到表達(dá)式以外的范圍逆波蘭表示法很容易擴(kuò)充到表達(dá)式以外的范圍 例如：例如：語句語句逆波蘭表示逆波蘭表示備注備注a:=b+cabc+:=:=看作二目運(yùn)算符看作二目運(yùn)算符GOTO LL ju

18、mpjump看成一目運(yùn)看成一目運(yùn)算符，表示算符，表示GOTOIf E then S1 else S2ES1S2￥把￥把￥ 看成三目運(yùn)看成三目運(yùn)算符，表示算符，表示if then else8.3.2 三元式和樹形表示三元式和樹形表示三元式三元式(算符算符op，第一個運(yùn)算對象第一個運(yùn)算對象ARG1,第二個運(yùn)算對象第二個運(yùn)算對象ARG2)說明：說明：三元式的某些運(yùn)算對象是另一三元式的某些運(yùn)算對象是另一個三元式的編號（代表其結(jié)果）個三元式的編號（代表其結(jié)果）一目算符只需選用一個運(yùn)算對一目算符只需選用一個運(yùn)算對象（象（ARG1）多目算符可用連續(xù)幾個三元式多目算符可用連續(xù)幾個三元式表示表示例：例： a :

19、b*c+b*d表示為表示為 (1) (* ,b,c)(2) (* ,b,d)(3) (+ ,(1),(2)(4) (:,(3),a)間接三元式間接三元式和三元式類似，只是合并相同的三元式，并和三元式類似，只是合并相同的三元式，并在三元式后面加一列執(zhí)行序列在三元式后面加一列執(zhí)行序列例：例： a :b*c+b*c表示為表示為 (1) (* ,b,c)(2) (* ,b,c)(3) (+ ,(1),(2)(4) (:,(3),a)(1) (* ,b,c)(2) (+ ,(1),(1)(3) (:,(2),a)執(zhí)行序列執(zhí)行序列（1）（）（1）（）（2）（3）三元式序列三元式序列間接三元式序列間接三元式

20、序列樹形表示樹形表示二目運(yùn)算對應(yīng)二叉子樹，多目運(yùn)算對應(yīng)多叉子二目運(yùn)算對應(yīng)二叉子樹，多目運(yùn)算對應(yīng)多叉子樹，但通常通過引入新結(jié)點(diǎn)表示成二叉子樹。樹，但通常通過引入新結(jié)點(diǎn)表示成二叉子樹。例如：例如：a:b*c+b*d 表示成表示成:=a+*bcbd8.3.3 四元式四元式四元式表示四元式表示四元式是一種比較普遍采用的中間代碼形式四元式是一種比較普遍采用的中間代碼形式(算符算符op，ARG1，ARG2，運(yùn)算結(jié)果運(yùn)算結(jié)果RESULT）例如：例如：a:b*c+b*d的四元式表示如下：的四元式表示如下： 1) (*,b,c,t1 )2) (*,b,d,t2 )3) (+,t1,t2,t3 )4) (:, t

21、3 ,a ) 其中其中t i（i1,2,3）是編譯程序引入的臨時變量是編譯程序引入的臨時變量四元式的優(yōu)點(diǎn)：四元式的優(yōu)點(diǎn)：四元式比三元式更便于優(yōu)化。四元式比三元式更便于優(yōu)化。優(yōu)化要求改變運(yùn)算順序或刪除某些運(yùn)算，引起編號優(yōu)化要求改變運(yùn)算順序或刪除某些運(yùn)算，引起編號的變化。的變化。三元式通過編號引用中間結(jié)果，編號的變化引起麻三元式通過編號引用中間結(jié)果，編號的變化引起麻煩；四元式通過臨時變量引用中間結(jié)果，編號變化煩；四元式通過臨時變量引用中間結(jié)果，編號變化無影響。無影響。四元式對生成目標(biāo)代碼有利。四元式對生成目標(biāo)代碼有利。四元式表示很類似于三地址指令，很容易轉(zhuǎn)換成機(jī)四元式表示很類似于三地址指令，很容易

22、轉(zhuǎn)換成機(jī)器代碼。器代碼。 例如：例如：a:b*c+b*d的四元式表示如下：的四元式表示如下： 1) (*,b,c,t1 )2) (:=, t1,t2 )3) (*,b,d,t3 )4) (+,t1,t3,t4 )5) (:,t4 ,a ) 例如：例如：a:b*c+b*d的三元式表示如下：的三元式表示如下： 1) (*,b,c )2) (:=, 1）, 2）)3) (*,b,d)4) (+,1）,3） )5) (:,4）, a ) 四元式的另一種表示四元式的另一種表示有時為了更直觀，把四元式寫成簡單賦值形式有時為了更直觀，把四元式寫成簡單賦值形式或更易理解的形式或更易理解的形式四元式四元式直觀形

23、式直觀形式（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）（4） a:t3( jump,，L)goto L( jrop, B，C，L)if B rop C goto L8.4 基本語言成分的自下而上語法制導(dǎo)翻譯基本語言成分的自下而上語法制導(dǎo)翻譯8.4.1 簡單賦值語句的翻譯簡單賦值語句的翻譯8.4.2 布爾表達(dá)式的翻譯布爾表達(dá)式的翻譯8.4.3 控制結(jié)構(gòu)的翻譯控制結(jié)構(gòu)的翻譯8.4.4 簡單說明語句的翻譯簡單說明語句

24、的翻譯8.4.1 簡單賦值語句的翻譯簡單賦值語句的翻譯簡單賦值語句簡單賦值語句是指不含復(fù)雜數(shù)據(jù)類型（如數(shù)組，記錄等）的是指不含復(fù)雜數(shù)據(jù)類型（如數(shù)組，記錄等）的賦值語句。賦值語句。賦值語句的語義審查包括：賦值語句的語義審查包括：1. 每個使用性標(biāo)識符是否都有聲明？每個使用性標(biāo)識符是否都有聲明？2. 運(yùn)算符的分量類型是否相容？運(yùn)算符的分量類型是否相容？3. 賦值語句的左右部的類型是否相容？賦值語句的左右部的類型是否相容？賦值語句的翻譯目標(biāo)：賦值語句的翻譯目標(biāo)：在賦值語句右部表達(dá)式產(chǎn)生的四元式序列后加在賦值語句右部表達(dá)式產(chǎn)生的四元式序列后加一條賦值四元式一條賦值四元式1屬性和語義規(guī)則中用到的變量、過

25、程和函數(shù)屬性和語義規(guī)則中用到的變量、過程和函數(shù)屬性：屬性：用用表示單詞表示單詞id的名字。的名字。用用E.place表示存放表示存放E值的變量名在符號表的入口地址值的變量名在符號表的入口地址或臨時變量編碼?；蚺R時變量編碼。變量、函數(shù)和過程變量、函數(shù)和過程：用用nextstat變量給出在輸出序列中下一個四元式的序號變量給出在輸出序列中下一個四元式的序號用用lookup（）函數(shù)審查函數(shù)審查是否出現(xiàn)在符是否出現(xiàn)在符號表中，是則返回號表中，是則返回id的入口地址，否則返回的入口地址，否則返回nil。用用emit過程向輸出序列輸出一個四元式，過程向輸出序列輸出一

26、個四元式，emit每調(diào)用每調(diào)用一次，一次，nextstat的值增加的值增加1用用newtemp函數(shù)生成臨時變量，每次調(diào)用生成一個新函數(shù)生成臨時變量，每次調(diào)用生成一個新的臨時變量，如的臨時變量，如t1, t2 , 用用error過程進(jìn)行錯誤處理。過程進(jìn)行錯誤處理。 (1) Sid:E p:lookup ( ) ; if pnil then emit (:, E.place , - , p ) else error 2簡單賦值語句的翻譯（假定變量只有一種類型）簡單賦值語句的翻譯（假定變量只有一種類型）(2)EE1+E2 E.place:newtemp ; emit ( + , E1

27、.place , E2.place , E.place ) 此情況下的語義審查只有：此情況下的語義審查只有：每個使用性標(biāo)識符是否都有聲明？每個使用性標(biāo)識符是否都有聲明？(4)EE1 E.place:newtemp ; emit ( , E1.place , - , E.place ) (5)E(E1)E.place:newtemp ; E.place:E1.place (6)Eid p:lookup ( ) ; if pnil then E.place:p else error (3)EE1*E2 E.place:newtemp ; emit ( * , E1.place ,

28、E2.place , E.place ) 例例 翻譯賦值語句翻譯賦值語句A:B+C （A、B、C為標(biāo)識符為標(biāo)識符id）E1.placePBE2.placePCE.placet1；(, PB ,PC , t1)(:, t1 , - , PA)SA:=EBE1+E2C(為了直觀，用為了直觀，用PB和和PC分別表示分別表示B和和C在符號表的入在符號表的入口地址口地址) 表達(dá)式中可能出現(xiàn)不同類型的變量和常量表達(dá)式中可能出現(xiàn)不同類型的變量和常量 語義審查包括：語義審查包括：1. 每個使用性標(biāo)識符是否都有聲明？每個使用性標(biāo)識符是否都有聲明？2. 運(yùn)算符的分量類型是否相容？運(yùn)算符的分量類型是否相容？若不接受

29、不同類型的運(yùn)算對象混合運(yùn)算，則應(yīng)指出錯誤；若不接受不同類型的運(yùn)算對象混合運(yùn)算，則應(yīng)指出錯誤；若接受混合運(yùn)算則要進(jìn)行類型轉(zhuǎn)換處理。若接受混合運(yùn)算則要進(jìn)行類型轉(zhuǎn)換處理。 例例：假定表達(dá)式可以有混合運(yùn)算，：假定表達(dá)式可以有混合運(yùn)算，id可以是整型可以是整型和實(shí)型，且當(dāng)兩個不同類型的和實(shí)型，且當(dāng)兩個不同類型的id進(jìn)行運(yùn)算時先把進(jìn)行運(yùn)算時先把整型整型id轉(zhuǎn)換成實(shí)型，再進(jìn)行運(yùn)算。轉(zhuǎn)換成實(shí)型，再進(jìn)行運(yùn)算。用用E.type表示表示E的類型信息，其值為的類型信息，其值為int或或real。用用 +i , *i 表示整型運(yùn)算，用表示整型運(yùn)算，用 +r , *r 表示實(shí)型運(yùn)算。表示實(shí)型運(yùn)算。用一目算符用一目算符 i

30、tr 表示將整型量轉(zhuǎn)換成實(shí)型量的運(yùn)算。表示將整型量轉(zhuǎn)換成實(shí)型量的運(yùn)算。3 簡單賦值語句的四元式翻簡單賦值語句的四元式翻譯譯E.place:newtemp ;if E1.typeint AND E2.typeint thenbegin emit ( +i , E1.place , E2.place , E.place) ; E.type:int endelse if E1.typereal AND E2.typereal thenbegin emit ( +r , E1.place , E2.place , E.place ) ; E.type:real end else if E1.typei

31、nt then begin t:newtemp ; emit ( itr , E1.place , - , t ) ; emit ( +r , t , E2.place , E.place ) ; E.type:real end else begin t:newtemp ; emit ( itr , E2.place , - , t ) ; emit ( +r , E1.place , t , E.place ) ; E.type:real end ;產(chǎn)生式產(chǎn)生式EE1+E2的包含類型屬性的語義規(guī)則為：的包含類型屬性的語義規(guī)則為：E.place=newtemp ;if (E1.type=int

32、 & E2.type=int) emit ( +i , E1.place , E2.place , E.place) ; E.type=intelse if (E1.type=real & E2.type=real) emit ( +r , E1.place , E2.place , E.place ) ; E.type:real else if (E1.type=int) t=newtemp ; emit ( itr , E1.place , - , t ) ; emit ( +r , t , E2.place , E.place ) ; E.type=real else t=newtemp

33、 ; emit ( itr , E2.place , - , t ) ; emit ( +r , E1.place , t , E.place ) ; E.type=real ;產(chǎn)生式產(chǎn)生式EE1+E2的包含類型屬性的語義規(guī)則為：的包含類型屬性的語義規(guī)則為：屬性文法的構(gòu)造屬性文法的構(gòu)造屬性：根據(jù)語義處理的需要，設(shè)計(jì)文法符號的相屬性：根據(jù)語義處理的需要，設(shè)計(jì)文法符號的相應(yīng)屬性（包括：屬性的個數(shù)和屬性的符號表示）應(yīng)屬性（包括：屬性的個數(shù)和屬性的符號表示）語義規(guī)則：滿足語義處理的要求，并生成相應(yīng)的語義規(guī)則：滿足語義處理的要求，并生成相應(yīng)的中間代碼中間代碼8.4.2 布爾表達(dá)式的翻譯布爾表達(dá)式的翻譯1

34、. 布爾表達(dá)式的作用與結(jié)構(gòu)布爾表達(dá)式的作用與結(jié)構(gòu)布爾表達(dá)式的兩個作用：布爾表達(dá)式的兩個作用： 計(jì)算邏輯值計(jì)算邏輯值 作為控制語句作為控制語句(如如if-then,while)的條件表達(dá)式的條件表達(dá)式布爾表達(dá)式的語法：布爾表達(dá)式的語法： or | and | not | () | true | false（布爾表達(dá)式）布爾表達(dá)式） relop | () （關(guān)系表達(dá)式）關(guān)系表達(dá)式） op | - | () | id | num （算術(shù)表達(dá)式）算術(shù)表達(dá)式）其中：其中：relop是是關(guān)系算符關(guān)系算符(如如, , =)op是是算術(shù)算符算術(shù)算符(+ , - , * , / )只考慮如下形式的布爾表達(dá)式的翻

35、譯只考慮如下形式的布爾表達(dá)式的翻譯EE or E | E and E | not E | (E ) | id rop id |true|false布 爾 算 符布 爾 算 符 的 優(yōu) 先 順 序 （ 從 高 到 低 ） 為 ：的 優(yōu) 先 順 序 （ 從 高 到 低 ） 為 ：notandor，且且and和和or都服從左結(jié)合，都服從左結(jié)合，not服服從右結(jié)合從右結(jié)合關(guān)系算符關(guān)系算符的優(yōu)先級都相同，而且高于任何布爾的優(yōu)先級都相同，而且高于任何布爾算符，低于任何算術(shù)算符。算符，低于任何算術(shù)算符。2.布爾表達(dá)式的計(jì)算方法：布爾表達(dá)式的計(jì)算方法：采用兩種方法：數(shù)值表示的采用兩種方法：數(shù)值表示的直接計(jì)算直

36、接計(jì)算與邏輯表示與邏輯表示的的短路計(jì)算短路計(jì)算直接計(jì)算與算術(shù)表達(dá)式計(jì)算方法基本相同直接計(jì)算與算術(shù)表達(dá)式計(jì)算方法基本相同如：如：1 or 0 and 1=1 or 0=1短路計(jì)算即布爾表達(dá)式計(jì)算到某一部分就可以得短路計(jì)算即布爾表達(dá)式計(jì)算到某一部分就可以得到結(jié)果，而無需對布爾表達(dá)式進(jìn)行完全計(jì)算。可到結(jié)果，而無需對布爾表達(dá)式進(jìn)行完全計(jì)算?？梢杂靡杂胕f-then-else來解釋來解釋A or B if A then 1 else BA and Bif A then B else 0not Aif A then 0 else 1 3.直接計(jì)算的語法制導(dǎo)翻譯直接計(jì)算的語法制導(dǎo)翻譯對關(guān)系表達(dá)式，如對關(guān)系表

37、達(dá)式，如ab，可翻譯成如下固定的三可翻譯成如下固定的三地址代碼序列：地址代碼序列：(1) (j,a,b,(4)(2) (:=,0,- ,t1)(3) (jump, - ,- ,(5)(4) (:=,1,- ,t1)(5) 如：如：A or B and not C被翻譯成：被翻譯成：(not,C,- ,t1)(and, B,t1,t2)(or,A,t2,t3)PC直接計(jì)算的翻譯方案直接計(jì)算的翻譯方案(1)EE1 or E2 E.place :newtemp ; emit ( or , E1.place , E2.place , E.place ) (2)EE1 and E2 E.place :n

38、ewtemp ; emit ( and , E1.place , E2.place , E.place ) (3)Enot E1 E.place :newtemp ; emit ( not , E1.place , E.place ) (4)E(E1) E.place :E1.place (5)Eid1 rop id2 E.place :newtemp ; emit (jrop , id1.place , id2.place , nextstat+3 ) ; emit ( :, 0 , E.place ) ; emit ( jump , nextstat+2 ) ; emit ( :, 1 ,

39、 E.place ) (6)Etrue E.place:newtemp;emit(:=,1,- ,E.place) (7)EfalseE.place:=newtemp;emit(:=,0,- ,E.place) 例：布爾表達(dá)式例：布爾表達(dá)式ab or cf的翻譯的翻譯E.place=t5E1.place=t1E2.place=t4E2.place=t3E1.place=t2EE1E2E1E2oranda bc f(1)(j, a, b, (4)(2)(:=, 0, - , t1)(3)(jump,- ,- ,(5)(4)(:=, 1, - , t1)(5)(j, e, f, (12)(10)(

40、:=, 0, - , t3)(11)(jump,- ,- ,(13)(12)(:=, 1, - , t3)(13)(and, t2, t3, t4)(14)(or, t1, t4, t5)4.作為條件控制的布爾表達(dá)式的翻譯作為條件控制的布爾表達(dá)式的翻譯基本翻譯方法基本翻譯方法當(dāng)布爾表達(dá)式用于控制條件時，并不需要計(jì)算表當(dāng)布爾表達(dá)式用于控制條件時，并不需要計(jì)算表達(dá)式的值，而是一旦確定了表達(dá)式為真或?yàn)榧?，達(dá)式的值，而是一旦確定了表達(dá)式為真或?yàn)榧?，就將控制轉(zhuǎn)向相應(yīng)的代碼序列。就將控制轉(zhuǎn)向相應(yīng)的代碼序列。S2 的代碼的代碼S1 的代碼的代碼E的代碼的代碼E.false E.true if E then

41、S1 else S2為布爾表達(dá)式為布爾表達(dá)式E引入兩個新的引入兩個新的屬性：屬性：E.true：表達(dá)式的真出口，表達(dá)式的真出口，它指向表達(dá)式為真時的轉(zhuǎn)向它指向表達(dá)式為真時的轉(zhuǎn)向E.false：表達(dá)式的假出口，表達(dá)式的假出口，它指向表達(dá)式為假時的轉(zhuǎn)向它指向表達(dá)式為假時的轉(zhuǎn)向把把E翻譯成下述形式的條件轉(zhuǎn)移和無條件轉(zhuǎn)移的四翻譯成下述形式的條件轉(zhuǎn)移和無條件轉(zhuǎn)移的四元式序列：元式序列：1.( jnz , A , - , p )若若A為真，則轉(zhuǎn)向四元式為真，則轉(zhuǎn)向四元式p2.( jrop , A , B , p )若若A rop B為真，則轉(zhuǎn)向四元式為真，則轉(zhuǎn)向四元式p3.( jump , - , - ,

42、 p )無條件轉(zhuǎn)向四元式無條件轉(zhuǎn)向四元式p(1) ( jnz , A , - , 5 )A的真出口為的真出口為5(2) ( jump , - , - , 3 )A的假出口為的假出口為3(3) ( j , B , D , 5 )BD的真出口為的真出口為5(4) (jump , - , - , p+1 )BD的假出口為的假出口為(p+1)(5) (關(guān)于關(guān)于S1的四元式序列的四元式序列)(p)( jump , - , - , q )跳過跳過S2的代碼段的代碼段(p+1) (關(guān)于關(guān)于S2的四元式序列的四元式序列)(q)(1) - (4)是布爾式是布爾式A or BD 翻譯產(chǎn)生的代碼，全部是條翻譯產(chǎn)生的

43、代碼，全部是條件轉(zhuǎn)移和無條件轉(zhuǎn)移四元式，沒有布爾運(yùn)算。件轉(zhuǎn)移和無條件轉(zhuǎn)移四元式，沒有布爾運(yùn)算。例：例：if A or BD then S1 else S2翻譯成如下四元式序列翻譯成如下四元式序列具體說明如下：具體說明如下：用用E.true和和E.false 分別表示分別表示E的的“真真”和和“假假”出出口轉(zhuǎn)移目標(biāo)，在翻譯口轉(zhuǎn)移目標(biāo)，在翻譯E時并未能確定。時并未能確定。對于對于E為為 a rop b 形式，生成代碼如下：形式，生成代碼如下：( jrop , a , b , E.true )( jump , E.false )以結(jié)構(gòu)圖表示：以結(jié)構(gòu)圖表示：E的代碼的代碼E.falseE.true對于

44、對于E為為 E1 or E2的形式，生成代碼結(jié)構(gòu)如下：的形式，生成代碼結(jié)構(gòu)如下：E1.的代碼的代碼E2.的代碼的代碼E1.falseE2.falseE.falseE1.trueE2.trueE.true若若E1為真，則可知為真，則可知E為真，即為真，即E1的真出口和的真出口和E的真出口一樣；的真出口一樣；若若E1為假，則必須計(jì)算為假，則必須計(jì)算E2，因此因此E1的假出口應(yīng)是的假出口應(yīng)是E2代碼的第代碼的第一個四元式序號；一個四元式序號；E2的真出口和假出口分別與的真出口和假出口分別與E的真出口和假出口一樣的真出口和假出口一樣E1.的代碼的代碼E2.的代碼的代碼E1.falseE2.falseE

45、.falseE1.trueE2.trueE.true對于對于E為為 E1 and E2的形式，生成代碼結(jié)構(gòu)如下：的形式，生成代碼結(jié)構(gòu)如下：對于對于E為為 not E1形式，只需調(diào)換形式，只需調(diào)換E1的真假出口，的真假出口，即可得到即可得到E的真假出口。的真假出口。例：例：E 為為 ab or cf ，翻譯為四元式序列：翻譯為四元式序列：（1） (j, a,b,E.true)（2） (jump, - ,- ,(3)（3） (j, e ,f ,E.true)（6） (jump, - ,- ,E.false)真假出口的拉鏈與回填真假出口的拉鏈與回填原因原因在把布爾式翻譯成一串條件轉(zhuǎn)和無條件轉(zhuǎn)四元在把

46、布爾式翻譯成一串條件轉(zhuǎn)和無條件轉(zhuǎn)四元式時，真假出口未能在生成四元式時確定；而式時，真假出口未能在生成四元式時確定；而且多個四元式可能有相同的出口且多個四元式可能有相同的出口說明：說明：E.true和和E.false不能在不能在產(chǎn)生四元式的同時確定，產(chǎn)生四元式的同時確定，要等將來目標(biāo)明確時再要等將來目標(biāo)明確時再回填，為此要記錄這些回填，為此要記錄這些要回填的四元式。要回填的四元式。通常采用通常采用“拉鏈拉鏈”的辦的辦法，把需要回填法，把需要回填E.true的四元式拉成一條的四元式拉成一條“真真”鏈，把需要回填鏈，把需要回填E.false的四元式拉成一條的四元式拉成一條“假假”鏈。鏈。if ab

47、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)于關(guān)于S1的四元式的四元式)（p） (jump, - ,- ,q)(p+1) (關(guān)于關(guān)于S2的四元式的四元式) (q)拉鏈方式：拉鏈方式：則鏈接成為：則鏈接成為：(10) goto (True) (20) goto (10) (30) goto (20)把地址（把地址（30）作為鏈?zhǔn)祝刂罚ǎ┳鳛殒準(zhǔn)?，地址?0）作為鏈尾）作為鏈尾, True為為真

48、真鏈尾標(biāo)志。鏈尾標(biāo)志。四元式的第四個區(qū)段存放鏈指針。四元式的第四個區(qū)段存放鏈指針。E.true 和和E.false用于存放用于存放“真真”鏈和鏈和“假假”鏈的鏈的鏈?zhǔn)祖準(zhǔn)?。若有四元式序列：若有四元式序列?10) goto E.true (20) goto E.true (30) goto E.true 為了完成拉鏈和回填工作，設(shè)計(jì)以下語義變量和為了完成拉鏈和回填工作，設(shè)計(jì)以下語義變量和過程（函數(shù)）：過程（函數(shù)）：1) 函數(shù)函數(shù)merge ( p1, p2 ) 用于把用于把P1和和P2為鏈?zhǔn)椎膬蔀殒準(zhǔn)椎膬蓷l鏈合并成條鏈合并成1條，返回合并后的鏈?zhǔn)字怠l，返回合并后的鏈?zhǔn)字?。其算法為：?dāng)其算法為

49、：當(dāng)P2為空鏈時，返回為空鏈時，返回P1；當(dāng)當(dāng)P2不為空不為空鏈時，把鏈時，把P2的鏈尾第四區(qū)段改為的鏈尾第四區(qū)段改為P1，返回返回P2。2) 過程過程backpatch ( p , t ) 用于把鏈?zhǔn)子糜诎焰準(zhǔn)譖所鏈接的每所鏈接的每個四元式的第四區(qū)段都填為轉(zhuǎn)移目標(biāo)個四元式的第四區(qū)段都填為轉(zhuǎn)移目標(biāo)t。3) 語義變量語義變量E.codebegin表示表達(dá)式表示表達(dá)式E的第一個四元的第一個四元式的序號。式的序號。 1)EE1 or E2 E.codebegin:E1.codebegin ;backpatch ( E1.false , E2.codebegin ) ;E.true:merge ( E

50、1.true , E2.true ) ; E.false:E2.false 自下而上分析中布爾表達(dá)式的一種翻譯方案自下而上分析中布爾表達(dá)式的一種翻譯方案2) EE1 and E2 E.codebegin:E1.codebigin ;backpatch ( E1.true , E2.codebegin ) ;E.true:E2.true ; E.false:merge ( E1.fasle , E2.false ) 3) Enot E1 E.codebegin:E1.codebigin ;E.true:E1.false ; E.false:E1.true 4)E(E1) E.codebegin:

51、E1.codebegin ;E.true:E1.true ; E.false:E1.false 5) Eid1 rop id2 E.codebegin:nextstat ; E.true:nextstat ; E.false:nextstat+1; emit ( jrop , id1.place , id2.place , true ) ; emit ( jump , false ) 6) Etrue E.codebegin:nextstat ; E.true:nextstat ;E.false:Nil;emit ( jump ,true ) 7) Efalse E.codebegin:nex

52、tstat ; E.false:nextstat ;E.true:Nil;emit ( jump ,false ) 例例 ab or cd and ef 的翻譯過程的翻譯過程假定四元式編號從假定四元式編號從100開始，開始，即開始時即開始時nextstat100EE1orE2E1andE2abcdefE1.begin=100E1.true=100E1.false=101E1.begin=102E1.true=102E1.false=103E2.begin=104E2.true=104E2.false=105E2.begin=102E2.true=104E2.false=103,105=105E

53、.begin=100E.true=100,104=104E.false=105100 : ( j , a , b , true )101: ( jump ,false )102: ( j , c , d , true )103: ( jump , fase )104: ( j , e , f , true )105: ( jump ,false )102 ( j , c , d ,104)105 ( jump ,103)101( jump,102)104 (j , e , f ,100)最終結(jié)果：最終結(jié)果：100：( j , a , b , true )101：( jump,102) 102：

54、( j , c , d , 104) 103：( jump, false ) 104：( j , e , f , 100) 105：( jump,103) “真真”鏈?zhǔn)祖準(zhǔn)譋.true104 , “假假”鏈?zhǔn)祖準(zhǔn)譋.false105。8.4.3 控制結(jié)構(gòu)的翻譯控制結(jié)構(gòu)的翻譯以以if 語句，語句，while語句為例說明控制語句的翻譯方法語句為例說明控制語句的翻譯方法S if E then Sif語句語句| if E then S else Sif語句語句| while E do Swhile語句語句| begin L end 復(fù)合語句復(fù)合語句| A賦值語句賦值語句A id:=EL L ; S語句

55、序列語句序列| S 語句語句 條件轉(zhuǎn)移語句的共同特點(diǎn)是：根據(jù)布爾表達(dá)式取值，條件轉(zhuǎn)移語句的共同特點(diǎn)是：根據(jù)布爾表達(dá)式取值，分別執(zhí)行不同的語句序列。分別執(zhí)行不同的語句序列。問題問題：不同的語句序列結(jié)束后，如何使控制轉(zhuǎn)向語句：不同的語句序列結(jié)束后，如何使控制轉(zhuǎn)向語句的結(jié)束。例如：的結(jié)束。例如：if E1 then if E2 then S1 else S2 else S3E1=1E2=1S1S2S3endstartYesNoYesNo參照布爾表達(dá)式的翻譯方參照布爾表達(dá)式的翻譯方法，對非終結(jié)符法，對非終結(jié)符S(和和L)，設(shè)立語義變量設(shè)立語義變量S.CHAIN（和和L.CHAIN ），用于記用于記住需

56、要在翻譯完住需要在翻譯完S(L)后回后回填轉(zhuǎn)移目標(biāo)的一串四元式填轉(zhuǎn)移目標(biāo)的一串四元式1. 代碼結(jié)構(gòu)代碼結(jié)構(gòu)E的代碼的代碼S1 的代碼的代碼E.false E.true S1.CHAIN S.CHAIN qif E then S1 代碼結(jié)構(gòu)代碼結(jié)構(gòu)qif E then S1 else S2 代碼結(jié)構(gòu)代碼結(jié)構(gòu)S2 的代碼的代碼Jump outS1 的代碼的代碼E的代碼的代碼S.CHAIN E.false E.true S1.CHAIN S2.CHAIN out:E.true qwhile E do S1 代碼結(jié)構(gòu)代碼結(jié)構(gòu)Jump beginS1 的代碼的代碼E 的代碼的代碼S.CHAIN E.fa

57、lse begin：S1.CHAIN2文法的改寫文法的改寫 原因：在自下而上的語法制導(dǎo)翻譯中，語義動作的原因：在自下而上的語法制導(dǎo)翻譯中，語義動作的執(zhí)行是在使用產(chǎn)生式進(jìn)行歸約之后，并不允許在產(chǎn)執(zhí)行是在使用產(chǎn)生式進(jìn)行歸約之后，并不允許在產(chǎn)生式的中間執(zhí)行。為了能及時地執(zhí)行語義動作（比生式的中間執(zhí)行。為了能及時地執(zhí)行語義動作（比如回填轉(zhuǎn)移目標(biāo)），需對源文法改寫如回填轉(zhuǎn)移目標(biāo)），需對源文法改寫 方法：在需要執(zhí)行語義動作的地方把產(chǎn)生式分段，方法：在需要執(zhí)行語義動作的地方把產(chǎn)生式分段，引入新的非終結(jié)符來表示它引入新的非終結(jié)符來表示它 需要改寫的產(chǎn)生式：需要改寫的產(chǎn)生式：1) 把把 Sif E then S

58、1改寫成改寫成Cif E then (回填回填E.true)SC S12) 把把 Sif E then S1 else S2改寫成改寫成Cif E then (回填回填E.true)TpC S1 else (產(chǎn)生無條件轉(zhuǎn)移，產(chǎn)生無條件轉(zhuǎn)移， 并回填并回填E.false) STp S23) 把把 Swhile E do S3 改寫成改寫成 Wwhile (記住入口記住入口) WdW E do (回填回填E.true) S Wd S3 (產(chǎn)生無條件轉(zhuǎn)移產(chǎn)生無條件轉(zhuǎn)移 返回循環(huán)入口返回循環(huán)入口)4) 把把 LL ; S改寫成改寫成LsL ; (回填前一語句的出口回填前一語句的出口)LLs S改寫后的

59、文法改寫后的文法(1) S C S1(2) S Tp S2(3) S Wd S3(4) S begin L end(5) S A (6) L Ls S(7) L S(8) C if E then(9) Tp C S1 else(10) W while(11) Wd W E do(12) Ls L ; 源文法：源文法：S if E then SS if E then S else SS while E do SS begin L end S AL L ; SL S(8)(1)(8)(9)(2)(10)(11)(3)(4)(5)(12)(6)(7)3安排語義動作安排語義動作Cif E then b

60、ackpatch ( E.true , nextstat ) ; C.CHAIN:=E.false SC S1/* if E then S1 */ S.CHAIN:merge ( C.CHAIN , S1.CHAIN ) TpC S1 else/* if E then S1 else */ q:=nextstat ; emit ( jump,false ) ;/*S1執(zhí)行完，跳離整個執(zhí)行完，跳離整個if語句語句*/backpatch ( C.CHAIN , nextstat ) ;Tp.CHAIN:merge ( q , S1.CHAIN ) STp S2/* if E then S1 els