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

1、屬性文法與屬性翻譯文法屬性文法與屬性翻譯文法 常見中間語言概述常見中間語言概述簡單算術(shù)表達式和賦值語句的翻譯簡單算術(shù)表達式和賦值語句的翻譯布爾表達式的翻譯布爾表達式的翻譯程序流控制語句的翻譯程序流控制語句的翻譯說明語句的翻譯說明語句的翻譯第8章 語法制導(dǎo)翻譯和中間代碼生成編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (2 2) ) 8.1 概述概述 1. 語義分析的概念語義分析的概念 一個源程序經(jīng)過詞法分析、語法分析之后，表一個源程序經(jīng)過詞法分析、語法分析之后，表明該源程序在書寫上是正確的，并且符合程序語言明該源程序在書寫上是正確的，并且符合程序語

2、言所規(guī)定的語法。但是語法分析并未對程序內(nèi)部的邏所規(guī)定的語法。但是語法分析并未對程序內(nèi)部的邏輯含義加以分析，因此編譯程序接下來的工作是語輯含義加以分析，因此編譯程序接下來的工作是語義分析，即審查每個語法成分的靜態(tài)語義。若靜態(tài)義分析，即審查每個語法成分的靜態(tài)語義。若靜態(tài)語義正確，則生成與該語言成分等效的中間代碼，語義正確，則生成與該語言成分等效的中間代碼，或者直接生成目標(biāo)代碼?；蛘咧苯由赡繕?biāo)代碼。 編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (3 3) )直接生成機器語言或匯編語言形式的目標(biāo)代碼直接生成機器語言或匯編語言形式的目標(biāo)代碼優(yōu)點：編譯時間

3、短且無需中間代碼到目標(biāo)代碼的翻譯。優(yōu)點：編譯時間短且無需中間代碼到目標(biāo)代碼的翻譯。中間代碼的優(yōu)點中間代碼的優(yōu)點 使編譯結(jié)構(gòu)在邏輯上更為簡單明確，特別是使目標(biāo)使編譯結(jié)構(gòu)在邏輯上更為簡單明確，特別是使目標(biāo)代碼的優(yōu)化比較容易實現(xiàn)。代碼的優(yōu)化比較容易實現(xiàn)。編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (4 4) ) 如同在進行詞法分析、語法分析的同時也進行著詞法如同在進行詞法分析、語法分析的同時也進行著詞法檢查、語法檢查一樣，在語義分析時也必然要進行語義檢查、語法檢查一樣，在語義分析時也必然要進行語義檢查。動態(tài)語義檢查需要生成相應(yīng)的目標(biāo)代碼，它是在檢查。動

4、態(tài)語義檢查需要生成相應(yīng)的目標(biāo)代碼，它是在運行時進行的；靜態(tài)語義檢查是在編譯時完成的，它涉運行時進行的；靜態(tài)語義檢查是在編譯時完成的，它涉及以下幾個方面：及以下幾個方面： (1) 類型檢查，如參與運算的操作數(shù)其類型應(yīng)相容。類型檢查，如參與運算的操作數(shù)其類型應(yīng)相容。 (2) 控制流檢查，用以保證控制語句有合法的轉(zhuǎn)向點?？刂屏鳈z查，用以保證控制語句有合法的轉(zhuǎn)向點。如如c語言中不允許語言中不允許goto語句轉(zhuǎn)入語句轉(zhuǎn)入case語句流；語句流；break語句語句需尋找包含它的最小需尋找包含它的最小switch、while或或for語句方可找到轉(zhuǎn)語句方可找到轉(zhuǎn)向點，否則出錯。向點，否則出錯。編譯原理編譯原

5、理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (5 5) ) (3) 一致性檢查一致性檢查，如在相同作用域中標(biāo)識符只能說明，如在相同作用域中標(biāo)識符只能說明一次、一次、case語句的標(biāo)號不能相同等。語句的標(biāo)號不能相同等。 語義分析階段只產(chǎn)生中間代碼而不生成目標(biāo)代碼語義分析階段只產(chǎn)生中間代碼而不生成目標(biāo)代碼的方法使編譯程序的開發(fā)變得較為容易，但語義分析的方法使編譯程序的開發(fā)變得較為容易，但語義分析不像詞法分析和語法分析那樣可以分別用正規(guī)文法和不像詞法分析和語法分析那樣可以分別用正規(guī)文法和上下文無關(guān)文法描述。由于上下文無關(guān)文法描述。由于語義是上下文有關(guān)的，因語義是上下

