語義分析與中間代碼生成

1、第第6 6章章 語義分析與語義分析與中間代碼生成中間代碼生成本章在編譯程序中的地位本章在編譯程序中的地位表格管理詞法分析器語法分析器語義分析與中間代碼產(chǎn)生優(yōu)化器目標代碼生成器源程序單詞符號語法單位中間代碼中間代碼目標代碼出錯處理6.1 概述 6.2 屬性文法 6.3 幾種常見的中間語言 （*四元式）6.4 表達式及賦值語句的翻譯 6.5 控制語句的翻譯 6.6 數(shù)組元素的翻譯 6.7 過程或函數(shù)調(diào)用語句的翻譯 *6.8 說明語句的翻譯內(nèi)容安排內(nèi)容安排6.1 概概 述述 6.1.1 語義分析的概念 一個源程序經(jīng)過詞法分析、語法分析之后，表明該源程序在書寫上是正確的，并且符合程序語言所規(guī)定的語法。

2、但是語法分析并未對程序內(nèi)部的邏輯含義加以分析，因此編譯程序接下來的工作是語義分析，即審查每個語法成分的靜態(tài)語義。如果靜態(tài)語義正確，則生成與該語言成分等效的中間代碼，或者直接生成目標代碼。 l 直接生成目標代碼 直接生成機器語言或匯編語言形式的目標代碼的優(yōu)點是編譯時間短且無需中間代碼到目標代碼的翻譯。l 生成中間代碼 生成中間代碼的優(yōu)點是使編譯結(jié)構(gòu)在邏輯上更為簡單明確，特別是使目標代碼的優(yōu)化比較容易實現(xiàn)。 語義分析時語義檢查的分類：u動態(tài)語義檢查動態(tài)語義檢查 需要生成相應的目標代碼，它是在運行時進行的；需要生成相應的目標代碼，它是在運行時進行的； 例如：除零溢出錯誤。u靜態(tài)語義檢查靜態(tài)語義檢查

3、在編譯時完成的，它涉及以下幾個方面：在編譯時完成的，它涉及以下幾個方面： (1) 類型檢查 (2) 控制流檢查 (3) 一致性檢查各種條件表達式的類型不是布爾類型;運算符的分量類型不相容;賦值語句左右類型不相容;形、實參類型不相容;函數(shù)說明和函數(shù)返回類型不相容;int x;int x;float f();float f();x = f();x = f();符合變量聲明的語法、語義符合函數(shù)聲明的語法、語義符合賦值語句的語法、不符合語義(1) 類型檢查 (2) 控制流檢查 用以保證控制語句有合法的轉(zhuǎn)向點。如C語言中不允許goto語句轉(zhuǎn)入case語句流；break語句需尋找包含它的最小switch、

4、while或for語句方可找到轉(zhuǎn)向點，否則出錯。 (3) 一致性檢查 如在相同作用域中標識符只能說明一次、case語句的標號不能相同、函數(shù)調(diào)用參數(shù)個數(shù)要相同等。 常見的語義錯誤聲明和使用相關(guān)的語義錯誤標識符沒有聲明; 重復聲明;如何檢查?每當遇到新聲明的標識符,查符號表如果當前有效的所有標識符中有相同名字的如果當前有效的所有標識符中有相同名字的, ,則是則是重復聲明錯誤重復聲明錯誤; ;否則生成它的屬性信息否則生成它的屬性信息, ,保存到符號表中保存到符號表中; ;每當遇到標識符的使用,查符號表如果沒有找到如果沒有找到, ,說明該標識符沒有聲明說明該標識符沒有聲明; ; 否則否則, , 得到該

5、標識符的屬性得到該標識符的屬性, ,進行進一步分析進行進一步分析; ; 語義分析階段只產(chǎn)生中間代碼而不生成目標代碼的方法使編譯程序的開發(fā)變得較為容易，但語義分析不像詞法分析和語法分析那樣可以分別用正規(guī)文法和上下文無關(guān)文法描述。 由于語義是上下文有關(guān)的，因此語義的形式化描述是非常困難的，目前較為常見的是用屬性文法作為描述程序語言語義的工具，并采用語法制導翻譯的方法完成對語法成分的翻譯工作。 語法制導翻譯的方法就是為每個規(guī)則配上一個翻譯子程序(稱語義動作或語義子程序)，并在語法分析的同時執(zhí)行這些子程序。 語義動作是為規(guī)則賦予具體意義的手段，它一方面指出了一個規(guī)則所產(chǎn)生的符號串的意義，另一方面又按照

6、這種意義規(guī)定了生成某種中間代碼應做哪些基本動作。 在語法分析過程中，當一個規(guī)則獲得匹配(對于自上而下分析)或用于歸約(對于自下而上分析)時，此規(guī)則相應的語義子程序就進入工作，完成既定的翻譯任務。6.1.2語法制導翻譯方法 語法制導翻譯分為自下而上語法制導翻譯和自上而下語法制導翻譯，我們重點介紹自下而上語法制導翻譯。 假定有一個自下而上的LR分析器，我們可以把這個LR分析器的能力加以擴大，使它能在用某個規(guī)則進行歸約的同時調(diào)用相應的語義子程序進行有關(guān)的翻譯工作；每個規(guī)則的語義子程序執(zhí)行之后，某些結(jié)果(語義信息)必須作為此規(guī)則的左部符號的語義值暫時保存下來，以便以后語義子程序引用這些信息。 此外，原

7、LR分析器的分析棧也加以擴充，以便能夠存放與文法符號相對應的語義值。這樣，分析?？梢源娣湃愋畔ⅲ悍治鰻顟B(tài)、文法符號及文法符號對應的語義值。擴充后的分析棧如圖61所示。 skXkVkvals1X1V1vals0#狀態(tài)文法符號 語義值TOP圖圖61 擴充后的擴充后的LR分析棧分析棧 作為一個例子，我們考慮下面的文法及語義動作所執(zhí)行的程序： 規(guī)則 語義動作 (0) SE print valTOP (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

