語(yǔ)義分析和中間代碼生成

語(yǔ)義分析和中間代碼生成第1頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月4.1概述

4.1.1語(yǔ)義分析的概念語(yǔ)法分析:

在編譯時(shí)對(duì)符合語(yǔ)法結(jié)構(gòu)的源程序內(nèi)部的邏輯含義加以分析，即審查每個(gè)語(yǔ)法成分的靜態(tài)語(yǔ)義(動(dòng)態(tài)語(yǔ)義檢查在程序運(yùn)行時(shí)進(jìn)行)。如果靜態(tài)語(yǔ)義正確，則生成與該語(yǔ)言成分等效的中間代碼，或者直接生成目標(biāo)代碼。第2頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月靜態(tài)語(yǔ)義檢查:

是在編譯時(shí)完成的，它涉及以下幾個(gè)方面：

(1)類(lèi)型檢查，如參與運(yùn)算的操作數(shù)其類(lèi)型應(yīng)相容。

(2)控制流檢查，用以保證控制語(yǔ)句有合法的轉(zhuǎn)向點(diǎn)。

(3)一致性檢查，如在相同作用域中標(biāo)識(shí)符只能說(shuō)明一次、case語(yǔ)句的標(biāo)號(hào)不能相同等。屬性文法:

語(yǔ)義分析階段只產(chǎn)生中間代碼,語(yǔ)義的形式化描述是非常困難的，目前較為常見(jiàn)的是用屬性文法作為描述程序語(yǔ)言語(yǔ)義的工具，并采用語(yǔ)法制導(dǎo)翻譯的方法完成對(duì)語(yǔ)法成分的翻譯工作。第3頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

4.1.2語(yǔ)法制導(dǎo)翻譯方法

語(yǔ)法制導(dǎo)翻譯方法:

就是為每個(gè)產(chǎn)生式配上一個(gè)翻譯子程序(稱(chēng)語(yǔ)義動(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ù)。語(yǔ)法制導(dǎo)翻譯分為自下而上語(yǔ)法制導(dǎo)翻譯和自上而下語(yǔ)法制導(dǎo)翻譯。第4頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月可拓展LR分析器能力，實(shí)現(xiàn)自下而上語(yǔ)法制導(dǎo)翻譯使LR分析器在用某個(gè)產(chǎn)生式進(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ǔ)義子程序引用這些信息。擴(kuò)充原LR分析器的分析棧以便能夠存放與文法符號(hào)相對(duì)應(yīng)的語(yǔ)義值。擴(kuò)充后的分析棧如圖4–1所示。第5頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月圖4–1擴(kuò)充后的LR分析棧第6頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月例子：val[TOP]表示放在語(yǔ)義棧頂?shù)闹诞a(chǎn)生式 語(yǔ)義動(dòng)作(0)S'→E printval[TOP](1)E→E(1)+E(2) val[TOP+2]=val[TOP]+val[TOP+2](2)E→E(1)*E(2) val[TOP+2]=val[TOP]*val[TOP+2](3)E→(E(1)) val[TOP+2]=val[TOP+1](4)E→i val[TOP]=lexval(注：lexval為i的整型內(nèi)部值)這個(gè)文法的LR分析表見(jiàn)表3.20。E.valE(2).valE(1).valE.val第7頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月表3.20算術(shù)表達(dá)式的SLR(1)分析表狀態(tài)ACTIONGOTOi+*()#E0s3

s2

11

s4s5

acc

2s3

s2

63

r4r4

r4r4

4s3

s2

75s3

s2

86

s4s5

s9

7

r1s5

r1r1

8

r2r2

r2r2

9

r3r3

r3r3

第8頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月表4.1則給出了根據(jù)表3.20用LR語(yǔ)法制導(dǎo)翻譯方法得到的表達(dá)式7＋9*5#的語(yǔ)義分析和計(jì)值過(guò)程。 圖4–2表示算術(shù)表達(dá)式7＋9*5#的語(yǔ)法樹(shù)及各結(jié)點(diǎn)值。第9頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月表4.1表達(dá)式7＋9*5#的語(yǔ)義分析和計(jì)值過(guò)程步驟狀態(tài)棧符號(hào)棧語(yǔ)義棧輸入串主要?jiǎng)幼?0#_7＋9*5#s3203#i(val=7)__＋9*5#r4301#E_7＋9*5#s44014#E+_7_9*5#s350143#E+i(9)_7__*5#r460147#E+E_7_9*5#s5701475#E+E*_7_9_5#s38014753#E+E*i(5)_7_9__#r49014758#E+E*E_7_9_5#r2100147#E+E_7_45#r11101#E_52#acc規(guī)約時(shí)執(zhí)行語(yǔ)義動(dòng)作第10頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月圖4–2語(yǔ)法制導(dǎo)翻譯計(jì)算表達(dá)式

7＋9*5#的語(yǔ)法樹(shù)注釋語(yǔ)法樹(shù)第11頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月4.2屬性文法屬性文法是在基礎(chǔ)文法的基礎(chǔ)上，附加上文法符號(hào)的屬性計(jì)算規(guī)則形成的文法。屬性文法可用作語(yǔ)言翻譯動(dòng)作的高層描述。4.2.1文法的屬性屬性:是指與文法符號(hào)的地址、類(lèi)型和值等有關(guān)的一些信息，在編譯中用屬性描述處理對(duì)象的特征。 例如，判斷變量X的類(lèi)型是否匹配，要用X的數(shù)據(jù)類(lèi)型來(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的類(lèi)型、存儲(chǔ)位置以及值等不同的特征。第12頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月文法符號(hào)的屬性可分為繼承屬性與綜合屬性?xún)深?lèi)。繼承屬性用于“自上而下”傳遞信息。繼承屬性由相應(yīng)語(yǔ)法樹(shù)中結(jié)點(diǎn)的父結(jié)點(diǎn)或兄弟節(jié)點(diǎn)屬性計(jì)算得到，即沿語(yǔ)法樹(shù)向下傳遞，由根結(jié)點(diǎn)到分枝(子)結(jié)點(diǎn)，它反映了對(duì)上下文依賴(lài)的特性。繼承屬性可以很方便地用來(lái)表示程序語(yǔ)言上下文的結(jié)構(gòu)關(guān)系。綜合屬性用于“自下而上”傳遞信息。綜合屬性由相應(yīng)語(yǔ)法分析樹(shù)中結(jié)點(diǎn)的分枝結(jié)點(diǎn)(即子結(jié)點(diǎn))屬性計(jì)算得到，其傳遞方向與繼承屬性相反，即沿語(yǔ)法分析樹(shù)向上傳遞，從分枝結(jié)點(diǎn)到根結(jié)點(diǎn)。第13頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