6、文有關(guān)的，因此語義的形式化描述是非常困難的，目前較為常見的此語義的形式化描述是非常困難的，目前較為常見的是用屬性文法作為描述程序語言語義的工具，并采用是用屬性文法作為描述程序語言語義的工具，并采用語法制導(dǎo)翻譯的方法完成對語法成分的翻譯工作。語法制導(dǎo)翻譯的方法完成對語法成分的翻譯工作。編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (6 6) ) 2. 語法制導(dǎo)翻譯方法語法制導(dǎo)翻譯方法 語法制導(dǎo)翻譯的方法就是為每個產(chǎn)生式配上一個翻譯子語法制導(dǎo)翻譯的方法就是為每個產(chǎn)生式配上一個翻譯子程序（稱語義動作或語義子程序），并在語法分析的同時程序（稱語義動作或語義

7、子程序），并在語法分析的同時執(zhí)行這些子程序。執(zhí)行這些子程序。語義動作是為產(chǎn)生式賦予具體意義的手語義動作是為產(chǎn)生式賦予具體意義的手段，段，它一方面指出了一個產(chǎn)生式所產(chǎn)生的符號串的意義，它一方面指出了一個產(chǎn)生式所產(chǎn)生的符號串的意義，另一方面又按照這種意義規(guī)定了生成某種中間代碼應(yīng)做哪另一方面又按照這種意義規(guī)定了生成某種中間代碼應(yīng)做哪些基本動作。些基本動作。在語法分析過程中，當(dāng)一個產(chǎn)生式獲得匹配在語法分析過程中，當(dāng)一個產(chǎn)生式獲得匹配（對于自上而下分析）或用于歸約（對于自下而上分析）（對于自上而下分析）或用于歸約（對于自下而上分析）時，此產(chǎn)生式相應(yīng)的語義子程序就進入工作，完成既定的時，此產(chǎn)生式相應(yīng)的語義

8、子程序就進入工作，完成既定的翻譯任務(wù)。翻譯任務(wù)。編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (7 7) ) 語法制導(dǎo)翻譯分為自下而上語法制導(dǎo)翻譯和自上而下語法制導(dǎo)翻譯分為自下而上語法制導(dǎo)翻譯和自上而下語法制導(dǎo)翻譯。語法制導(dǎo)翻譯。本章重點介紹自下而上語法制導(dǎo)翻譯。本章重點介紹自下而上語法制導(dǎo)翻譯。 假定有一個自下而上的假定有一個自下而上的lr分析器，可以把這個分析器，可以把這個lr分分析器的能力加以擴大，使它能在用某個產(chǎn)生式進行歸約析器的能力加以擴大，使它能在用某個產(chǎn)生式進行歸約的同時調(diào)用相應(yīng)的語義子程序進行有關(guān)的翻譯工作；每的同時調(diào)用相應(yīng)的語義子

9、程序進行有關(guān)的翻譯工作；每個產(chǎn)生式的語義子程序執(zhí)行之后，某些結(jié)果個產(chǎn)生式的語義子程序執(zhí)行之后，某些結(jié)果(語義信息語義信息)必必須作為此產(chǎn)生式的左部符號的語義值暫時保存下來，以須作為此產(chǎn)生式的左部符號的語義值暫時保存下來，以便以后語義子程序引用這些信息。便以后語義子程序引用這些信息。編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (8 8) ) 此外，原此外，原lr分析器的分析棧也加以擴充，以便能分析器的分析棧也加以擴充，以便能夠存放與文法符號相對應(yīng)的語義值。這樣，分析?？梢詨虼娣排c文法符號相對應(yīng)的語義值。這樣，分析?？梢源娣湃愋畔ⅲ悍治鰻顟B(tài)、文法符

10、號及文法符號對應(yīng)的存放三類信息：分析狀態(tài)、文法符號及文法符號對應(yīng)的語義值。擴充后的分析棧如圖語義值。擴充后的分析棧如圖5.1所示。所示。 考查下面的文法及語義動作所執(zhí)行的程序：考查下面的文法及語義動作所執(zhí)行的程序：編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (9 9) )skxkvkvals1x1v1vals0#狀態(tài)文法符號語義值top 圖圖5.1 擴充后的擴充后的lr分析棧分析棧 編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (1010) )產(chǎn)生式產(chǎn)生式 語義動作語義動作(0) se print v

11、altop(1) ee(1)+e(2) valtop=valtop+valtop+2(2) ee(1)*e(2) valtop=valtop*valtop+2(3) e(e(1) valtop= valtop+1(4) ei valtop=lexval (注：注：lexval為為i的整型內(nèi)部值的整型內(nèi)部值)這個文法的這個文法的lr分析見表分析見表5.1。編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (1111) ) 擴充分析棧工作的總控程序功能擴充分析棧工作的總控程序功能 在完成語法分析的同時也能完成語義分析工作在完成語法分析的同時也能完成語義分析

