編譯原理語(yǔ)義分析和中間代碼生成

1、編譯原理語(yǔ)義分析和中間代碼生成第1頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二4.1 概 述 4.1.1 語(yǔ)義分析的概念 一個(gè)源程序經(jīng)過(guò)詞法分析、語(yǔ)法分析之后，表明該源程序在書(shū)寫(xiě)上是正確的，并且符合程序語(yǔ)言所規(guī)定的語(yǔ)法。但是語(yǔ)法分析并未對(duì)程序內(nèi)部的邏輯含義加以分析，因此編譯程序接下來(lái)的工作是語(yǔ)義分析，即審查每個(gè)語(yǔ)法成分的靜態(tài)語(yǔ)義。如果靜態(tài)語(yǔ)義正確，則生成與該語(yǔ)言成分等效的中間代碼，或者直接生成目標(biāo)代碼。 第2頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 直接生成機(jī)器語(yǔ)言或匯編語(yǔ)言形式的目標(biāo)代碼的優(yōu)點(diǎn)是編譯時(shí)間短且無(wú)需中間代碼到目標(biāo)代碼的翻譯，而中間代碼的優(yōu)點(diǎn)是使

2、編譯結(jié)構(gòu)在邏輯上更為簡(jiǎn)單明確，特別是使目標(biāo)代碼的優(yōu)化比較容易實(shí)現(xiàn)。第3頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 如同在進(jìn)行詞法分析、語(yǔ)法分析的同時(shí)也進(jìn)行著詞法檢查、語(yǔ)法檢查一樣，在語(yǔ)義分析時(shí)也必然要進(jìn)行語(yǔ)義檢查。動(dòng)態(tài)語(yǔ)義檢查需要生成相應(yīng)的目標(biāo)代碼，它是在運(yùn)行時(shí)進(jìn)行的；靜態(tài)語(yǔ)義檢查是在編譯時(shí)完成的，它涉及以下幾個(gè)方面： (1) 類型檢查，如參與運(yùn)算的操作數(shù)其類型應(yīng)相容。 (2) 控制流檢查，用以保證控制語(yǔ)句有合法的轉(zhuǎn)向點(diǎn)。如C語(yǔ)言中不允許goto語(yǔ)句轉(zhuǎn)入case語(yǔ)句流；break語(yǔ)句需尋找包含它的最小switch、while或for語(yǔ)句方可找到轉(zhuǎn)向點(diǎn)，否則出錯(cuò)。 第4頁(yè)，共1

3、69頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 (3) 一致性檢查，如在相同作用域中標(biāo)識(shí)符只能說(shuō)明一次、case語(yǔ)句的標(biāo)號(hào)不能相同等。 語(yǔ)義分析階段只產(chǎn)生中間代碼而不生成目標(biāo)代碼的方法使編譯程序的開(kāi)發(fā)變得較為容易，但語(yǔ)義分析不像詞法分析和語(yǔ)法分析那樣可以分別用正規(guī)文法和上下文無(wú)關(guān)文法描述。由于語(yǔ)義是上下文有關(guān)的，因此語(yǔ)義的形式化描述是非常困難的，目前較為常見(jiàn)的是用屬性文法作為描述程序語(yǔ)言語(yǔ)義的工具，并采用語(yǔ)法制導(dǎo)翻譯的方法完成對(duì)語(yǔ)法成分的翻譯工作。第5頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 語(yǔ)法制導(dǎo)翻譯方法 語(yǔ)法制導(dǎo)翻譯的方法就是為每個(gè)產(chǎn)生式配上一個(gè)翻譯子程序(稱語(yǔ)

4、義動(dòng)作或語(yǔ)義子程序)，并在語(yǔ)法分析的同時(shí)執(zhí)行這些子程序。語(yǔ)義動(dòng)作是為產(chǎn)生式賦予具體意義的手段，它一方面指出了一個(gè)產(chǎn)生式所產(chǎn)生的符號(hào)串的意義，另一方面又按照這種意義規(guī)定了生成某種中間代碼應(yīng)做哪些基本動(dòng)作。在語(yǔ)法分析過(guò)程中，當(dāng)一個(gè)產(chǎn)生式獲得匹配(對(duì)于自上而下分析)或用于歸約(對(duì)于自下而上分析)時(shí)，此產(chǎn)生式相應(yīng)的語(yǔ)義子程序就進(jìn)入工作，完成既定的翻譯任務(wù)。第6頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 語(yǔ)法制導(dǎo)翻譯分為自下而上語(yǔ)法制導(dǎo)翻譯和自上而下語(yǔ)法制導(dǎo)翻譯，我們重點(diǎn)介紹自下而上語(yǔ)法制導(dǎo)翻譯。 假定有一個(gè)自下而上的LR分析器，我們可以把這個(gè)LR分析器的能力加以擴(kuò)大，使它能在用某個(gè)產(chǎn)

5、生式進(jìn)行歸約的同時(shí)調(diào)用相應(yīng)的語(yǔ)義子程序進(jìn)行有關(guān)的翻譯工作；每個(gè)產(chǎn)生式的語(yǔ)義子程序執(zhí)行之后，某些結(jié)果(語(yǔ)義信息)必須作為此產(chǎn)生式的左部符號(hào)的語(yǔ)義值暫時(shí)保存下來(lái)，以便以后語(yǔ)義子程序引用這些信息。第7頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 此外，原LR分析器的分析棧也加以擴(kuò)充，以便能夠存放與文法符號(hào)相對(duì)應(yīng)的語(yǔ)義值。這樣，分析?？梢源娣湃愋畔ⅲ悍治鰻顟B(tài)、文法符號(hào)及文法符號(hào)對(duì)應(yīng)的語(yǔ)義值。擴(kuò)充后的分析棧如圖41所示。 作為一個(gè)例子，我們考慮下面的文法及語(yǔ)義動(dòng)作所執(zhí)行的程序：第8頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二產(chǎn)生式 語(yǔ)義動(dòng)作(0) SE print va

6、lTOP(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)部值)這個(gè)文法的LR分析表見(jiàn)表3.20。第9頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 我們擴(kuò)充分析棧工作的總控程序功能，使其在完成語(yǔ)法分析的同時(shí)也能完成語(yǔ)義分析工作(這時(shí)的語(yǔ)法分析棧已成為語(yǔ)義分析棧)；即在用某一個(gè)規(guī)則進(jìn)行歸約之后，調(diào)用相應(yīng)的語(yǔ)義子程序完成與所用產(chǎn)生式相應(yīng)的語(yǔ)義動(dòng)作，并將每次工作后的語(yǔ)

