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

1、天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系第六章第六章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成學(xué)習(xí)目標(biāo)：學(xué)習(xí)目標(biāo)：v掌握：掌握：常見語法成分的中間代碼形式；常見語法成分的中間代碼形式；常見語法成分的屬性文法或翻譯方法常見語法成分的屬性文法或翻譯方法v理解：理解：屬性文法、語法制導(dǎo)翻譯方法屬性文法、語法制導(dǎo)翻譯方法天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系主要內(nèi)容主要內(nèi)容屬性文法和語法制導(dǎo)翻譯：屬性文法和語法制導(dǎo)翻譯：屬性文法屬性文法語法制導(dǎo)翻譯基本思想語法制導(dǎo)翻譯基本思想中間代碼的表示形式（逆波蘭式、四元中間代碼的表示形式（逆波蘭式、四元式、三元式、間接三元式、樹結(jié)構(gòu)等等）式、三元式、間接三元式、樹結(jié)構(gòu)等等

2、）簡單算術(shù)表達(dá)式和賦值語句的翻譯簡單算術(shù)表達(dá)式和賦值語句的翻譯布爾表達(dá)式到四元式的翻譯布爾表達(dá)式到四元式的翻譯控制結(jié)構(gòu)翻譯成四元式控制結(jié)構(gòu)翻譯成四元式天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系目標(biāo)程序目標(biāo)程序源程序源程序詞法分析詞法分析語法分析語法分析語義分析語義分析中間代碼生成中間代碼生成代碼優(yōu)化代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成表格管理表格管理出錯(cuò)處理出錯(cuò)處理天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系語義分析基礎(chǔ)語義分析基礎(chǔ)n語義分析的內(nèi)容語義分析的內(nèi)容主要是類型相容檢查，有以下幾種：主要是類型相容檢查，有以下幾種：各種條件表達(dá)式的類型是不是各種條件表達(dá)式的類型是不是boolean型？型？運(yùn)算符的分量類型是否相容？運(yùn)算

3、符的分量類型是否相容？賦值語句的左右部的類型是否相容？賦值語句的左右部的類型是否相容？形參和實(shí)參的類型是否相容形參和實(shí)參的類型是否相容?下標(biāo)表達(dá)式的類型是否為所允許的類型？下標(biāo)表達(dá)式的類型是否為所允許的類型？函數(shù)說明中的函數(shù)類型和返回值的類型是否一函數(shù)說明中的函數(shù)類型和返回值的類型是否一致？致？天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系語義分析基礎(chǔ)語義分析基礎(chǔ)-語義分析的內(nèi)容（續(xù)）語義分析的內(nèi)容（續(xù)）其它語義檢查：其它語義檢查：VE中的中的V是不是變量，而且是數(shù)組類型？是不是變量，而且是數(shù)組類型？V.i中的中的V是不是變量，而且是記錄類型？是不是變量，而且是記錄類型？i是是不是該記錄的域名？不是該記錄的域名

4、？x+f()中的中的f是不是函數(shù)名？形參個(gè)數(shù)和實(shí)參是不是函數(shù)名？形參個(gè)數(shù)和實(shí)參個(gè)數(shù)是否一致？個(gè)數(shù)是否一致？每個(gè)使用性標(biāo)識(shí)符是否都有聲明？有無標(biāo)識(shí)每個(gè)使用性標(biāo)識(shí)符是否都有聲明？有無標(biāo)識(shí)符的重復(fù)聲明？符的重復(fù)聲明？天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系語義分析基礎(chǔ)語義分析基礎(chǔ)q在語義分析同時(shí)產(chǎn)生中間代碼，在這種模式下，在語義分析同時(shí)產(chǎn)生中間代碼，在這種模式下，語義分析的主要功能如下：語義分析的主要功能如下：語義審查語義審查在掃描聲明部分時(shí)構(gòu)造標(biāo)識(shí)符的符號(hào)表在掃描聲明部分時(shí)構(gòu)造標(biāo)識(shí)符的符號(hào)表在掃描語句部分時(shí)產(chǎn)生中間代碼在掃描語句部分時(shí)產(chǎn)生中間代碼中間代碼：中間代碼：獨(dú)立于機(jī)器，復(fù)雜性介于源語言和機(jī)獨(dú)立于機(jī)器，