12、工作(這時這時的語法分析棧已成為語義分析棧的語法分析棧已成為語義分析棧)；即在用某一個規(guī)則進；即在用某一個規(guī)則進行歸約之后，調(diào)用相應(yīng)的語義子程序完成與所用產(chǎn)生式行歸約之后，調(diào)用相應(yīng)的語義子程序完成與所用產(chǎn)生式相應(yīng)的語義動作。相應(yīng)的語義動作。 將每次工作后的語義值保存在擴充后的將每次工作后的語義值保存在擴充后的“語義值語義值”棧中。棧中。 圖圖5.2表示算術(shù)表達式表示算術(shù)表達式79*5#的語法樹及各結(jié)點值。的語法樹及各結(jié)點值。 表表5.1則給出了用則給出了用lr語法制導(dǎo)翻譯方法得到的該表達式語法制導(dǎo)翻譯方法得到的該表達式的語義分析和計值過程。的語義分析和計值過程。編譯原理編譯原理 第第8 8章章

13、 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (1212) )eval52eval7eval457eval9*eval595圖圖5.2 語法制導(dǎo)翻譯計算表達式語法制導(dǎo)翻譯計算表達式 79*5#的語法樹的語法樹編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (1313) )表5.1 表達式79*5#的語義分析和計值過程步驟步驟狀態(tài)棧狀態(tài)棧符號棧符號棧語義棧語義棧輸入串輸入串主要動作主要動作10#_79*5#s3203# 7_ _9*5#r4301# e_79*5#s44014# e+_7_9*5#s350143# e+9_7_ _*5#r

14、460147# e+e_7_9*5#s5701475# e+e*_7_9_5#s38014753# e+e*5_7_9_ _#r49014758# e+e*e_7_9_5#r2100147# e+e_7_45#r11101# e_52#acc編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (1414) )5.2 屬性文法與屬性翻譯文法屬性文法與屬性翻譯文法 5.2.1 語義屬性與屬性文法語義屬性與屬性文法 屬性是指與文法符號的類型和值等有關(guān)的一些信息，在屬性是指與文法符號的類型和值等有關(guān)的一些信息，在編譯中用屬性描述處理對象的特征。隨著編譯的進展，對

15、編譯中用屬性描述處理對象的特征。隨著編譯的進展，對語法分析產(chǎn)生的語法樹進行語義分析，且分析的結(jié)果用中語法分析產(chǎn)生的語法樹進行語義分析，且分析的結(jié)果用中間代碼描述出來。對于一棵等待翻譯的語法樹，它的各個間代碼描述出來。對于一棵等待翻譯的語法樹，它的各個結(jié)點都是文法中的一個符號結(jié)點都是文法中的一個符號x，該，該x可以是終結(jié)符或非終結(jié)可以是終結(jié)符或非終結(jié)符。根據(jù)語義處理的需要，在用產(chǎn)生式符。根據(jù)語義處理的需要，在用產(chǎn)生式ax進行歸約或進行歸約或推導(dǎo)時，應(yīng)能準(zhǔn)確而恰當(dāng)?shù)乇磉_文法符號推導(dǎo)時，應(yīng)能準(zhǔn)確而恰當(dāng)?shù)乇磉_文法符號x在歸約或推導(dǎo)在歸約或推導(dǎo)時的不同特征。時的不同特征。 編譯原理編譯原理 第第8 8章

16、章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (1515) )例如：例如： 判斷變量判斷變量x的類型是否匹配，要用的類型是否匹配，要用x的數(shù)據(jù)類型來描述；的數(shù)據(jù)類型來描述； 判斷變量判斷變量x是否存在，要用是否存在，要用x的存儲位置來描述；的存儲位置來描述； 而對而對x的運算，則要用的運算，則要用x的值來描述。的值來描述。 因此，語義分析階段引入因此，語義分析階段引入x的屬性，如的屬性，如x.type、x.place、x.val等來分別描述變量等來分別描述變量x的類型、存儲位置以的類型、存儲位置以及值等不同的特征。及值等不同的特征。編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯

17、和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (1616) )文法符號的屬性：繼承屬性與綜合屬性兩類。文法符號的屬性：繼承屬性與綜合屬性兩類。 （1）繼承屬性用于）繼承屬性用于“自上而下自上而下”傳遞信息傳遞信息 繼承屬性由相應(yīng)語法樹中結(jié)點的父結(jié)點屬性繼承屬性由相應(yīng)語法樹中結(jié)點的父結(jié)點屬性計算得到，即沿語法樹向下傳遞，由根結(jié)點到分枝計算得到，即沿語法樹向下傳遞，由根結(jié)點到分枝(子子)結(jié)點；結(jié)點； 繼承屬性反映了對上下文依賴的特性。繼承屬性反映了對上下文依賴的特性。 繼承屬性可以很方便地用來表示程序語言上下繼承屬性可以很方便地用來表示程序語言上下文的結(jié)構(gòu)關(guān)系。文的結(jié)構(gòu)關(guān)系。編譯原理編譯原理 第第