7、義值保存在擴(kuò)充后的“語(yǔ)義值”棧中。圖42表示算術(shù)表達(dá)式79*5#的語(yǔ)法樹(shù)及各結(jié)點(diǎn)值，而表4.1則給出了根據(jù)表3.20用LR語(yǔ)法制導(dǎo)翻譯方法得到的該表達(dá)式的語(yǔ)義分析和計(jì)值過(guò)程。第10頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二圖41 擴(kuò)充后的LR分析棧 第11頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二圖42 語(yǔ)法制導(dǎo)翻譯計(jì)算表達(dá)式 79*5#的語(yǔ)法樹(shù)第12頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二表4.1 表達(dá)式79*5#的語(yǔ)義分析和計(jì)值過(guò)程步驟狀態(tài)棧符號(hào)棧語(yǔ)義棧輸入串主要?jiǎng)幼?0#_79*5#s3203# 7_ _9*5#r4301# E_7

8、9*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#acc第13頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二4.2 屬 性 文 法 4.2.1 文法的屬性 屬性是指與文法符號(hào)的類型和值等有關(guān)的一些信息，在編譯中用屬性描述處理對(duì)象的特征。隨著編譯的進(jìn)展，對(duì)語(yǔ)法分析產(chǎn)生的語(yǔ)法樹(shù)進(jìn)行語(yǔ)義分析，且分析的結(jié)果用中間代碼描述出

9、來(lái)。對(duì)于一棵等待翻譯的語(yǔ)法樹(shù)，它的各個(gè)結(jié)點(diǎn)都是文法中的一個(gè)符號(hào)X，該X可以是終結(jié)符或非終結(jié)符。根據(jù)語(yǔ)義處理的需要，在用產(chǎn)生式AX進(jìn)行歸約或推導(dǎo)時(shí)，應(yīng)能準(zhǔn)確而恰當(dāng)?shù)乇磉_(dá)文法符號(hào)X在歸約或推導(dǎo)時(shí)的不同特征。 第14頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 例如，判斷變量X的類型是否匹配，要用X的數(shù)據(jù)類型來(lái)描述；判斷變量X是否存在，要用X的存儲(chǔ)位置來(lái)描述；而對(duì)X的運(yùn)算，則要用X的值來(lái)描述；因此，語(yǔ)義分析階段引入X的屬性，如X.type、X.place、X.val等來(lái)分別描述變量X的類型、存儲(chǔ)位置以及值等不同的特征。 文法符號(hào)的屬性可分為繼承屬性與綜合屬性兩類。繼承屬性用于“自上而

10、下”傳遞信息。繼承屬性由相應(yīng)語(yǔ)法樹(shù)中結(jié)點(diǎn)的父結(jié)點(diǎn)屬性計(jì)算得到，即沿語(yǔ)法樹(shù)向下傳遞，由根結(jié)點(diǎn)到分枝(子)結(jié)點(diǎn)，它反映了對(duì)上下文依賴的特性。繼承屬性可以很方便地用來(lái)表示程序語(yǔ)言上下文的結(jié)構(gòu)關(guān)系。第15頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 綜合屬性用于“自下而上”傳遞信息。綜合屬性由相應(yīng)語(yǔ)法分析樹(shù)中結(jié)點(diǎn)的分枝結(jié)點(diǎn)(即子結(jié)點(diǎn))屬性計(jì)算得到，其傳遞方向與繼承屬性相反，即沿語(yǔ)法分析樹(shù)向上傳遞，從分枝結(jié)點(diǎn)到根結(jié)點(diǎn)。第16頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 4.2.2 屬性文法 屬性文法是一種適用于定義語(yǔ)義的特殊文法，即在語(yǔ)言的文法中增加了屬性的文法，它將文法

11、符號(hào)的語(yǔ)義以“屬性”的形式附加到各個(gè)文法的符號(hào)上(如上述與變量X相關(guān)聯(lián)的屬性X.type、X.place和X.val等)，再根據(jù)產(chǎn)生式所包含的含義，給出每個(gè)文法符號(hào)屬性的求值規(guī)則，從而形成一種帶有語(yǔ)義屬性的上下文無(wú)關(guān)文法，即屬性文法。屬性文法也是一種翻譯文法，屬性有助于更詳細(xì)地指定文法中的代碼生成動(dòng)作。第17頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二例如，簡(jiǎn)單算術(shù)表達(dá)式求值的屬性文法如下： 產(chǎn)生式 語(yǔ)義規(guī)則(1) SE print (E.val)(2) EE(1)+TE.val=E(1).val+T.val(3) ET E.val=T.val(4) TT(1)*FT.val=

12、T(1).val*F.val(5) TT(1)T.val=T(1).val(6) F(E)F.val=E.val(7) Fi F.val=i.lexval第18頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二上面的一組產(chǎn)生式中，每一個(gè)非終結(jié)符都有一個(gè)屬性val來(lái)表示整型值，如E.val表示E的整型值，而i.lexval則表示i的整型內(nèi)部值。與產(chǎn)生式關(guān)聯(lián)的每一個(gè)語(yǔ)義規(guī)則的左部符號(hào)E、T、F等的屬性值的計(jì)算由其各自相應(yīng)的右部符號(hào)決定，這種屬性也稱為綜合屬性。與產(chǎn)生式SE關(guān)聯(lián)的語(yǔ)義規(guī)則是一個(gè)函數(shù)print(E.val)，其功能是打印E產(chǎn)生式的值。S在語(yǔ)義規(guī)則中沒(méi)有出現(xiàn)，可以理解為其屬性是

13、一個(gè)虛屬性。我們?cè)倥e一例說(shuō)明屬性文法。一簡(jiǎn)單變量類型說(shuō)明的文法GD如下：GD：Dint Lfloat LLL, idid第19頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二其對(duì)應(yīng)的屬性文法為： 產(chǎn)生式語(yǔ)義規(guī)則(1) DTLL.in=T.type(2) TintT.type=int(3) TfloatT.type=float(4) LL(1)，idL(1).in=L.in; addtype(id.entry,L.in)(5) Lidaddtype(id.entry,L.in)注意到與文法GD相應(yīng)的說(shuō)明語(yǔ)句形式可為int id1，id2,，idn 或者 float id1，id2,，

14、idn第20頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 非終結(jié)符T有一個(gè)綜合屬性type，其值為int或float。語(yǔ)義規(guī)則L.in=T.type表示L.in的屬性值由相應(yīng)說(shuō)明語(yǔ)句指定的類型T.type決定；屬性L.in被確定后將隨語(yǔ)法樹(shù)的逐步生成而傳遞到下邊的有關(guān)結(jié)點(diǎn)使用，這種結(jié)點(diǎn)屬性稱為繼承屬性。由此可見(jiàn)，標(biāo)識(shí)符的類型可以通過(guò)繼承屬性的復(fù)寫(xiě)規(guī)則來(lái)傳遞。例如，對(duì)輸入串int a,b，根據(jù)上述的語(yǔ)義規(guī)則，可在其生成的語(yǔ)法樹(shù)中看到用“”表示的屬性傳遞情況，如圖43所示。 第21頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二圖43 屬性信息傳遞情況示意第22頁(yè)，共1