5、復(fù)雜性介于源語言和機(jī)器語言之間，十分接近目標(biāo)機(jī)器指令的一種表示器語言之間，十分接近目標(biāo)機(jī)器指令的一種表示形式。形式。對(duì)于中間代碼的產(chǎn)生，是很困難的，因?yàn)檎Z義形式化對(duì)于中間代碼的產(chǎn)生，是很困難的，因?yàn)檎Z義形式化比語法形式化難得多。目前普遍采用的比語法形式化難得多。目前普遍采用的q語義分析方法語義分析方法語法制導(dǎo)翻譯語法制導(dǎo)翻譯方法方法q使用使用屬性文法屬性文法為工具來說明程序設(shè)計(jì)語言的為工具來說明程序設(shè)計(jì)語言的語義。語義。天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.1屬性文法屬性文法(Attribute Grammar) )q屬性屬性q對(duì)文法的每一個(gè)符號(hào)，引進(jìn)一些屬性，這些對(duì)文法的每一個(gè)符號(hào)，引進(jìn)一些屬性，

6、這些屬性代表與文法符號(hào)相關(guān)的信息，如類型、值、屬性代表與文法符號(hào)相關(guān)的信息，如類型、值、存儲(chǔ)位置等。存儲(chǔ)位置等。n語義規(guī)則語義規(guī)則為文法的每一個(gè)產(chǎn)生式配備的計(jì)算屬性的計(jì)算規(guī)為文法的每一個(gè)產(chǎn)生式配備的計(jì)算屬性的計(jì)算規(guī)則，稱為語義規(guī)則。則，稱為語義規(guī)則。n屬性文法屬性文法是帶屬性的一種文法是帶屬性的一種文法它的主要思想：它的主要思想：首先對(duì)于每個(gè)文法符號(hào)引進(jìn)相關(guān)的屬性符號(hào)；首先對(duì)于每個(gè)文法符號(hào)引進(jìn)相關(guān)的屬性符號(hào)；其次對(duì)于每個(gè)產(chǎn)生式寫出計(jì)算屬性值的語義規(guī)則其次對(duì)于每個(gè)產(chǎn)生式寫出計(jì)算屬性值的語義規(guī)則天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.1 屬性文法屬性文法(續(xù)續(xù))q屬性文法的形式定義屬性文法的形式定義一個(gè)屬

7、性文法是一個(gè)三元組一個(gè)屬性文法是一個(gè)三元組,A,A(G, V, F)(G, V, F)G G是一個(gè)上下文無關(guān)文法；是一個(gè)上下文無關(guān)文法；V V是屬性的有窮集；是屬性的有窮集；F F是關(guān)于屬性的斷言的有窮集。是關(guān)于屬性的斷言的有窮集。說明：說明：w每個(gè)每個(gè)屬性屬性與文法符號(hào)相聯(lián)，與文法符號(hào)相聯(lián)，N.tN.t表示文法符號(hào)表示文法符號(hào)N N的的屬性屬性t t。屬性值屬性值又稱又稱語義值語義值。存儲(chǔ)屬性值的變量。存儲(chǔ)屬性值的變量又稱又稱語義變量語義變量。w每個(gè)斷言與文法的某個(gè)產(chǎn)生式相聯(lián)，寫在每個(gè)斷言與文法的某個(gè)產(chǎn)生式相聯(lián)，寫在 內(nèi)。內(nèi)。屬性的斷言又稱屬性的斷言又稱語義規(guī)則語義規(guī)則，它所描述的工作可以，

8、它所描述的工作可以包括屬性計(jì)算、靜態(tài)語義檢查、符號(hào)表的操作、包括屬性計(jì)算、靜態(tài)語義檢查、符號(hào)表的操作、代碼生成等，有時(shí)寫成函數(shù)或過程段。代碼生成等，有時(shí)寫成函數(shù)或過程段。天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.1 屬性文法屬性文法(續(xù)續(xù))例例 完成類型檢查的屬性文法完成類型檢查的屬性文法wE ET T1 1+T+T2 2TT1 1.t.tint AND Tint AND T2 2.t.tintintwE ET T1 1 or T or T2 2TT1 1.t.tbool AND Tbool AND T2 2.t.tboolboolwT TnumnumT.t :T.t :intintwT Ttruetr

9、ueT.t :T.t :boolbool1)1)T TfalsefalseT.t :T.t :boolbool天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.1 屬性文法屬性文法(續(xù)續(xù))q屬性的分類：屬性的分類：w綜合屬性：綜合屬性：從語法樹的角度來看，如果一個(gè)結(jié)點(diǎn)的某一從語法樹的角度來看，如果一個(gè)結(jié)點(diǎn)的某一屬性值是由該結(jié)點(diǎn)的子結(jié)點(diǎn)的屬性值計(jì)算來屬性值是由該結(jié)點(diǎn)的子結(jié)點(diǎn)的屬性值計(jì)算來的，則稱該屬性為綜合屬性。的，則稱該屬性為綜合屬性。內(nèi)在屬性是綜合屬性。內(nèi)在屬性是綜合屬性。用于用于“自下而上自下而上”傳遞信息傳遞信息天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.1 屬性文法屬性文法(續(xù)續(xù))繼承屬性繼承屬性從語法樹的角度來看

