43-幾種常見的中間語言解析課件

1、編 譯 原 理 Principle of Compiling郭 一 晶 廈門大學(xué)嘉庚學(xué)院 2008 年 9 月10/11/20221編 譯 原 理 Principle of Compi4.3 幾種常見的中間語言4.3.1 抽象語法樹4.3.2逆波蘭表示法4.3.3 三地址代碼10/11/202224.3 幾種常見的中間語言4.3.1 抽象語法樹10/為什么使用中間代碼?Intermediate code；Intermediate representation；Intermediate language使用中間代碼的優(yōu)點(diǎn)與機(jī)器無關(guān)，便于移植。便于進(jìn)行獨(dú)立于機(jī)器的代碼優(yōu)化。介紹幾種常用的中間表示圖

2、形表示: 語法樹逆波蘭表示法: 后綴表示三地址代碼用語法制導(dǎo)定義和翻譯方案的方法將源程序翻譯成中間形式10/11/20223為什么使用中間代碼?Intermediate code；In4.3.1 抽象語法樹抽象語法樹(Abstract syntax tree)：每一個葉結(jié)點(diǎn)都表示諸如常量或變量這樣的運(yùn)算對象(操作數(shù))，而其它內(nèi)部結(jié)點(diǎn)則表示運(yùn)算符(操作符) 。注意，語法樹是分析樹的壓縮表示：算符和關(guān)鍵字作為內(nèi)部結(jié)點(diǎn)。 10/11/202244.3.1 抽象語法樹抽象語法樹(Abstract s語法規(guī)則中包含的某些符號可能起標(biāo)點(diǎn)符號作用也可能起解釋作用。如賦值語句語法規(guī)則： SV=e 其中的賦值號

3、“=”僅起標(biāo)點(diǎn)符號作用，其目的是把V與e分開；如條件語句語法規(guī)則：Sif(e)S1; else S2 保留字符號if和else起注釋作用，說明當(dāng)布爾表達(dá)式e為真時執(zhí)行S1，否則執(zhí)行S2；而“；”僅起標(biāo)點(diǎn)符號作用。10/11/20225語法規(guī)則中包含的某些符號可能起標(biāo)點(diǎn)符號作用也可能起解釋作用。賦值語句x=ab*c的抽象語法樹如圖44(a)所示，而圖44(b)則是該賦值語句的普通語法樹。assignx-a*bc(a)SVE=xEE EE*abc(b)10/11/20226賦值語句x=ab*c的抽象語法樹如圖44(a)所示，而圖If (e) S1; else S2 和8+5*2 對應(yīng)的語法樹：if

4、-then-elseeS1S2+*258龍書P190提到了如何構(gòu)造表達(dá)式的語法樹。10/11/20227If (e) S1; else S2 和8+5*2 對應(yīng)的4.3.2逆波蘭表示法逆波蘭表示法是波蘭邏輯學(xué)家盧卡西維奇(Lukasiewicz)發(fā)明的一種表示表達(dá)式的方法，這種表示法把運(yùn)算量(操作數(shù))寫在前面，把運(yùn)算符寫在后面，因而又稱后綴表示法。例如，把a(bǔ)+b寫成ab+，把a(bǔ)*(b+c)寫成abc+*。10/11/202284.3.2逆波蘭表示法逆波蘭表示法是波蘭邏輯學(xué)家盧卡西維奇1表達(dá)式的逆波蘭表示表達(dá)式E的后綴表示的遞歸定義如下： (1) 如果E是變量或常數(shù)，則E的后綴表示即E自身。 (

5、2) 如果E為E1 op E2形式，則它的后綴表示為E1E2op；其中op是二元運(yùn)算符，而E1、E2分別又是E1和E2的后綴表示。若op為一元運(yùn)算符，則E1和E1為空。 (3) 如果E為(E1)形式，則E1的后綴表示即為E的后綴表示。P96 例4.1。10/11/202291表達(dá)式的逆波蘭表示表達(dá)式E的后綴表示的遞歸定義如下：10上述定義的實(shí)質(zhì)：操作數(shù)出現(xiàn)的順序與原來一致，而運(yùn)算符則按運(yùn)算先后的順序放入相應(yīng)的操作數(shù)之后(即運(yùn)算符先后的順序發(fā)生變化)。這種表示已不需要用括號來規(guī)定運(yùn)算的順序。后綴表示中的計(jì)值用棧實(shí)現(xiàn)非常方便。一般的計(jì)算過程是自左至右掃描后綴表達(dá)式，每碰到運(yùn)算數(shù)就把它推進(jìn)棧，每碰到

6、K目運(yùn)算符就把它作用于棧頂?shù)腒個運(yùn)算量，并用運(yùn)算的結(jié)果(即一個運(yùn)算量)來取代棧頂?shù)腒個運(yùn)算數(shù)?？梢酝貜V到表示賦值語句和控制語句，但很難用棧來描述它的計(jì)算。10/11/202210上述定義的實(shí)質(zhì)：操作數(shù)出現(xiàn)的順序與原來一致，而運(yùn)算符則按運(yùn)算 2程序語句的逆波蘭表示自學(xué)10/11/202211 2程序語句的逆波蘭表示自學(xué)10/9/2022114.3.3 三地址代碼1三地址代碼的形式三地址代碼語句的一般形式為 x=y op z操作數(shù)：名字、常量或編譯時產(chǎn)生的臨時變量；op：運(yùn)算符，如+ - * / % uminus not and or xor = if-goto三地址代碼的每條語句通常包含三個地址