15、69頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二4.3 幾種常見(jiàn)的中間語(yǔ)言 4.3.1 抽象語(yǔ)法樹(shù) 抽象語(yǔ)法樹(shù)也稱圖表示，是一種較為流行的中間語(yǔ)言表示形式。在抽象語(yǔ)法樹(shù)表示中，每一個(gè)葉結(jié)點(diǎn)都表示諸如常量或變量這樣的運(yùn)算對(duì)象，而其它內(nèi)部結(jié)點(diǎn)則表示運(yùn)算符。抽象語(yǔ)法樹(shù)不同于前述的語(yǔ)法樹(shù)，它展示了一個(gè)操作過(guò)程并同時(shí)描述了源程序的層次結(jié)構(gòu)。第23頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 注意，語(yǔ)法規(guī)則中包含的某些符號(hào)可能起標(biāo)點(diǎn)符號(hào)作用也可能起解釋作用。如賦值語(yǔ)句語(yǔ)法規(guī)則： SV=e 其中的賦值號(hào)“=”僅起標(biāo)點(diǎn)符號(hào)作用，其目的是把V與e分開(kāi)；而條件語(yǔ)句語(yǔ)法規(guī)則：Sif(e)S1;

16、else S2第24頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 其中的保留字符號(hào)if和else起注釋作用，說(shuō)明當(dāng)布爾表達(dá)式e為真時(shí)執(zhí)行S1，否則執(zhí)行S2；而“；”僅起標(biāo)點(diǎn)符號(hào)作用?？梢钥闯觯鲜稣Z(yǔ)句的本質(zhì)部分是V、e和Si。當(dāng)把語(yǔ)法規(guī)則中本質(zhì)部分抽象出來(lái)而將非本質(zhì)部分去掉后，便得到抽象語(yǔ)法規(guī)則。這種去掉不必要信息的做法可以獲得高效的源程序中間表示。上述語(yǔ)句的抽象語(yǔ)法規(guī)則為：第25頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 (1) 賦值語(yǔ)句：左部 表達(dá)式 (2) 條件語(yǔ)句：表達(dá)式 語(yǔ)句1 語(yǔ)句2 與抽象語(yǔ)法相對(duì)應(yīng)的語(yǔ)法樹(shù)稱為抽象語(yǔ)法樹(shù)或抽象樹(shù)，如賦值語(yǔ)句x=a

17、b*c的抽象語(yǔ)法樹(shù)如圖44(a)所示，而圖44(b)則是該賦值語(yǔ)句的普通語(yǔ)法樹(shù)。第26頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二圖44 x=ab*c的語(yǔ)法樹(shù) 第27頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 抽象語(yǔ)法樹(shù)的一個(gè)顯著特點(diǎn)是結(jié)構(gòu)緊湊，容易構(gòu)造且結(jié)點(diǎn)數(shù)較少。圖44(b)所示的普通語(yǔ)法樹(shù)的結(jié)點(diǎn)為14個(gè)；而圖44(a)所示的抽象語(yǔ)法樹(shù)的結(jié)點(diǎn)僅有7個(gè)，且每個(gè)內(nèi)部結(jié)點(diǎn)最多只有兩個(gè)分支，因此可以將每個(gè)賦值語(yǔ)句或表達(dá)式表示為一棵二叉樹(shù)。對(duì)于含有多元運(yùn)算的更為復(fù)雜的語(yǔ)法成分，相應(yīng)的抽象語(yǔ)法樹(shù)則為一棵多叉樹(shù)，但我們總可以將其轉(zhuǎn)變?yōu)橐豢枚鏄?shù)。第28頁(yè)，共169頁(yè)，2

18、022年，5月20日，20點(diǎn)33分，星期二 逆波蘭表示法 逆波蘭表示法是波蘭邏輯學(xué)家盧卡西維奇(Lukasiewicz)發(fā)明的一種表示表達(dá)式的方法，這種表示法把運(yùn)算量(操作數(shù))寫(xiě)在前面，把運(yùn)算符寫(xiě)在后面，因而又稱后綴表示法。例如，把a(bǔ)+b寫(xiě)成ab+，把a(bǔ)*(b+c)寫(xiě)成abc+*。第29頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 1表達(dá)式的逆波蘭表示 表達(dá)式E的后綴表示的遞歸定義如下： (1) 如果E是變量或常數(shù)，則E的后綴表示即E自身。 (2) 如果E為E1 op E2形式，則它的后綴表示為E1E2op；其中op是二元運(yùn)算符，而E1、E2分別又是E1和E2的后綴表示。若op

19、為一元運(yùn)算符，則視E1和E1為空。 (3) 如果E為(E1)形式，則E1的后綴表示即為E的后綴表示。第30頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二上述遞歸定義的實(shí)質(zhì)是：后綴表示中，操作數(shù)出現(xiàn)的順序與原來(lái)一致，而運(yùn)算符則按運(yùn)算先后的順序放入相應(yīng)的操作數(shù)之后(即運(yùn)算符先后的順序發(fā)生了變化)。這種表示已不再需要用括號(hào)來(lái)規(guī)定運(yùn)算的順序了。后綴表示中的計(jì)值用棧實(shí)現(xiàn)非常方便。一般的計(jì)值過(guò)程是自左至右掃描后綴表達(dá)式，每碰到運(yùn)算量就把它推進(jìn)棧，每碰到K目運(yùn)算符就把它作用于棧頂?shù)腒個(gè)運(yùn)算量，并用運(yùn)算的結(jié)果(即一個(gè)運(yùn)算量)來(lái)取代棧頂?shù)腒個(gè)運(yùn)算量。第31頁(yè)，共169頁(yè)，2022年，5月20日，2

20、0點(diǎn)33分，星期二 2程序語(yǔ)句的逆波蘭表示 為了用逆波蘭式表示一些控制語(yǔ)句，我們定義轉(zhuǎn)移操作如下： (1) BL：轉(zhuǎn)向某標(biāo)號(hào)； (2) BT：條件為真時(shí)轉(zhuǎn)移； (3) BF：條件為假時(shí)轉(zhuǎn)移； (4) BR：無(wú)條件轉(zhuǎn)移。第32頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 部分程序語(yǔ)句的逆波蘭表示如下： (1) 賦值語(yǔ)句。賦值語(yǔ)句“=”的逆波蘭表示為 = 例如，賦值語(yǔ)句“x=a+b*c”可按逆波蘭式寫(xiě)為“xabc*+=”。 (2) GOTO語(yǔ)句。轉(zhuǎn)向語(yǔ)句“GOTO”的逆波蘭表示為BL 其中，“BL”為單目后綴運(yùn)算符，“”則為BL的一個(gè)運(yùn)算分量。第33頁(yè)，共169頁(yè)，2022年，5月