4.2.2屬性文法屬性文法： 在語(yǔ)言文法的基礎(chǔ)上，附加上文法符號(hào)的屬性計(jì)算規(guī)則形成的文法即屬性文法。屬性文法也是一種翻譯文法，屬性有助于更詳細(xì)地指定文法中的代碼生成動(dòng)作。第14頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月例1，簡(jiǎn)單算術(shù)表達(dá)式求值的屬性文法如下：產(chǎn)生式 語(yǔ)義規(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)*F T.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注意：E、T、F等符號(hào)的屬性由其各自相應(yīng)的右部符號(hào)決定，為綜合屬性。第15頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月例2：一簡(jiǎn)單變量類(lèi)型說(shuō)明的文法G[D]如下：G[D]：D→intL∣floatLL→L,id∣id其對(duì)應(yīng)的屬性文法為：產(chǎn)生式語(yǔ)義規(guī)則(1)?D→TL L.in=T.type(2)?T→int

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

或者floatid1，id2,…，idn第16頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月 屬性L.in=T.type表示L.in的屬性值由其兄弟節(jié)點(diǎn)屬性T.type決定，同樣L(1).in由其父節(jié)點(diǎn)屬性L.in決定，L.in和L(1).in均為繼承屬性。 由此可見(jiàn)，標(biāo)識(shí)符的類(lèi)型可以通過(guò)繼承屬性的復(fù)寫(xiě)規(guī)則來(lái)傳遞。例如，對(duì)輸入串inta,b，根據(jù)上述的語(yǔ)義規(guī)則，可在其生成的語(yǔ)法樹(shù)中看到用“→”表示的屬性傳遞情況，如圖4–3所示。第17頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月圖4–3屬性信息傳遞情況示意第18頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月4.3幾種常見(jiàn)的中間語(yǔ)言

4.3.1抽象語(yǔ)法樹(shù)抽象語(yǔ)法樹(shù)也稱(chēng)圖表示，是一種較為流行的中間語(yǔ)言表示形式。在抽象語(yǔ)法樹(shù)表示中，每一個(gè)葉結(jié)點(diǎn)都表示諸如常量或變量這樣的運(yùn)算對(duì)象，而其它內(nèi)部結(jié)點(diǎn)則表示運(yùn)算符和關(guān)鍵字。第19頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月例1：如賦值語(yǔ)句語(yǔ)法規(guī)則：

S→V=EV→id E→E-E|E*E|id|i

分析x=a?b*c的抽象語(yǔ)法樹(shù)如圖4–4(a)所示，而圖4–4(b)則是該賦值語(yǔ)句的普通語(yǔ)法樹(shù)。圖4–4x=a?b*c的語(yǔ)法樹(shù)第20頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月例2： 條件語(yǔ)句語(yǔ)法規(guī)則：

S→if(e)S1;elseS2

抽象語(yǔ)法樹(shù)形式為：抽象語(yǔ)法樹(shù)的一個(gè)顯著特點(diǎn)是結(jié)構(gòu)緊湊，容易構(gòu)造且結(jié)點(diǎn)數(shù)較少。gcc等編譯器把抽象語(yǔ)法樹(shù)當(dāng)作中間語(yǔ)言。第21頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

4.3.2逆波蘭表示法逆波蘭表示法： 是波蘭邏輯學(xué)家盧卡西維奇(Lukasiewicz)發(fā)明的一種表示表達(dá)式的方法，這種表示法把運(yùn)算量(操作數(shù))寫(xiě)在前面，把運(yùn)算符寫(xiě)在后面，因而又稱(chēng)后綴表示法。例如，把a(bǔ)+b寫(xiě)成ab+，把a(bǔ)*(b+c)寫(xiě)成abc+*。第22頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

1．表達(dá)式的逆波蘭表示表達(dá)式E的后綴表示的遞歸定義如下：

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

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

(3)如果E為(E1)形式，則E1的后綴表示即為E的后綴表示。第23頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月后綴表示中的計(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)算量。

2．程序語(yǔ)句的逆波蘭表示(自學(xué))第24頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

4.3.3三地址代碼三地址代碼的形式

x=yopzx、y和z為名字、常量或編譯時(shí)產(chǎn)生的臨時(shí)變量；op為運(yùn)算符。三地址代碼的每條語(yǔ)句通常最多包含三個(gè)地址，兩個(gè)用來(lái)存放運(yùn)算對(duì)象，一個(gè)用來(lái)存放運(yùn)算結(jié)果。第25頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月三地址語(yǔ)句只含有一個(gè)運(yùn)算符，因此多個(gè)運(yùn)算符組成的表達(dá)式必須用三地址語(yǔ)句序列來(lái)表示。三地址代碼是語(yǔ)法樹(shù)的一種線性表示(深度優(yōu)先遍歷語(yǔ)法樹(shù)可以得到對(duì)應(yīng)的三地址語(yǔ)句。)，在語(yǔ)法制導(dǎo)翻譯中常用臨時(shí)變量代替抽象語(yǔ)法樹(shù)中的內(nèi)部結(jié)點(diǎn)(相應(yīng)的三地址代碼亦然)。 如圖4–4(a)所示的語(yǔ)法樹(shù)用三地址代碼表示為：

t1=b*c

t2=a?t1 x=t2第26頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月2．三地址語(yǔ)句的種類(lèi) 三地址語(yǔ)句非常類(lèi)似于匯編代碼，它可以有符號(hào)標(biāo)號(hào)和各種控制流語(yǔ)句。常用的三地址語(yǔ)句有以下幾種：

(1)賦值語(yǔ)句：x=yopz，其中op為二目的算術(shù)運(yùn)算符或邏輯運(yùn)算符。x=opy，其中op為一目運(yùn)算符，如一目減uminus、邏輯否定not、移位運(yùn)算符以及將定點(diǎn)數(shù)轉(zhuǎn)換成浮點(diǎn)數(shù)的類(lèi)型轉(zhuǎn)換符。x=y，將y的值賦給χ。第27頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月x=y[i]：變址賦值語(yǔ)句，其中x、y、i均代表數(shù)據(jù)對(duì)象，表示把從地址y開(kāi)始的第i個(gè)地址單元中的值賦給x。x[i]=y則表示把y的值賦給從地址x開(kāi)始的第i個(gè)地址單元。地址和指針賦值語(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的值。第28頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月(2)轉(zhuǎn)移語(yǔ)句gotoL，無(wú)條件轉(zhuǎn)移語(yǔ)句，即下一個(gè)將被執(zhí)行的語(yǔ)句是標(biāo)號(hào)為L(zhǎng)的語(yǔ)句。

ifxropygotoL，條件轉(zhuǎn)移語(yǔ)句，其中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ǔ)句。第29頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月(3)過(guò)程調(diào)用和返回語(yǔ)句：parX和callP,n。源程序中的過(guò)程調(diào)用語(yǔ)句P(X1、X2、…，Xn)可用下列三地址代碼表示：