8、(4) Ei valTOP=lexval (注：lexval為i的整型 內(nèi) 部值) 我們擴充分析棧工作的總控程序功能，使其在完成語法分析的同時也能完成語義分析工作(這時的語法分析棧已成為語義分析棧)；即在用某一個規(guī)則進行歸約之后，調(diào)用相應的語義子程序完成與所用規(guī)則相應的語義動作，并將每次工作后的語義值保存在擴充后的“語義值”棧中。 圖62表示算術(shù)表達式79*5#的語法樹及各結(jié)點值，而表6.1則給出了根據(jù)分析表用LR語法制導翻譯方法得到的該表達式的語義分析和計值過程。Eval52Eval7Eval457Eval9*Eval595圖圖62 語法制導翻譯計算表達式語法制導翻譯計算表達式 79*5#的

9、語法樹的語法樹表表6.1 表達式表達式79*5#的語義分析和計值過程的語義分析和計值過程步驟狀態(tài)棧符號棧語義棧輸入串動作10#_79*5#s3203# 7_ _9*5#r4301# E_79*5#s44014# E+_7_9*5#s350143# E+9_7_ _*5#r460147# 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#acc6.2 屬屬 性性 文文 法法 6.2.1 文法的屬性 屬性是指與文法符號的類型和值等

10、有關(guān)的一些信息，在編譯中用屬性描述處理對象的特征。 隨著編譯的進展，對語法分析產(chǎn)生的語法樹進行語義分析，且分析的結(jié)果用中間代碼描述出來。對于一棵等待翻譯的語法樹，它的各個結(jié)點都是文法中的一個符號X，該X可以是終結(jié)符或非終結(jié)符。根據(jù)語義處理的需要，在用規(guī)則AX進行歸約或推導時，應能準確而恰當?shù)乇磉_文法符號X在歸約或推導時的不同特征。 例如: 判斷變量X的類型是否匹配，要用X的數(shù)據(jù)類型來描述； 判斷變量X是否存在，要用X的存儲位置來描述； 而對X的運算，則要用X的值來描述； 因此，語義分析階段引入X的屬性，如X.type、X.place、X.val等來分別描述變量X的類型、存儲位置以及值等不同的特

11、征。 文法符號屬性分：n 繼承屬性n 綜合屬性 繼承屬性 用于“自上而下”傳遞信息。繼承屬性由相應語法樹中結(jié)點的父結(jié)點屬性計算得到，即沿語法樹向下傳遞，由根結(jié)點到分枝(子)結(jié)點，它反映了對上下文依賴的特性。繼承屬性可以很方便地用來表示程序語言上下文的結(jié)構(gòu)關(guān)系。 綜合屬性 用于“自下而上”傳遞信息。綜合屬性由相應語法分析樹中結(jié)點的分枝結(jié)點(即子結(jié)點)屬性計算得到，其傳遞方向與繼承屬性相反，即沿語法分析樹向上傳遞，從分枝結(jié)點到根結(jié)點。 屬性文法 是一種適用于定義語義的特殊文法，即在語言的文法中增加了屬性的文法，它將文法符號的語義以“屬性”的形式附加到各個文法的符號上(如上述與變量X相關(guān)聯(lián)的屬性X.

12、type、X.place和X.val等)，再根據(jù)規(guī)則所包含的含義，給出每個文法符號屬性的求值規(guī)則，從而形成一種帶有語義屬性的上下文無關(guān)文法，即屬性文法。 屬性文法也是一種翻譯文法，屬性有助于更詳細地指定文法中的代碼生成動作。6.2.2 屬性文法例如，簡單算術(shù)表達式求值的屬性文法如下： 規(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.val=E.val(7)

13、Fi F.val=i.lexval 上面的一組規(guī)則中，每一個非終結(jié)符都有一個屬性val來表示整型值，如E.val表示E的整型值，而i.lexval則表示i的整型內(nèi)部值。與規(guī)則關(guān)聯(lián)的每一個語義規(guī)則的左部符號E、T、F等的屬性值的計算由其各自相應的右部符號決定，這種屬性也稱為綜合屬性。與規(guī)則SE關(guān)聯(lián)的語義規(guī)則是一個函數(shù)print(E.val)，其功能是打印E規(guī)則的值。S在語義規(guī)則中沒有出現(xiàn)，可以理解為其屬性是一個虛屬性。簡單變量類型說明的文法GD如下：GD：Dint L float L LL, id id其對應的屬性文法為： 規(guī)則 語義規(guī)則(1) DTL L.in=T.type(2) Tint T

14、.type=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)注意到與文法GD相應的說明語句形式可為int id1，id2,，idn 或者 float id1，id2,，idn 非終結(jié)符T有一個綜合屬性type，其值為int或float。語義規(guī)則L.in=T.type表示L.in的屬性值由相應說明語句指定的類型T.type決定；屬性L.in被確定后將隨語法樹的逐步生成而傳遞到下邊的有關(guān)結(jié)點使用，這種結(jié)點屬性稱為繼承屬性。由此可見，標識符

15、的類型可以通過繼承屬性的復寫規(guī)則來傳遞。 例如，對輸入串int a,b，根據(jù)上述的語義規(guī)則，可在其生成的語法樹中看到用“”表示的屬性傳遞情況，如圖63所示。 圖圖63 屬性信息傳遞情況示意屬性信息傳遞情況示意屬性翻譯文法（屬性文法）屬性翻譯文法（屬性文法） 如語法分析方法是自下而上的，在用某一規(guī)則進行規(guī)約的如語法分析方法是自下而上的，在用某一規(guī)則進行規(guī)約的同時就執(zhí)行相應的語義，在分析出一個句子時，這個句子同時就執(zhí)行相應的語義，在分析出一個句子時，這個句子的的“值值”也就同時產(chǎn)生了。也就同時產(chǎn)生了。對于文法的每個規(guī)則都配備了一組屬性的計算規(guī)則，稱為對于文法的每個規(guī)則都配備了一組屬性的計算規(guī)則，稱