18、8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (1717) )（2）綜合屬性用于）綜合屬性用于“自下而上自下而上”傳遞信息傳遞信息 綜合屬性由相應(yīng)語法分析樹中結(jié)點的分枝綜合屬性由相應(yīng)語法分析樹中結(jié)點的分枝結(jié)點結(jié)點(即子結(jié)點即子結(jié)點)屬性計算得到，其傳遞方向與屬性計算得到，其傳遞方向與繼承屬性相反，即沿語法分析樹向上傳遞，從繼承屬性相反，即沿語法分析樹向上傳遞，從分枝結(jié)點到根結(jié)點。分枝結(jié)點到根結(jié)點。編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (1818) ) 5.2.2 屬性翻譯文法屬性翻譯文法 屬性文法是一種適用于定義語義

19、的特殊文法，即在屬性文法是一種適用于定義語義的特殊文法，即在語言的文法中增加了屬性的文法，它將文法符號的語義語言的文法中增加了屬性的文法，它將文法符號的語義以以“屬性屬性”的形式附加到各個文法的符號上的形式附加到各個文法的符號上(如上述與變?nèi)缟鲜雠c變量量x相關(guān)聯(lián)的屬性相關(guān)聯(lián)的屬性x.type、x.place和和x.val等等)，再根據(jù)產(chǎn)，再根據(jù)產(chǎn)生式所包含的含義，給出每個文法符號屬性的求值規(guī)則，生式所包含的含義，給出每個文法符號屬性的求值規(guī)則，從而形成一種從而形成一種帶有語義屬性的上下文無關(guān)文法帶有語義屬性的上下文無關(guān)文法，即屬性即屬性文法。文法。屬性文法也是一種翻譯文法，屬性有助于更詳細屬性

20、文法也是一種翻譯文法，屬性有助于更詳細地指定文法中的代碼生成動作。地指定文法中的代碼生成動作。編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (1919) )例如，簡單算術(shù)表達式求值的屬性文法如下：例如，簡單算術(shù)表達式求值的屬性文法如下： 產(chǎn)生式產(chǎn)生式 語義規(guī)則語義規(guī)則 (1) se print (e.val) (2) ee(1)+t e.val=e(1).val+t.val (3) et e.val=t.val (4) tt(1)*f t.val=t(1).val*f.val (5) tt(1) t.val=t(1).val (6) f(e) f.

21、val=e.val (7) fi f.val=i.lexval編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (2020) ) 與產(chǎn)生式關(guān)聯(lián)的每一個語義規(guī)則的左部符號與產(chǎn)生式關(guān)聯(lián)的每一個語義規(guī)則的左部符號e、t、f等等的屬性值的計算由其各自相應(yīng)的右部符號決定，這種屬性的屬性值的計算由其各自相應(yīng)的右部符號決定，這種屬性也稱為也稱為綜合屬性綜合屬性。 與產(chǎn)生式與產(chǎn)生式se關(guān)聯(lián)的語義規(guī)則是一個函數(shù)關(guān)聯(lián)的語義規(guī)則是一個函數(shù)print(e.val)，其功能是打印其功能是打印e產(chǎn)生式的值。產(chǎn)生式的值。s在語義規(guī)則中沒有出現(xiàn)，在語義規(guī)則中沒有出現(xiàn)，可以理解為其屬性

22、是一個虛屬性?？梢岳斫鉃槠鋵傩允且粋€虛屬性。 另一說明屬性文法例：一簡單變量類型說明的文法如另一說明屬性文法例：一簡單變量類型說明的文法如下：下： gd：dint l float l ll, id id編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (2121) )注意到與文法注意到與文法gd相應(yīng)的說明語句形式可為相應(yīng)的說明語句形式可為int id1，id2,，idn 或者或者 float id1，id2,，idn其對應(yīng)的屬性文法為：其對應(yīng)的屬性文法為： 產(chǎn)生式產(chǎn)生式 語義規(guī)則語義規(guī)則 (1) dtl l.in=t.type (2) tint t.t

23、ype=int (3) tfloat t.type=float (4) ll(1),id l(1).in=l.in; addtype(id.entry,l.in) (5) lid addtype(id.entry,l.in)編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (2222) ) 非終結(jié)符非終結(jié)符t有一個綜合屬性有一個綜合屬性type，其值為，其值為int或或float。 語義規(guī)則語義規(guī)則l.in=t.type表示表示l.in的屬性值由相應(yīng)的屬性值由相應(yīng)說明語句指定的類型說明語句指定的類型t.type決定；屬性決定；屬性l.in被確定被確定后

