語義分析和中間代碼生成

關(guān)于語義分析和中間代碼生成本章在編譯程序中的地位表格管理詞法分析器語法分析器語義分析與中間代碼產(chǎn)生優(yōu)化器目標(biāo)代碼生成器源程序單詞符號語法單位中間代碼中間代碼目標(biāo)代碼出錯處理第2頁,共84頁，星期六，2024年，5月6.1概述6.2屬性文法6.3幾種常見的中間語言（*四元式）6.4表達式及賦值語句的翻譯6.5控制語句的翻譯 6.6數(shù)組元素的翻譯6.7過程或函數(shù)調(diào)用語句的翻譯*6.8說明語句的翻譯內(nèi)容安排第3頁,共84頁，星期六，2024年，5月6.1概述

6.1.1語義分析的概念一個源程序經(jīng)過詞法分析、語法分析之后，表明該源程序在書寫上是正確的，并且符合程序語言所規(guī)定的語法。但是語法分析并未對程序內(nèi)部的邏輯含義加以分析，因此編譯程序接下來的工作是語義分析，即審查每個語法成分的靜態(tài)語義。如果靜態(tài)語義正確，則生成與該語言成分等效的中間代碼，或者直接生成目標(biāo)代碼。

第4頁,共84頁，星期六，2024年，5月直接生成目標(biāo)代碼

直接生成機器語言或匯編語言形式的目標(biāo)代碼的優(yōu)點是編譯時間短且無需中間代碼到目標(biāo)代碼的翻譯。生成中間代碼

生成中間代碼的優(yōu)點是使編譯結(jié)構(gòu)在邏輯上更為簡單明確，特別是使目標(biāo)代碼的優(yōu)化比較容易實現(xiàn)。第5頁,共84頁，星期六，2024年，5月

語義分析時語義檢查的分類：動態(tài)語義檢查需要生成相應(yīng)的目標(biāo)代碼，它是在運行時進行的；例如：除零溢出錯誤。靜態(tài)語義檢查在編譯時完成的，它涉及以下幾個方面：

(1)類型檢查

(2)控制流檢查

(3)一致性檢查第6頁,共84頁，星期六，2024年，5月各種條件表達式的類型不是布爾類型;運算符的分量類型不相容;賦值語句左右類型不相容;形、實參類型不相容;函數(shù)說明和函數(shù)返回類型不相容;……intx;floatf();x=f();符合變量聲明的語法、語義符合函數(shù)聲明的語法、語義符合賦值語句的語法、不符合語義(1)類型檢查第7頁,共84頁，星期六，2024年，5月

(2)控制流檢查用以保證控制語句有合法的轉(zhuǎn)向點。如C語言中不允許goto語句轉(zhuǎn)入case語句流；break語句需尋找包含它的最小switch、while或for語句方可找到轉(zhuǎn)向點，否則出錯。

(3)一致性檢查如在相同作用域中標(biāo)識符只能說明一次、case語句的標(biāo)號不能相同、函數(shù)調(diào)用參數(shù)個數(shù)要相同等。

第8頁,共84頁，星期六，2024年，5月常見的語義錯誤聲明和使用相關(guān)的語義錯誤標(biāo)識符沒有聲明;重復(fù)聲明;如何檢查?每當(dāng)遇到新聲明的標(biāo)識符,查符號表如果當(dāng)前有效的所有標(biāo)識符中有相同名字的,則是重復(fù)聲明錯誤;否則生成它的屬性信息,保存到符號表中;每當(dāng)遇到標(biāo)識符的使用,查符號表如果沒有找到,說明該標(biāo)識符沒有聲明;否則,得到該標(biāo)識符的屬性,進行進一步分析;第9頁,共84頁，星期六，2024年，5月

語義分析階段只產(chǎn)生中間代碼而不生成目標(biāo)代碼的方法使編譯程序的開發(fā)變得較為容易，但語義分析不像詞法分析和語法分析那樣可以分別用正規(guī)文法和上下文無關(guān)文法描述。

由于語義是上下文有關(guān)的，因此語義的形式化描述是非常困難的，目前較為常見的是用屬性文法作為描述程序語言語義的工具，并采用語法制導(dǎo)翻譯的方法完成對語法成分的翻譯工作。第10頁,共84頁，星期六，2024年，5月