21、20日，20點(diǎn)33分，星期二 (3) 條件語(yǔ)句。BR表示無(wú)條件轉(zhuǎn)移單目后綴運(yùn)算符。例如，“BR”表示無(wú)條件轉(zhuǎn)移到“”處，這里的順序號(hào)是BR的一個(gè)特殊運(yùn)算分量，用來(lái)表示逆波蘭式中單詞符號(hào)的順序號(hào)(即第幾個(gè)單詞)，它不同于GOTO語(yǔ)句中的語(yǔ)句標(biāo)號(hào)。BT和BF表示按條件轉(zhuǎn)移的兩個(gè)雙目后綴運(yùn)算符。例如：BTBF第34頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 分別表示當(dāng)e為真或假時(shí)轉(zhuǎn)移到順序號(hào)處；其中，布爾表達(dá)式e的逆波蘭式和順序號(hào)是兩個(gè)特殊的運(yùn)算分量。若使用BT和BF兩個(gè)運(yùn)算符，則條件語(yǔ)句if(e)S1;else S2的逆波蘭式為： BF /*e為假則轉(zhuǎn)S2的第一個(gè)單詞的順序號(hào)*/

22、 /*e為真則執(zhí)行S1*/BR /*S1執(zhí)行結(jié)束后無(wú)條件轉(zhuǎn)出該條件語(yǔ)句*/ 第35頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 (3) 條件語(yǔ)句。BR表示無(wú)條件轉(zhuǎn)移單目后綴運(yùn)算符。例如，“BR”表示無(wú)條件轉(zhuǎn)移到“”處，這里的順序號(hào)是BR的一個(gè)特殊運(yùn)算分量，用來(lái)表示逆波蘭式中單詞符號(hào)的順序號(hào)(即第幾個(gè)單詞)，它不同于GOTO語(yǔ)句中的語(yǔ)句標(biāo)號(hào)。BT和BF表示按條件轉(zhuǎn)移的兩個(gè)雙目后綴運(yùn)算符。例如：BTBF第36頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二例如，條件語(yǔ)句if(mn) k=i+1；else k=i1的逆波蘭式表示為(1)(18)為單詞編號(hào))：(1) mn(

23、4) 13BF(6) ki1+=(11) 18BR(13) ki1=(18) if語(yǔ)句的后繼語(yǔ)句此逆波蘭式也可寫(xiě)在一行上，即mn13BFki1+=18BRki1 =第37頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 (4) 循環(huán)語(yǔ)句。for循環(huán)語(yǔ)句為：for(i=m；i=n；i+)S；其中，i為循環(huán)控制變量，m為初值，n為終值，S為循環(huán)體。循環(huán)語(yǔ)句不能直接用逆波蘭表示，因而將其展開(kāi)為等價(jià)的條件語(yǔ)句后再用逆波蘭表示，即i=m；10：if(i=n) S；i=i+1；goto l0第38頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 4.3.3 三地址代碼 1三地址代碼

24、的形式 三地址代碼語(yǔ)句的一般形式為 x=y op z 其中，x、y和z為名字、常量或編譯時(shí)產(chǎn)生的臨時(shí)變量；op為運(yùn)算符，如定點(diǎn)運(yùn)算符、浮點(diǎn)算符和邏輯運(yùn)算符等。三地址代碼的每條語(yǔ)句通常包含三個(gè)地址，兩個(gè)用來(lái)存放運(yùn)算對(duì)象， 第39頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 一個(gè)用來(lái)存放運(yùn)算結(jié)果。在實(shí)際實(shí)現(xiàn)中，用戶定義的名字將由指向符號(hào)表中該名字項(xiàng)的指針?biāo)〈Ｓ捎谌刂氛Z(yǔ)句只含有一個(gè)運(yùn)算符，因此多個(gè)運(yùn)算符組成的表達(dá)式必須用三地址語(yǔ)句序列來(lái)表示，如表達(dá)式x+y*z的三地址代碼為：t1=y*zt2= x+t1第40頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 其中，t

25、1和t2是編譯時(shí)產(chǎn)生的臨時(shí)變量。三地址代碼是語(yǔ)法樹(shù)的一種線性表示，如圖44(a)所示的語(yǔ)法樹(shù)用三地址代碼表示為：t1=b*ct2= a t1x=t2第41頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二2三地址語(yǔ)句的種類 作為中間語(yǔ)言的三地址語(yǔ)句非常類似于匯編代碼，它可以有符號(hào)標(biāo)號(hào)和各種控制流語(yǔ)句。常用的三地址語(yǔ)句有以下幾種：(1) x=y op z形式的賦值語(yǔ)句，其中op為二目的算術(shù)運(yùn)算符或邏輯運(yùn)算符。(2) x=op y形式的賦值語(yǔ)句，其中op為一目運(yùn)算符，如一目減uminus、邏輯否定not、移位運(yùn)算符以及將定點(diǎn)數(shù)轉(zhuǎn)換成浮點(diǎn)數(shù)的類型轉(zhuǎn)換符。第42頁(yè)，共169頁(yè)，2022年，5

26、月20日，20點(diǎn)33分，星期二(3) x=y形式的賦值語(yǔ)句，將y的值賦給。(4) 無(wú)條件轉(zhuǎn)移語(yǔ)句goto L，即下一個(gè)將被執(zhí)行的語(yǔ)句是標(biāo)號(hào)為L(zhǎng)的語(yǔ)句。(5) 條件轉(zhuǎn)移語(yǔ)句if x rop y goto L，其中rop為關(guān)系運(yùn)算符，如、=等。若x和y滿足關(guān)系rop就轉(zhuǎn)去執(zhí)行標(biāo)號(hào)為L(zhǎng)的語(yǔ)句，否則繼續(xù)按順序執(zhí)行本語(yǔ)句的下一條語(yǔ)句。第43頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二(6) 過(guò)程調(diào)用語(yǔ)句par X和call P,n。源程序中的過(guò)程調(diào)用語(yǔ)句P(X1、X2、，Xn)可用下列三地址代碼表示：par X1par X2par Xncall P,n 其中，整數(shù)n為實(shí)參個(gè)數(shù)。過(guò)程返回語(yǔ)

27、句為return y，其中y為過(guò)程返回值。第44頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 (7) 變址賦值語(yǔ)句x=yi，其中x、y、i均代表數(shù)據(jù)對(duì)象，表示把從地址y開(kāi)始的第i個(gè)地址單元中的值賦給x。xi=y則表示把y的值賦給從地址x開(kāi)始的第i個(gè)地址單元。 (8) 地址和指針賦值語(yǔ)句 x=&y表示將y的地址賦給x，y可以是一個(gè)名字或一個(gè)臨時(shí)變量，而x是指針名或臨時(shí)變量； x=*y表示將y所指示的地址單元中的內(nèi)容(值)賦給x，y是一個(gè)指針或臨時(shí)變量； *x=y表示指將x所指對(duì)象的值置為y的值。第45頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 3三地址代碼的具體