24、將隨語法樹的逐步生成而傳遞到下邊的有關(guān)結(jié)點后將隨語法樹的逐步生成而傳遞到下邊的有關(guān)結(jié)點使用，這種結(jié)點屬性稱為繼承屬性。使用，這種結(jié)點屬性稱為繼承屬性。 由此可見，標(biāo)識符的類型可以通過繼承屬性的由此可見，標(biāo)識符的類型可以通過繼承屬性的復(fù)寫規(guī)則來傳遞。復(fù)寫規(guī)則來傳遞。編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (2323) )圖圖5.3 屬性信息傳遞情況示意屬性信息傳遞情況示意dtlintl，id2id1例如，對輸入串例如，對輸入串int a,b，根據(jù)上，根據(jù)上述的語義規(guī)則，可在其生成的語述的語義規(guī)則，可在其生成的語法樹中看到用法樹中看到用“”表示的

25、屬性表示的屬性傳遞情況，如圖所示。傳遞情況，如圖所示。 編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (2424) )3*5+4的帶注釋的分析樹的帶注釋的分析樹只使用綜合屬性。只使用綜合屬性。se.val=19e.val=15t.val=4t.val=15f.val=4t.val=3f.val=3f.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的帶注釋的分析樹的帶注釋的分析樹編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (2525) )s-

26、屬性文法和自下而上翻譯屬性文法和自下而上翻譯 一個一般的屬性文法的翻譯器是很難建立的，然而有一一個一般的屬性文法的翻譯器是很難建立的，然而有一大類屬性文法的翻譯器是很容易建立的，那就是大類屬性文法的翻譯器是很容易建立的，那就是l-屬性文法。屬性文法。 s-屬性文法（屬性文法（l-屬性文法的特例）屬性文法的特例）s-屬性文法是屬性文法是只含有綜合屬性只含有綜合屬性的屬性文法。的屬性文法。綜合屬性可以在分析輸入符號的同時自下而上的來計算。綜合屬性可以在分析輸入符號的同時自下而上的來計算。通常借助通常借助lr分析器實現(xiàn)。分析器實現(xiàn)。保存與棧中文法符號相關(guān)的綜合屬性值。保存與棧中文法符號相關(guān)的綜合屬性

27、值。 當(dāng)歸約時，新的屬性值由正在歸約的產(chǎn)生式右邊符號當(dāng)歸約時，新的屬性值由正在歸約的產(chǎn)生式右邊符號的的屬性值來計算。屬性值來計算。編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (2626) )g：ee e t+t e tot t n t b編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (2727) )g：ee e t+t e tot t n t b編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (2828) )g：ee e t+t e tot t n t b編

28、譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (2929) )g：ee e t+t e tot t n t b編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (3030) )l-屬性文法在自上而下分析中的實現(xiàn)屬性文法在自上而下分析中的實現(xiàn) l-屬性文法屬性文法，對于每一個產(chǎn)生式，對于每一個產(chǎn)生式a x1 x2 xn，其每個，其每個語義規(guī)則中的每個屬性或者是綜合屬性，或者是語義規(guī)則中的每個屬性或者是綜合屬性，或者是xj(1j n)的一個繼承屬性且這個繼承屬性僅依賴于：的一個繼承屬性且這個繼承屬性僅依賴于：（1

29、）產(chǎn)生式）產(chǎn)生式xj在左邊符號在左邊符號x1， x2， xj-1的屬性；的屬性；（2）a的繼承屬性。的繼承屬性。可以借助可以借助ll分析器實現(xiàn)。分析器實現(xiàn)?？梢越柚梢越柚鷏r分析器實現(xiàn)。分析器實現(xiàn)。編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (3131) )l-屬性文法在自上而下分析中的實現(xiàn)屬性文法在自上而下分析中的實現(xiàn)例例5.3 將中綴表達式翻譯成相應(yīng)的后綴表達式的屬性文將中綴表達式翻譯成相應(yīng)的后綴表達式的屬性文法法 e e addop t print(addop.lexeme) t t num print(num.val)編譯原理編譯原理

30、第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (3232) ) 例例5.3 將中綴表達式翻譯成相應(yīng)的后綴表達是式的屬性文法將中綴表達式翻譯成相應(yīng)的后綴表達是式的屬性文法(lr)，其中其中addop表示表示或或。 e e addop t print(addop.lexme) t t num print(num.val) 對表達式對表達式2+3-5的分析：打印出的分析：打印出23 5 eet-printe+tprint5print5tprint232print3編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (3333) )上

31、述文法含有左遞歸，如采用上述文法含有左遞歸，如采用ll(1)分析須改寫如下：分析須改寫如下： e tr r addop t print(addop.lexme)r1 t num print(num.val) 對表達式對表達式2+3-5的分析：打印出的分析：打印出23+5-rrprint-+5-3print5tprint22print3etprint+tr編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (3434) )l-屬性文法在自下而上分析中的實現(xiàn)屬性文法在自下而上分析中的實現(xiàn) 自下而上計算繼承屬性有兩種辦法自下而上計算繼承屬性有兩種辦法（1）從翻