語法制導(dǎo)翻譯的方法就是為每個規(guī)則配上一個翻譯子程序(稱語義動作或語義子程序)，并在語法分析的同時執(zhí)行這些子程序。

語義動作是為規(guī)則賦予具體意義的手段，它一方面指出了一個規(guī)則所產(chǎn)生的符號串的意義，另一方面又按照這種意義規(guī)定了生成某種中間代碼應(yīng)做哪些基本動作。

在語法分析過程中，當(dāng)一個規(guī)則獲得匹配(對于自上而下分析)或用于歸約(對于自下而上分析)時，此規(guī)則相應(yīng)的語義子程序就進入工作，完成既定的翻譯任務(wù)。6.1.2語法制導(dǎo)翻譯方法第11頁,共84頁，星期六，2024年，5月

語法制導(dǎo)翻譯分為自下而上語法制導(dǎo)翻譯和自上而下語法制導(dǎo)翻譯，我們重點介紹自下而上語法制導(dǎo)翻譯。假定有一個自下而上的LR分析器，我們可以把這個LR分析器的能力加以擴大，使它能在用某個規(guī)則進行歸約的同時調(diào)用相應(yīng)的語義子程序進行有關(guān)的翻譯工作；每個規(guī)則的語義子程序執(zhí)行之后，某些結(jié)果(語義信息)必須作為此規(guī)則的左部符號的語義值暫時保存下來，以便以后語義子程序引用這些信息。第12頁,共84頁，星期六，2024年，5月

此外，原LR分析器的分析棧也加以擴充，以便能夠存放與文法符號相對應(yīng)的語義值。這樣，分析棧可以存放三類信息：分析狀態(tài)、文法符號及文法符號對應(yīng)的語義值。擴充后的分析棧如圖6–1所示。

第13頁,共84頁，星期六，2024年，5月圖6–1擴充后的LR分析棧第14頁,共84頁，星期六，2024年，5月

作為一個例子，我們考慮下面的文法及語義動作所執(zhí)行的程序：規(guī)則 語義動作

(0)S'→E printval[TOP](1)E→E(1)+E(2) val[TOP]=val[TOP]+val[TOP+2](2)E→E(1)*E(2) val[TOP]=val[TOP]*val[TOP+2](3)E→(E(1))val[TOP]=val[TOP+1](4)E→i val[TOP]=lexval(注：lexval為i的整型內(nèi)部值)第15頁,共84頁，星期六，2024年，5月

我們擴充分析棧工作的總控程序功能，使其在完成語法分析的同時也能完成語義分析工作(這時的語法分析棧已成為語義分析棧)；即在用某一個規(guī)則進行歸約之后，調(diào)用相應(yīng)的語義子程序完成與所用規(guī)則相應(yīng)的語義動作，并將每次工作后的語義值保存在擴充后的“語義值”棧中。圖6–2表示算術(shù)表達式7＋9*5#的語法樹及各結(jié)點值，而表6.1則給出了根據(jù)分析表用LR語法制導(dǎo)翻譯方法得到的該表達式的語義分析和計值過程。第16頁,共84頁，星期六，2024年，5月圖6–2語法制導(dǎo)翻譯計算表達式

7＋9*5#的語法樹第17頁,共84頁，星期六，2024年，5月表6.1表達式7＋9*5#的語義分析和計值過程步驟狀態(tài)棧符號棧語義棧輸入串動作10#_7＋9*5#s3203#7__＋9*5#r4301#E_7＋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第18頁,共84頁，星期六，2024年，5月6.2屬性文法

6.2.1文法的屬性

屬性是指與文法符號的類型和值等有關(guān)的一些信息，在編譯中用屬性描述處理對象的特征。隨著編譯的進展，對語法分析產(chǎn)生的語法樹進行語義分析，且分析的結(jié)果用中間代碼描述出來。對于一棵等待翻譯的語法樹，它的各個結(jié)點都是文法中的一個符號X，該X可以是終結(jié)符或非終結(jié)符。根據(jù)語義處理的需要，在用規(guī)則A→αXβ進行歸約或推導(dǎo)時，應(yīng)能準(zhǔn)確而恰當(dāng)?shù)乇磉_文法符號X在歸約或推導(dǎo)時的不同特征。第19頁,共84頁，星期六，2024年，5月

例如:

判斷變量X的類型是否匹配，要用X的數(shù)據(jù)類型來描述；判斷變量X是否存在，要用X的存儲位置來描述；而對X的運算，則要用X的值來描述；

因此，語義分析階段引入X的屬性，如X.type、X.place、X.val等來分別描述變量X的類型、存儲位置以及值等不同的特征。

文法符號屬性分：繼承屬性綜合屬性第20頁,共84頁，星期六，2024年，5月

繼承屬性

用于“自上而下”傳遞信息。繼承屬性由相應(yīng)語法樹中結(jié)點的父結(jié)點屬性計算得到，即沿語法樹向下傳遞，由根結(jié)點到分枝(子)結(jié)點，它反映了對上下文依賴的特性。繼承屬性可以很方便地用來表示程序語言上下文的結(jié)構(gòu)關(guān)系。

綜合屬性

用于“自下而上”傳遞信息。綜合屬性由相應(yīng)語法分析樹中結(jié)點的分枝結(jié)點(即子結(jié)點)屬性計算得到，其傳遞方向與繼承屬性相反，即沿語法分析樹向上傳遞，從分枝結(jié)點到根結(jié)點。第21頁,共84頁，星期六，2024年，5月

屬性文法是一種適用于定義語義的特殊文法，即在語言的文法中增加了屬性的文法，它將文法符號的語義以“屬性”的形式附加到各個文法的符號上(如上述與變量X相關(guān)聯(lián)的屬性X.type、X.place和X.val等)，再根據(jù)規(guī)則所包含的含義，給出每個文法符號屬性的求值規(guī)則，從而形成一種帶有語義屬性的上下文無關(guān)文法，即屬性文法。屬性文法也是一種翻譯文法，屬性有助于更詳細地指定文法中的代碼生成動作。6.2.2屬性文法第22頁,共84頁，星期六，2024年，5月例如，簡單算術(shù)表達式求值的屬性文法如下：規(guī)則 語義規(guī)則(1)?S→E print(E.val)(2)?E→E(1)+T

E.val=E(1).val+T.val(3)?E→T E.val=T.val(4)?T→T(1)*FT.val=T(1).val*F.val(5)?T→T(1) T.val=T(1).val(6)?F→(E) F.val=E.val(7)?F→i F.val=i.lexval第23頁,共84頁，星期六，2024年，5月

上面的一組規(guī)則中，每一個非終結(jié)符都有一個屬性val來表示整型值，如E.val表示E的整型值，而i.lexval則表示i的整型內(nèi)部值。與規(guī)則關(guān)聯(lián)的每一個語義規(guī)則的左部符號E、T、F等的屬性值的計算由其各自相應(yīng)的右部符號決定，這種屬性也稱為綜合屬性。與規(guī)則S→E關(guān)聯(lián)的語義規(guī)則是一個函數(shù)print(E.val)，其功能是打印E規(guī)則的值。S’在語義規(guī)則中沒有出現(xiàn)，可以理解為其屬性是一個虛屬性。第24頁,共84頁，星期六，2024年，5月簡單變量類型說明的文法G[D]如下：G[D]：D→intL∣floatLL→L,id∣id其對應(yīng)的屬性文法為：規(guī)則語義規(guī)則(1)?D→TL L.in=T.type(2)?T→int

T.type=int(3)?T→float T.type=float(4)?L→L(1)，idL(1).in=L.in;addtype(id.entry,L.in)(5)?L→id addtype(id.entry,L.in)注意到與文法G[D]相應(yīng)的說明語句形式可為intid1，id2,…，idn

或者floatid1，id2,…，idn第25頁,共84頁，星期六，2024年，5月

非終結(jié)符T有一個綜合屬性type，其值為int或float。語義規(guī)則L.in=T.type表示L.in的屬性值由相應(yīng)說明語句指定的類型T.type決定；屬性L.in被確定后將隨語法樹的逐步生成而傳遞到下邊的有關(guān)結(jié)點使用，這種結(jié)點屬性稱為繼承屬性。由此可見，標(biāo)識符的類型可以通過繼承屬性的復(fù)寫規(guī)則來傳遞。例如，對輸入串inta,b，根據(jù)上述的語義規(guī)則，可在其生成的語法樹中看到用“→”表示的屬性傳遞情況，如圖6–3所示。第26頁,共84頁，星期六，2024年，5月圖6–3屬性信息傳遞情況示意第27頁,共84頁，星期六，2024年，5月屬性翻譯文法（屬性文法）