10、，若一個(gè)結(jié)點(diǎn)的某一屬從語法樹的角度來看，若一個(gè)結(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é)符只有綜合屬性，它們由詞法分析器提供只有綜合屬性，它們由詞法分析器提供v非終結(jié)符非終結(jié)符既有綜合屬性也有繼承屬性，但既有綜合屬性也有繼承屬性，但文法開文法開始符始符沒有繼承屬性沒有繼承屬性天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.1 屬性文法屬性文法(續(xù)續(xù))例例 簡單算術(shù)表達(dá)式求值的屬性文法簡單算術(shù)表達(dá)式求值的屬性文法

11、wLE Print(E.val) wEE1+T E.val :E1.val +T.val wET E.val :T.val wTT1*F T.val :T1.val * F.val wTF T.val :F.val wF(E) F.val :E.val 1)Fdigit F.val :digit.lexval E.val、T.val、F.val都是綜合屬性都是綜合屬性終結(jié)符終結(jié)符digit只有綜合屬性只有綜合屬性lexval ，它的值由詞法分，它的值由詞法分析器提供析器提供天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.2 語法制導(dǎo)翻譯概論語法制導(dǎo)翻譯概論w 語法制導(dǎo)翻譯語法制導(dǎo)翻譯基本思想：基本思想：在語法

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

13、l :E1.val +T.val wET E.val :T.val wTT1*digit T.val :T1.val * digit.lexval 1)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)輸入符號(hào)串是一個(gè)句子，它的值也同時(shí)由一旦語法分析確認(rèn)輸入符號(hào)串是一個(gè)句子，它的值也同時(shí)由語義規(guī)則計(jì)算出來語義規(guī)則計(jì)算出來天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.3 中間代碼的形式中間代碼的形式n定義：定義：

14、中間代碼是獨(dú)立于機(jī)器，復(fù)雜性介于源語言和中間代碼是獨(dú)立于機(jī)器，復(fù)雜性介于源語言和機(jī)器語言之間，十分接近目標(biāo)機(jī)器指令的一種機(jī)器語言之間，十分接近目標(biāo)機(jī)器指令的一種表示形式。表示形式。n使用中間代碼的好處：使用中間代碼的好處：中間代碼與具體機(jī)器無關(guān)，便于編譯程序改變中間代碼與具體機(jī)器無關(guān)，便于編譯程序改變目標(biāo)機(jī)目標(biāo)機(jī)便于對(duì)中間代碼進(jìn)行與機(jī)器無關(guān)的優(yōu)化便于對(duì)中間代碼進(jìn)行與機(jī)器無關(guān)的優(yōu)化n表示形式：表示形式：逆波蘭式、四元式、三元式、間接三元式和樹逆波蘭式、四元式、三元式、間接三元式和樹形表示形表示天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.3.1 逆波蘭表示法（后綴式）逆波蘭表示法（后綴式）n 逆波蘭表示法逆波

15、蘭表示法將運(yùn)算對(duì)象寫在前面，把運(yùn)算符寫在后面，將運(yùn)算對(duì)象寫在前面，把運(yùn)算符寫在后面，因而也稱后綴式。因而也稱后綴式。例如：例如：程序設(shè)計(jì)語言中的表示程序設(shè)計(jì)語言中的表示 逆波蘭表示逆波蘭表示a+bab+a+b*c abc * +(a+b)*cab+c *天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系bt1dct1t2t1t1= - bt2= c*dt3= t1+t2例：表達(dá)式例：表達(dá)式bc*d的后綴式的后綴式 bcd*+的計(jì)值過程的計(jì)值過程n后綴式的計(jì)算機(jī)處理后綴式的計(jì)算機(jī)處理后綴式的最大優(yōu)點(diǎn)是易于計(jì)算機(jī)處理后綴式的最大優(yōu)點(diǎn)是易于計(jì)算機(jī)處理處理過程：處理過程：從左到右掃描后綴式，每碰到運(yùn)算對(duì)象就推進(jìn)棧；從左到右