32、譯模式中去掉嵌入在產(chǎn)生式中間的動作；）從翻譯模式中去掉嵌入在產(chǎn)生式中間的動作；（2）用綜合屬性代替繼承屬性。）用綜合屬性代替繼承屬性。 為了使所有的嵌入的動作都出現(xiàn)在產(chǎn)生式的末尾，可為了使所有的嵌入的動作都出現(xiàn)在產(chǎn)生式的末尾，可以采用以采用方法：方法：引入一個新的非終結(jié)符引入一個新的非終結(jié)符n和產(chǎn)生式和產(chǎn)生式 n ，把嵌入在產(chǎn)生式中間的動作用非終結(jié)符把嵌入在產(chǎn)生式中間的動作用非終結(jié)符n代替，并把這個代替，并把這個動作放在產(chǎn)生式后面。動作放在產(chǎn)生式后面。編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (3535) )例如：例如：et r et rr +

33、t print(+) r1 引入引入m和和n r + t mr1r -t print(-) r1 變換變換 r - tnr1r r t num print(num.val) t num print(num.val) m print(+) n print(-)編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (3636) ) 用綜合屬性代替繼承屬性，改變基礎(chǔ)文法是用綜合屬性代替繼承屬性，改變基礎(chǔ)文法是一種可能的辦法。一種可能的辦法。 例如例如pascal標(biāo)識符說明語句的文法如下標(biāo)識符說明語句的文法如下：dl： t /l.in=t.type ，繼承自右部，

34、不符合，繼承自右部，不符合 l-屬性文法屬性文法tinteger|charl l,id|id以綜合屬性代替繼承屬性，重新構(gòu)造文法以綜合屬性代替繼承屬性，重新構(gòu)造文法did ll, id l|:tt integer|char編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (3737) )屬性文法屬性文法did l addtype(id.entery,l.type)l, id l l.type:=l.type;addtype(id.entery,l.type)l :t l.type:=t.typet integer t.type:=intt char t

35、.type:=ch編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (3838) )5.3 常見中間語言概述常見中間語言概述何謂中間代碼何謂中間代碼( intermediate code)是源程序的一種內(nèi)部表示。是源程序的一種內(nèi)部表示。復(fù)雜性介于源語言和目標(biāo)機語言之間。復(fù)雜性介于源語言和目標(biāo)機語言之間。中間代碼的作用中間代碼的作用使編譯程序的邏輯結(jié)構(gòu)更加簡單明確；使編譯程序的邏輯結(jié)構(gòu)更加簡單明確；利于進行與目標(biāo)機無關(guān)的優(yōu)化；利于進行與目標(biāo)機無關(guān)的優(yōu)化；利于在不同目標(biāo)機上實現(xiàn)同一種語言的前端編譯程利于在不同目標(biāo)機上實現(xiàn)同一種語言的前端編譯程序設(shè)計。序設(shè)計

36、。中間代碼的形式中間代碼的形式逆波蘭式逆波蘭式、四元式四元式、三元式、間接三元式、樹、三元式、間接三元式、樹編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (3939) )中間代碼的層次中間代碼的層次 中間代碼按照其與高級語言和機器語言的接近程度，中間代碼按照其與高級語言和機器語言的接近程度，分成三個層次。分成三個層次。高級高級：最接近高級語言，保留了大部分源語言的最接近高級語言，保留了大部分源語言的結(jié)構(gòu)。結(jié)構(gòu)。中級中級：介于二者之間，與源語言和機器語言都有：介于二者之間，與源語言和機器語言都有一定差異。一定差異。低級低級：最接近機器語言，能夠反映目

37、標(biāo)機的系統(tǒng)最接近機器語言，能夠反映目標(biāo)機的系統(tǒng)結(jié)構(gòu)，因而經(jīng)常依賴于目標(biāo)機。結(jié)構(gòu)，因而經(jīng)常依賴于目標(biāo)機。編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (4040) )不同層次的中間代碼舉例不同層次的中間代碼舉例源語言源語言（高級語言）（高級語言）中間代碼（高中間代碼（高級）級）中間代碼（中中間代碼（中級）級）中間代碼（低中間代碼（低級）級）float a1020;aij+2;t1 = ai, j+2t1 = j + 2t2 = i * 20t3 = t1 + t2t4 = 4 * t3t5 = addr at6 = t5 + t4t7 = *t6r1

38、 = fp - 4r2 = r1 + 2r3 = fp - 8r4 = r3 * 20r5 = r4 + r2r6 = 4 * r5 r7 = fp 216f1 = r7 + r6編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (4141) )編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (4242) ) 三三元元式式 (1) ( - c d ) (2) ( * b (1) ) (3) ( + a (2) ) (4) ( - c d ) (5) ( (4) n ) (6) ( / e (5) ) (7)