如語法分析方法是自下而上的，在用某一規(guī)則進行規(guī)約的同時就執(zhí)行相應(yīng)的語義，在分析出一個句子時，這個句子的“值”也就同時產(chǎn)生了。對于文法的每個規(guī)則都配備了一組屬性的計算規(guī)則，稱為語義規(guī)則。屬性與變量一樣，可以進行計算和傳遞。屬性加工的過程即是語義處理的過程。第28頁,共84頁，星期六，2024年，5月6.3幾種常見的中間語言6.3.1

抽象語法樹6.3.2逆波蘭表示法6.3.3三地址代碼第29頁,共84頁，星期六，2024年，5月6.3.1抽象語法樹語法制導(dǎo)翻譯既可以基于語法分析樹也可以基于抽象語法樹進行，采用的基本方法是一樣的。現(xiàn)在對語法樹進行改造，去掉那些對翻譯不必要的信息，將語法樹進行抽象---抽象語法樹。在表達式的抽象語法樹中，運算符、關(guān)鍵字不作葉子結(jié)點而作為內(nèi)部結(jié)點，葉子結(jié)點只是運算量。語法制導(dǎo)翻譯以語法樹作基礎(chǔ),實際上,語法樹可以作為一種合適的中間語言形式。抽象語法樹也可以屬性化，給結(jié)點加上屬性變成帶屬性的抽象語法樹。第30頁,共84頁，星期六，2024年，5月

當(dāng)把語法規(guī)則中本質(zhì)部分抽象出來而將非本質(zhì)部分去掉后，便得到抽象語法規(guī)則。這種去掉不必要信息的做法可以獲得高效的源程序中間表示。如賦值語句x=a?b*c的抽象語法樹如圖6–4(a)所示，而圖6–4(b)則是該賦值語句的普通語法樹。圖6–4x=a?b*c的語法樹第31頁,共84頁，星期六，2024年，5月

抽象語法樹的一個顯著特點是結(jié)構(gòu)緊湊，容易構(gòu)造且結(jié)點數(shù)較少。圖6–4(b)所示的普通語法樹的結(jié)點為14個；而圖6–4(a)所示的抽象語法樹的結(jié)點僅有7個，且每個內(nèi)部結(jié)點最多只有兩個分支，因此可以將每個賦值語句或表達式表示為一棵二叉樹。對于含有多元運算的更為復(fù)雜的語法成分，相應(yīng)的抽象語法樹則為一棵多叉樹，但我們總可以將其轉(zhuǎn)變?yōu)橐豢枚鏄洹５?2頁,共84頁，星期六，2024年，5月為下面文法的句子a-4+c

建立抽象語法樹。

EE+T|E－T|TT(E)Tid|num為每個運算量或運算符號都建立一個結(jié)點。可以根據(jù)表達式的運算順序自下而上的構(gòu)造---手工構(gòu)造。a－+c4抽象語法樹運算符作內(nèi)部結(jié)點id(a)EE－TE+TTnum(4)id(c)語法樹第33頁,共84頁，星期六，2024年，5月抽象語法樹的實現(xiàn)抽象語法樹中的每一個結(jié)點可以由包含幾個域的記錄來實現(xiàn)；有向邊用指針實現(xiàn)。在一個運算量對應(yīng)的結(jié)點(葉結(jié))中,一個域標(biāo)識運算量，另一個域是該運算量的屬性值(或指針)。在一個運算符對應(yīng)的結(jié)點中,一個域標(biāo)識運算符，其它域包含指向運算分量的結(jié)點的指針。運算符通常叫做這個結(jié)點的標(biāo)號。進行翻譯時，抽象語法樹中的結(jié)點可能會用附加域來存放結(jié)點的屬性值(或指向?qū)傩缘闹羔槪?。numvalid.op..Toentryofid右子樹根結(jié)左子樹根結(jié)第34頁,共84頁，星期六，2024年，5月

建立表達式的抽象語法樹使用的函數(shù),這些函數(shù)返回新建立結(jié)點的指針。1.mknode(op,left,right)

建立一個運算符結(jié)點，標(biāo)號是op,兩個域left和right指向左右運算分量結(jié)點的指針。2.mkleaf(id,entry)