28、實(shí)現(xiàn) 三地址代碼是中間代碼的一種抽象形式。在編譯程序中，三地址代碼語(yǔ)言的具體實(shí)現(xiàn)通常有三種表示方法：四元式、三元式和間接三元式。 1) 四元式 四元式是具有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域?yàn)?op，arg1，arg2，result)第46頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 其中，op為運(yùn)算符；arg1、arg2及result為指針，它們可指向有關(guān)名字在符號(hào)表中的登記項(xiàng)或一臨時(shí)變量(也可空缺)。常用的三地址語(yǔ)句與相應(yīng)的四元式對(duì)應(yīng)如下：x=y op z 對(duì)應(yīng)(op, y, z, x)x=y 對(duì)應(yīng)(uminus, y, _, x)x=y 對(duì)應(yīng)(=, y, _, x)par x1

29、對(duì)應(yīng)(par, x1, _, _)call P 對(duì)應(yīng)(call, _, _, P)goto L 對(duì)應(yīng)(j, _, _, L)if x rop y goto L 對(duì)應(yīng)(jrop, x, y, L)第47頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二例如，賦值語(yǔ)句a=b*(c+d)相應(yīng)的四元式代碼為： (+,c,d,t1) (*,b,t1,t2) (=,t2,_,a) 我們約定：凡只需一個(gè)運(yùn)算量的算符一律使用arg1。此外，注意這樣一個(gè)規(guī)則：如果op是一個(gè)算術(shù)或邏輯運(yùn)算符，則result總是一個(gè)新引進(jìn)的臨時(shí)變量，它用來(lái)存放運(yùn)算結(jié)果。由上例也可看出，四元式出現(xiàn)的順序與表達(dá)式計(jì)值的順序是

30、一致的，四元式之間的聯(lián)系是通過(guò)臨時(shí)變量實(shí)現(xiàn)的。四元式由于其表示更接近程序設(shè)計(jì)的習(xí)慣而成為一種普遍采用的中間代碼形式。第48頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 2) 三元式 三元式是具有三個(gè)域的記錄結(jié)構(gòu)，這三個(gè)域?yàn)?op，arg1，arg2) 其中，op為運(yùn)算符；arg1、arg2既可指向有關(guān)名字在符號(hào)表中的登記項(xiàng)或臨時(shí)變量，也可以指向三元式表中的某一個(gè)三元式。例如，相應(yīng)于賦值語(yǔ)句a=(b+c)*(b+c)的三元式代碼為：第49頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 (+,b,c) (+,b,c) (*,) (=,a,) 上述三元式表示的結(jié)果與的結(jié)

31、果相乘。由上例可知，三元式出現(xiàn)的先后順序和表達(dá)式各部分的計(jì)值順序是一致的。第50頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 3) 間接三元式 在三元式代碼表的基礎(chǔ)上另設(shè)一張表，該表按運(yùn)算的次序列出相應(yīng)三元式在三元式表中的位置，這張表稱為間接碼表。三元式表只記錄不同的三元式語(yǔ)句，而間接碼表則表示由這些語(yǔ)句組成的運(yùn)算次序。例如，賦值語(yǔ)句a=(b+c)*(b+c)對(duì)應(yīng)的三元式表與間接碼表為：三元式表： (+,b,c) (*,) (=,a,)間接碼表： 第51頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 在三元式表示中，每個(gè)語(yǔ)句的位置同時(shí)有兩個(gè)作用：一是可作為該三元式

32、的結(jié)果被其它三元式引用；二是三元式位置順序即為運(yùn)算順序。在代碼優(yōu)化階段，需要調(diào)整三元式的運(yùn)算順序時(shí)會(huì)遇到困難，這是因?yàn)槿街械腶rg1、arg2也可以是指向某些三元式位置的指針，當(dāng)這些三元式的位置順序發(fā)生變化時(shí)，含有指向這些三元式位置指針的相關(guān)三元式也需隨之改變指針值。因此，變動(dòng)一張三元式表是很困難的。第52頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 對(duì)四元式來(lái)說(shuō)，引用另一語(yǔ)句的結(jié)果可以通過(guò)引用該語(yǔ)句的result(通常是一個(gè)臨時(shí)變量)來(lái)實(shí)現(xiàn)，而間接三元式則通過(guò)間接碼表來(lái)描述語(yǔ)句的運(yùn)算次序。這兩種方法都不存在語(yǔ)句位置同時(shí)具有兩種功能的現(xiàn)象，代碼調(diào)整時(shí)要做的改動(dòng)只是局部的，因

33、此，當(dāng)需要對(duì)中間代碼表進(jìn)行優(yōu)化處理時(shí)，四元式與間接三元式都比三元式方便得多。第53頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二4.4 表達(dá)式及賦值語(yǔ)句的翻譯 4.4.1 簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯 簡(jiǎn)單算術(shù)表達(dá)式是一種僅含簡(jiǎn)單變量的算術(shù)表達(dá)式；簡(jiǎn)單變量是指普通變量和常數(shù)，但不含數(shù)組元素及結(jié)構(gòu)引用等復(fù)合型數(shù)據(jù)結(jié)構(gòu)。簡(jiǎn)單算術(shù)表達(dá)式的計(jì)值順序與四元式出現(xiàn)的順序相同，因此很容易將其翻譯成四元式形式，這些翻譯方法稍加修改也可用于產(chǎn)生三元式或間接三元式。第54頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二考慮以下文法GA：Ai=EEE+EE*EE(E)i 在此，非終結(jié)符A

34、代表“賦值句”。文法GA雖然是一個(gè)二義文法，但通過(guò)確定運(yùn)算符的結(jié)合性及規(guī)定運(yùn)算符的優(yōu)先級(jí)就可避免二義性的發(fā)生。 為了實(shí)現(xiàn)由表達(dá)式到四元式的翻譯，需要給文法加上語(yǔ)義子程序，以便在進(jìn)行歸約的同時(shí)執(zhí)行對(duì)應(yīng)的語(yǔ)義子程序。語(yǔ)義子程序所涉及的語(yǔ)義變量、語(yǔ)義過(guò)程及函數(shù)說(shuō)明如下：第55頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二(1) 對(duì)非終結(jié)符E定義語(yǔ)義變量E.place，即用E.place表示存放E值的變量名在符號(hào)表中的入口地址或臨時(shí)變量名的整數(shù)碼。(2) 定義語(yǔ)義函數(shù)newtemp()，即每次調(diào)用newtemp()時(shí)都將回送一個(gè)代表新臨時(shí)變量的整數(shù)碼；臨時(shí)變量名按產(chǎn)生的順序可設(shè)為T1、T