39、( + (3) (6) )編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (4343) ) 5.4 簡單算術(shù)表達式和賦值語句的翻譯簡單算術(shù)表達式和賦值語句的翻譯 (1) 對非終結(jié)符對非終結(jié)符e定義語義變量定義語義變量e.place，即用，即用e.place表示表示存放存放e值的變量名在符號表中的入口地址或臨時變量名值的變量名在符號表中的入口地址或臨時變量名的整數(shù)碼。的整數(shù)碼。 (2) 定義語義函數(shù)定義語義函數(shù)newtemp()，即每次調(diào)用，即每次調(diào)用newtemp()時時都將回送一個代表新臨時變量的整數(shù)碼；臨時變量名都將回送一個代表新臨時變量的整數(shù)碼

40、；臨時變量名按產(chǎn)生的順序可設(shè)為按產(chǎn)生的順序可設(shè)為t1、t2、。 (3) 定義語義過程定義語義過程emit(op,arg1,arg2,result), emit的功能是的功能是產(chǎn)生一個四元式并填入四元式表中。產(chǎn)生一個四元式并填入四元式表中。編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (4444) )簡單賦值語句的四元式翻譯簡單賦值語句的四元式翻譯(4) 定義語義函數(shù)定義語義函數(shù)lookup()，其功能是審查，其功能是審查是是否出現(xiàn)在符號表中，是則返回否出現(xiàn)在符號表中，是則返回在符號表的入口指在符號表的入口指針，否

41、則返回針，否則返回null。 ga : ai=e ee(1)+e(2)e(1)*e(2)e(1)(e(1) ei 使用上述語義變量、過程和函數(shù)，可寫出文法使用上述語義變量、過程和函數(shù)，可寫出文法ga中的每一個產(chǎn)生式的語義子程序。中的每一個產(chǎn)生式的語義子程序。編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (4545) ) (1) ai=e p=lookup(); if(p=null) error(); else emit(=,e.place,_,p); (2) ee(1)+e(2) e.place=newtemp(); emit(+,e(

42、1) .place, e(2).place,e.place); (3) ee(1)*e(2) e.place=newtemp(); emit(,e(1) .place, e(2).place,e.place);編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (4646) ) (4) ee(1) e.place=newtemp(); emit(uminus,e(1) .place,_,e.place); (5) e(e(1) e.place= e(1) .place ; (6) ei p=lookup(); if(p!=null) e.pl

43、ace=p; /*另一種表示為另一種表示為e.place=entry(i)*/ else error();編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (4747) ) 例例5.5 試分析賦值語句試分析賦值語句x= b*(c+d)的語法制導(dǎo)翻譯過程。的語法制導(dǎo)翻譯過程。輸入串輸入串歸約產(chǎn)歸約產(chǎn)生式生式符號棧符號棧語義棧語義棧(place)四元式四元式x=b*(c+d# #_ =b*(c+d)# (6)#i_x b*(c+d)# #i=_x_ b*(c+d)# #i=_x_ _ *(c+d)# (6)#i=i_x_ _b *(c+d)# (4)#i=

44、e_x_ _b(uminus,b, _,t1)*(c+d)# #i=e_x_t1 ai=e ee(1)+e(2)e(1)*e(2)e(1) (e(1) ei (4)ee(1) e.place=newtemp(); emit(uminus,e(1) .place,_,e.place);編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (4848) )(c+d)# #i=e*_x_t1_ c+d)# #i=e*(_x_t1_ _ +d)# (6)#i=e*(i_x_t1_ _c +d)# #i=e*(e_x_t1_ _c d)# #i=e*(e+_x_t1

45、_ _c_ )# (6)#i=e*(e+i_x_t1_ _c_d )# (2)#i=e*(e+e_x_t1_ _c_d(+,c,d,t2)# #i=e*(e_x_t1_ _t2 # (5)#i=e*(e)_x_t1_ _t2_ # (3)#i=e*e_x_t1_t2(*,t1,t2,t3)# (1)#i=e_x_t3(=,t3, _,x)# #a_x ai=e ee(1)+e(2)e(1)*e(2)e(1) (e(1) ei (2) ee(1)+e(2) e.place=newtemp(); emit(+,e(1).place, e(2) .place,e.place);(3) ee(1)*e