建立一個“標(biāo)識符”葉子結(jié)點,由標(biāo)號id標(biāo)識，一個域entry指向標(biāo)識符在符號表中相應(yīng)的項。3.mkleaf(num,val)

建立一個“數(shù)”葉子結(jié)點，標(biāo)號為num，域val用于存放數(shù)的值。抽象語法樹的構(gòu)造函數(shù)

第35頁,共84頁，星期六，2024年，5月

調(diào)用上述函數(shù)建立表達式a-4+c

的抽象語法樹。建立順序自下而上是:

p1,p2,p3,p4,p5抽象語法樹構(gòu)造idtoentryap1num4p2

–p3idtoentrycp4

+p5第36頁,共84頁，星期六，2024年，5月

規(guī)則語義規(guī)則

E

E1+TE.nptr:=mknode('+',E1.nptr,T.nptr)E

E1-TE.nptr:=mknode('-',E1.nptr,T.nptr)E

TE.nptr:=T.nptrT

(E)T.nptr:=E.nptrT

idT.nptr:=mkleaf(id,id.entry)T

numT.nptr:=mkleaf(num,num.val)建立抽象語法樹的語義規(guī)則屬性文法,nptr是綜合屬性第37頁,共84頁，星期六，2024年，5月手工構(gòu)造表達式a＋b*(c-d)-e/f的抽象語法樹，根據(jù)表達式的運算順序自下而上的構(gòu)造。練習(xí)

+a－–dc*b/fe第38頁,共84頁，星期六，2024年，5月

逆波蘭表示法是波蘭邏輯學(xué)家盧卡西維奇(Lukasiewicz)發(fā)明的一種表示表達式的方法，這種表示法把運算量(操作數(shù))寫在前面，把運算符寫在后面，因而又稱后綴表示法。例如，把a+b寫成ab+，把a*(b+c)寫成abc+*。6.3.2逆波蘭表示法第39頁,共84頁，星期六，2024年，5月

1．表達式的逆波蘭表示

表達式E的后綴表示的遞歸定義如下：

(1)如果E是變量或常數(shù)，則E的后綴表示即E自身。

(2)如果E為E1?opE2形式，則它的后綴表示為E1'E2'op；其中op是二元運算符，而E1'、E2'分別又是E1和E2的后綴表示。若op為一元運算符，則視E1和E1'為空。

(3)如果E為(E1)形式，則E1的后綴表示即為E的后綴表示。第40頁,共84頁，星期六，2024年，5月

上述遞歸定義的實質(zhì)是：后綴表示中，操作數(shù)出現(xiàn)的順序與原來一致，而運算符則按運算先后的順序放入相應(yīng)的操作數(shù)之后(即運算符先后的順序發(fā)生了變化)。這種表示已不再需要用括號來規(guī)定運算的順序了。第41頁,共84頁，星期六，2024年，5月寫表達式的后綴式要點：1.后綴式中運算量的順序與中綴式的相同；2.算符出現(xiàn)的次序即表達式的運算次序；3.不使用括號。例：a+bab+a*(b+c)abc+*(a+b)*(c+d)ab+cd+*-a+b*ca

bc*+a/b**c-d*eabc**/de*-

(A＝0∧B≠0)A0=B0≠∧

用

表示取負算符(uminus)第42頁,共84頁，星期六，2024年，5月練習(xí)寫出下列各式的逆波蘭表示:(1)-a-(b*c/(c-d)+(-b)*a)(2)-A+B*C↑(D/E)/F(3)x:=a-b/(c+d)解：(1)a

bc*cd-/b

a*+-(2)A

BCDE/↑*F/+(3)xabcd+/-:=

用

表示取負算符(uminus):=表示賦值算符(assign)第43頁,共84頁，星期六，2024年，5月

后綴表示法表示表達式，其最大優(yōu)點是易于計算機處理表達式。常用的算法是使用一個棧，自左至右掃描算術(shù)表達式（后綴表示)，每掃描到運算對象，就把它推進棧；掃描到運算符，若該運算符是二目的，則對棧頂部的兩個運算對象實施該運算，并將運算結(jié)果代替這兩個運算對象而進棧；若是一目運算符，則對棧頂元素執(zhí)行該運算，并以運算結(jié)果代替該元素進棧，最后的結(jié)果留在棧頂。例如