35、2、。(3) 定義語(yǔ)義過(guò)程emit(op,arg1,arg2,result), emit的功能是產(chǎn)生一個(gè)四元式并填入四元式表中。第56頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 (4) 定義語(yǔ)義函數(shù)lookup()，其功能是審查是否出現(xiàn)在符號(hào)表中，是則返回在符號(hào)表的入口指針，否則返回NULL。使用上述語(yǔ)義變量、過(guò)程和函數(shù)，可寫(xiě)出文法GA中的每一個(gè)產(chǎn)生式的語(yǔ)義子程序。 (1) Ai=E p=lookup();if(p=NULL) error();else emit(=,E.place,_,P); (2) EE(1)+E(2) E.

36、place=newtemp();emit(+,E(1) .place, E(2).place,E.place);第57頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二(3) EE(1)*E(2) E.place=newtemp();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.plac

37、e=p; /*另一種表示為E.place=entry(i)*/else error();第58頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 例4.1 試分析賦值語(yǔ)句X= B*(C+D)的語(yǔ)法制導(dǎo)翻譯過(guò)程。 解答 賦值語(yǔ)句X=B*(C+D)的語(yǔ)法制導(dǎo)翻譯過(guò)程如表4.2所示(加工分析過(guò)程參考表4.1)。第59頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二表4.2 賦值語(yǔ)句X=B*(C+D)的翻譯過(guò)程輸入串歸約產(chǎn)生式符號(hào)棧語(yǔ)義棧(place)四元式X=B*(C+D)# # _=B*(C+D)# (6)#i_XB*(C+D)# #i=_X_B*(C+D)# #i=_X_

38、_*(C+D)# (6)#i=i_X_ _B*(C+D)# (4)#i=E_X_ _B(uminus,B, _,T1)*(C+D)# #i=E_X_T1第60頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二(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_ _CD)# #i=E*(E+_X_T1_ _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)

39、#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第61頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 4.4.2 布爾表達(dá)式的翻譯 在程序語(yǔ)言中，布爾表達(dá)式一般由運(yùn)算符與運(yùn)算對(duì)象組成。布爾表達(dá)式的運(yùn)算符為布爾運(yùn)算符，即、，或?yàn)閚ot、and和or(注：C語(yǔ)言中為！、&和|)，其運(yùn)算對(duì)象為布爾變量，也可為常量或關(guān)系表達(dá)式。關(guān)系表達(dá)式的運(yùn)算對(duì)象為算術(shù)表達(dá)式，其運(yùn)算符為關(guān)系運(yùn)算符、=、等。關(guān)系運(yùn)算符的優(yōu)先級(jí)相同但不得結(jié)合，其運(yùn)算優(yōu)先級(jí)低于任何算術(shù)運(yùn)算符。布爾運(yùn)算符的運(yùn)算順序

40、一般為、，且和服從左結(jié)合， 第62頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 布爾算符的運(yùn)算優(yōu)先級(jí)低于任何關(guān)系運(yùn)算符(注意，此處的運(yùn)算優(yōu)先級(jí)約定不同于C語(yǔ)言)。此外，對(duì)布爾運(yùn)算、關(guān)系運(yùn)算、算術(shù)運(yùn)算的運(yùn)算對(duì)象的類型可不區(qū)分布爾型或算術(shù)型，假定不同類型的變換工作將在需要時(shí)強(qiáng)制執(zhí)行。為簡(jiǎn)單起見(jiàn)，我們遵循以上運(yùn)算約定討論下述文法GE生成的布爾表達(dá)式： GE：EEEEEE(E)ii rop i 第63頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 另一種方法是根據(jù)布爾運(yùn)算的特點(diǎn)實(shí)施某種優(yōu)化，即不必一步一步地計(jì)算布爾表達(dá)式中所有運(yùn)算對(duì)象的值，而是省略不影響運(yùn)算結(jié)果的運(yùn)算。例

41、如，在計(jì)算AB時(shí)，若計(jì)算出的A值為1，則B值就無(wú)需再計(jì)算了；因?yàn)椴还蹷的結(jié)果是什么，AB的值都為1。同理，在計(jì)算AB時(shí)若發(fā)現(xiàn)A值為0，則B值也無(wú)需計(jì)算，AB的值一定為0。第64頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 在后面的論述中，我們假定函數(shù)過(guò)程的工作不出現(xiàn)上述的副作用情況。 如何確定一個(gè)表達(dá)式的真假出口呢？考慮表達(dá)式E(1)E(2)，若E(1)為真，則立即知道E也為真，因此，E(1)的真出口也就是整個(gè)E的真出口；若E(1)為假，則E(2)必須被計(jì)值，此時(shí)E(2)的第一個(gè)四元式就是E(1)的假出口。當(dāng)然，E(2)的真假出口也就是整個(gè)E的真假出口。類似的考慮適用于對(duì)E(1

42、)E(2)的翻譯。我們將E(1)E(2)和E(1)E(2)的翻譯用圖45表示，而對(duì)形如E(1)的表達(dá)式則只需調(diào)換E(1)的真假出口就可得到該表達(dá)式E的真假出口。第65頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二圖45 E(1)E(2)和E(1)E(2)的翻譯圖(a) E(1)E(2)；(b) E(1)E(2)第66頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 在自下而上的分析過(guò)程中，一個(gè)布爾式的真假出口往往不能在產(chǎn)生四元式的同時(shí)就填上，我們只好把這種未完成的四元式的地址(編號(hào))作為E的語(yǔ)義值暫存起來(lái)，待到整個(gè)表達(dá)式的四元式產(chǎn)生完畢之后，再來(lái)填寫(xiě)這個(gè)未填入的轉(zhuǎn)移目

43、標(biāo)。第67頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 對(duì)于每個(gè)非終結(jié)符E，我們需要為它賦予兩個(gè)語(yǔ)義值E.tc和E.fc，以分別記錄E所對(duì)應(yīng)的四元式需要回填“真”、“假”出口的四元式地址所構(gòu)成的鏈。這是因?yàn)樵诜g過(guò)程中，常常會(huì)出現(xiàn)若干轉(zhuǎn)移四元式轉(zhuǎn)向同一個(gè)目標(biāo)但目標(biāo)位置又未確定的情況，此時(shí)可用“拉鏈”的方法將這些四元式鏈接起來(lái)，待獲得轉(zhuǎn)移目標(biāo)的四元式地址時(shí)再進(jìn)行返填。例如，假定E的四元式需要回填“真”出口的有p、q、r這三個(gè)四元式，則它們可鏈接成如圖46所示的一條真值鏈(記作tc)。 第68頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二圖46 拉鏈法鏈接四元式示意第