7、，兩個用來存放運(yùn)算對象，一個用來存放運(yùn)算結(jié)果。10/11/2022124.3.3 三地址代碼1三地址代碼的形式10/9/2如表達(dá)式x+y*z的三地址代碼為：t1 = y*zt2 = x+t1其中，t1和t2是編譯時產(chǎn)生的臨時變量。三地址代碼是語法樹的一種線性表示，如圖44(a)所示的語法樹用三地址代碼表示為：t1= b*ct2 = a t1x = t210/11/202213如表達(dá)式x+y*z的三地址代碼為：10/9/2022132三地址語句的種類作為中間語言的三地址語句非常類似于匯編代碼，它可以有符號標(biāo)號和各種控制流語句。常用的三地址語句有以下幾種：(1) x=y op z形式的賦值語句，其

8、中op為二目的算術(shù)運(yùn)算符或邏輯運(yùn)算符。(2) x=op y形式的賦值語句，其中op為一目運(yùn)算符，如一目減uminus、邏輯否定not、移位運(yùn)算符以及將定點(diǎn)數(shù)轉(zhuǎn)換成浮點(diǎn)數(shù)的類型轉(zhuǎn)換符。(3) x=y形式的賦值語句，將y的值賦給。10/11/2022142三地址語句的種類作為中間語言的三地址語句非常類似于匯編代(4) 無條件轉(zhuǎn)移語句goto L，即下一個將被執(zhí)行的語句是標(biāo)號為L的語句。(5) 條件轉(zhuǎn)移語句if x rop y goto L，其中rop為關(guān)系運(yùn)算符，如、=等。若x和y滿足關(guān)系rop就轉(zhuǎn)去執(zhí)行標(biāo)號為L的語句，否則按順序執(zhí)行本語句的下一條語句。(6) 過程調(diào)用語句par X和call P

9、,n。源程序中的P(X1、X2、，Xn)可用下列三地址代碼表示：par X1par X2par Xncall P,n 其中，整數(shù)n為實(shí)參個數(shù)。 過程返回語句為return y，其中y為過程返回值。10/11/202215(4) 無條件轉(zhuǎn)移語句goto L，即下一個將被執(zhí)行的語句是 (7) 變址賦值語句x=yi，其中x、y、i均代表數(shù)據(jù)對象，表示把從地址y開始的第i個地址單元中的值賦給x。xi=y則表示把y的值賦給從地址x開始的第i個地址單元。 (8) 地址和指針賦值語句 x=&y表示將y的地址賦給x，y可以是一個名字或一個臨時變量，而x是指針名或臨時變量； x=*y表示將y所指示的地址單元中的