-B+C*D的計算過程：第44頁,共84頁，星期六，2024年，5月-B+C*D的后綴表示為B

CD*+:第45頁,共84頁，星期六，2024年，5月

把表達式翻譯為后綴式的

語義規(guī)則(屬性文法)

規(guī)則

語義規(guī)則E→E1opE2

E.code:=E1.code||E2.code||opE→(E1)E.code:=E1.codeE→idE.code:=id屬性E.code:是E的后綴式代碼屬性op:二元算符‖:后綴式的連接運算算符第46頁,共84頁，星期六，2024年，5月

1．三地址代碼的形式三地址代碼語句的一般形式為

x=yopz

其中，x、y和z為變量、結(jié)果或編譯時產(chǎn)生的臨時變量；op為運算符。

三地址代碼的每條語句通常包含三個地址，兩個用來存放運算對象，一個用來存放運算結(jié)果。6.3.3三地址代碼第47頁,共84頁，星期六，2024年，5月

在實際實現(xiàn)中，用戶定義的變量將由指向符號表中該變量項的指針?biāo)〈?/p>

由于三地址語句只含有一個運算符，因此多個運算符組成的表達式必須用三地址語句序列來表示，如表達式x+y*z的三地址代碼為：

t1=y*zt2=x+t1

其中，t1和t2是編譯時產(chǎn)生的臨時變量。第48頁,共84頁，星期六，2024年，5月例：賦值語句a:=(-b)*(c+d)-(c+d)的三地址碼如下所示。t1:=minusbt2:=c+dt3:=t1*t2t4:=c+dt5:=t3-t4a:=t5第49頁,共84頁，星期六，2024年，5月

2．三地址代碼的具體實現(xiàn)三地址代碼是中間代碼的一種抽象形式。在編譯程序中，三地址代碼語言的具體實現(xiàn)通常有三種表示方法：四元式、三元式和間接三元式。

1)四元式四元式是具有四個域的記錄結(jié)構(gòu)，這四個域為

(op，arg1，arg2，result)

其中，op為運算符，arg1、arg2及result為指針，它們可指向有關(guān)變量在符號表中的登記項或一臨時變量(也可空缺)。第50頁,共84頁，星期六，2024年，5月

常用的三地址語句與相應(yīng)的四元式對應(yīng)如下：

x=yopz對應(yīng)(op,y,z,x)x=?y 對應(yīng)(-,y,_,x)x=y 對應(yīng)(=,y,_,x)callP 對應(yīng)(call,_,_,P)gotoL 對應(yīng)(j,_,_,L)ifxropygotoL對應(yīng)(jrop,x,y,L)第51頁,共84頁，星期六，2024年，5月例如，賦值語句a=b*(c+d)相應(yīng)的四元式代碼為：①(+,c,d,t1)②(*,b,t1,t2)③(=,t2,_,a)

約定：凡只需一個運算量的算符一律使用arg1；如果op是一個算術(shù)或邏輯運算符，則result總是一個新引進的臨時變量，它用來存放運算結(jié)果。由上例也可看出，四元式出現(xiàn)的順序與表達式計值的順序是一致的，四元式之間的聯(lián)系是通過臨時變量實現(xiàn)的。四元式由于其表示更接近程序設(shè)計的習(xí)慣而成為一種普遍采用的中間代碼形式。第52頁,共84頁，星期六，2024年，5月

2)三元式三元式是具有三個域的記錄結(jié)構(gòu)，這三個域為

(op，arg1，arg2)

其中，op為運算符，arg1、arg2既可指向有關(guān)名字在符號表中的登記項或臨時變量，也可以指向三元式表中的某一個三元式。

第53頁,共84頁，星期六，2024年，5月例如對于表達式：A+B*(C-D)+E/(C-D)^N的三元式代碼為：

由上例可知，三元式出現(xiàn)的先后順序和表達式各部分的計值順序是一致的。第54頁,共84頁，星期六，2024年，5月

3)間接三元式在三元式代碼表的基礎(chǔ)上另設(shè)一張表，該表按運算的次序列出相應(yīng)三元式在三元式表中的位置，這張表稱為間接碼表。三元式表只記錄不同的三元式語句，而間接碼表則表示由這些語句組成的運算次序。例如對于表達式：A+B*(C-D)+E/(C-D)^N的三元式與間接碼表為：