parX1 parX2 parXn callP,n

其中，整數(shù)n為實(shí)參個(gè)數(shù)。returny：過(guò)程返回語(yǔ)句，其中y為過(guò)程返回值。第30頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

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

1)四元式 四元式是具有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域?yàn)?/p>

(op，arg1，arg2，result) op為運(yùn)算符；arg1、arg2及result為指針，它們可 指向有關(guān)名字在符號(hào)表中的登記項(xiàng)或一臨時(shí)變量 (也可空缺)。第31頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月例：常用的三地址語(yǔ)句與相應(yīng)的四元式對(duì)應(yīng)如下：約定：凡只需一個(gè)運(yùn)算量的算符一律使用arg1。x=yopz 對(duì)應(yīng)(op,y,z,x)x=?y 對(duì)應(yīng)(uminus,y,_,x)x=y 對(duì)應(yīng)(=,y,_,x)parx1 對(duì)應(yīng)(par,x1,_,_)callP 對(duì)應(yīng)(call,_,_,P)gotoL 對(duì)應(yīng)(j,_,_,L)ifxropygotoL 對(duì)應(yīng)(jrop,x,y,L)第32頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

2)三元式三元式是具有三個(gè)域的記錄結(jié)構(gòu)，這三個(gè)域?yàn)?/p>

(op，arg1，arg2)

其中，op為運(yùn)算符；arg1、arg2既可指向有關(guān)名字 在符號(hào)表中的登記項(xiàng)或臨時(shí)變量，也可以指向三 元式表中的某一個(gè)三元式——四元式中的result域 用對(duì)應(yīng)三元式的指針代替。例如，相應(yīng)于賦值語(yǔ) 句a=(b+c)*(b+c)的三元式代碼為： ①(+,b,c) ②(+,b,c) ③(*,①,②) ④(=,a,③)第33頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月3)間接三元式間接碼表：在三元式代碼表的基礎(chǔ)上另設(shè)一張表，該表按運(yùn)算的次序列出相應(yīng)三元式在三元式表中的位置，這張表稱(chēng)為間接碼表。三元式表：只記錄不同的三元式語(yǔ)句，而間接碼表則表示由這些語(yǔ)句組成的運(yùn)算次序。例，賦值語(yǔ)句a=(b+c)*(b+c)對(duì)應(yīng)三元式表與間接碼表為： 三元式表：①(+,b,c) ②(*,①,①) ③(=,a,②)

間接碼表：①①②③第34頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月三地址表示方式與代碼優(yōu)化：三元式表示：代碼優(yōu)化階段調(diào)整三元式的運(yùn)算順序需修改指向這些三元式位置指針的相關(guān)三元式的指針值(arg1或arg2)。不利于代碼優(yōu)化。四元式：代碼調(diào)整時(shí)不需修改四元式的任何域值。間接三元式：通過(guò)間接碼表來(lái)描述語(yǔ)句的運(yùn)算次序，代碼調(diào)整時(shí)只需修改間接碼表，無(wú)需修改三元式的任何域值。第35頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月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)。

G[A]：A→i=E //非終結(jié)符A代表“賦值句”。

E→E+E∣E*E∣?E∣(E)∣i第36頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月 語(yǔ)義子程序所涉及的語(yǔ)義變量、語(yǔ)義過(guò)程及函數(shù)說(shuō)明如下：(1)語(yǔ)義變量E.place:表示存放E值的變量名在符號(hào)表中的入口地址或臨時(shí)變量名的整數(shù)碼。(2)語(yǔ)義函數(shù)newtemp(?):

創(chuàng)建一個(gè)臨時(shí)變量。返回一個(gè)代表新臨時(shí)變量的整數(shù)碼；臨時(shí)變量名按產(chǎn)生的順序可設(shè)為T(mén)1、T2、……。(3)語(yǔ)義過(guò)程emit(op,arg1,arg2,result):

產(chǎn)生一個(gè)四元式并填入四元式表中。(4)語(yǔ)義函數(shù)lookup()： 在符號(hào)表中查找變量，有則返回在符號(hào)表的入口指針，否則返回NULL。第37頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月文法G[A]中的每一個(gè)產(chǎn)生式的語(yǔ)義子程序如下。

(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); }如規(guī)約出左部E的時(shí)候，E的屬性值為一新值，需創(chuàng)建一個(gè)臨時(shí)變量，保存該新值第38頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月(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; elseerror(?);}第39頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月例4.1

試分析賦值語(yǔ)句X=?B*(C+D)的語(yǔ)法制導(dǎo)翻譯過(guò)程。

[解答]第40頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月表4.2賦值語(yǔ)句X=?B*(C+D)的翻譯過(guò)程輸入串歸約產(chǎn)生式符號(hào)棧語(yǔ)義棧(place)四元式X=?B*(C+D)#

#

_

=?B*(C+D)##i_X

?B*(C+D)#

#i=_X_

B*(C+D)#

#i=?_X__

*(C+D)#(6)#i=?i_X__B

*(C+D)#(4)#i=?E_X__B(uminus,B,_,T1)*(C+D)#

#i=E_X_T1

第41頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月(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__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

第42頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

4.4.2布爾表達(dá)式的翻譯布爾表達(dá)式的組成： 由運(yùn)算符與運(yùn)算對(duì)象組成。布爾運(yùn)算符：┐、∧、∨，或?yàn)閚ot、and和or(注：C語(yǔ)言中為！、&&和|?|)。布爾運(yùn)算符的運(yùn)算順序一般為┐、∧、∨，且∧和∨服從左結(jié)合。布爾算符的運(yùn)算優(yōu)先級(jí)低于任何關(guān)系運(yùn)算符運(yùn)算對(duì)象：為布爾變量，也可為常量或關(guān)系表達(dá)式。關(guān)系運(yùn)算符：<、<=、==、!=、>=、>等。關(guān)系運(yùn)算符的優(yōu)先級(jí)相同但不得結(jié)合，其運(yùn)算優(yōu)先級(jí)低于任何算術(shù)運(yùn)算符。，第43頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月布爾表達(dá)式文法G[E]：

