編譯原理課件

南開大學(xué)軟件學(xué)院編譯原理李忠偉2主樓A201lizhongwei@第七章常用中間語言7.1抽象語法樹7.2逆波蘭表示7.3三地址代碼7.1抽象語法樹抽象語法樹也稱圖表示，是一種較為流行的中間語言表示形式。在抽象語法樹表示中，每一個(gè)葉結(jié)點(diǎn)都表示諸如常量或變量這樣的運(yùn)算對(duì)象，而其它內(nèi)部結(jié)點(diǎn)則表示運(yùn)算符。抽象語法樹不同于前述的語法樹，它展示了一個(gè)操作過程并同時(shí)描述了源程序的層次結(jié)構(gòu)。語法規(guī)則中包含的某些符號(hào)可能起標(biāo)點(diǎn)符號(hào)作用也可能起解釋作用。如賦值語句語法規(guī)則：

S→V=e

其中的賦值號(hào)“=”僅起標(biāo)點(diǎn)符號(hào)作用，其目的是把V與e分開；

條件語句語法規(guī)則：

S→if(e)S1;elseS2

其中的保留字符號(hào)if和else起注釋作用，說明當(dāng)布爾表達(dá)式e為真時(shí)執(zhí)行S1，否則執(zhí)行S2?！?；”僅起標(biāo)點(diǎn)符號(hào)作用?？梢钥闯?，上述語句的本質(zhì)部分是V、e和Si。當(dāng)把語法規(guī)則中本質(zhì)部分抽象出來而將非本質(zhì)部分去掉后，便得到抽象語法規(guī)則。圖1x=a?b*c的語法樹與抽象語法相對(duì)應(yīng)的語法樹稱為抽象語法樹或抽象樹，如賦值語句x=a?b*c的抽象語法樹如圖1(a)所示，而圖1(b)則是該賦值語句的普通語法樹。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的后綴表示。2．程序語句的逆波蘭表示為了用逆波蘭式表示一些控制語句，我們定義轉(zhuǎn)移操作如下：(1)?BL：轉(zhuǎn)向某標(biāo)號(hào)；(2)?BT：條件為真時(shí)轉(zhuǎn)移；(3)?BF：條件為假時(shí)轉(zhuǎn)移；(4)?BR：無條件轉(zhuǎn)移。(3)條件語句。BR表示無條件轉(zhuǎn)移單目后綴運(yùn)算符。例如，“<順序號(hào)>BR”表示無條件轉(zhuǎn)移到“<順序號(hào)>”處，這里的順序號(hào)是BR的一個(gè)特殊運(yùn)算分量，用來表示逆波蘭式中單詞符號(hào)的順序號(hào)(即第幾個(gè)單詞)，它不同于GOTO語句中的語句標(biāo)號(hào)。BT和BF表示按條件轉(zhuǎn)移的兩個(gè)雙目后綴運(yùn)算符。例如：<布爾表達(dá)式e的逆波蘭式><順序號(hào)N1>BT<布爾表達(dá)式e的逆波蘭式><順序號(hào)N2>BF分別表示當(dāng)e為真或假時(shí)轉(zhuǎn)移到順序號(hào)處；其中，布爾表達(dá)式e的逆波蘭式和順序號(hào)是兩個(gè)特殊的運(yùn)算分量。若使用BT和BF，則條件語句if(e)S1;elseS2的逆波蘭式為：<e的逆波蘭式><N1>BF<S1的逆波蘭式><N2>BR<S2的逆波蘭式>N1為S2的逆波蘭式的第一個(gè)符號(hào)在逆波蘭表示中的序號(hào)；N2為跟在S2的逆波蘭式后面的符號(hào)在逆波蘭表示中的序號(hào)，即該條件語句的后續(xù)語句的逆波蘭式的第一個(gè)符號(hào)的序號(hào)?；蛘邔懗桑?lt;e的逆波蘭式><N1>BF/*e為假則轉(zhuǎn)S2的第一個(gè)單詞的順序號(hào)*/<S1的逆波蘭式> /*e為真則執(zhí)行S1*/<N2>BR /*S1執(zhí)行結(jié)束后無條件轉(zhuǎn)出該條件語句*/<S2的逆波蘭式>例如，條件語句if(m<n)k=i+1；elsek=i?1的逆波蘭式表示為：((1)～(18)為單詞編號(hào))(1)?mn<(4)?13BF(6)?ki1+=(11)?18BR(13)?ki1?=(18)?{if語句的后繼語句}