16、掃描后綴式，每碰到運(yùn)算對(duì)象就推進(jìn)棧；碰到運(yùn)算符就從棧頂彈出相應(yīng)目數(shù)的運(yùn)算對(duì)象施碰到運(yùn)算符就從棧頂彈出相應(yīng)目數(shù)的運(yùn)算對(duì)象施加運(yùn)算，并把結(jié)果推進(jìn)棧。最后的結(jié)果留在棧頂。加運(yùn)算，并把結(jié)果推進(jìn)棧。最后的結(jié)果留在棧頂。天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系n逆波蘭表示法的擴(kuò)充逆波蘭表示法的擴(kuò)充逆波蘭表示法很容易擴(kuò)充到表達(dá)式以外的范圍逆波蘭表示法很容易擴(kuò)充到表達(dá)式以外的范圍 例如：例如：語句語句逆波蘭表示逆波蘭表示備注備注a:=b+cabc+:=:=看作二目運(yùn)算符看作二目運(yùn)算符GOTO LL jumpjump看成一目運(yùn)看成一目運(yùn)算符，表示算符，表示GOTOIf E then S1 else S2ES1S2￥把￥把￥

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

18、4) (:,(3),a)天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.3.3 樹形表示樹形表示n樹形表示樹形表示二目運(yùn)算對(duì)應(yīng)二叉子樹，多目運(yùn)算對(duì)應(yīng)多叉子二目運(yùn)算對(duì)應(yīng)二叉子樹，多目運(yùn)算對(duì)應(yīng)多叉子樹，但通常通過引入新結(jié)點(diǎn)表示成二叉子樹。樹，但通常通過引入新結(jié)點(diǎn)表示成二叉子樹。例如例如：a:b*c+b*d 表示成表示成:=a+*bcbd葉子結(jié)點(diǎn)代表運(yùn)算量，葉子結(jié)點(diǎn)代表運(yùn)算量，非葉子結(jié)點(diǎn)代表運(yùn)算符非葉子結(jié)點(diǎn)代表運(yùn)算符天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.3.4 四元式四元式n四元式四元式四元式是一種比較普遍采用的中間代碼形式四元式是一種比較普遍采用的中間代碼形式(算符算符op，ARG1，ARG2，運(yùn)算結(jié)果，運(yùn)算結(jié)果RES

19、ULT）例如：例如：a:b*c+b*d的四元式表示如下：的四元式表示如下： w(*,b,c,t1 )w(*,b,d,t2 )w(+,t1,t2,t3 )w(:, t3 ,a ) 1) 其中其中t i（i1,2,3）是編譯程序引入的臨時(shí)變）是編譯程序引入的臨時(shí)變量量天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.3.4 四元式（續(xù)）四元式（續(xù)）n四元式的優(yōu)點(diǎn)：四元式的優(yōu)點(diǎn)：四元式比三元式更便于優(yōu)化四元式比三元式更便于優(yōu)化優(yōu)化要求改變運(yùn)算順序或刪除某些運(yùn)算，引起編號(hào)優(yōu)化要求改變運(yùn)算順序或刪除某些運(yùn)算，引起編號(hào)的變化。的變化。三元式通過編號(hào)引用中間結(jié)果，編號(hào)的變化引起麻三元式通過編號(hào)引用中間結(jié)果，編號(hào)的變化引起麻煩

20、；四元式通過臨時(shí)變量引用中間結(jié)果，編號(hào)變化煩；四元式通過臨時(shí)變量引用中間結(jié)果，編號(hào)變化無影響。無影響。四元式對(duì)生成目標(biāo)代碼有利四元式對(duì)生成目標(biāo)代碼有利四元式表示很類似于三地址指令，很容易轉(zhuǎn)換成機(jī)四元式表示很類似于三地址指令，很容易轉(zhuǎn)換成機(jī)器代碼。器代碼。天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.3.4 四元式（續(xù)）四元式（續(xù)）n四元式的另一種表示四元式的另一種表示有時(shí)為了更直觀，把四元式寫成簡單賦值形式有時(shí)為了更直觀，把四元式寫成簡單賦值形式或更易理解的形式或更易理解的形式(三地址碼三地址碼)四元式四元式直觀形式直觀形式（1）（）（ * , b , c , t1） （1） t1:b*c（2）（）（ *

21、, b , d , t2）（2） t2:b*d（3）（）（ +, t1 , t2 , t3） （3） t3:t1+t2（4）（）（:, t3 , a）（4） a:t3天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.3.5 間接三元式間接三元式n為了便于優(yōu)化處理，不直接使用三元式，為了便于優(yōu)化處理，不直接使用三元式，而是另設(shè)一張指示器表（稱為間接碼而是另設(shè)一張指示器表（稱為間接碼表），它按照運(yùn)算的先后順序列出有關(guān)表），它按照運(yùn)算的先后順序列出有關(guān)三元式在三元式表中的位置。即：三元式在三元式表中的位置。即：用一用一張間接碼表輔以三元式表的方法來表示張間接碼表輔以三元式表的方法來表示中間代碼。中間代碼。n四元式、間