G[E]：E→E∧E∣E∨E∣┐E∣(E)∣i∣iropi布爾表達(dá)式的計(jì)算：從左往右，按優(yōu)先級(jí)逐個(gè)計(jì)算根據(jù)布爾運(yùn)算的特點(diǎn)實(shí)施某種優(yōu)化，不必一步一步地計(jì)算布爾表達(dá)式中所有運(yùn)算對(duì)象的值，省略不影響運(yùn)算結(jié)果的運(yùn)算。 例如，在計(jì)算A∨B時(shí)，若計(jì)算出的A值為1，則B值就無(wú)需再計(jì)算了；因?yàn)椴还蹷的結(jié)果是什么，A∨B的值都為1。同理，在計(jì)算A∧B時(shí)若發(fā)現(xiàn)A值為0，則B值也無(wú)需計(jì)算，A∧B的值一定為0。第44頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月布爾表達(dá)式常用于條件或循環(huán)語(yǔ)句中表示條件，表達(dá)式為真時(shí)程序跳轉(zhuǎn)到一個(gè)”真出口”(對(duì)應(yīng)一條條件跳轉(zhuǎn)語(yǔ)句(jmp,條件,_,真出口)),否則跳轉(zhuǎn)到一個(gè)“假出口”。 如何確定一個(gè)表達(dá)式的真假出口的位置呢？第45頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月圖4–5E(1)∨E(2)和E(1)∧E(2)的翻譯圖(a)?E(1)∨E(2)；(b)?E(1)∧E(2)若E(1)為真，則立即知道E也為真，E(1)的真出口也就是整個(gè)E的真出口若E(1)為假，則E(2)必須被計(jì)值，E(2)的第一個(gè)四元式就是E(1)的假出口。第46頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月 在語(yǔ)法的分析過(guò)程中，一個(gè)布爾式的真假出口往往不能在產(chǎn)生四元式的同時(shí)就填上，我們只好把這種未完成的四元式的地址(編號(hào))作為E的語(yǔ)義值暫存起來(lái)，待到整個(gè)表達(dá)式的四元式產(chǎn)生完畢之后，再來(lái)填寫(xiě)這個(gè)未填入的轉(zhuǎn)移目標(biāo)。 對(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è)四元式，則它們可鏈接成如圖4–6所示的一條真值鏈(記作tc)。第47頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月圖4–6拉鏈法鏈接四元式示意第48頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月為了處理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。第49頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

merge(?)函數(shù)如下：merge(p1，p2){if(p2==0)return(p1);else{p=p2;while(四元式p的第四區(qū)段內(nèi)容不為0)第50頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

p=四元式p的第四區(qū)段內(nèi)容；把p1填進(jìn)四元式p的第四區(qū)段；

return(p2);}}Backpatch(?)函數(shù)如下：Backpatch(p,t){Q=p;while(Q!=0)第51頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

{q=四元式Q的第四區(qū)段內(nèi)容；把t填進(jìn)四元式Q的第四區(qū)段；

Q=q;}}第52頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月為了便于實(shí)現(xiàn)布爾表達(dá)式的語(yǔ)法制導(dǎo)翻譯，并在掃描到“∧”與“∨”時(shí)能及時(shí)回填一些已經(jīng)確定了的待填轉(zhuǎn)移目標(biāo)，我們將前述文法G[E]改寫(xiě)為下面的文法G‘[E]，以利于編制相應(yīng)的語(yǔ)義子程序：

G'[E]：E→EAE∣EBE∣┐E∣(E)∣i∣iropi EA→E∧ EB→E∨第53頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月這時(shí)，文法G'[E]的每個(gè)產(chǎn)生式和相應(yīng)的語(yǔ)義子程序如下：(1)?E→i{E.tc=nxq;E.fc=nxq+1; emit(jnz,entry(i),_,0); emit(j,_,_,0);}(2)?E→i(1)ropi(2){E.tc=nxq;E.fc=nxq+1; emit(jrop,entry(i(1)),entry(i(2)),0); emit(j,_,_,0);}(3)?E→(E(1)){E.tc=E(1).tc;E.fc=E(1).fc;}(4)?E→┐E(1){E.tc=E(1).fc;E.fc=E(1).tc;}第54頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月(5)?EA→E(1)∧

{Backpatch(E(1).tc,nxq); EA.fc=E(1).fc;}(6)?E→EAE(2)

{E.tc=E(2).tc; E.fc=merge(EA.fc，E(2).fc);}(7)?EB→E(1)∨

{Backpatch(E(1).fc，nxq); EB.tc=E(1).tc;}(8)?E→EBE(2) {E.fc=E(2).fc;

E.tc=merge(EB.tc，E(2).tc);}第55頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月例4.2

試給出布爾表達(dá)式a∧b∨c≥d作為控制條件的四元式中間代碼。

[解答]設(shè)四元式序號(hào)從100開(kāi)始，則布爾表達(dá)式a∧b∨c≥d的分析過(guò)程如圖4–7所示。第56頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月圖4–7表達(dá)式a∧b∨c≥d分析示意注意此時(shí)合并兩條假出口鏈,結(jié)果103（j,_,_,101)注意此時(shí)合并兩條真出口鏈,結(jié)果104（j>=,c,d,102)第57頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月即：100(jnz，a，_，102)101(j，_，_，104)102(jnz，b，_，106)103(j，_，_，104)104(j≥，c，d，106)105(j，_，_，q)T:106

F:q第58頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月圖4–8a∧b∨c≥d的翻譯圖第59頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月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)。第60頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

4.5.1條件語(yǔ)句if的翻譯

1．條件語(yǔ)句if的代碼結(jié)構(gòu)

if(E)S1;elseS2

布爾表達(dá)式E的作用僅在于控制對(duì)S1和S2的選擇，因此可將作為轉(zhuǎn)移條件的布爾式E賦予兩種“出口”：一是“真”出口，出向S1；一是“假”出口，出向S2。條件語(yǔ)句可以翻譯成如圖4–9所示的代碼結(jié)構(gòu)。第61頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月圖4–9條件語(yǔ)句if(E)S1;elseS2