44、69頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 為了處理E.tc和E.fc這兩項(xiàng)語(yǔ)義值，我們需要引入如下的語(yǔ)義變量和函數(shù)： (1) nxq：始終指向下一條將要產(chǎn)生的四元式的地址(序號(hào))，其初值為1。每當(dāng)執(zhí)行一次emit語(yǔ)句后，nxq自動(dòng)增1。 (2) merge(p1,p2)：把以p1和p2為鏈?zhǔn)椎膬蓷l鏈合并為一條以p2為鏈?zhǔn)椎逆?即返回鏈?zhǔn)字祊2)。 (3) Backpatch(p,t)：把鏈?zhǔn)譸所鏈接的每個(gè)四元式的第四區(qū)段(即result)都改寫(xiě)為地址t。第70頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 merge()函數(shù)如下：merge(p1，p2)

45、if(p2=0) return(p1); else p=p2; while(四元式p的第四區(qū)段內(nèi)容不為0)第71頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 p=四元式p的第四區(qū)段內(nèi)容； 把p1填進(jìn)四元式p的第四區(qū)段； return(p2); Backpatch()函數(shù)如下：Backpatch(p,t) Q=p; while(Q!=0)第72頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 q=四元式Q的第四區(qū)段內(nèi)容； 把t填進(jìn)四元式Q的第四區(qū)段； Q=q; 第73頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 為了便于實(shí)現(xiàn)布爾表達(dá)式的語(yǔ)法制導(dǎo)翻譯，并

46、在掃描到“”與“”時(shí)能及時(shí)回填一些已經(jīng)確定了的待填轉(zhuǎn)移目標(biāo)，我們將前述文法GE改寫(xiě)為下面的文法GE，以利于編制相應(yīng)的語(yǔ)義子程序： GE：EEAEEBEE(E)ii rop iEAEEBE第74頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二這時(shí)，文法GE的每個(gè)產(chǎn)生式和相應(yīng)的語(yǔ)義子程序如下：(1) Ei E.tc=nxq; E.fc=nxq+1;emit(jnz,entry(i),_,0);emit(j,_,_,0);(2) Ei(1) rop i(2) E.tc=nxq; E.fc=nxq+1; emit(jrop, entry(i(1), entry(i(2),0); emit(

47、j,_,_,0);(3) E(E(1) ) E.tc = E(1).tc;E.fc = E(1).fc;(4) EE(1) E.tc = E(1).fc;E.fc = E(1).tc;第75頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二(5) EAE(1) Backpatch(E(1).tc,nxq);EA.fc = E(1).fc;(6) EEAE(2) E.tc = E(2).tc;E.fc =merge( EA.fc，E(2).fc); (7) EBE(1) Backpatch(E(1).fc，nxq); EB.tc = E(1).tc; (8) EEBE(2) E.fc

48、= E(2).fc; E.tc = merge(EB.tc，E(2).tc);第76頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 例4.2 試給出布爾表達(dá)式abcd作為控制條件的四元式中間代碼。 解答 設(shè)四元式序號(hào)從100開(kāi)始，則布爾表達(dá)式abcd的分析過(guò)程如圖47所示。第77頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 圖47 表達(dá)式abcd分析示意 第78頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二即： 100(jnz，a，_，102) 101(j，_，_，104) 102(jnz，b，_，106) 103(j，_，_，104) 104(j，

49、c，d，106) 105(j，_，_，q) T: 106 F: q第79頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 當(dāng)然，我們也可以通過(guò)圖48的分析得到上述四元式序列。 由例4.2可知，每一個(gè)布爾變量a都對(duì)應(yīng)一真一假兩個(gè)四元式，并且格式是固定的，即 (jnz，a，_，0) /*a為布爾變量*/ ( j，_，_，0) 而每一個(gè)關(guān)系表達(dá)式同樣對(duì)應(yīng)一真一假兩個(gè)四元式，其格式也是固定的，即 (jrop，X，Y，0) /*X、Y為關(guān)系運(yùn)算符兩側(cè)的變量或值*/ ( j，_，_，0)第80頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二圖48 abcd的翻譯圖第81頁(yè)，共169

50、頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二4.5 控制語(yǔ)句的翻譯在源程序中，控制語(yǔ)句用于實(shí)現(xiàn)程序流程的控制。一般程序流程控制可分為下面三種基本結(jié)構(gòu)：(1) 順序結(jié)構(gòu)，一般用復(fù)合語(yǔ)句實(shí)現(xiàn)；(2) 選擇結(jié)構(gòu)，用if和case等語(yǔ)句實(shí)現(xiàn)；(3) 循環(huán)結(jié)構(gòu)，用for、while、do(即repeat)等語(yǔ)句實(shí)現(xiàn)。第82頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 4.5.1 條件語(yǔ)句if的翻譯 1條件語(yǔ)句if的代碼結(jié)構(gòu) 我們按下面的條件語(yǔ)句if的模式進(jìn)行討論： if(E)S1;else S2 條件語(yǔ)句if (E); else S2中布爾表達(dá)式E的作用僅在于控制對(duì)S1和S2的選擇，

51、因此可將作為轉(zhuǎn)移條件的布爾式E賦予兩種“出口”：一是“真”出口，出向S1；一是“假”出口，出向S2。于是，條件語(yǔ)句可以翻譯成如圖49所示的代碼結(jié)構(gòu)。第83頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二圖49 條件語(yǔ)句if(E)S1;else S2 的代碼結(jié)構(gòu)第84頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 我們知道，非終結(jié)符E具有兩項(xiàng)語(yǔ)義值E.tc和E.fc，它們分別指出了尚待回填真假出口的四元式串。E的“真”出口只有在掃描完布爾表達(dá)式E后的“)”時(shí)才能知道，而它的“假”出口則需要處理過(guò)S1之后并且到else時(shí)才能明確。這就是說(shuō)，必須把E.fc的值傳下去，以便到

52、達(dá)相應(yīng)的else時(shí)才進(jìn)行回填。S1語(yǔ)句執(zhí)行完就意味著整個(gè)if-else語(yǔ)句也已執(zhí)行完畢，因此， 第85頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二在S1的編碼之后應(yīng)產(chǎn)生一條無(wú)條件轉(zhuǎn)移指令，這條轉(zhuǎn)移指令將導(dǎo)致程序控制離開(kāi)整個(gè)if-else語(yǔ)句。但是，在完成S2的翻譯之前，這條無(wú)條件轉(zhuǎn)移指令的轉(zhuǎn)移目標(biāo)是不知道的，甚至在翻譯完S2之后仍無(wú)法確定，這種情形是由語(yǔ)句的嵌套性所引起的。例如下面的語(yǔ)句：if (E1) if (E2) S1; else S2;else S3 在S1代碼之后的那條無(wú)條件轉(zhuǎn)移指令不僅應(yīng)跨越S2，而且應(yīng)跨越S3。這也就是說(shuō)，轉(zhuǎn)移目標(biāo)的確定和語(yǔ)句所處的環(huán)境密切相關(guān)。第

53、86頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 2條件語(yǔ)句if的文法和語(yǔ)義子程序的設(shè)計(jì) 條件語(yǔ)句if的文法GS如下： GS：Sif(E) S(1)Sif(E) S(1);else S(2) 為了在掃描條件語(yǔ)句過(guò)程中不失時(shí)機(jī)地處理和回填有關(guān)信息，可將GS改寫(xiě)為如下的GS： GS：(1) SCS(1)(2) Cif(E)(3) STpS(2)(4) TPCS(1);else第87頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二根據(jù)程序語(yǔ)言的處理順序，首先用產(chǎn)生式(2) Cif(E)進(jìn)行歸約，這時(shí)E的真出口即為E所生成四元式序列后的下一個(gè)地址。因此，將“)”后的第一個(gè)四