22、接三元式的優(yōu)化同樣方便，四元式、間接三元式的優(yōu)化同樣方便，三元式的優(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, T5, T6)1)(+, T3, T6, T7)天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系舉例：舉例：給出給出A+B*(C-D)+E/(C

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

24、行翻譯（產(chǎn)生中間代碼）語義動(dòng)作進(jìn)行翻譯（產(chǎn)生中間代碼）天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.4.1簡單賦值語句到四元式的翻譯簡單賦值語句到四元式的翻譯簡單賦值語句簡單賦值語句是指不含復(fù)雜數(shù)據(jù)類型（如數(shù)組，記錄等）的是指不含復(fù)雜數(shù)據(jù)類型（如數(shù)組，記錄等）的賦值語句。賦值語句。賦值語句的語義檢查包括賦值語句的語義檢查包括：每個(gè)使用性標(biāo)識(shí)符是否都有聲明？每個(gè)使用性標(biāo)識(shí)符是否都有聲明？運(yùn)算符的分量類型是否相容？運(yùn)算符的分量類型是否相容？賦值語句的左右部的類型是否相容？賦值語句的左右部的類型是否相容？賦值語句的翻譯目標(biāo)：賦值語句的翻譯目標(biāo)：在賦值語句右部表達(dá)式產(chǎn)生的四元式序列后加在賦值語句右部表達(dá)式產(chǎn)生的四元

25、式序列后加一條賦值四元式一條賦值四元式天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.4.1簡單賦值語句到四元式的翻譯簡單賦值語句到四元式的翻譯考慮如下文法描述的簡單賦值句的翻譯：考慮如下文法描述的簡單賦值句的翻譯：Ai:=E EE+E|E*E|-E|(E)|i (6.1)A代表賦值語句，設(shè)只含整型變量的運(yùn)算代表賦值語句，設(shè)只含整型變量的運(yùn)算1、需要定義一系列的語義變量和語義過程：、需要定義一系列的語義變量和語義過程：NEWTEMP：函數(shù)，生成臨時(shí)變量，每次調(diào)用生成一個(gè)：函數(shù)，生成臨時(shí)變量，每次調(diào)用生成一個(gè)新的臨時(shí)變量，如新的臨時(shí)變量，如t1, t2 , 返回一個(gè)整數(shù)碼作為函數(shù)值。返回一個(gè)整數(shù)碼作為函數(shù)值。E

26、NTRY(i)：函數(shù)過程，查找并取得與：函數(shù)過程，查找并取得與i相對(duì)應(yīng)的標(biāo)識(shí)符相對(duì)應(yīng)的標(biāo)識(shí)符在符號(hào)表中的位置（入口），簡稱在符號(hào)表中的位置（入口），簡稱i值。值。E.PLACE：與：與E相聯(lián)系的語義變量，表示存放相聯(lián)系的語義變量，表示存放E值的變量值的變量名在符號(hào)表的入口。名在符號(hào)表的入口。GEN(OP,ARG1,ARG1,RESULT)：語義過程，將四元式：語義過程，將四元式(OP,ARG1,ARG1,RESULT)填進(jìn)四元式表中。填進(jìn)四元式表中。 天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系n使用上述變量和過程，對(duì)文法使用上述變量和過程，對(duì)文法6.1所定義的賦值所定義的賦值語句的翻譯算法可由下述語義動(dòng)作予

27、以描述語句的翻譯算法可由下述語義動(dòng)作予以描述6.4.1簡單賦值語句到四元式的翻譯簡單賦值語句到四元式的翻譯產(chǎn)生式產(chǎn)生式語義動(dòng)作語義動(dòng)作Ai:=E GEN(:=,E.PLACE,-,ENTRY(i) EE(1)+E (2) E.PLACE:=NEWTEMP; 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:

28、=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_ _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+i

29、A_T1 _ _C_D) i:= E*( E+E A_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例例：寫出下面賦值語句：寫出下面賦值語句A:=-B*(C+D)的自下而的自下而上語法制導(dǎo)翻譯的過程，上語法制導(dǎo)翻譯的過程，及生成的四元式。及生成的四元式。Ai:=E EE+E|E*E|-E|(E)|i 四元式為四元式為:(1)(,B,-,T1) (2) (+,C,D,T2) (3)(*, T1 ,T2,T3)

30、(4) (:=, T3, - ,A)天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系3、類型轉(zhuǎn)換、類型轉(zhuǎn)換表達(dá)式中可能出現(xiàn)不同類型的變量和常量表達(dá)式中可能出現(xiàn)不同類型的變量和常量若不接受不同類型的運(yùn)算對(duì)象混合運(yùn)算，則應(yīng)指出錯(cuò)誤；若不接受不同類型的運(yùn)算對(duì)象混合運(yùn)算，則應(yīng)指出錯(cuò)誤；若接受混合運(yùn)算則要進(jìn)行類型轉(zhuǎn)換處理。若接受混合運(yùn)算則要進(jìn)行類型轉(zhuǎn)換處理。例：假定表達(dá)式可以有混合運(yùn)算，變量可以是整型和實(shí)例：假定表達(dá)式可以有混合運(yùn)算，變量可以是整型和實(shí)型，且當(dāng)兩個(gè)不同類型的變量進(jìn)行運(yùn)算時(shí)先把整型變量型，且當(dāng)兩個(gè)不同類型的變量進(jìn)行運(yùn)算時(shí)先把整型變量轉(zhuǎn)換成實(shí)型，再進(jìn)行運(yùn)算。轉(zhuǎn)換成實(shí)型，再進(jìn)行運(yùn)算。用用 +i , *i , i

31、表示整型運(yùn)算，用表示整型運(yùn)算，用 +r , *r, r表示實(shí)型表示實(shí)型運(yùn)算，用一目算符運(yùn)算，用一目算符 itr 表示將整型量轉(zhuǎn)換成實(shí)型量表示將整型量轉(zhuǎn)換成實(shí)型量的運(yùn)算的運(yùn)算令文法令文法6.1中的中的 i 既可以是整型也可以是實(shí)型既可以是整型也可以是實(shí)型用用E.MODE表示表示E的類型信息，其值為的類型信息，其值為int或或r，則，則產(chǎn)生式產(chǎn)生式EE(1) op E(2)的語義動(dòng)作中，關(guān)于的語義動(dòng)作中，關(guān)于E.MODE的語義規(guī)的語義規(guī)則可定義為：則可定義為： if E1. MODE int AND E2. MODE int then E. MODE :=int else E. MODE :=r

32、天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系3、類型轉(zhuǎn)換（續(xù)）、類型轉(zhuǎn)換（續(xù)）nEE(1) op E(2) 的語義程序應(yīng)該修改，必要的語義程序應(yīng)該修改，必要時(shí)產(chǎn)生對(duì)運(yùn)算量進(jìn)行類型轉(zhuǎn)換的四元式：時(shí)產(chǎn)生對(duì)運(yùn)算量進(jìn)行類型轉(zhuǎn)換的四元式：(itr,A,-,T)，表示把整型，表示把整型A轉(zhuǎn)換成實(shí)型量，結(jié)轉(zhuǎn)換成實(shí)型量，結(jié)果存于果存于T中。中。n例：假定輸入串為例：假定輸入串為X:=Y+I*J，其中，其中X,Y為為實(shí)型，實(shí)型，I,J為整型，則其產(chǎn)生的四元式為：為整型，則其產(chǎn)生的四元式為：(1) (*i ,I,J,T1) (2)(itr,T1,-,T2) (3) (+r ,Y,T2,T3) (4) (:=,T3,-,X)n例：

33、關(guān)于產(chǎn)生式例：關(guān)于產(chǎn)生式EE(1) op E(2) 的語義子程的語義子程序更為具體的描述為：序更為具體的描述為：天津財(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 GEN(opr , E1.PLACE, E2.PLACE,T); E.MODE:=r ENDELSE IF E1.MODE=int /*AND E2.MODE=r */ T

34、HEN 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) op E(2)天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系布爾表達(dá)式的兩個(gè)作用：布爾表達(dá)式的兩個(gè)作用： 用于邏輯運(yùn)算，計(jì)算邏輯值用于邏輯運(yùn)算，計(jì)算邏輯值 作為控制語句作為控制語句(如如

35、if-then,while)的條件的條件表達(dá)式表達(dá)式布爾表達(dá)式由布爾算符（布爾表達(dá)式由布爾算符（not,and,or）作）作用于布爾變量（或常數(shù)）或關(guān)系表達(dá)式用于布爾變量（或常數(shù)）或關(guān)系表達(dá)式而形成的。而形成的。關(guān)系表達(dá)式的形式：關(guān)系表達(dá)式的形式：E1 rop E2，rop是是關(guān)關(guān)系算符系算符(如如, , =)6.4.2布爾表達(dá)式到四元式的翻譯布爾表達(dá)式到四元式的翻譯天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系為簡單起見，只考慮如下形式的布爾表達(dá)式的為簡單起見，只考慮如下形式的布爾表達(dá)式的翻譯，文法翻譯，文法(6.2)EE or E | E and E | not E | (E ) | id rop id |

36、id布 爾 算 符布 爾 算 符 的 優(yōu) 先 順 序 （ 從 高 到 低 ） 為 ：的 優(yōu) 先 順 序 （ 從 高 到 低 ） 為 ：not,and,or，且，且and和和or都服從左結(jié)合，都服從左結(jié)合，not服服從右結(jié)合從右結(jié)合關(guān)系算符關(guān)系算符的優(yōu)先級(jí)都相同，而且高于任何布爾的優(yōu)先級(jí)都相同，而且高于任何布爾算符，低于任何算術(shù)算符算符，低于任何算術(shù)算符6.4.2布爾表達(dá)式到四元式的翻譯布爾表達(dá)式到四元式的翻譯-續(xù)續(xù)天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系1.布爾表達(dá)式的計(jì)算方法：布爾表達(dá)式的計(jì)算方法： 采用兩種方法：數(shù)值表示的采用兩種方法：數(shù)值表示的直接計(jì)算直接計(jì)算與邏輯表與邏輯表示的示的短路計(jì)算短路計(jì)算

37、直接計(jì)算與算術(shù)表達(dá)式計(jì)算方法基本相同直接計(jì)算與算術(shù)表達(dá)式計(jì)算方法基本相同如：如：1 or 0 and 1=1 or 0 的結(jié)果為：的結(jié)果為：1短路計(jì)算即布爾表達(dá)式計(jì)算到某一部分就可以得短路計(jì)算即布爾表達(dá)式計(jì)算到某一部分就可以得到結(jié)果，而無需對(duì)布爾表達(dá)式進(jìn)行完全計(jì)算。可到結(jié)果，而無需對(duì)布爾表達(dá)式進(jìn)行完全計(jì)算?？梢杂靡杂胕f-then-else來解釋來解釋A or B if A then true else BA and Bif A then B else falsenot Aif A then false else true天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系2、直接計(jì)算的語法制導(dǎo)翻譯、直接計(jì)算的語法制

38、導(dǎo)翻譯布爾表達(dá)式有兩種翻譯方法。（視計(jì)算機(jī)硬件條布爾表達(dá)式有兩種翻譯方法。（視計(jì)算機(jī)硬件條件來確定，如果執(zhí)行條件轉(zhuǎn)移效率較低，就用件來確定，如果執(zhí)行條件轉(zhuǎn)移效率較低，就用第一種方法）第一種方法）n直接計(jì)算的語法制導(dǎo)翻譯直接計(jì)算的語法制導(dǎo)翻譯 如同翻譯算術(shù)表達(dá)式一樣來翻譯布爾表達(dá)式如同翻譯算術(shù)表達(dá)式一樣來翻譯布爾表達(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á)式用于控

39、制條件時(shí)，并不需要計(jì)算表當(dāng)布爾表達(dá)式用于控制條件時(shí)，并不需要計(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 S1 else S2為布爾表達(dá)式為布爾表達(dá)式E引入兩個(gè)新的引入兩個(gè)新的屬性：屬性：E.true：表達(dá)式的真出口，：表達(dá)式的真出口，它指向表達(dá)式為真時(shí)的轉(zhuǎn)向它指向表達(dá)式為真時(shí)的轉(zhuǎn)向E.false：表達(dá)式的假出口，：表達(dá)式的假出口，它指向表達(dá)式為假時(shí)的轉(zhuǎn)向它指向表達(dá)式為假時(shí)的轉(zhuǎn)向天津財(cái)經(jīng)大學(xué)信息科

40、學(xué)與技術(shù)系把布爾表達(dá)式把布爾表達(dá)式E翻譯成下述形式的條件轉(zhuǎn)移和無條翻譯成下述形式的條件轉(zhuǎn)移和無條件轉(zhuǎn)移的四元式序列：件轉(zhuǎn)移的四元式序列：w( jnz , A , - , p )w若若A為真，則轉(zhuǎn)向四元式為真，則轉(zhuǎn)向四元式pw( jrop , A , B , p )若若A rop B為真，則轉(zhuǎn)向四元式為真，則轉(zhuǎn)向四元式pw( j , - , - , p )無條件轉(zhuǎn)向四元式無條件轉(zhuǎn)向四元式p3.作為條件控制的布爾式翻譯作為條件控制的布爾式翻譯-續(xù)續(xù)(1) ( jnz , A , - , 5 )A的真出口為的真出口為5(2) ( j , - , - , 3 )A的假出口為的假出口為3(3) ( j

41、, B , D , 5 )BD的真出口為的真出口為5(4) ( j , - , - , p+1 ) BD的假出口為的假出口為(p+1)(5) (關(guān)于關(guān)于S1的四元式序列的四元式序列)(p)( j , - , - , q )跳過跳過S2的代碼段的代碼段(p+1) (關(guān)于關(guān)于S2的四元式序列的四元式序列)(q)(1) - (4)是布爾式是布爾式A or BD 翻譯產(chǎn)生的代碼，全部是條翻譯產(chǎn)生的代碼，全部是條件轉(zhuǎn)移和無條件轉(zhuǎn)移四元式，沒有布爾運(yùn)算。件轉(zhuǎn)移和無條件轉(zhuǎn)移四元式，沒有布爾運(yùn)算。例：例：if A or BD then S1 else S2翻譯成如下四元式序列翻譯成如下四元式序列天津財(cái)經(jīng)大學(xué)信

42、息科學(xué)與技術(shù)系具體說明如下：具體說明如下：用用E.true和和E.false 分別表示分別表示E的的“真真”和和“假假”出口轉(zhuǎn)移目標(biāo)，在翻譯出口轉(zhuǎn)移目標(biāo)，在翻譯E時(shí)并未能確時(shí)并未能確定。定。對(duì)于對(duì)于E為為 a rop b 形式，生成代碼如下：形式，生成代碼如下：( jrop , a , b , E.true )( j , E.false )以結(jié)構(gòu)圖表示：以結(jié)構(gòu)圖表示：E的代碼的代碼E.falseE.true天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系對(duì)于對(duì)于E為為 E1 or E2的形式，生成代碼結(jié)構(gòu)如下：的形式，生成代碼結(jié)構(gòu)如下：E1.的代碼的代碼E2.的代碼的代碼E1.falseE2.falseE.fal

43、seE1.trueE2.trueE.true若若E1為真，則可知為真，則可知E為真，即為真，即E1的真出口和的真出口和E的真出口一樣；的真出口一樣；若若E1為假，則必須計(jì)算為假，則必須計(jì)算E2，因此，因此E1的假出口應(yīng)是的假出口應(yīng)是E2代碼的第代碼的第一個(gè)四元式序號(hào)；一個(gè)四元式序號(hào)；E2的真出口和假出口分別與的真出口和假出口分別與E的真出口和假出口一樣的真出口和假出口一樣天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系E1.的代碼的代碼E2.的代碼的代碼E1.falseE2.falseE.falseE1.trueE2.trueE.true對(duì)于對(duì)于E為為 E1 and E2的形式，生成代碼結(jié)構(gòu)如下：的形式，生成代碼

44、結(jié)構(gòu)如下：對(duì)于對(duì)于E為為 not E1形式，只需調(diào)換形式，只需調(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)和無條件轉(zhuǎn)四元在把布爾式翻譯成一串條件轉(zhuǎn)和無條件轉(zhuǎn)四元式時(shí)，真假出口未能在生成四元式時(shí)確定；而式時(shí)，真假出口未能在生成四元式時(shí)確

45、定；而且多個(gè)四元式可能有相同的出口且多個(gè)四元式可能有相同的出口天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系說明：說明：E.true和和E.false不能不能在產(chǎn)生四元式的同在產(chǎn)生四元式的同時(shí)確定，要等將來時(shí)確定，要等將來目標(biāo)明確時(shí)再回填，目標(biāo)明確時(shí)再回填，為此要記錄這些要為此要記錄這些要回填的四元式。回填的四元式。通常采用通常采用“拉鏈拉鏈”的辦法，把需要回的辦法，把需要回填填E.true的四元式拉的四元式拉成一條成一條“真真”鏈，鏈，把需要回填把需要回填E.false的的四元式拉成一條四元式拉成一條“假假”鏈。鏈。if ab or cf then S1 else S2翻譯為四元式序列：翻譯為四元式序列：（1

46、） (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)天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系練習(xí)：練習(xí)：把下面的語句翻譯成四元式序列：把下面的語句翻譯成四元式序列：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說明：說明： 產(chǎn)生是產(chǎn)生是100103是對(duì)應(yīng)布爾式是對(duì)應(yīng)布爾式AB or C=,C,D,106)。但這些是。但這些是下一階段代碼優(yōu)化要討論的下一階段代碼優(yōu)化要討論的問題，暫不討論。問題，暫不討論。天津財(cái)經(jīng)大學(xué)信息科學(xué)與技術(shù)系6.4.3 控制語句的翻譯控制語句的翻譯n以以if 語句，語句，while語句為例說明控制語句的翻譯方法語句為例說明控制語句的翻譯方法S if E then S1