16、為語義規(guī)則。語義規(guī)則。屬性與變量一樣，可以進行計算和傳遞。屬性與變量一樣，可以進行計算和傳遞。屬性加工的過程即是語義處理的過程。屬性加工的過程即是語義處理的過程。6.3 幾種常見的中間語言幾種常見的中間語言6.3.1 抽象語法樹6.3.2 逆波蘭表示法6.3.3 三地址代碼6.3.1 6.3.1 抽象語法樹抽象語法樹語法制導翻譯既可以基于語法分析樹也可以基于抽象語法語法制導翻譯既可以基于語法分析樹也可以基于抽象語法樹進行，采用的基本方法是一樣的。樹進行，采用的基本方法是一樣的。現(xiàn)在對語法樹進行改造，去掉那些對翻譯不必要的信息，現(xiàn)在對語法樹進行改造，去掉那些對翻譯不必要的信息，將語法樹進行抽象將

17、語法樹進行抽象 - - 抽象語法樹。抽象語法樹。在表達式的抽象語法樹中，運算符、關(guān)鍵字不作葉子結(jié)點在表達式的抽象語法樹中，運算符、關(guān)鍵字不作葉子結(jié)點而作為內(nèi)部結(jié)點，葉子結(jié)點只是運算量。而作為內(nèi)部結(jié)點，葉子結(jié)點只是運算量。語法制導翻譯以語法樹作基礎(chǔ)語法制導翻譯以語法樹作基礎(chǔ), , 實際上實際上, , 語法樹可以作為語法樹可以作為一種合適的中間語言形式。一種合適的中間語言形式。抽象語法樹也可以屬性化，給結(jié)點加上屬性變成帶屬性的抽象語法樹也可以屬性化，給結(jié)點加上屬性變成帶屬性的抽象語法樹。抽象語法樹。 當把語法規(guī)則中本質(zhì)部分抽象出來而將非本質(zhì)部分去掉后，便得到抽象語法規(guī)則。這種去掉不必要信息的做法可

18、以獲得高效的源程序中間表示。 如賦值語句x=ab*c的抽象語法樹如圖64(a)所示，而圖64(b)則是該賦值語句的普通語法樹。圖圖64 x=ab*c的語法樹的語法樹 抽象語法樹的一個顯著特點是結(jié)構(gòu)緊湊，容易構(gòu)造且結(jié)點數(shù)較少。 圖64(b)所示的普通語法樹的結(jié)點為14個；而圖64(a)所示的抽象語法樹的結(jié)點僅有7個，且每個內(nèi)部結(jié)點最多只有兩個分支，因此可以將每個賦值語句或表達式表示為一棵二叉樹。 對于含有多元運算的更為復雜的語法成分，相應的抽象語法樹則為一棵多叉樹，但我們總可以將其轉(zhuǎn)變?yōu)橐豢枚鏄洹橄旅嫖姆ǖ木渥訛橄旅嫖姆ǖ木渥?a-4+ca-4+c 建立抽象語法樹。建立抽象語法樹。 E E+

19、T | ET | T T (E) T id | num為每個運算量或運算符號都建立一個結(jié)點。為每個運算量或運算符號都建立一個結(jié)點。可以可以根據(jù)表達式的運算順序自下而上的構(gòu)造根據(jù)表達式的運算順序自下而上的構(gòu)造 - 手工構(gòu)造。手工構(gòu)造。a+c4抽象語法樹抽象語法樹運算符作內(nèi)運算符作內(nèi)部結(jié)點部結(jié)點id(a)E E TE + TTnum(4)id(c )語法樹語法樹抽象語法樹的實現(xiàn)抽象語法樹的實現(xiàn)抽象語法樹中的每一個抽象語法樹中的每一個結(jié)點可以由包含幾個域的記錄來實現(xiàn)；結(jié)點可以由包含幾個域的記錄來實現(xiàn)；有向邊用指針實現(xiàn)有向邊用指針實現(xiàn)。在一個在一個運算量運算量對應的結(jié)點對應的結(jié)點(葉結(jié)葉結(jié))中中,一個

20、域標識運算量，另一個一個域標識運算量，另一個域是該運算量的屬性值域是該運算量的屬性值(或指針或指針)。在一個在一個運算符運算符對應的結(jié)點中對應的結(jié)點中,一個域標識運算符，其它域包含指一個域標識運算符，其它域包含指向運算分量的結(jié)點的指針。運算符通常叫做這個結(jié)點的向運算分量的結(jié)點的指針。運算符通常叫做這個結(jié)點的標號標號。進行翻譯時，抽象語法樹中的結(jié)點可能會進行翻譯時，抽象語法樹中的結(jié)點可能會用附加域來存放結(jié)點用附加域來存放結(jié)點的屬性值的屬性值(或指向?qū)傩缘闹羔槪??；蛑赶驅(qū)傩缘闹羔槪?。numvalid .op . .To entry of id右子樹根結(jié)右子樹根結(jié)左子樹根結(jié)左子樹根結(jié) 建立表達式的抽

21、象語法樹使用的函數(shù)建立表達式的抽象語法樹使用的函數(shù), 這些函數(shù)返回新建這些函數(shù)返回新建立結(jié)點的指針。立結(jié)點的指針。1.mknode(op, left, right) 建立一個建立一個運算符結(jié)點運算符結(jié)點，標號是，標號是 op, 兩個域兩個域 left 和和 right 指向左右運算分量結(jié)點的指針。指向左右運算分量結(jié)點的指針。 2.mkleaf(id,entry) 建立一個建立一個“標識符標識符”葉子結(jié)點葉子結(jié)點, 由標號由標號 id 標識，一個域標識，一個域 entry 指向標識符在符號表中相應的項。指向標識符在符號表中相應的項。 3.mkleaf(num, val) 建立一個建立一個“數(shù)數(shù)”