的代碼結(jié)構(gòu)非終結(jié)符E具有兩項(xiàng)語(yǔ)義值E.tc和E.fc，它們分別指出了尚待回填真假出口的四元式串。E的“真”出口E.tc只有在掃描完布爾表達(dá)式E后的“)”時(shí)才能知道非終結(jié)符E具有兩項(xiàng)語(yǔ)義值E.tc和E.fc，“假”出口E.fc則需要處理過(guò)S1之后并且到else時(shí)才能明確。必須把E.fc的值傳下去，以便到達(dá)相應(yīng)的else時(shí)才進(jìn)行回填。S1語(yǔ)句執(zhí)行完就意味著整個(gè)if-else語(yǔ)句也已執(zhí)行完畢，在S1的編碼之后應(yīng)產(chǎn)生一條無(wú)條件轉(zhuǎn)移指令。在完成S2的翻譯之前，這條無(wú)條件轉(zhuǎn)移指令的轉(zhuǎn)移目標(biāo)是不知道的，甚至在翻譯完S2之后仍無(wú)法確定，需要把該條轉(zhuǎn)移四元式編號(hào)傳下去，在后續(xù)代碼翻譯的某個(gè)時(shí)刻填入轉(zhuǎn)移地址。第62頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月代碼結(jié)構(gòu)說(shuō)明：

(1)非終結(jié)符E具有兩項(xiàng)語(yǔ)義值E.tc和E.fc，它們分別指出了尚待回填真假出口的四元式串。E的“真”出口只有在掃描完布爾表達(dá)式E后的“)”時(shí)才能知道，而它的“假”出口則需要處理過(guò)S1之后并且到else時(shí)才能明確。必須把E.fc的值傳下去，以便到達(dá)相應(yīng)的else時(shí)才進(jìn)行回填。

(2)S1語(yǔ)句執(zhí)行完就意味著整個(gè)if-else語(yǔ)句也已執(zhí)行完畢，在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ú)法確定，需要傳下去，在外層代碼翻譯的某個(gè)時(shí)刻填入。第63頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

2．條件語(yǔ)句if的文法和語(yǔ)義子程序的設(shè)計(jì)條件語(yǔ)句if的文法G[S]如下：

G[S]：S→if(E)S(1) S→if(E)S(1);elseS(2)

為了在掃描條件語(yǔ)句過(guò)程中不失時(shí)機(jī)地處理和回填有關(guān)信息，可將G[S]改寫(xiě)為如下的G'[S]：

G‘[S]： (1)?S→CS(1) (2)?C→if(E) (3)?S→TpS(2) (4)?TP→CS(1);else第64頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月根據(jù)程序語(yǔ)言的處理順序來(lái)看語(yǔ)句的翻譯。用(2)C→if(E)進(jìn)行歸約。

C→if(E){Backpatch(E.tc,nxq);C.chain=E.fc;}如條件語(yǔ)句為不含else的條件句，用產(chǎn)生式(1)S→CS(1)繼續(xù)向上歸約。

S→CS(1){S.chain=merge(C.chain,S(1).chain)}“)”后的第一個(gè)四元式地址回填至E的真出口E的假出口地址則作為待填信息放在C的語(yǔ)義變量C.chain(不然的話，if(E)規(guī)約完E的屬性值就消失了)E的假出口、S的出口S(1)的出口相同未定，將C.chain和S(1).chain一起作為S的待填信息鏈用函數(shù)merge鏈在一起保留在S的語(yǔ)義值S.chain中第65頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月 條件語(yǔ)句為不含else的條件句，則在產(chǎn)生式(1)、(2)歸約為S后即可以用下一個(gè)將要產(chǎn)生的四元式地址(即S的出口地址)來(lái)回填S的出口地址鏈(即S.chain)；在if語(yǔ)句的下一條語(yǔ)句翻譯前完成。如果條件語(yǔ)句為if-else形式，用產(chǎn)生式(4)TP→CS(1);else歸約,產(chǎn)生一個(gè)無(wú)條件轉(zhuǎn)移四元式。

Tp→CS(1);else{ q=nxq;? emit(j,_,_,0);? Tp.chain=merge(S.chain,q); Backpatch(C.chain,nxq); }(1)S(1)語(yǔ)句序列后產(chǎn)生一個(gè)無(wú)條件轉(zhuǎn)移四元式(見(jiàn)圖4–9的結(jié)構(gòu)框圖)，該四元式的地址(即標(biāo)號(hào))保留在q中，以便待獲知要轉(zhuǎn)移的地址后再進(jìn)行回填(2)q的出口也就是整個(gè)條件語(yǔ)句的出口，將其與S.chain鏈接后掛入鏈頭為T(mén)p.chain的鏈中。(3)(q+1)地址即為else后(也即S(2))的第一個(gè)四元式地址，是E的假出口地址，因此應(yīng)將此地址回填到E.fc即C.chain中第66頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月用產(chǎn)生式(3)S→TpS(2)歸約。當(dāng)，即

S→TpS(2){S.chain=merge(Tp.chain,S(2).chain);}S、Tp和S(2)的出口地址一樣，在翻譯完if語(yǔ)句之后的后繼語(yǔ)句才可以填入，可能(非一定)是if語(yǔ)句之后的后繼語(yǔ)句翻譯得到的四元式地址，故將Tp.chain與S(2).chain鏈接后掛入鏈頭為S.chain的鏈中,以便在后續(xù)翻譯過(guò)程中回填跳轉(zhuǎn)地址(如標(biāo)號(hào)為p的四元式的跳轉(zhuǎn)地址)。第67頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

4.5.2條件循環(huán)語(yǔ)句while的翻譯

1．條件循環(huán)語(yǔ)句while的代碼結(jié)構(gòu)條件循環(huán)語(yǔ)句while(E)S(1)通常被翻譯成圖4–10所示的代碼結(jié)構(gòu)。第68頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月圖4–10條件循環(huán)while語(yǔ)句的代碼結(jié)構(gòu)布爾表達(dá)式E的“真”出口出向S(1)代碼段的第一個(gè)四元式，而E的“假”出口將導(dǎo)致程序控制離開(kāi)整個(gè)while語(yǔ)句而去執(zhí)行while語(yǔ)句之后的后繼語(yǔ)句。緊接S(1)代碼段之后應(yīng)產(chǎn)生一條轉(zhuǎn)向測(cè)試E的無(wú)條件轉(zhuǎn)移指令；第69頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

2．條件循環(huán)語(yǔ)句while的文法和語(yǔ)義子程序設(shè)計(jì)為了易于及時(shí)處理和回填，給出條件循環(huán)語(yǔ)句while的文法G[S]如下：

G[S]：(1)?S→WdS(1)(2)?Wd→W(E)(3)?W→while根據(jù)while語(yǔ)句的掃描加工順序，看語(yǔ)義處理動(dòng)作：第70頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月首先用產(chǎn)生式(3)W→while進(jìn)行歸約

(1)?W→while{W.quad=nxq;}nxq即為E的第一個(gè)四元式地址，我們將其保留在W.quad中(后續(xù)語(yǔ)句翻譯過(guò)程中nxq的值將發(fā)生變化)，S(1)后的無(wú)條件跳轉(zhuǎn)語(yǔ)句將要跳轉(zhuǎn)到該地址。第71頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月繼續(xù)掃描并用Wd→W(E)歸約