此逆波蘭式也可寫在一行上，即mn<13BFki1+=18BRki1?=(4)循環(huán)語句for循環(huán)語句為：for(i=m；i<=n；i++)S；其中，i為循環(huán)控制變量，m為初值，n為終值，S為循環(huán)體。循環(huán)語句不能直接用逆波蘭表示，因而將其展開為等價(jià)的條件語句后再用逆波蘭表示，即：i=m；10：if(i<=n){S；i=i+1；gotol0}1．三地址代碼的形式三地址代碼語句的一般形式為：x=yopz其中，x、y和z為名字、常量或編譯時(shí)產(chǎn)生的臨時(shí)變量；op為運(yùn)算符，如定點(diǎn)運(yùn)算符、浮點(diǎn)算符和邏輯運(yùn)算符等。三地址代碼的每條語句通常包含三個(gè)地址，兩個(gè)用來存放運(yùn)算對(duì)象，一個(gè)用來存放運(yùn)算結(jié)果。7.3三地址代碼2．三地址語句的種類作為中間語言的三地址語句非常類似于匯編代碼，它可以有符號(hào)標(biāo)號(hào)和各種控制流語句。常用的三地址語句有以下幾種：(1)?x=yopz形式的賦值語句，其中op為二目的算術(shù)運(yùn)算符或邏輯運(yùn)算符。(2)?x=opy形式的賦值語句，其中op為一目運(yùn)算符，如一目減uminus、邏輯否定not、移位運(yùn)算符以及將定點(diǎn)數(shù)轉(zhuǎn)換成浮點(diǎn)數(shù)的類型轉(zhuǎn)換符。(3)?x=y形式的賦值語句，將y的值賦給χ。(4)無條件轉(zhuǎn)移語句gotoL，即下一個(gè)將被執(zhí)行的語句是標(biāo)號(hào)為L(zhǎng)的語句。(5)條件轉(zhuǎn)移語句ifxropygotoL，其中rop為關(guān)系運(yùn)算符，如<、<=、==、!=、>、>=等。若x和y滿足關(guān)系rop就轉(zhuǎn)去執(zhí)行標(biāo)號(hào)為L(zhǎng)的語句，否則繼續(xù)按順序執(zhí)行本語句的下一條語句。(7)變址賦值語句x=y[i]，其中x、y、i均代表數(shù)據(jù)對(duì)象，表示把從地址y開始的第i個(gè)地址單元中的值賦給x。x[i]=y則表示把y的值賦給從地址x開始的第i個(gè)地址單元。

(8)地址和指針賦值語句①x=&y表示將y的地址賦給x，y可以是一個(gè)名字或一個(gè)臨時(shí)變量，而x是指針名或臨時(shí)變量；②x=*y表示將y所指示的地址單元中的內(nèi)容(值)賦給x，y是一個(gè)指針或臨時(shí)變量；③*x=y表示指將x所指對(duì)象的值置為y的值。3．三地址代碼的具體實(shí)現(xiàn)三地址代碼是中間代碼的一種抽象形式。在編譯程序中，三地址代碼語言的具體實(shí)現(xiàn)通常有三種表示方法：四元式、三元式和間接三元式。1)四元式四元式是具有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域?yàn)椋?op，arg1，arg2，result)例如，賦值語句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í)變量，它用來存放運(yùn)算結(jié)果。由上例也可看出，四元式出現(xiàn)的順序與表達(dá)式計(jì)值的順序是一致的，四元式之間的聯(lián)系是通過臨時(shí)變量實(shí)現(xiàn)的。四元式由于其表示更接近程序設(shè)計(jì)的習(xí)慣而成為一種普遍采用的中間代碼形式。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)于賦值語句a=(b+c)*(b+c)的三元式代碼為： ①(+,b,c) ②(+,b,c) ③(*,①,②) ④(=,a,③)上述三元式③表示①的結(jié)果與②的結(jié)果相乘。由上例可知，三元式出現(xiàn)的先后順序和表達(dá)式各部分的計(jì)值順序是一致的。在三元式表示中，每個(gè)語句的位置同時(shí)有兩個(gè)作用：一是可作為該三元式的結(jié)果被其它三元式引用；二是三元式位置順序即為運(yùn)算順序。在代碼優(yōu)化階段，需要調(diào)整三元式的運(yùn)算順序時(shí)會(huì)遇到困難，這是因?yàn)槿街械腶rg1、arg2也可以是指向某些三元式位置的指針，當(dāng)這些三元式的位置順序發(fā)生變