22、葉子結(jié)點葉子結(jié)點，標號為，標號為 num ，域，域 val 用于存放數(shù)的值。用于存放數(shù)的值。 抽象語法樹的構(gòu)造函數(shù)抽象語法樹的構(gòu)造函數(shù) 調(diào)用上述函數(shù)建立表達式調(diào)用上述函數(shù)建立表達式 a-4+ca-4+c 的抽象語法樹。的抽象語法樹。建立順序自下而上是建立順序自下而上是: : p1, p2, p3, p4, p5p1, p2, p3, p4, p5抽象語法樹構(gòu)造抽象語法樹構(gòu)造idto entry ap1num 4p2 p3 idto entry cp4 +p5 規(guī)則 語義規(guī)則 EE1+T E.nptr:=mknode(+,E1.nptr,T.nptr) E E1-T E.nptr:=mknode

23、(-,E1.nptr,T.nptr) E T E.nptr:=T.nptr T (E) T.nptr:=E.nptr T id T.nptr:=mkleaf(id,id.entry) T num T.nptr:=mkleaf(num,num.val)建立抽象語法樹的語義規(guī)則建立抽象語法樹的語義規(guī)則屬性文法屬性文法, nptr, nptr是綜合屬性是綜合屬性n手工構(gòu)造表達式手工構(gòu)造表達式 ab*(c-d)-e/f 的抽象語法樹的抽象語法樹 ，根，根據(jù)表達式的運算順序自下而上的構(gòu)造。據(jù)表達式的運算順序自下而上的構(gòu)造。 練習練習 +adc*b/fe 逆波蘭表示法是波蘭邏輯學家盧卡西維奇(Lukasi

24、ewicz)發(fā)明的一種表示表達式的方法，這種表示法把運算量(操作數(shù))寫在前面，把運算符寫在后面，因而又稱后綴表示法。 例如，把a+b寫成ab+，把a*(b+c)寫成abc+*。6.3.2逆波蘭表示法 1表達式的逆波蘭表示 表達式E的后綴表示的遞歸定義如下： (1) 如果E是變量或常數(shù)，則E的后綴表示即E自身。 (2) 如果E為E1 op E2形式，則它的后綴表示為 E1E2op；其中op是二元運算符，而E1、E2分別又是E1和E2的后綴表示。若op為一元運算符，則視E1和E1為空。 (3) 如果E為(E1)形式，則E1的后綴表示即為E的后綴表示。 上述遞歸定義的實質(zhì)是：后綴表示中，操作數(shù)出現(xiàn)的

25、順序與原來一致，而運算符則按運算先后的順序放入相應的操作數(shù)之后(即運算符先后的順序發(fā)生了變化)。這種表示已不再需要用括號來規(guī)定運算的順序了。寫表達式的后綴式寫表達式的后綴式要點要點：1.后綴式中運算量的順序與中綴式的相同；后綴式中運算量的順序與中綴式的相同；2.算符出現(xiàn)的次序即表達式的運算次序；算符出現(xiàn)的次序即表達式的運算次序；3.不使用括號。不使用括號。例：例：a+b ab+ a*(b+c) abc+* (a+b)*(c+d) ab+cd+* -a+b*c a bc*+ a/b*c-d*e abc*/de*- (A0B0) A0=B0 用用 表示取表示取負算符負算符(uminus)練習練習寫