(2)?Wd→W(E)?{Backpatch(E.tc,nxq); Wd.chain=E.fc; Wd.quad=W.quad;}掃描完“)”后可以用Backpatch(E.tc,nxq)回填E.tc值E.fc作為待填信息用Wd.chain=E.fc傳下去(不然的話，Wd→W(E)規(guī)約完E的屬性值就消失了)E的第一個(gè)四元式地址也通過(guò)W.quad向Wd傳遞第72頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月用產(chǎn)生式(1)S→WdS(1)歸約時(shí)，S(1)語(yǔ)句序列的全部四元式已經(jīng)產(chǎn)生。

(3)?S→WdS(1){Backpatch(S(1).chain,Wd.quad);emit((j,_,_,Wd.quad);S.chain=Wd.chain;}無(wú)條件返回到E的第一個(gè)四元式繼續(xù)對(duì)條件E進(jìn)行測(cè)試S(1)語(yǔ)句序列中的跳轉(zhuǎn)出口語(yǔ)句地址也應(yīng)該是E的第一個(gè)四元式，所以回填S(1).chain無(wú)條件轉(zhuǎn)移語(yǔ)句(j,_,_,Wd.quad)之后即為while語(yǔ)句的后繼語(yǔ)句，而這個(gè)后繼語(yǔ)句中的第一個(gè)四元式地址即為while語(yǔ)句E的假出口，保存在Wd.chain中。考慮到嵌套情況，將Wd.chain信息作為整個(gè)while語(yǔ)句的出口保留在S.chain中，以便適當(dāng)時(shí)機(jī)回填。第73頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月翻譯示例例4.3

將下面語(yǔ)句翻譯成四元式：

while(A<B)if(C<D)X=Y+Z第74頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月圖4–11例4.3的代碼結(jié)構(gòu)圖[解答]我們首先畫(huà)出該語(yǔ)句對(duì)應(yīng)的代碼結(jié)構(gòu)圖如圖4–11所示。第75頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月按照文法及加工子程序(包括前述賦值句和布爾表達(dá)式的翻譯法)得到該語(yǔ)句對(duì)應(yīng)的四元式序列如下：100(j<，A，B，102)/*E1為T(mén)*/101(j，_，_，107)/*E1為F*/

102(j<，C，D，104)/*E2為T(mén)*/103(j<，_，_，106)/*E2為F*/104(+，Y，Z，T)105(=，T，_，X)106(j，_，_，100)/*轉(zhuǎn)對(duì)E的測(cè)試*/

107第76頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月4.5.3三種基本控制結(jié)構(gòu)的翻譯1．三種基本控制結(jié)構(gòu)的文法我們給出三種基本控制結(jié)構(gòu)的文法G[S]如下：

G[S]：(1)S→CS(2)∣TPS(3)∣WdS(4)∣{L}(5)∣A/*A代表賦值語(yǔ)句*/(6)L→LSS第77頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

(7)∣S(8)C→if(E)(9)TP→CS;else(10)Wd→W(E)(11)W→while(12)LS→L;第78頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月G[S]中各產(chǎn)生式對(duì)應(yīng)的語(yǔ)義子程序如下：(1)S→CS(1) {S.chain=merge(C.chain,S(1).chain);}(2)S→TPS(2) {S.chain=merge(TP.chain,S(2).chain);}(3)S→WdS(1) {Backpatch(S(1).chain,Wd.quad); emit(j,_,_,Wd.quad); S.chain=Wd.chain;}(4)S→{L} {S.chain=L.chain};}(5)S→A {S.chain=0;/*空鏈*/}第79頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月(6)L→LSS(1) {L.chain=S(1).chain}(7)L→S {L.chain=S.chain}(8)C→if(E) {Backpatch(E.tc,nxq); C.chain=E.fc;}(9)TP→CS(1);else{q=nxq; emit(j,_,_,0); Backpatch(C.chain,nxq); TP.chain=merge(S(1).chain,q);}第80頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月(10)W→while{W.quad=nxq;}(11)Wd→W(E){Backpatch(E.tc,nxq); Wd.chain=E.fc; Wd.quad=W.quad;}(12)LS→L;{Backpatch(L.chain,nxq);}第81頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月例4.4

按已學(xué)過(guò)的文法及語(yǔ)義加工子程序分析下述語(yǔ)句語(yǔ)義加工的全過(guò)程：while(x<y)x=x+1[解答]語(yǔ)句while(x<y)x=x+1的語(yǔ)義加工過(guò)程見(jiàn)表4.3所示。第82頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月表4.3while(x<y)x=x+1#的語(yǔ)義加工過(guò)程輸入串符號(hào)棧語(yǔ)義棧（place）語(yǔ)義動(dòng)作四元式while(x<y)…#_移進(jìn)

(x<y)x=x+1##while__歸約

w.quad=100

(x<y)x=x+1##W__移進(jìn)

x<y)x=x+1##W(___移進(jìn)

<y)x=x+1##W(x____歸約（參見(jiàn)賦值句文法）

第83頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月E1.tc=100

i1.place=entry(x)

<y)x=x+1##W(i1___x移進(jìn)

y)x=x+1##W(i1<___x_移進(jìn)

)x=x+1##W(i1<y___x__歸約

i2.place=entry(y)

)x=x+1##W(i1<i2___x_y歸約（參見(jiàn)布爾表達(dá)式文法）

E1.fc=101

102

100(j<,x,y,0)

105

101(j,_,_,0))x=x+1##W(E1____移進(jìn)

x=x+1##W(E1)_____歸約

第84頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

Backpatch(100,102)

Wd.chain=101

x=x+1##Wd__移進(jìn)

=x+1##Wdx___歸約

i3.place=entry(x)

=x+1##Wdi3__x移進(jìn)

x+1##Wdi3=__x_移進(jìn)

+1##Wdi3=x__x__歸約

E2.place=entry(x)

+1##Wdi3=E2__x_x移進(jìn)

1##Wdi3=E2+__x_x_移進(jìn)

##Wdi3=E2+1__x_x__歸約

第85頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

E3.place=entry(1)

##Wdi3=E2+E3__x_x_1歸約

E4.place=T1

102(+,x,1,T1)##Wdi3=E4__x__歸約

103(=,T1,_,x)##WdS(1)___歸約

Backpatch(S(1).chain,100)

(因無(wú)S(1).chain故不回填)

104(j,_,_,100)

S.chain=101

##S__while語(yǔ)句分析結(jié)束

外層返填：