每生成一條指令，先檢查已生成的間接三元式序列，若已有，不再生成，只把序號列入間接碼表中。第55頁,共84頁，星期六，2024年，5月

在三元式表示中，每個語句的位置同時有兩個作用：一是可作為該三元式的結(jié)果被其它三元式引用；二是三元式位置順序即為運算順序。在代碼優(yōu)化階段，需要調(diào)整三元式的運算順序時會遇到困難，這是因為三元式中的arg1、arg2也可以是指向某些三元式位置的指針，當(dāng)這些三元式的位置順序發(fā)生變化時，含有指向這些三元式位置指針的相關(guān)三元式也需隨之改變指針值。因此，變動一張三元式表是很困難的。第56頁,共84頁，星期六，2024年，5月

對四元式來說，引用另一語句的結(jié)果可以通過引用該語句的result(通常是一個臨時變量)來實現(xiàn)，而間接三元式則通過間接碼表來描述語句的運算次序。這兩種方法都不存在語句位置同時具有兩種功能的現(xiàn)象，代碼調(diào)整時要做的改動只是局部的，因此，當(dāng)需要對中間代碼表進行優(yōu)化處理時，四元式與間接三元式都比三元式方便得多。第57頁,共84頁，星期六，2024年，5月寫中間語言：練習(xí)

寫出表達式：A+B*(C-D)-E/F↑G

的逆波蘭表示、三元式表示、四元式表示。解:四元式表示：①(-,C,D,T1)②(*,B,T1,T2)③(+,A,T2,T3)④(↑,F,G,T4)⑤(/,E,T4,T5)⑥(-,T3,T5,T6)解:三元式表示：①(-,C,D)②

(*,B,①)③

(+,A,②)④(↑,F,G)⑤(/,E,④)⑥(-,③,⑤)解：逆波蘭表示：ABCD-*+EFG↑/-第58頁,共84頁，星期六，2024年，5月語法制導(dǎo)翻譯

翻譯的任務(wù)：首先是語義分析和正確性檢查，若正確，則翻譯成中間代碼或目標(biāo)代碼。第59頁,共84頁，星期六，2024年，5月語法制導(dǎo)翻譯法的基本思想對文法中的每個規(guī)則都附加上一個語義動作或語義子程序，在執(zhí)行語法分析的過程中，每當(dāng)使用一條規(guī)則進行推導(dǎo)或歸約時，就執(zhí)行相應(yīng)規(guī)則的語義動作，從而完成翻譯工作。第60頁,共84頁，星期六，2024年，5月什么是語法制導(dǎo)翻譯法在語法分析過程中，隨著分析的逐步進展，根據(jù)相應(yīng)文法的每一規(guī)則所對應(yīng)的語義子程序進行翻譯的方法（即隨語法分析的進展，識別出一個語法結(jié)構(gòu)，就對它的語義進行分析和翻譯）。第61頁,共84頁，星期六，2024年，5月

語法制導(dǎo)翻譯技術(shù)分為自底向上語法制導(dǎo)翻譯和自頂向下語法制導(dǎo)翻譯。第62頁,共84頁，星期六，2024年，5月自底向上語法制導(dǎo)翻譯自底向上語法制導(dǎo)翻譯方法是在自下而上的語法分析過程中逐步實現(xiàn)語義規(guī)則的方法。自底向上語法制導(dǎo)翻譯的特點：（1）當(dāng)棧頂形成句柄執(zhí)行歸約時，調(diào)用相應(yīng)的語義動作。（2）語法分析棧和語義分析棧同步操作。第63頁,共84頁，星期六，2024年，5月

以LR語法制導(dǎo)翻譯為例，說明如何實現(xiàn)語法制導(dǎo)翻譯：

1、為文法G的每一個規(guī)則設(shè)計相應(yīng)的語義子程序。

2、構(gòu)造文法G的LR分析表。

3、將原LR語法分析棧擴充，以便存放文法符號對應(yīng)的語義值。