26、出下列各式的逆波蘭表示寫出下列各式的逆波蘭表示: (1) -a-(b*c/(c-d) + (-b)*a) (2) -A+B*C (D/E)/F (3) x := a-b/(c+d) n解：解： (1) a bc*cd-/b a*+ - (2) A BCDE/*F/+ (3) x a b c d + / - := 用用 表示取負算符表示取負算符(uminus) := 表示賦值算符表示賦值算符(assign) 后綴表示法表示表達式，其最大優(yōu)點是后綴表示法表示表達式，其最大優(yōu)點是易于計易于計算機處理算機處理表達式。常用的算法是使用一個棧，自左表達式。常用的算法是使用一個棧，自左至右掃描算術(shù)表達式（后

27、綴表示至右掃描算術(shù)表達式（后綴表示)，每掃描到運算，每掃描到運算對象，就把它推進棧；掃描到運算符，若該運算符對象，就把它推進棧；掃描到運算符，若該運算符是二目的，則對棧頂部的兩個運算對象實施該運算，是二目的，則對棧頂部的兩個運算對象實施該運算，并將運算結(jié)果代替這兩個運算對象而進棧；若是一并將運算結(jié)果代替這兩個運算對象而進棧；若是一目運算符，則對棧頂元素執(zhí)行該運算，并以運算結(jié)目運算符，則對棧頂元素執(zhí)行該運算，并以運算結(jié)果代替該元素進棧，最后的結(jié)果留在棧頂。果代替該元素進棧，最后的結(jié)果留在棧頂。 例如例如 -B+C*D的計算過程：的計算過程： -B+C*D的后綴表示為的后綴表示為B CD*+: 把

28、表達式翻譯為后綴式的把表達式翻譯為后綴式的語義規(guī)則語義規(guī)則( (屬性文法屬性文法) ) 規(guī)則規(guī)則 語義規(guī)則語義規(guī)則 EE1 op E2 E.code:=E1.code | E2 .code | op E(E1) E.code:=E1.code Eid E.code:=idn屬性屬性E.code: : 是是E E的后綴式代碼屬性的后綴式代碼屬性nop: op: 二元算符二元算符n: : 后綴式的連接運算算符后綴式的連接運算算符 1三地址代碼的形式 三地址代碼語句的一般形式為 x=y op z 其中，x、y和z為變量、結(jié)果或編譯時產(chǎn)生的臨時變量；op為運算符。 三地址代碼的每條語句通常包含三個地址

29、，兩個用來存放運算對象，一個用來存放運算結(jié)果。 6.3.3 三地址代碼 在實際實現(xiàn)中，用戶定義的變量將由指向符號表中該變量項的指針所取代。 由于三地址語句只含有一個運算符，因此多個運算符組成的表達式必須用三地址語句序列來表示， 如表達式x+y*z的三地址代碼為： t1=y*z t2= x+t1 其中，t1和t2是編譯時產(chǎn)生的臨時變量。例：賦值語句a:=(-b)*(c+d)-(c+d)的三地址碼如下所示 。t1 := minus bt2 := c+dt3 := t1*t2t4 := c+dt5 := t3-t4a := t5 2三地址代碼的具體實現(xiàn) 三地址代碼是中間代碼的一種抽象形式。在編譯程序

30、中，三地址代碼語言的具體實現(xiàn)通常有三種表示方法：四元式、三元式和間接三元式。 1) 四元式 四元式是具有四個域的記錄結(jié)構(gòu)，這四個域為 (op，arg1，arg2，result) 其中，op為運算符，arg1、arg2及result為指針，它們可指向有關(guān)變量在符號表中的登記項或一臨時變量(也可空缺)。 常用的三地址語句與相應的四元式對應如下： x=y op z 對應(op, y, z, x) x=y 對應(-, y, _, x) x=y 對應(=, y, _, x) call P 對應(call, _, _, P) goto L 對應(j, _, _, L) if x rop y goto L

31、對應(jrop, x, y, L)例如，賦值語句a=b*(c+d)相應的四元式代碼為： (+,c,d,t1) (*,b,t1,t2) (=,t2,_,a) 約定：凡只需一個運算量的算符一律使用arg1；如果op是一個算術(shù)或邏輯運算符，則result總是一個新引進的臨時變量，它用來存放運算結(jié)果。由上例也可看出，四元式出現(xiàn)的順序與表達式計值的順序是一致的，四元式之間的聯(lián)系是通過臨時變量實現(xiàn)的。四元式由于其表示更接近程序設(shè)計的習慣而成為一種普遍采用的中間代碼形式。 2) 三元式 三元式是具有三個域的記錄結(jié)構(gòu)，這三個域為 (op，arg1，arg2) 其中，op為運算符，arg1、arg2既可指向有關(guān)

32、名字在符號表中的登記項或臨時變量，也可以指向三元式表中的某一個三元式。 例如對于表達式：A+B*(C-D)+E/(C-D)N的三元式代碼為： 由上例可知，三元式出現(xiàn)的先后順序和表達式各部分的計值順序是一致的。 3) 間接三元式 在三元式代碼表的基礎(chǔ)上另設(shè)一張表，該表按運算的次序列出相應三元式在三元式表中的位置，這張表稱為間接碼表。三元式表只記錄不同的三元式語句，而間接碼表則表示由這些語句組成的運算次序。 例如對于表達式：A+B*(C-D)+E/(C-D)N的三元式與間接碼表為： 每生成一條指令，先檢查已生成的間接三元式序列，若已有，不再生成，只把序號列入間接碼表中。 在三元式表示中，每個語句的

33、位置同時有兩個作用：一是可作為該三元式的結(jié)果被其它三元式引用；二是三元式位置順序即為運算順序。在代碼優(yōu)化階段，需要調(diào)整三元式的運算順序時會遇到困難，這是因為三元式中的arg1、arg2也可以是指向某些三元式位置的指針，當這些三元式的位置順序發(fā)生變化時，含有指向這些三元式位置指針的相關(guān)三元式也需隨之改變指針值。因此，變動一張三元式表是很困難的。 對四元式來說，引用另一語句的結(jié)果可以通過引用該語句的result(通常是一個臨時變量)來實現(xiàn)，而間接三元式則通過間接碼表來描述語句的運算次序。這兩種方法都不存在語句位置同時具有兩種功能的現(xiàn)象，代碼調(diào)整時要做的改動只是局部的，因此，當需要對中間代碼表進行優(yōu)

34、化處理時，四元式與間接三元式都比三元式方便得多。寫中間語言：練習寫中間語言：練習 寫出表達式：寫出表達式：A+B*(C-D)-E/FG 的逆波蘭表示、三元式表示、四元式表示。的逆波蘭表示、三元式表示、四元式表示。n解解: 四元式表示：四元式表示：( - , C , D , T1 ) (* , B , T1, T2 ) ( + , A , T2, T3 ) ( ,F , G , T4 ) ( / , E, T4, T5 ) ( - , T3, T5, T6 )n解解: 三元式表示：三元式表示：( - , C , D )(* , B , )( + , A , ) ( ,F , G ) ( / ,

35、E, ) ( - , , )n解：逆波蘭表示：解：逆波蘭表示： ABCD -*+EFG/ -語法制導翻譯語法制導翻譯 翻譯的任務：翻譯的任務：首先是語義分析首先是語義分析和正確性檢查，若正確，則翻譯成和正確性檢查，若正確，則翻譯成中間代碼或目標代碼。中間代碼或目標代碼。語法制導翻譯法的基本思想語法制導翻譯法的基本思想 對文法中的每個規(guī)則都附加上一對文法中的每個規(guī)則都附加上一個語義動作或語義子程序，在執(zhí)行語個語義動作或語義子程序，在執(zhí)行語法分析的過程中，每當使用一條規(guī)則法分析的過程中，每當使用一條規(guī)則進行推導或歸約時，就執(zhí)行相應規(guī)則進行推導或歸約時，就執(zhí)行相應規(guī)則的語義動作，從而完成翻譯工作。的

36、語義動作，從而完成翻譯工作。什么是語法制導翻譯法什么是語法制導翻譯法 在語法分析過程中，隨著分析在語法分析過程中，隨著分析的逐步進展，根據(jù)相應文法的每一的逐步進展，根據(jù)相應文法的每一規(guī)則所對應的規(guī)則所對應的語義子程序進行翻譯語義子程序進行翻譯的方法（的方法（即隨語法分析的進展，識即隨語法分析的進展，識別出一個語法結(jié)構(gòu)，就對它的語義別出一個語法結(jié)構(gòu)，就對它的語義進行分析和翻譯進行分析和翻譯）。）。 語法制導翻譯技術(shù)分為自語法制導翻譯技術(shù)分為自底向上語法制導翻譯和自頂向底向上語法制導翻譯和自頂向下語法制導翻譯。下語法制導翻譯。自底向上語法制導翻譯自底向上語法制導翻譯 自底向上語法制導翻譯方法是在自

37、下而上自底向上語法制導翻譯方法是在自下而上的語法分析過程中逐步實現(xiàn)語義規(guī)則的方法。的語法分析過程中逐步實現(xiàn)語義規(guī)則的方法。自底向上語法制導翻譯的特點：自底向上語法制導翻譯的特點： （1）當棧頂形成句柄執(zhí)行歸約時，調(diào)用相）當棧頂形成句柄執(zhí)行歸約時，調(diào)用相應的語義動作。應的語義動作。 （2）語法分析棧和語義分析棧同步操作。）語法分析棧和語義分析棧同步操作。 以以LR語法制導翻譯為例，說明如何實現(xiàn)語語法制導翻譯為例，說明如何實現(xiàn)語法制導翻譯：法制導翻譯： 1、為文法、為文法G的每一個規(guī)則設(shè)計相應的的每一個規(guī)則設(shè)計相應的語義語義子程序。子程序。 2、構(gòu)造、構(gòu)造文法文法G的的LR分析表。分析表。 3、將

38、原、將原LR語法分析棧擴充，以便存放文法語法分析棧擴充，以便存放文法符號對應的符號對應的語義值。語義值。 4、在用某一規(guī)則進行歸約的同時，調(diào)用相、在用某一規(guī)則進行歸約的同時，調(diào)用相應的語義子程序，完成所用規(guī)則式相應的語義動應的語義子程序，完成所用規(guī)則式相應的語義動作。作。中間語言中間語言 為了使編譯程序在邏輯上更為簡單明確，特為了使編譯程序在邏輯上更為簡單明確，特別是為了使目標代碼的優(yōu)化比較容易實現(xiàn)，許多別是為了使目標代碼的優(yōu)化比較容易實現(xiàn)，許多編譯程序都采用了某種復雜性介于源程序語言和編譯程序都采用了某種復雜性介于源程序語言和機器語言之間的中間語言，并且首先把源程序翻機器語言之間的中間語言，

39、并且首先把源程序翻譯成這種中間語言程序（中間代碼）。譯成這種中間語言程序（中間代碼）。 常見的中間語言形式常見的中間語言形式u 逆波蘭式逆波蘭式u 三元式三元式u 四元式四元式 四元式是一種比較普遍采用的中間代碼形式。四元式是一種比較普遍采用的中間代碼形式。 四元式的四個成分是：算符四元式的四個成分是：算符OPOP、第一運算量、第一運算量ARG1ARG1、第二運算量第二運算量ARG2ARG2以及運算結(jié)果以及運算結(jié)果RESULTRESULT。其中，運算。其中，運算量和運算結(jié)果有時指用戶自定義的變量，有時指編譯量和運算結(jié)果有時指用戶自定義的變量，有時指編譯程序引進的臨時變量。程序引進的臨時變量。賦

40、值語句賦值語句 A：=-B*（C+D）的四元式序列：）的四元式序列：序號序號 OP ARG1 ARG2 RESULT 注釋注釋（1） B _ T1 T1 為臨時變量為臨時變量（2） + C D T2 T2 為臨時變量為臨時變量（3） * T1 T2 T3 T3 為臨時變量為臨時變量（4） ：= T3 _ A 賦值運算賦值運算 表中：表中：“ ”是為了區(qū)別是為了區(qū)別“-”而表示的求負運算符。而表示的求負運算符。 凡只需一個運算量的算符，使用凡只需一個運算量的算符，使用ARG1。6.4 表達式及賦值語句的翻譯表達式及賦值語句的翻譯 6.4.1 簡單算術(shù)表達式和賦值語句的翻譯 簡單算術(shù)表達式是一種僅

41、含簡單變量的算術(shù)表達式；簡單變量是指普通變量和常數(shù)，但不含數(shù)組元素及結(jié)構(gòu)引用等復合型數(shù)據(jù)結(jié)構(gòu)。 簡單算術(shù)表達式的計值順序與四元式出現(xiàn)的順序相同，因此很容易將其翻譯成四元式形式。 實現(xiàn)簡單算術(shù)表達式和賦值語句到四元式實現(xiàn)簡單算術(shù)表達式和賦值語句到四元式的翻譯一般采取下列步驟：的翻譯一般采取下列步驟： （1）分析文法的特點。）分析文法的特點。 （2）設(shè)置一系列語義變量，定義語義過程、）設(shè)置一系列語義變量，定義語義過程、語義函數(shù)。語義函數(shù)。 （3）修改文法，寫出每一條規(guī)則的語義子）修改文法，寫出每一條規(guī)則的語義子程序。程序。 （4）擴充）擴充LR分析棧，構(gòu)造分析棧，構(gòu)造LR分析表。分析表。 考慮以下

42、文法GA：Ai=E EE+E E*E E (E) i 為了實現(xiàn)由表達式到四元式的翻譯，需要給文法加上語義子程序，以便在進行歸約的同時執(zhí)行對應的語義子程序。 語義子程序所涉及的語義變量、語義過程及函數(shù)說明如下： (1) 對非終結(jié)符E定義語義變量E.place，即用E.place表示存放E值的變量名在符號表中的入口地址或臨時變量名的整數(shù)碼。 (2) 定義語義函數(shù)newtemp()，即每次調(diào)用newtemp()時都將回送一個代表新臨時變量的整數(shù)碼；臨時變量名按產(chǎn)生的順序可設(shè)為T1、T2、。 (3) 定義語義過程emit(op,arg1,arg2,result), emit的功能是產(chǎn)生一個四元式并填入

43、四元式表中。 (4) 定義語義函數(shù)lookup()，其功能是檢查是否出現(xiàn)在符號表中，是則返回在符號表的入口指針，否則返回NULL。 使用上述語義變量、過程和函數(shù)，可寫出文法GA中的每一個規(guī)則的語義子程序。 (1) Ai=E p=lookup(); if(p=NULL) error(); else emit(=,E.place,_,p); (2) EE(1)+E(2) E.place=newtemp(); emit(+,E(1).place,E(2).place,E.place); (3) EE(1)*E(2) E.place=newtemp();

44、 emit(*,E(1).place,E(2).place,E.place);(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.place=p; /*另一種表示為E.place=entry(i)*/ else error();p運算合法性檢查利用符號表保存的名字類型p類型自動轉(zhuǎn)換填加專用指令p臨時變量空間的統(tǒng)計了解需求、及時釋放若考慮到變量的類型檢查和轉(zhuǎn)換，則第（若考慮到變量