10、內(nèi)容(值)賦給x，y是一個指針或臨時變量； *x=y表示指將x所指對象的值置為y的值。10/11/202216 (7) 變址賦值語句x=yi，其中x、y、i均代表數(shù)據(jù) 3三地址代碼的具體實(shí)現(xiàn)三地址代碼是中間代碼的一種抽象形式。在編譯程序中，三地址代碼語言的具體實(shí)現(xiàn)通常有三種表示方法：四元式、三元式和間接三元式。1) 四元式 (quadruples) 四元式是具有四個域的記錄結(jié)構(gòu)，這四個域?yàn)?(op，arg1，arg2，result)其中，op為運(yùn)算符；arg1、arg2及result為指針，它們可指向有關(guān)名字在符號表中的登記項(xiàng)或一臨時變量(也可空缺)。10/11/202217 3三地址代碼的具

11、體實(shí)現(xiàn)三地址代碼是中間代碼的一種抽象形式常用的三地址語句與相應(yīng)的四元式對應(yīng)如下：x=y op z 對應(yīng)(op, y, z, x)x=y 對應(yīng)(uminus, y, _, x)x=y 對應(yīng)(=, y, _, x)par x1 對應(yīng)(par, x1, _, _)call P 對應(yīng)(call, _, _, P)goto L 對應(yīng)(j, _, _, L)if x rop y goto L 對應(yīng)(jrop, x, y, L)10/11/202218常用的三地址語句與相應(yīng)的四元式對應(yīng)如下：10/9/20221例如，賦值語句a=b*(c+d)相應(yīng)的四元式代碼為： (+,c,d,t1) (*,b,t1,t2)

12、 (=,t2,_,a)t1 := -ct2 := b * t1t3 := -ct4 := b * t3t5 := t2 + t4a := t5 op arg1 arg2 result(0) uminus c t1(1) * b t1 t2(2) uminus c t3 (3) * b t3 t4 (4) + t2 t4 t5 (5) := t5 a 10/11/202219例如，賦值語句a=b*(c+d)相應(yīng)的四元式代碼為：t1 :注意：凡只需一個運(yùn)算量的算符一律使用arg1。此外，注意這樣一個規(guī)則：如果op是一個算術(shù)或邏輯運(yùn)算符，則result總是一個新引進(jìn)的臨時變量，它用來存放運(yùn)算結(jié)果。由

13、上例也可看出，四元式出現(xiàn)的順序與表達(dá)式計(jì)值的順序是一致的，四元式之間的聯(lián)系是通過臨時變量實(shí)現(xiàn)的。四元式由于其表示更接近程序設(shè)計(jì)的習(xí)慣而成為一種普遍采用的中間代碼形式。10/11/202220注意：10/9/2022202) 三元式 (Triples)三元式是具有三個域的記錄結(jié)構(gòu)，這三個域?yàn)?(op，arg1，arg2)其中，op為運(yùn)算符；arg1、arg2既可指向有關(guān)名字在符號表中的登記項(xiàng)，也可以指向三元式表中的某一個三元式。實(shí)際上，三元式是省去中間變量，代之以產(chǎn)生中間變量值的三地址語句的地址。10/11/2022212) 三元式 (Triples)10/9/202221例：t1 := -ct

14、2 := b * t1t3 := -ct4 := b * t3t5 := t2 + t4a := t5 op arg1 arg2(0) uminus c(1) * b (0)(2) uminus c(3) * b (2)(4) + (1) (3)(5) assign a (4) 10/11/202222例：t1 := -c op 3. 間接三元式 (Indirect triples) 使用三元式雖然省去了中間變量，但是要移動三元式就比較麻煩，因而不便于優(yōu)化。解決的方法是引入索引表間接碼表，當(dāng)調(diào)整三元式的位置時，只改動間接碼表中的索引位置。注意，使用間接碼表后，三元式表中的重復(fù)三元式可以省去；注

15、意，在前一種的三元式表示中，每個語句的位置同時有兩個作用：一是可作為該三元式的結(jié)果被其它三元式引用；二是三元式位置順序即為運(yùn)算順序。10/11/2022233. 間接三元式 (Indirect triples)10例：間接三元式表示 op arg1 arg2(14) uminus c(15) * b (14)(16) uminus c(17) * b (16)(18) + (15) (17)(19) assign a (18) statement(0) (14)(1) (15)(2) (16)(3) (17) (4) (18)(5) (19)10/11/202224例：間接三元式表示 op 例：合并相同的三元式 op arg1 arg2(14) uminus c