54、元式地址回填至E的真出口，E的假出口地址則作為待填信息放在C的語(yǔ)義變量C.chain中，即： Cif(E) Backpatch(E.tc,nxq); C.chain=E.fc; 接下來(lái)用產(chǎn)生式(1) SCS(1)繼續(xù)向上歸約。這時(shí)已經(jīng)處理到Sif(E) S(1)，由于歸約時(shí)E的真出口已經(jīng)處理，而E的假出口(即語(yǔ)句S的出口)同時(shí)是語(yǔ)句S(1)的出口， 第88頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 但此時(shí)語(yǔ)句S的出口地址未定，故將C.chain和S(1).chain一起作為S的待填信息鏈用函數(shù)merge鏈在一起保留在S的語(yǔ)義值S.chain中，即有SCS(1) S.chain

55、=merge(C.chain,S(1).chain) 如果此時(shí)條件語(yǔ)句為不含else的條件句，則在產(chǎn)生式(1)、(2)歸約為S后即可以用下一個(gè)將要產(chǎn)生的四元式地址(即S的出口地址)來(lái)回填S的出口地址鏈(即S.chain)；如果此時(shí)條件語(yǔ)句為if-else形式，則繼續(xù)用產(chǎn)生式(4) TPCS(1);else歸約。第89頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 用TpCS(1);else 歸約時(shí)首先產(chǎn)生S(1)語(yǔ)句序列之后的一個(gè)無(wú)條件轉(zhuǎn)移四元式(以便跳過(guò)S(2)，見(jiàn)圖49的結(jié)構(gòu)框圖)，該四元式的地址(即標(biāo)號(hào))保留在q中，以便待獲知要轉(zhuǎn)移的地址后再進(jìn)行回填，也即： (i) (S(

56、1)的第一個(gè)四元式) /*E的真出口*/ (q1) (S(1)的最后一個(gè)四元式) (q) (j, _, _,0) /*無(wú)條件跳過(guò)S(2)，其轉(zhuǎn)移地址有待回填*/ (q+1)(S(2)的第一個(gè)四元式) /*E的假出口*/第90頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 此時(shí)q的出口也就是整個(gè)條件語(yǔ)句的出口，因此應(yīng)將其與S.chain鏈接后掛入鏈頭為Tp.chain的鏈中。此外，emit 產(chǎn)生四元式q后nxq自動(dòng)加1(即為q+1)，其地址即為else后(也即S(2)的第一個(gè)四元式地址，它也是E的假出口地址，因此應(yīng)將此地址回填到E.fc即C.chain中，即有： TpCS(1);

57、else q=nxq; emit(j,_,_,0); Backpatch(C.chain,nxq); Tp.chain=merge(S.chain,q);第91頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 最后用產(chǎn)生式(3) STpS(2)歸約。當(dāng)S(2)語(yǔ)句序列處理完后繼續(xù)翻譯if語(yǔ)句之后的后繼語(yǔ)句，這時(shí)就有了后繼語(yǔ)句的四元式地址，該地址也是整個(gè)if語(yǔ)句的出口地址，它與S(2)語(yǔ)句序列的出口一致。由于S(2)的出口待填信息在S(2).chain中，故將Tp.chain與S(2).chain鏈接后掛入鏈頭為S.chain的鏈中，即 STpS(2) S.chain=merge(T

58、p.chain, S(2).chain);第92頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 4.5.2 條件循環(huán)語(yǔ)句while的翻譯 1條件循環(huán)語(yǔ)句while的代碼結(jié)構(gòu) 條件循環(huán)語(yǔ)句while (E) S(1) 通常被翻譯成圖410所示的代碼結(jié)構(gòu)。布爾表達(dá)式E的“真”出口出向S(1)代碼段的第一個(gè)四元式，緊接S(1)代碼段之后應(yīng)產(chǎn)生一條轉(zhuǎn)向測(cè)試E的無(wú)條件轉(zhuǎn)移指令；而E的“假”出口將導(dǎo)致程序控制離開(kāi)整個(gè)while語(yǔ)句而去執(zhí)行while語(yǔ)句之后的后繼語(yǔ)句。第93頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二圖410 條件循環(huán)while語(yǔ)句的代碼結(jié)構(gòu)第94頁(yè)，共169

59、頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 2條件循環(huán)語(yǔ)句while的文法和語(yǔ)義子程序設(shè)計(jì) 同樣，我們給出易于及時(shí)處理和回填的條件循環(huán)語(yǔ)句while的文法GS如下： GS：(1) SWdS(1) (2) WdW(E) (3) Wwhile 根據(jù)while語(yǔ)句的掃描加工順序，首先用產(chǎn)生式(3) Wwhile進(jìn)行歸約，這時(shí)nxq即為E的第一個(gè)四元式地址，我們將其保留在W.quad中。 第95頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 然后繼續(xù)掃描并用WdW(E)歸約，即掃描完“)”后可以用Backpatch(E.tc,nxq)回填E.tc值；而E.fc則要等到S(1)語(yǔ)句序

60、列全部產(chǎn)生后才能回填，因此E.fc作為待填信息用Wd.chain=E.fc傳下去。 當(dāng)用產(chǎn)生式(1)SWdS(1)歸約時(shí)，S(1)語(yǔ)句序列的全部四元式已經(jīng)產(chǎn)生。根據(jù)圖410 while語(yǔ)句代碼結(jié)構(gòu)的特點(diǎn)，此時(shí)應(yīng)無(wú)條件返回到E的第一個(gè)四元式繼續(xù)對(duì)條件E進(jìn)行測(cè)試，即形成四元式(j,_,_,Wd.quad)，同時(shí)用Backpatch(S(1).chain,Wd.quad)回填E的入口地址到S(1)語(yǔ)句序列中所有需要該信息的四元式中。第96頁(yè)，共169頁(yè)，2022年，5月20日，20點(diǎn)33分，星期二 在無(wú)條件轉(zhuǎn)移語(yǔ)句(j,_,_,Wd.quad)之后即為while語(yǔ)句的后繼語(yǔ)句，而這個(gè)后繼語(yǔ)句中的第一