45、的類型檢查和轉(zhuǎn)換，則第（3）條產(chǎn)生式及其有關(guān)語）條產(chǎn)生式及其有關(guān)語義描述如下：義描述如下：Eplace =newtemp；if E（1）typeint AND E（2）typeint then begin emit(*,E(1).place,E(2).place,E.place)；Etype =int endelse if E（1）typereal AND E（2）typereal then begin emit(*,E(1).place,E(2).place,E.place)； Etype =real endelse if E（1）typeint and E（2）type=realthen

46、begin t =newtemp；emit（itr，E（1）Place，_,t）；）；emit(*,t,E(2).place,E.place) ；Etype =real endelseE(1)typereal and E(2)typeint begin t =newtemp；emit （itr，E（2）Place，_,t） ；emit(*,t,E(1).place,E.place) ；Etype =real end； 6.4.2 布爾表達式的翻譯 在程序語言中，布爾表達式一般由運算符與運算對象組成。布爾表達式的運算符為布爾運算符，即、，或為not、and和or(注：C語言中為！、&和|

47、)，其運算對象為布爾變量，也可為常量或關(guān)系表達式。 關(guān)系表達式的運算對象為算術(shù)表達式，其運算符為關(guān)系運算符、=、等。關(guān)系運算符的優(yōu)先級相同但不得結(jié)合，其運算優(yōu)先級低于任何算術(shù)運算符。布爾表達式文法： E EE|EE|E|(E)|i rop i |i計算布爾表達式值的兩種表示方法： 數(shù)值表示法 真： E.place=1； 假：E.place=0； 真假出口表示法（作為其它語句的條件改變控制流程） 真出口：E.true 假出口：E.false 仿照計算算術(shù)表達式的思想，按照布爾表達式的運算順序，一步一步計算出其真假值。 設(shè)邏輯值設(shè)邏輯值truetrue用用1 1表示，表示，falsefalse用用