46、(2) e.place=newtemp(); emit(,e(1).place, e(2).place,e.place);(1)ai=e p=lookup(); if(p=null) error(); else emit(=,e.place,_,p); 編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (4949) ) 類型轉(zhuǎn)換的語義處理類型轉(zhuǎn)換的語義處理 產(chǎn)生式產(chǎn)生式 語義動作語義動作 ee1+e2 e.place:= newtemp; if(e1type=int and e2.type=int then begin emit(e.pla

47、ce“:=”e1.place“+”e2.place) e.type:=int; end; else if(e1type=real and e2.type=real then begin emit(e.place“:=”e1.place“+”e2.place) e.type:=real; end; 編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (5050) )else if(e1type=int ) then /兩個運算量類型不同兩個運算量類型不同 begin t:=newtemp; emit(t“:=”,itr,e1.place) /轉(zhuǎn)換成實型轉(zhuǎn)換

48、成實型(real) emit(e.place“:=”t“+”e2.place) e.type:=real; end;else begin t:=newtemp; emit(t“:=”,itr,e2.place) emit(e.place“:=”e1.place“+”t) e.type:=real; end; 編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (5151) )5.5 布爾表達式的翻譯布爾表達式的翻譯程序設(shè)計語言中的布爾表達式的作用程序設(shè)計語言中的布爾表達式的作用計算邏輯值；計算邏輯值；用做改變控制流語句中的條件表達式。用做改變控制流語句中

49、的條件表達式。只考慮下面文法生成的布爾表達式只考慮下面文法生成的布爾表達式ee and e|e or e|not e|id rop id|true|false約定布爾運算符的優(yōu)先順序（從高到低）為：約定布爾運算符的優(yōu)先順序（從高到低）為： not、and、or， 并且并且and和和or服從左結(jié)合。服從左結(jié)合。編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (5252) )布爾表達式的翻譯方法布爾表達式的翻譯方法計算布爾表達式的兩種辦法：計算布爾表達式的兩種辦法：（1）非簡潔）非簡潔 （2）簡潔）簡潔布爾表達式翻成四元式的描述布爾表達式翻成四元式的描述

50、 例如：例如： a or b and not c 翻譯成的四元式序列為：翻譯成的四元式序列為： (1) t1=not c (2) t2=b and t1 (3) t3=a or t2編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (5353) )布爾表達式的翻譯方法布爾表達式的翻譯方法對于像對于像ab這一類的關(guān)系表達式，可以視為等價的條件語句這一類的關(guān)系表達式，可以視為等價的條件語句 if ab then 1 else 0 , 它翻譯成的四元式序列為：它翻譯成的四元式序列為： (1) if ab goto(4) (2) t=0 (3) goto (5

51、) (4) t=1 (5) 其中：臨時變量其中：臨時變量 t 存放布爾表達式存放布爾表達式ab的值的值; (5)為后續(xù)的四元式序號。為后續(xù)的四元式序號。編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (5454) ) 具體的布爾表達式翻譯成四元式的描述如下：具體的布爾表達式翻譯成四元式的描述如下： ee1 or e2 e.place:= newtemp; emit(e.place“:=” e1.place“or”e2.place) ee1 and e2 e.place:= newtemp; emit(e.place“:=” e1.place“and”

52、e2.place) enot e1 e.place:=newtemp; emit(e.place“:=”“not” e1.place) e( e1 ) e.place:=e1.place) 編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (5555) ) eid1 rop id2 e.place:= newtemp; emit(if id1 .place “rop” id2 .place “goto” nextstart+3); emit(e.place“:=”“0”) emit( “goto” nextstart+2) emit(e.place“:

53、=”“1”) etrue e.place:=newtemp; emit(e.place“:=”“1”) efalse e.place:=newtemp; emit(e.place“:=”“0”) 其中：其中：nextstat 給出在輸出序列中下一四元式序號。給出在輸出序列中下一四元式序號。 emit 過程每被調(diào)用一次，過程每被調(diào)用一次，nextatat 增加增加1。編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (5656) ) 5.6 程序流程控制語句的翻譯程序流程控制語句的翻譯 控制語句控制語句 sif e then s1 else s2e的代碼

54、的代碼 e.true e.falsee.true: s1的代碼的代碼goto oute.false: s2的代碼的代碼 out: 編譯原理編譯原理 第第8 8章章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成 ( (5757) ) 作為條件轉(zhuǎn)移的作為條件轉(zhuǎn)移的e，僅把，僅把e翻譯成代碼是一串條件轉(zhuǎn)移和翻譯成代碼是一串條件轉(zhuǎn)移和無條件轉(zhuǎn)移的四元式?；舅悸肥菍τ跓o條件轉(zhuǎn)移的四元式?；舅悸肥菍τ趀為為a rop b的形式生的形式生成代碼為：成代碼為： if a rop b goto e.true和和 goto e.false例例8.5 ab or cf 翻譯如下：翻譯如下：這不是最優(yōu)的，因為這不是最優(yōu)的，因為(2)是不需是不需要的。由代碼優(yōu)化階段解決。要的。由代碼優(yōu)化階段解決。用用e.true和和e.false分別表示整個分別表