由LS→L歸約得：

Backpatch(S.chain,105)

第86頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月<以下自學(xué)>4.5.4多分支控制語(yǔ)句case的翻譯多分支控制語(yǔ)句具有如下形式的語(yǔ)法結(jié)構(gòu)：switch(E){ casec1:S1;casec2:S2;caseci:Si;casecn:Sn;default:Sn+1}第87頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月其中n≥1。switch語(yǔ)句的語(yǔ)義是：先計(jì)算整型表達(dá)式E的值，然后將表達(dá)式的值依次和case后的常數(shù)ci比較，當(dāng)與某常數(shù)ci相等時(shí)就執(zhí)行語(yǔ)句Si，并結(jié)束多分支控制語(yǔ)句；若與諸常數(shù)均不相等，則執(zhí)行語(yǔ)句Sn+1。多分支控制語(yǔ)句switch常見(jiàn)的中間代碼形式如下：

E計(jì)值后存放在臨時(shí)單元T的中間代碼；第88頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

gototest；P1: S1的中間代碼；

gotonext；P2: S2的中間代碼；

gotonext；

Pn: Sn的中間代碼；

gotonext；第89頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月default: Sn+1的中間代碼；

gotonext；test: if(T==c1)gotoP1；

if(T==c2)gotoP2；

if(T==cn)gotoPn；

if(T=='default')gotoPn+1；next:第90頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月進(jìn)行語(yǔ)義加工處理時(shí)應(yīng)先設(shè)置一空隊(duì)列queue，當(dāng)遇到ci時(shí)，將這個(gè)ci連同nxq(指向標(biāo)號(hào)ci后語(yǔ)句Si的入口)送入隊(duì)列queue，然后按通常的辦法產(chǎn)生語(yǔ)句Si的四元式。需要注意的是，在Si的四元式之后要有一個(gè)gotonext的四元式。當(dāng)處理完default:Sn+1之后，應(yīng)產(chǎn)生以test為標(biāo)號(hào)的n個(gè)條件轉(zhuǎn)移語(yǔ)句的四元式。這時(shí)，逐項(xiàng)讀出queue的內(nèi)容即可形成如下的四元式序列：第91頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月(case,c1,P1,_?)(case,c2,P2,_?)

(case,cn,Pn,_?)(case,T.place,default,_?)

其中，T.place是存放E值的臨時(shí)變量名，每個(gè)四元式(case,ci,Pi,_?)實(shí)際上代表一個(gè)如下的條件語(yǔ)句：

if(T==ci)gotoPi第92頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月為了便于語(yǔ)法制導(dǎo)翻譯，我們給出了switch語(yǔ)句的文法和相應(yīng)的語(yǔ)義加工子程序如下：(1)?A→switch(E)?{T.place=E.place；F1.quad=nxq；emit(j,_,_,0)； /*轉(zhuǎn)向test*/}(2)?B→A{casec?{P=1；queue[P].label=c；queue[P].quad=nxq；}第93頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月(3)?D→B:S?{生成S的四元式序列；Backpatch(S.chain,nxq)；B.quad=nxq；emit(j,_,_,0)； /*轉(zhuǎn)向next*/}(4)?D→F:S{生成S的四元式序列；Backpatch(S.chain,nxq)；B.quad=nxq；emit(j,_,_,0)； /*轉(zhuǎn)向next*/F.quad=merge(B.quad,F.quad)；/*轉(zhuǎn)向next的語(yǔ)句拉成鏈*/}第94頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月(5)?F→D;casec?{P=P+1；queue[P].label=c；queue[P].quad=nxq；}(6)?S→D;default:S}{生成S的四元式序列；Backpatch(S.chain,nxq)；B.quad=nxq；第95頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月emit(j,_,_,0)；F.quad=merge(B.quad,F.quad)；

/*形成轉(zhuǎn)向next的鏈?zhǔn)?/}P=P+1；queue[P].label='default'；queue[P].quad=nxq；F3.quad=nxq； /*指向標(biāo)號(hào)test*/m=1；do{ci=queue[m].label；第96頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

Pi=queue[m].quad；

m=m+1；

if(ci!='default')emit(case,ci,Pi,_)elseemit(case,T.place,default,_)}while(m<=P+1)；Backpatch(F1.quad,F3.quad)；Backpatch(F.quad,nxq)；

/*填寫(xiě)所有轉(zhuǎn)向next語(yǔ)句的轉(zhuǎn)移地址*/}第97頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

4.5.5語(yǔ)句標(biāo)號(hào)和轉(zhuǎn)移語(yǔ)句的翻譯程序語(yǔ)言中直接改變控制流程的語(yǔ)句是gotoL語(yǔ)句；其中L是源程序中的語(yǔ)句標(biāo)號(hào)。標(biāo)號(hào)L在源程序中可以以?xún)煞N方式出現(xiàn)：

(1)定義性出現(xiàn)。定義性出現(xiàn)的語(yǔ)句形式為

L：S

此時(shí)，帶標(biāo)號(hào)的語(yǔ)句S所生成的第一個(gè)四元式地址即為標(biāo)號(hào)L的值。第98頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

(2)引用性出現(xiàn)。引用性出現(xiàn)的語(yǔ)句形式為

gotoL

它引用L的值作為四元式(j,_,_,L)中轉(zhuǎn)向的目標(biāo)地址。對(duì)標(biāo)號(hào)L的處理方法是：當(dāng)標(biāo)號(hào)L定義性出現(xiàn)時(shí)，應(yīng)將標(biāo)號(hào)此時(shí)對(duì)應(yīng)的四元式地址(即標(biāo)號(hào)L的值)登錄到符號(hào)表中L所對(duì)應(yīng)的項(xiàng)；當(dāng)標(biāo)號(hào)L引用性出現(xiàn)時(shí)，則引用符號(hào)表中該標(biāo)號(hào)L的值。第99頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月顯然，在源程序中，如果標(biāo)號(hào)的定義性出現(xiàn)在前而引用性出現(xiàn)在后，即先定值后引用(稱(chēng)為向后引用)，則填、查符號(hào)表及將轉(zhuǎn)移語(yǔ)句翻譯成四元式很容易。但是，如果標(biāo)號(hào)引用性出現(xiàn)在前而定義性出現(xiàn)在后(稱(chēng)為向前引用)，則引用時(shí)不可能從符號(hào)表中獲得標(biāo)號(hào)L的值，此時(shí)只能生成有待回填的四元式(j,_,_,0)，等到向前翻譯到標(biāo)號(hào)L定義性出現(xiàn)時(shí)，再將標(biāo)號(hào)L的值回填到待填的四元式中。第100頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月翻譯gotoL語(yǔ)句時(shí)需要查符號(hào)表，看L是否定值，有以下幾種情況：