48、0 0表示，布爾表達式表示，布爾表達式1 1 (0 (0 0) 0) 11的計值過程是：的計值過程是： 1 1 (0 (0 0) 0) 11= 1 = 1 (0 1(0 1) ) 11= 1 = 1 0 0 11= 1 = 1 0 0=1=1數(shù)值表示法 用數(shù)值表示布爾值的翻譯方案 EE1 or E2 Eplace=newtemp； emit（EPlace =E1place orE2place）EE1 and E2Eplace =newtemp； emit（Eplace=E1placeandE2place）Enot E1 Eplace =newtemp：； emit（Eplace=notE1pl

49、ace）E（E1） Eplace=E1placeEE or E |E and E| not E|(E)|i rop i|true|false Ei1 relop i2 Eplace=newtemp；emit（ifi1place relop i2place gotoquad+3）；emit（EPlace = 0）；emit（gotoquad+2）；emit（EPlace =1）EtrueEplace=newtemp；emit（EPlace =1）EfalseEplace=newtemp； emit（EPlace =0） 布爾表達式布爾表達式ab可用等價的條件語句可用等價的條件語句if ab th

50、en 1 else 0翻翻譯，翻譯成的四元式序列為：譯，翻譯成的四元式序列為：（1）if ab goto (4)（2）t:=0（3）goto (5)（4）t:=1（5）其中用臨時變量其中用臨時變量t t存放布爾表達式存放布爾表達式abab的值，（的值，（5 5）為后）為后續(xù)的四元式序號。續(xù)的四元式序號。 根據(jù)布爾運算的特點實施某種優(yōu)化，即不必一步一步地計算布爾表達式中所有運算對象的值，而是省略不影響運算結(jié)果的運算。 例如，在計算AB時，若計算出的A值為1，則B值就無需再計算了；因為不管B的結(jié)果是什么，AB的值都為1。同理，在計算AB時若發(fā)現(xiàn)A值為0，則B值也無需計算，AB的值一定為0。優(yōu)化求值

51、優(yōu)化求值圖圖65 E(1)E(2)和和E(1)E(2)的翻譯圖的翻譯圖(a) E(1)E(2)；(b) E(1)E(2)TE(1)E(2)FTF“真”出口“假”出口TE(1)E(2)FTF“真”出口“假”出口(a)(b) 考慮表達式E=E(1)E(2)，若E(1)為真，則立即知道E也為真，因此，E(1)的真出口也就是整個E的真出口；若E(1)為假，則E(2)必須被計值。當然，E(2)的真假出口也就是整個E的真假出口。類似的考慮適用于對E=E(1)E(2)的翻譯。 我們將E(1)E(2)和E(1)E(2)的翻譯用圖65表示，而對形如E(1)的表達式則只需調(diào)換E(1)的真假出口就可得到該表達式E的