4、在用某一規(guī)則進行歸約的同時，調(diào)用相應(yīng)的語義子程序，完成所用規(guī)則式相應(yīng)的語義動作。第64頁,共84頁，星期六，2024年，5月中間語言為了使編譯程序在邏輯上更為簡單明確，特別是為了使目標(biāo)代碼的優(yōu)化比較容易實現(xiàn)，許多編譯程序都采用了某種復(fù)雜性介于源程序語言和機器語言之間的中間語言，并且首先把源程序翻譯成這種中間語言程序（中間代碼）。第65頁,共84頁，星期六，2024年，5月

常見的中間語言形式逆波蘭式三元式四元式第66頁,共84頁，星期六，2024年，5月

四元式是一種比較普遍采用的中間代碼形式。四元式的四個成分是：算符OP、第一運算量ARG1、第二運算量ARG2以及運算結(jié)果RESULT。其中，運算量和運算結(jié)果有時指用戶自定義的變量，有時指編譯程序引進的臨時變量。第67頁,共84頁，星期六，2024年，5月賦值語句A：=-B*（C+D）的四元式序列：序號OPARG1ARG2RESULT注釋（1）

B_T1T1

為臨時變量（2）+CDT2T2

為臨時變量（3）*T1T2T3T3

為臨時變量（4）：=T3_A賦值運算

表中：“

”是為了區(qū)別“-”而表示的求負運算符。凡只需一個運算量的算符，使用ARG1。第68頁,共84頁，星期六，2024年，5月6.4表達式及賦值語句的翻譯

6.4.1簡單算術(shù)表達式和賦值語句的翻譯

簡單算術(shù)表達式是一種僅含簡單變量的算術(shù)表達式；簡單變量是指普通變量和常數(shù)，但不含數(shù)組元素及結(jié)構(gòu)引用等復(fù)合型數(shù)據(jù)結(jié)構(gòu)。

簡單算術(shù)表達式的計值順序與四元式出現(xiàn)的順序相同，因此很容易將其翻譯成四元式形式。第69頁,共84頁，星期六，2024年，5月

實現(xiàn)簡單算術(shù)表達式和賦值語句到四元式的翻譯一般采取下列步驟：（1）分析文法的特點。（2）設(shè)置一系列語義變量，定義語義過程、語義函數(shù)。（3）修改文法，寫出每一條規(guī)則的語義子程序。（4）擴充LR分析棧，構(gòu)造LR分析表。第70頁,共84頁，星期六，2024年，5月

考慮以下文法G[A]：A→i=E?E→E+E∣E*E∣?E∣(E)∣i

為了實現(xiàn)由表達式到四元式的翻譯，需要給文法加上語義子程序，以便在進行歸約的同時執(zhí)行對應(yīng)的語義子程序。第71頁,共84頁，星期六，2024年，5月

語義子程序所涉及的語義變量、語義過程及函數(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)生一個四元式并填入四元式表中。第72頁,共84頁，星期六，2024年，5月

(4)定義語義函數(shù)lookup()，其功能是檢查是否出現(xiàn)在符號表中，是則返回在符號表的入口指針，否則返回NULL。

使用上述語義變量、過程和函數(shù)，可寫出文法G[A]中的每一個規(guī)則的語義子程序。

(1)?A→i=E{p=lookup();if(p==NULL)error(?);elseemit(=,E.place,_,p);}(2)?E→E(1)+E(2){E.place=newtemp(?);emit(+,E(1).place,E(2).place,E.place);}第73頁,共84頁，星期六，2024年，5月(3)?E→E(1)*E(2){E.place=newtemp(?);

emit(*,E(1).place,E(2).place,E.place);}(4)?E→?E(1){E.place=newtemp(?);

emit(uminus,E(1).place,_,E.place);}(5)?E→(E(1))?{E.place=E(1).place;}(6)?E→i

?{p=lookup();if(p!=NULL)E.place=p;/*另一種表示為E.place=entry(i)*/elseerror(?);}第74頁,共84頁，星期六，2024年，5月運算合法性檢查利用符號表保存的名字類型類型自動轉(zhuǎn)換填加專用指令臨時變量空間的統(tǒng)計了解需求、及時釋放表達式翻譯中的其他問題第75頁,共84頁，星期六，2024年，5月若考慮到變量的類型檢查和轉(zhuǎn)換，則第（3）條產(chǎn)生式及其有關(guān)語義描述如下：｛E．place∶=newtemp；ifE（1）．type＝intANDE（2）．type＝intthen

beginemit(*,E(1).place,E(2).place,E.place)；

E．