(1)?L已經(jīng)定值，即L.value為符號(hào)表中所記錄的L值，這時(shí)生成(j,_,_,L.value)語(yǔ)句。

(2)在符號(hào)表中未出現(xiàn)標(biāo)號(hào)L項(xiàng)，則gotoL中的L是首次出現(xiàn)，故生成(j,_,_,0)形式的語(yǔ)句并在符號(hào)表中登錄L項(xiàng)，給L項(xiàng)標(biāo)記為“未定值”并將四元式(j,_,_,0)的地址作為L(zhǎng)的值記入符號(hào)表(作為L(zhǎng)引用鏈的鏈頭)，以待L定值后回填。第101頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

(3)在符號(hào)表中已有標(biāo)號(hào)L項(xiàng)但未定值，此時(shí)的gotoL語(yǔ)句并非首次出現(xiàn)，故生成四元式(j,_,_,0)并將其地址掛入到L的引用鏈中，待L定值后再進(jìn)行回填。翻譯語(yǔ)句L：S時(shí)，在識(shí)別L后也要查符號(hào)表。如L為首次出現(xiàn)，則在符號(hào)表中建立L項(xiàng)，將此時(shí)的nxq值作為L(zhǎng)的值登入符號(hào)表并置“已定值”標(biāo)記；如果符號(hào)表中已有L項(xiàng)且標(biāo)記為“未定值”，這意味著是向前引用情況，應(yīng)將此時(shí)的nxq值作為L(zhǎng)的值登入符號(hào)表并置“已定值”，同時(shí)以此值回填L的引用鏈；若查找符號(hào)表發(fā)現(xiàn)L已定值，則表示L出現(xiàn)了重復(fù)定義的錯(cuò)誤。第102頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月4.6數(shù)組元素的翻譯

4.6.1數(shù)組元素的地址計(jì)算及中間代碼形式在表達(dá)式或賦值語(yǔ)句中若出現(xiàn)數(shù)組元素，則翻譯時(shí)將牽涉到數(shù)組元素的地址計(jì)算。數(shù)組在存儲(chǔ)器中的存放方式?jīng)Q定了數(shù)組元素的地址計(jì)算法，從而也決定了應(yīng)該產(chǎn)生什么樣的中間代碼。數(shù)組在存儲(chǔ)器中的存放方式通常有按行存放和按列存放兩種。在此，我們討論以行為主序存放方式的數(shù)組元素地址計(jì)算方法。第103頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月數(shù)組的一般定義為A[l1:u1,l2:u2,…,lk:uk,…,ln:un]

其中，A是數(shù)組名，lk是數(shù)組A第k維的下界，uk是第k維的上界。為簡(jiǎn)單起見(jiàn)，假定數(shù)組A中每個(gè)元素的存儲(chǔ)長(zhǎng)度為1，a是數(shù)組A的首地址，則數(shù)組元素A[i1,i2,…in]的地址D的計(jì)算公式如下：D=a+(i1?l1)d2d3…dn+(i2?l2)d3d4…dn+…+(in-1?ln?1)dn+(in?ln)第104頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月其中，di=ui?li+1(i=1,2,…,n?1)。整理后得到D=CONSPART+VARPART

其中，CONSPART=a?(…((l1d2+l2)d3+l3)d4+…+ln-1)dn+lnVARPART=(…((i1d2+i2)d3+i3)d4+…+in?1dn)+inCONSPART中的各項(xiàng)(如li、di(i=1,2,…,n))在處理說(shuō)明語(yǔ)句時(shí)就可以得到，因此CONSPART值可在編譯時(shí)計(jì)算出來(lái)后保存在數(shù)組A的相關(guān)符號(hào)表項(xiàng)里。此后，在計(jì)算數(shù)組A的元素地址時(shí)僅需計(jì)算VARPART值而直接引用CONSPART值。第105頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月實(shí)現(xiàn)數(shù)組元素的地址計(jì)算時(shí)，將產(chǎn)生兩組四元式序列：一組計(jì)算CONSPART，其值存放在臨時(shí)變量T中；另一組計(jì)算VARPART，其值存放在臨時(shí)變量T1中，即用T1[T]表示數(shù)組元素的地址。這樣，對(duì)數(shù)組元素的引用和賦值就有如下兩種不同的四元式：

(1)變址存數(shù)：若有T1[T]=X，則可以用四元式([?]=，X，_，T1[T])表示。

(2)變址取數(shù)：若有X=T1[T]，則可用四元式(=[?]，T1[T]，_，X)表示。第106頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月

4.6.2賦值語(yǔ)句中數(shù)組元素的翻譯為了便于語(yǔ)法制導(dǎo)翻譯，我們定義一個(gè)含有數(shù)組元素的賦值語(yǔ)句文法G[A]如下：

G[A]：(1)?A→V=E(2)?V→i[elist]∣i(3)?elist→elist,E∣E(4)?E→E+E∣(E)∣V第107頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月其中，A代表賦值語(yǔ)句；V代表變量名；E代表算術(shù)表達(dá)式；elist代表由逗號(hào)分隔的表達(dá)式，它表示數(shù)組的一維下標(biāo)；i代表簡(jiǎn)單變量名或數(shù)組名。在用產(chǎn)生式(2)、(3)進(jìn)行歸約時(shí)，為了能夠及時(shí)計(jì)算數(shù)組元素的VARPART，我們將產(chǎn)生式(2)、(3)改寫(xiě)為：(2')?V→elist]∣i(3')?elist→elist,E∣i[E第108頁(yè)，課件共145頁(yè)，創(chuàng)作于2023年2月把數(shù)組名i和最左的下標(biāo)式寫(xiě)在一起的目的是在整個(gè)下標(biāo)串elist的翻譯過(guò)程中隨時(shí)都能知道數(shù)組名i的符號(hào)表入口，從而隨時(shí)能夠了解登記在符號(hào)表中有關(guān)數(shù)組i的全部信息。為產(chǎn)生計(jì)算VARPART的四元式序列，還需要設(shè)置如下的語(yǔ)義變量和函數(shù)：(1)?elist.ARRAY：表示數(shù)組名在符號(hào)表的入口。(2)?elist.DIM：計(jì)數(shù)器，用來(lái)計(jì)算數(shù)組的維數(shù)。(3)?elist.place：登錄已生成VARPART中間結(jié)果的單元名字在符號(hào)表中的存放位置，或是一個(gè)臨時(shí)變量的整數(shù)碼。第109頁(yè)，課件共145