52、真假出口。如何確定一個表達式的真假出口呢？真假出口表示法 對于ab 的四元式翻譯： if ab goto p (j，a，b，p) goto q ( j，_，_，q) 一般情況，每一個關(guān)系表達式對應一真一假兩個四元式，其格式也是固定的，即 (jrop，X，Y，0) ( j，_，_，0) /*X、Y為關(guān)系運算符兩側(cè)的變量或值*/ 每一個布爾變量a也對應一真一假兩個四元式，并且格式是固定的，即 (jnz，a，_，0) /*a為布爾變量*/ ( j，_，_，0)布爾表達式到四元式的翻譯布爾表達式到四元式的翻譯若將其作為條件表達式，例如：if ab then s1 else s2（J,a,b ,p) p

53、為s1的第一個代碼序號 (j , , , q) q為s2的第一個代碼序號例 IF ABD THEN S1 ELSE S2E的結(jié)構(gòu)從整體上，E對外只能轉(zhuǎn)向兩個目標EE轉(zhuǎn)向E為假時的目標轉(zhuǎn)向E為真時的目標(1) (1) (jnz,A,_,5)(jnz,A,_,5)(2) (j,_,_,3)(2) (j,_,_,3)(3) (3) (j,B,D,5)(j,B,D,5)(4) (4) (j,_,_,p+1)(j,_,_,p+1)(5) (5) (p)(p)(p+1)(p+1)(q)(q)S1S1(j,_,_,q)(j,_,_,q)S2S2 下一語句下一語句 IF語句的四元式結(jié)構(gòu) 解決辦法解決辦法 一般

54、地討論：凡是先有目標應用的出現(xiàn)，后有目標的定義，如何處理？設(shè)p、q、r三條四元式均要轉(zhuǎn)向t四元式p p(2)(2)回填回填 p(_,_,_,0) p(_,_,_,0) . . . . q(_,_,_,_)q(_,_,_,_)q q . . . . q(_,_,_,q(_,_,_,p p) ) . . . . r(_,_,_,_) r(_,_,_,_)r r . . . . r(_,_,_, r(_,_,_,q q) ) . . . . t(_,_,_,_) t(_,_,_,_)0為鏈尾標志(2)(2)回填回填 p(_,_,_,0)p(_,_,_,0) . . . . q(_,_,_,p) q(

55、_,_,_,p) . . . . q(_,_,_, q(_,_,_,t t) ) . . . . r(_,_,_,q) r(_,_,_,q)r r . . . . r(_,_,_, r(_,_,_,t t) ) . . . . t(_,_,_,_) t(_,_,_,_)q q p p p(_,_,_,p(_,_,_,t t) )q q p pL1( L1( ( ( L2(L2( L3(L3( . . .L4(L4( . . .L5(L5( . . . . Li( Li( . . . . Lj(Lj( . . .Ln(Ln( LiLiE.trueLnLnE.false) ) ) ) ) ) )

56、) ) )0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 L5L5L2L2L1L1LjLjL4L4L3L30 0 0 0 什么是什么是“回填回填”？（1）先產(chǎn)生暫時沒有填寫目標標號的四元式。（2）對于每一條這樣的四元式作適當?shù)挠涗?，即可用“拉鏈”的方法將這些四元式鏈接起來（同值合并）。（3）一旦目標標號（即將要轉(zhuǎn)移的目標四元式的地址）被確定下來，再將它“回填”到相應的指令（四元式的第四個區(qū)段）中。 為了處理E.true和E.false這兩項語義值，我們需要引入如下的語義變量和函數(shù)： (1) nxq：始終指向下一條將要產(chǎn)生的四元式的地址(序號)，其初值為1。每當執(zhí)行一次emit語

57、句后，nxq自動增1。 (2) merge(p1,p2)：把以p1和p2為鏈首的兩條鏈合并為一條以p2為鏈首的鏈(即返回鏈首值p2)。 (3) Backpatch(p,t)：把鏈首p所鏈接的每個四元式的第四區(qū)段(即result)都改寫為地址t。 merge()函數(shù)如下： merge(p1，p2) if(p2=0) return(p1); else p=p2; while(四元式p的第四區(qū)段內(nèi)容不為0) p=四元式p的第四區(qū)段內(nèi)容； 把p1填進四元式p的第四區(qū)段； return(p2); Backpatch()函數(shù)如下： Backpatch(p,t) Q=p; while(Q!=0) q=四元式

58、Q的第四區(qū)段內(nèi)容； 把t填進四元式Q的第四區(qū)段； Q=q; 為了便于實現(xiàn)布爾表達式的語法制導翻譯，并在掃描到“”與“”時能及時回填一些已經(jīng)確定了的待填轉(zhuǎn)移目標，我們將前述文法GE改寫為下面的文法GE，以利于編制相應的語義子程序： GE：EEAE EBE E (E) i i rop i EAE EBE 這時，文法GE的每個規(guī)則和相應的語義子程序如下：(1) Ei E.true=nxq; E.false=nxq+1; emit(jnz,entry(i),_,0); emit(j,_,_,0);(2) Ei(1) rop i(2) E.true=nxq; E.false=nxq+1; emit(jr

59、op, entry(i(1), entry(i(2),0); emit(j,_,_,0);(3) E(E(1) ) E.true = E(1).ture;E.false = E(1).false;(4) EE(1) E.true = E(1).false;E.false = E(1).ture;(5) EAE(1) Backpatch(E(1).ture,nxq); EA.false = E(1).false;(6) EEAE(2) E.true = E(2).ture; E.false=merge(EA.false，E(2).false); (7) EBE(1) Backpatch(E(1)

60、.false，nxq); EB.ture = E(1).ture; (8) EEBE(2) E.false = E(2).false; E.true = merge(EB.ture，E(2).ture);102105 107100： （j,c,5, ? ）101： （j,-,-, ? ）102： （+,x,1,t1）103： （=, t1,-,z）104： （j,-,-, ? ）105： （=,y,-,t2）107:106： （=,t2,-,z）6.5 控制語句的翻譯控制語句的翻譯 在源程序中，控制語句用于實現(xiàn)程序流程的控制。 文法： Sif E then S1 | if E then S1 else