第六章中間代碼江西師范大學

1、.第六章第六章 中間代碼中間代碼l中間代碼的形式中間代碼的形式l表達式的翻譯表達式的翻譯l簡單賦值語句的翻譯簡單賦值語句的翻譯l布爾表達式的翻譯布爾表達式的翻譯l控制語句的翻譯控制語句的翻譯. 何謂中間代碼何謂中間代碼： 語法制導(dǎo)翻譯。語法制導(dǎo)翻譯。.優(yōu)點優(yōu)點 形式簡單、語義明確、便于翻譯形式簡單、語義明確、便于翻譯 獨立于目標語言獨立于目標語言 要掌握幾種常見的中間語言的基本結(jié)構(gòu)：要掌握幾種常見的中間語言的基本結(jié)構(gòu)：圖表示法：抽象語法樹圖表示法：抽象語法樹逆波蘭表示法逆波蘭表示法( (也稱后綴式也稱后綴式) )三地址代碼三地址代碼四元式四元式三元式、間接三元式三元式、間接三元式幾種常見的中間

2、語言幾種常見的中間語言4圖表示法：抽象語法樹圖表示法：抽象語法樹 語法制導(dǎo)翻譯以語法樹作基礎(chǔ)語法制導(dǎo)翻譯以語法樹作基礎(chǔ), 實際上實際上, 語法樹可以作語法樹可以作為一種合適的中間語言形式。為一種合適的中間語言形式。 現(xiàn)在對語法樹進行改造，去掉那些對翻譯不必要的信現(xiàn)在對語法樹進行改造，去掉那些對翻譯不必要的信息，將語法樹進行抽象息，將語法樹進行抽象 - 抽象語法樹抽象語法樹。 在抽象語法樹中，每個葉結(jié)點都表示諸如常量或變量在抽象語法樹中，每個葉結(jié)點都表示諸如常量或變量這樣的運算對象，而其它內(nèi)部結(jié)點則表示運算符。這樣的運算對象，而其它內(nèi)部結(jié)點則表示運算符。 語法制導(dǎo)翻譯既可以基于語法分析樹也可以基

3、于抽象語法制導(dǎo)翻譯既可以基于語法分析樹也可以基于抽象語法樹進行，語法樹進行，采用的基本方法是一樣的。采用的基本方法是一樣的。5 為下面文法的句子為下面文法的句子 x = a-4x = a-4* *c c 建立抽象語法樹：建立抽象語法樹： SV=E Vid E E+E | E-E | E*E | (E) | id | num 為每個運算量或運算符號都建立一個結(jié)點。為每個運算量或運算符號都建立一個結(jié)點。 可以可以根據(jù)表達式的運算順序自下而上的構(gòu)造根據(jù)表達式的運算順序自下而上的構(gòu)造 - 手工手工構(gòu)造。構(gòu)造。抽象語法樹抽象語法樹運算符作內(nèi)運算符作內(nèi)部結(jié)點部結(jié)點語法樹語法樹 比較：抽象語法樹的特點是結(jié)構(gòu)

4、比較：抽象語法樹的特點是結(jié)構(gòu)緊湊，容易構(gòu)造，結(jié)點較少。緊湊，容易構(gòu)造，結(jié)點較少。c*4a-xassign 表示賦值表示賦值id(c)E E * EE - Enum(4)id(a )S V = id(x )6l構(gòu)造賦值語句：構(gòu)造賦值語句： x=ab*(c-d)-e/f 的抽象語法樹，根據(jù)表達的抽象語法樹，根據(jù)表達式的運算順序自下而上的式的運算順序自下而上的構(gòu)造。構(gòu)造。l可以設(shè)計屬性文法構(gòu)造抽可以設(shè)計屬性文法構(gòu)造抽象語法樹。象語法樹。 手工構(gòu)造抽象語法樹手工構(gòu)造抽象語法樹 -a+xassign *b -cd/ef.逆波蘭表示法 逆波蘭表示法逆波蘭表示法又稱又稱后綴式后綴式表示法。逆波蘭表表示法。逆

5、波蘭表示法是波蘭邏輯學家盧卡西維奇發(fā)明的一種示法是波蘭邏輯學家盧卡西維奇發(fā)明的一種表示表達式的方法表示表達式的方法。這種方法是，把運算量。這種方法是，把運算量( (操作數(shù)操作數(shù)) )寫在運算符的前面，把運算符寫在寫在運算符的前面，把運算符寫在運算量的后面運算量的后面( (后綴后綴) )。 例：a+b ab+ a*(b+c) abc+* (a+b)*(c+d) ab+cd+*. 表達式的逆波蘭表示表達式的逆波蘭表示 一個一個表達式的后綴式表達式的后綴式可以如下遞歸定義：可以如下遞歸定義：1. 如果如果E是一個變量或常量，則是一個變量或常量，則E的后綴式是的后綴式是E自身。自身。2. 如果如果E是

6、是 E1 op E2 形式的表達式，這里形式的表達式，這里op是是任何二元操作符，則任何二元操作符，則E的后綴式為的后綴式為 E1 E2 op,這里這里E1 和和E2分別為分別為E1和和E2的后綴式。的后綴式。3. 如果如果E是是(E1)形式的表達式，則形式的表達式，則E1的后綴式的后綴式就是就是E的后綴式。的后綴式。. 后綴式與抽象語法樹的關(guān)系 后綴式是抽象語后綴式是抽象語法樹的線性表示法樹的線性表示形式。形式。是樹的后是樹的后序遍歷序遍歷(左，右，左，右，根根)的一個序列。的一個序列。 例如例如: a = b * - c+b * -c的抽象語法樹。的抽象語法樹。assigna+*bc-*-

7、cb后綴式后綴式: : a b c - * b c - * + assign.無環(huán)有向圖（無環(huán)有向圖（DAG） DAG指出了表達式中公共子表達式。指出了表達式中公共子表達式。 結(jié)點結(jié)點N（一個公共子表達式），可能有多個（一個公共子表達式），可能有多個父結(jié)點。父結(jié)點。.a+a*(b-c)+(b-c)*d+ba-*+dc.DAG的值編碼方法的值編碼方法=10i+idnum10+12=13到到i對應(yīng)對應(yīng) 的條目的條目12345.=a+*bc-給出給出a = b * - c+b * -c的的DAG及其值編碼。及其值編碼。.三地址代碼三地址代碼 三地址代碼是由下面一般形式的語句構(gòu)成的三地址代碼是由下面一

8、般形式的語句構(gòu)成的序列序列: x = y op z 其中，其中，x、y、z為名字、常數(shù)或編譯時產(chǎn)生為名字、常數(shù)或編譯時產(chǎn)生的臨時變量；的臨時變量；op代表運算符號。代表運算符號。 每個三地址語句的右邊只能有一個運算符。每個三地址語句的右邊只能有一個運算符。 例例, 表達式表達式 x+y*z 翻譯為三地址代碼翻譯為三地址代碼: t1 = y*z t2 = x+t1 t1, t2是編譯時產(chǎn)生的臨時變量。是編譯時產(chǎn)生的臨時變量。.三地址代碼：說明三地址代碼：說明 1. 之所以稱為三地址代碼，是因為三地址代碼之所以稱為三地址代碼，是因為三地址代碼語句類似與匯編指令語句類似與匯編指令, 涉及三個地址涉及

9、三個地址 x、y和和z，其中其中y、z表示操作數(shù)，表示操作數(shù)，x存放結(jié)果。存放結(jié)果。地址常用地址常用屬性屬性place(addr)表示。表示。 名字名字.place：指向符號表名字入口的指針：指向符號表名字入口的指針 臨時變量臨時變量.place：臨時變量值存放的單元地址：臨時變量值存放的單元地址 常數(shù)常數(shù).place：指向常數(shù)表中常數(shù)入口的指針：指向常數(shù)表中常數(shù)入口的指針 2.在三地址代碼中，一條指令的右側(cè)最多有一在三地址代碼中，一條指令的右側(cè)最多有一個運算符。個運算符。 3. 三地址代碼是抽象語法樹的線性化表示三地址代碼是抽象語法樹的線性化表示 - 樹的每個內(nèi)部結(jié)點對應(yīng)一個三地址語句。樹的

10、每個內(nèi)部結(jié)點對應(yīng)一個三地址語句。. 按樹自下而上的順序?qū)懗雒總€內(nèi)部結(jié)點對應(yīng)的三按樹自下而上的順序?qū)懗雒總€內(nèi)部結(jié)點對應(yīng)的三地址代碼。地址代碼。 注：注： 臨時變量的名字對應(yīng)抽象語法樹的內(nèi)部結(jié)點臨時變量的名字對應(yīng)抽象語法樹的內(nèi)部結(jié)點(算符結(jié)點算符結(jié)點), 表達式中的每個運算都要引入一個新表達式中的每個運算都要引入一個新的臨時變量存放計算結(jié)果的臨時變量存放計算結(jié)果, 要多少引入多少。要多少引入多少。+ba-*+dcT1=b-cT2=a*T1T3=a+T2T4=T1*dT5=T3+T4. 畫出賦值語句畫出賦值語句 x=a-b*c 的抽象語法樹的抽象語法樹 。給。給出其三地址表示。出其三地址表示。=x-

11、a*bc T1 b* c T2 a-T1 x T2 .n(1) 賦值語句賦值語句 x y op z ; op是二元算術(shù)或邏輯運算符是二元算術(shù)或邏輯運算符n(2) 賦值語句賦值語句 x op y ; op是一元算符，如取負運算符是一元算符，如取負運算符minus、邏輯非運算符、邏輯非運算符not、移位運算符及類型轉(zhuǎn)換運算符。、移位運算符及類型轉(zhuǎn)換運算符。n(3) 復(fù)制語句復(fù)制語句 x y;n(4) 無條件轉(zhuǎn)移語句無條件轉(zhuǎn)移語句 goto L; L是語句標號。是語句標號。 n(5) 條件轉(zhuǎn)移語句條件轉(zhuǎn)移語句 if x goto L ; if False x goto L ; X為真或為假時轉(zhuǎn)移到為

12、真或為假時轉(zhuǎn)移到L三地址語句的種類三地址語句的種類.n（6）條件轉(zhuǎn)移語句條件轉(zhuǎn)移語句 if x relop y goto L，關(guān)系運算，關(guān)系運算符號符號relop( ，=，= 等等）等等）;n(7) 過程調(diào)用語句過程調(diào)用語句 param x1; xi 是實參數(shù)是實參數(shù) param x2; param xn; call p, n ; p過程名過程名, n實參個數(shù)實參個數(shù) y=call p,n； p 函數(shù)名函數(shù)名 返回語句返回語句 return y; y返回值返回值, 可有可無可有可無三地址語句的種類三地址語句的種類. (8) 變址賦值語句變址賦值語句 x = yi; = 變址取數(shù)變址取數(shù) xi

13、= y ; = 變址存數(shù)變址存數(shù) (9) 地址和指針賦值語句地址和指針賦值語句 x y; x * y; * x y;. 四元式四元式 ( op, arg1, arg2, result ) 用了四個域用了四個域 三元式三元式 ( op, arg1, arg2 ) 只用三個域只用三個域 間接三元式間接三元式 間接碼表間接碼表+三元式表，三元式表， 便于進行優(yōu)化便于進行優(yōu)化三地址代碼的具體實現(xiàn)三地址代碼的具體實現(xiàn)算符算符 操作數(shù)操作數(shù)1(指針指針)操作數(shù)操作數(shù)2(指針指針)結(jié)果結(jié)果(臨變臨變)n三地址代碼的具體實現(xiàn)三地址代碼的具體實現(xiàn): 用記錄結(jié)構(gòu)用記錄結(jié)構(gòu), 含四個域含四個域 . 四元式需要較多的

14、臨時單元。四元式之間四元式需要較多的臨時單元。四元式之間 的聯(lián)系通過臨時變量實現(xiàn)的聯(lián)系通過臨時變量實現(xiàn), 三元式之間的聯(lián)三元式之間的聯(lián)系通過指針實現(xiàn)。系通過指針實現(xiàn)。 中間代碼優(yōu)化處理時，四元式比三元式方中間代碼優(yōu)化處理時，四元式比三元式方便得多便得多, 間接三元式與四元式同樣方便，四間接三元式與四元式同樣方便，四元式和三元式兩種實現(xiàn)方式需要的存儲空元式和三元式兩種實現(xiàn)方式需要的存儲空間大體相同。間大體相同。. 三地址語句三地址語句 四元式表示四元式表示 x = y op z ( op, y, z, x ) x = -y ( minus, y, _ , x ) x = y ( =, y, _,

15、 x ) par x1 ( param, x1, _, _ ) call P (call, _, _, P ) goto L ( j, _, _, L ) 無條件轉(zhuǎn)移無條件轉(zhuǎn)移 if a goto L ( jnz, a, _, L ) 條件轉(zhuǎn)移條件轉(zhuǎn)移 a是邏輯量，是邏輯量，a非非0, 即即a為真時轉(zhuǎn)移為真時轉(zhuǎn)移 if x rop y goto L ( jrop, x, y, L ) 條件轉(zhuǎn)移條件轉(zhuǎn)移 rop是關(guān)系運算符是關(guān)系運算符, x和和y為算術(shù)量，為算術(shù)量，x rop y 為真時轉(zhuǎn)移為真時轉(zhuǎn)移常用的三地址語句對應(yīng)的四元式常用的三地址語句對應(yīng)的四元式.n例：賦值語句例：賦值語句a=ba=b

16、* *-c+b-c+b* *-c -c 的四元式：的四元式：(0)(1)(2)(3)(4)(5)minus*minus*+Assign(=)cbcbT2T5arg1T1T3T4arg2resultT1T2T3T4T5aop三地址代碼實現(xiàn)：四元式表示三地址代碼實現(xiàn)：四元式表示n注：注：四元式出現(xiàn)的順序與表達式計值的順序四元式出現(xiàn)的順序與表達式計值的順序一致；四元式之間的聯(lián)系通過臨時變量實現(xiàn)。一致；四元式之間的聯(lián)系通過臨時變量實現(xiàn)。.(0)(1)(2)(3)(4)(5)minus*minus*+assigncbcb(1)aarg1(0)(2)(3)(4)arg2opn例：賦值語句例：賦值語句a=b

17、a=b* *-c+b-c+b* *-c -c 的三元式：的三元式：.n注：注：三元式中使用了指向三元式語句的指針三元式中使用了指向三元式語句的指針( (序號序號) )，序號也表示該三元式計算的結(jié)果值；，序號也表示該三元式計算的結(jié)果值； 三元式之間的聯(lián)系通過指針實現(xiàn)。三元式之間的聯(lián)系通過指針實現(xiàn)。三地址代碼實現(xiàn)：三元式表示三地址代碼實現(xiàn)：三元式表示.n例：賦值語句例：賦值語句a=ba=b* *-c+b-c+b* *-c -c的的間接三元式間接三元式：(0)(1)(2)(3)minus*+assigncb(1)aarg1(0)(1)(2)arg2op三元式表三元式表(0)(1)(0)(1)(2)(

18、3)間接碼表間接碼表n間接碼表按運算的次序列出三元式序號，三元式表只間接碼表按運算的次序列出三元式序號，三元式表只列出不同的三元式。列出不同的三元式。 三元式表中沒有了重復(fù)的三元式，三元式表中沒有了重復(fù)的三元式，語句的移動僅改變左邊的間接碼表。語句的移動僅改變左邊的間接碼表。三地址代碼實現(xiàn)：間接三元式三地址代碼實現(xiàn)：間接三元式. 寫出賦值語句寫出賦值語句：A=B*(C-D)-E/FG 的逆波蘭表示、三元式表示、四元式表示。的逆波蘭表示、三元式表示、四元式表示。n解解: 四元式表示四元式表示：( - , C , D , T1 ) (* , B , T1, T2 ) ( , F , G , T3

19、) ( / , E , T3, T4 ) ( - , T2, T4, T5 ) ( = , T5, _ , A )n解解: 三元式表示三元式表示：( - , C , D )(* , B , )( , F , G ) ( / , E , ) ( - , , ) ( = , , A )n解：解：逆波蘭表示逆波蘭表示： ABCD -*EFG/ - =.給出給出a := ( b + c d ) + c d的抽象語法樹和的抽象語法樹和DAG所對應(yīng)的三地址代碼。所對應(yīng)的三地址代碼。assigna+ bcdcd minus(a)抽象語法樹抽象語法樹assigna+ bcd minus(b)DAG(b)DAG

20、 .(1)E.addr表示存放E值的名字。語法制導(dǎo)翻譯生成三地址代碼 幾個用到的量：(2)newtemp是個函數(shù)，對它的調(diào)用將產(chǎn)生一個新的臨時變量。Sid:=EEE1+E2E-E1E(E1)Eid.gen(id.addr:=E.addr)產(chǎn)生式語義規(guī)則EE1+E2Sid:=EE.addr:=newtemp; gen(E.addr:=E1.addr +E2.addr)E-E1E.addr:=newtemp;gen(E.addr:=minusE1.addr)Entry(id).產(chǎn)生式語義規(guī)則E.addr:=E1.addr; E(E1) 產(chǎn)生賦值語句三地址代碼的語法制導(dǎo)定義產(chǎn)生賦值語句三地址代碼的語

21、法制導(dǎo)定義. .增加一條乘法的產(chǎn)生式及語義規(guī)則。增加一條乘法的產(chǎn)生式及語義規(guī)則。Eid E.addr:=id.addr; EE1*E2E.addr:=newtemp; gen(E.addr:=E1.addr *E2.addr).S.code:=E.codegen(id.addr:=E.addr)產(chǎn)生式語義規(guī)則EE1+E2Sid:=EE.addr:=newtemp; E.code:=E1.codeE2.codegen(E.addr:=E1.addr +E2.addr)p=lookup(); if(p=NULL) error(); else gen(p:=E.addr).EE1*E2

22、E.place:=newtemp; E.code:=E1.codeE2.code gen(E.addr:=E1.addr *E2.addr)語義規(guī)則產(chǎn)生式E-E1E.addr:=newtemp;E.code:=E1.codegen(E.addr:=minusE1.addr).產(chǎn)生式語義規(guī)則E.addr:=E1.addr; E.code:=E1.code E(E1) Eid E.addr:=id.addr; E.code:=p=lookup(); if(p!=NULL) E.addr=p; else error();.三地址語句序列是語法樹的線性表示，三地址語句序列是語法樹的線性表

23、示，用臨時變量代替語法樹中的結(jié)點。用臨時變量代替語法樹中的結(jié)點。實際實現(xiàn)中，三地址語句序列往往是被實際實現(xiàn)中，三地址語句序列往往是被存放到一個輸出文件中，而不是將三地存放到一個輸出文件中，而不是將三地址語句序列置入址語句序列置入codecode屬性之中。屬性之中。.思考題思考題簡單算術(shù)表達式和賦值語句到四元式的翻譯？簡單算術(shù)表達式和賦值語句到四元式的翻譯？Gen(OP, ARG1 ,ARG2 ,Result): 過程，產(chǎn)生四元式過程，產(chǎn)生四元式(1) S id := E GEN(:=,E.addr,-,id.addr)Entry(id)(2) EE1+E2 E.addr:= NewTemp;

24、Gen(+, E1.addr,E2.addr,E.addr) (3) EE1*E2 E.addr:= NewTemp; Gen(*, E1.addr,E2.addr,E.addr).(4) E - E1 E.addr:=NewTemp; Gen(minus, E1.addr, _ ,E.addr) (5) E( E1) E.addr:= E1.addr (6) Ei E.addr:=id.addr.n分析賦值語句：分析賦值語句： X= -B*(C+D) 的語法制導(dǎo)翻譯的語法制導(dǎo)翻譯過程。過程。n四元式序列四元式序列: (6)查表查表 (6)查表查表(6)查表查表(4)生成生成(2)生成生成(3

25、)生成生成(1)查表查表, 生成生成 (minus, B, _, T1) ( +, C, D, T2) ( *, T1, T2, T3) ( =, T3, _, X) i(X) = E.addrAE.addr * E.addr i(B )E.addr + E.addr E. addri(D )i(C)( E. addr )(5).考慮表達式的類型考慮表達式的類型 在前面關(guān)于算術(shù)表達式和賦值語句的翻譯中，我在前面關(guān)于算術(shù)表達式和賦值語句的翻譯中，我們假定所有的們假定所有的 i 都是同一類型的。實際上，在表都是同一類型的。實際上，在表達式中可能出現(xiàn)各種類型的變量或常量。達式中可能出現(xiàn)各種類型的變量

26、或常量。 編譯程序必須做到：或者拒絕接受某種混合運算，編譯程序必須做到：或者拒絕接受某種混合運算，或者產(chǎn)生有關(guān)類型轉(zhuǎn)換的指令?；蛘弋a(chǎn)生有關(guān)類型轉(zhuǎn)換的指令。 這種表達式和賦值語句的語義規(guī)則簡單說明如下這種表達式和賦值語句的語義規(guī)則簡單說明如下: (1) 引入引入語義變量語義變量 E.type 表示表達式表示表達式 E 的類型的類型 (2) 增加類型轉(zhuǎn)換的三地址語句增加類型轉(zhuǎn)換的三地址語句: x=inttoreal y (3) 對對EE(1)+E(2) | E(1)*E(2)的語義動作進行修改的語義動作進行修改, 增加判斷表達式類型并確定類型的操作增加判斷表達式類型并確定類型的操作.E E1 +

27、E2E.addr := newtempif E1.type = integer and E2.type = integer then begin gen (E.addr, :=, E1.addr, int+, E2.addr);E.type = integerendelse if E1.type = integer and E2.type = real then beginu := newtemp;gen (u, :=, inttoreal, E1.addr);gen (E.addr, :=, u, real+, E2.addr);E.type := realelse if else .1、數(shù)

28、組元素地址的計算公式 數(shù)組元素的三地址代碼是什么？ 數(shù)組元素的尋址數(shù)組元素的尋址每個數(shù)組元素的寬度數(shù)組首地址=bace-low*w + i*w如何生成數(shù)組元素的三地址代碼?一維數(shù)組的數(shù)組元素計算公式VAR a:ARRAY low.high OF real;求 ai的地址：base（ilow ）* w. 對于一個二維數(shù)組，可以按行或按列存放。若按行存放，則可用如下公式計算：數(shù)組地址計算： 可在編譯時計算出來常量部分+變量部分：base-low*w + i*w . base（i1 一一low1）* n2i2 一一low2）*w） 令令c= （low1 *n2）low2）*w 則常量部分則常量部分=

29、alow=alow1 1,low,low2 2-c-c A1,1 A1,2 A1,3 A2,1 A2,2 A2,3 A2,3按行存放AiAi1 1,i ,i2 2 的地址的地址： A1,2= base-(1*3+1)+(1*3+2)= base+1= base（low1 *n2）low2）*w （i1*n2）i2)* w.整理后：常量部分： c=(.(low1*n2+low2)*n3+low3).)*nk +lowk) * w 變量部分變量部分v= (.(i1*n2+i2)*n3+i3.)*nk+ik)*w 多維數(shù)組Ai1,i2,.,ik 的地址的計算(.(i1*n2+i2)*n3+i3.)*

30、nk+ik)*w+base-(.(low1*n2+low2)*n3+low3.)*nk+lowk)*w ai1,i2,in的地址 =base-c+v.x:=ai1,.,in的三地址代碼結(jié)構(gòu)： t1: =vt2:=base-ct3:=t2t1 x:=t3. 令令a表示表示2*3的整數(shù)數(shù)組，的整數(shù)數(shù)組，c,i,j都是整數(shù)。那都是整數(shù)。那么么a的類型就是的類型就是array(2,array(3,integer)。假定整數(shù)的寬度為假定整數(shù)的寬度為4，那么，那么a類型的寬度就類型的寬度就是是24。ai的類型是的類型是array(3,integer)，寬度，寬度為為12.要求給出要求給出c+aij的三地址

31、代碼。的三地址代碼。t1=i*12t2=j*4t3=t1+t2t4=at3t5=c+t4.數(shù)組引用的翻譯數(shù)組引用的翻譯 L id E | LE .翻譯翻譯ai1j+bi2 其中其中a表示表示2*3的整數(shù)數(shù)組的整數(shù)數(shù)組,b為一為一維數(shù)組，整數(shù)的寬度為維數(shù)組，整數(shù)的寬度為4。翻譯翻譯x=aij+bi翻譯翻譯xk=aij+bi增加產(chǎn)生式及語義規(guī)則。增加產(chǎn)生式及語義規(guī)則。 E E1+E2E L. 試寫出下列賦值語句的三地址中間代碼，試寫出下列賦值語句的三地址中間代碼，其中數(shù)組類型為整型其中數(shù)組類型為整型(大小為大小為1)，數(shù)組的下，數(shù)組的下界為界為1，上界為，上界為10。 AAi：=i+1 t1=i-

32、1 t2=t1*1 t3=at2 t4=t3-1 t5=t4*1 t6=i+1 at5 =t6.布爾表達式的翻譯 布爾表達式是用布爾運算符號布爾表達式是用布爾運算符號not (!)、and(&)、or (|)作用到布爾變量或關(guān)系表達作用到布爾變量或關(guān)系表達式上而組成的。式上而組成的。 關(guān)系表達式形式如關(guān)系表達式形式如 E1 rel E2，其中，其中E1 和和E2是是算術(shù)表達式，算術(shù)表達式， rel代表代表6個關(guān)系運算符個關(guān)系運算符: 、=、=、!= 。 程序設(shè)計語言中程序設(shè)計語言中布爾表達式有兩個基本作用布爾表達式有兩個基本作用： 一個是用作計算邏輯值一個是用作計算邏輯值(真真1，假，

33、假0)。 另一個是用另一個是用作控制流語句如作控制流語句如 if-else和和 while等中的條件表達式。等中的條件表達式。 無論作用如何，都必須先計算布爾表達式的值。無論作用如何，都必須先計算布爾表達式的值。 .布爾表達式的文法布爾表達式的文法 考慮由下列文法考慮由下列文法GB產(chǎn)生的布爾表達式：產(chǎn)生的布爾表達式： BB | B|B& B| ! B|E rel E|true|falsen假定使用假定使用 rel 的的 屬性屬性rel.op 來確定來確定 rel所指的所指的6種關(guān)系運算中的哪一個。種關(guān)系運算中的哪一個。n假定按慣例確定算術(shù)運算符，關(guān)系運算符及假定按慣例確定算術(shù)運算符，關(guān)

34、系運算符及布爾運算符布爾運算符!、&、|的優(yōu)先級和結(jié)合性。的優(yōu)先級和結(jié)合性。.布爾表達式的語義布爾表達式的語義 布爾式的語義布爾式的語義是指明計算一個邏輯值的規(guī)則是指明計算一個邏輯值的規(guī)則, 有兩種計算規(guī)則有兩種計算規(guī)則: 1. 用數(shù)值用數(shù)值(1/0)表示真和假表示真和假, 同計算算術(shù)表同計算算術(shù)表達式一樣達式一樣, 一步不差地按順序計算出整個一步不差地按順序計算出整個布爾式的值。布爾式的值。 例如例如: 計算計算 1 | (!0 & 0) | 0 =1 2. 優(yōu)化優(yōu)化(短路短路)方法，不一定一步不差的計方法，不一定一步不差的計算，可以由某個子布爾式的值確定整個布算，可以由某個

35、子布爾式的值確定整個布爾式的值。爾式的值。規(guī)則規(guī)則2 2用于翻譯控制流語句中用于翻譯控制流語句中的布爾表達式尤其方便。的布爾表達式尤其方便。.對于像對于像ab這樣的關(guān)系表達式，可看成等價的這樣的關(guān)系表達式，可看成等價的條件語句條件語句if ab then 1 else 0，它翻譯成的，它翻譯成的三地址代碼為：三地址代碼為：（1）ifab goto （4）（2）t =0（3）goto （5）（4）t =1（5） 其中用臨時變量其中用臨時變量t存放布爾表達式存放布爾表達式ab的值，的值，(5)為后續(xù)的三地址序號。為后續(xù)的三地址序號。數(shù)值表示法數(shù)值表示法.考慮由下列文法考慮由下列文法GB產(chǎn)生的布爾表

36、達式：產(chǎn)生的布爾表達式： BB | B|B& B| ! B|E rel E|true|false的語法制導(dǎo)翻譯。的語法制導(dǎo)翻譯。 nextstat是一個計數(shù)器，指向下一個三地址是一個計數(shù)器，指向下一個三地址語句在輸出序列中的索引序號語句在輸出序列中的索引序號,也就是即將也就是即將生成的三地址語句序號。生成的三地址語句序號。 地址常用屬性地址常用屬性place(addr)表示。表示。.BB1 | B2 B.addr =newtemp； gen（B.addr = B1.addr| B2.addr）BB1 & B2 B.addr =newtemp； gen （B.addr = B1.

37、addr & B2.addr）B!B1 B.addr =newtemp：；：； gen （B.addr =! B1.addr）B（B1） B.addr =B1.addrBE1 rel E2B.addr =newtemp； gen （if E1.addr rel E2.addr goto nextstat+3）；）； gen （B.addr =0 ）；）； gen （goto nextstat+2）；）； gen （B.addr =1）Btrue B.addr =newtemp； gen （B.addr =1）Bfalse B.addr =newtemp； gen （B.addr =0）

38、 .給出布爾表達式給出布爾表達式 ab & cd & efab & cd & ef三三地址代碼。地址代碼。100: if ab goto 103 101: t1=0102: goto 104103: t1=1104: if cd goto 107 105: t2=0106: goto 108107: t2=1108: t3=t1 & t2 109: if ef goto 112 110: t4=0111: goto 113112: t4=1113: t5=t3 & t4.布爾式的優(yōu)化計值規(guī)則布爾式的優(yōu)化計值規(guī)則解釋為解釋為: if B1 then

39、 true else B2 B1真則真則 B 真，不須計算真，不須計算 B2 解釋為解釋為: if B1 then B2 else false B1 假則假則 B 假，不須計算假，不須計算B2(a) 計算計算 B B1 B2 | = 真真真真真真假假假假假假B B1 B2 & = 真真真真真真假假假假假假(b) 計算計算 .理解布爾表達式的真、假出口 出現(xiàn)在條件語句：if B then S1 else S2 假出口假出口 真出口真出口 無條件轉(zhuǎn)移無條件轉(zhuǎn)移跳過跳過S2分支分支 中的布爾表達式中的布爾表達式 B，它的作用僅在于控制對，它的作用僅在于控制對 S1 和和 S2的選擇。只要能完

40、成這一使命，的選擇。只要能完成這一使命，B 的值就無需最終保的值就無需最終保留在某個臨時單元中。留在某個臨時單元中。n因此，作為轉(zhuǎn)移條件的布爾式因此，作為轉(zhuǎn)移條件的布爾式 B，可以賦予它兩種，可以賦予它兩種“出口出口”。 一個是一個是“真真”出口出口，為真時出向，為真時出向S1；一個；一個是是“假假”出口出口，為假時出向，為假時出向S2。.if B then S1 else S2 的代碼結(jié)構(gòu) 語義值語義值B.code 表示表示 布爾式布爾式B的中間代碼的中間代碼 語義值語義值S.code 表示表示 語句語句S的中間代碼的中間代碼n語義值語義值B.true, 真出口真出口，B為為真真時控制流轉(zhuǎn)向

41、的標時控制流轉(zhuǎn)向的標號號n語義值語義值B.false, 假出口假出口，B為為假假時控制流轉(zhuǎn)向的時控制流轉(zhuǎn)向的標號標號n語義值語義值S.next, 一個標號一個標號, 表示緊隨表示緊隨S代碼之后的地址代碼之后的地址B.codeS1.codeGoto S.nextS2.codeB.ture:B.false:S.next:To B.tureTo B.false.S if B then S1 | if B then S1 else S2 | while B do S1 | S1; S2 控制流語句的翻譯控制流語句的翻譯.B.codeS1.codeB.true:. . .指向指向B.true指向指向B.

42、false(a) if-thenB.codeS1.codeB.true:. . .指向指向B.true指向指向B.falseB.false:goto S.nextS2.code(b) if-then-elseB.codeS1.codeB.true:. . .指向指向B.true指向指向B.falsegoto S.beginS.begin:(c) while-doS1.codeS2.codeS1.next:. . .(d) S1; S2.S if B then S1B.true := newlabel; B.false := S.next; S1.next := S.next; S.code :

43、= B.code | gen(B.true, :) | S1.code B.codeS1.codeB.true:. . .指向指向B.true指向指向B.false(a) if-then.S if B then S1 else S2B.true := newlabel; B.false := newlabel; S1.next := S.next; S2.next := S.next; S.code := B.code | gen(B.true, :) | S1.code | gen(goto, S.next) | gen(B.false, :) |S2.code B.codeS1.codeB

44、.true:. . .指向指向B.true指向指向B.falseB.false:goto S.nextS2.code(b) if-then-else.S while B do S1 S.begin:= newlabel; B.true := newlabel; B.false := S.next; S1.next := S.begin; S.code := gen(S.begin, :) | B.code | gen(B.true, :) | S1.code | gen(goto, S.begin) B.codeS1.codeB.true:. . .指向指向B.true指向指向B.falseg

45、oto S.beginS.begin:(c) while-do.S S1; S2S.code := S1.code | gen(S1.next, :) | S2.code S1.codeS2.codeS1.next:. . .(d) S1; S2.布爾表達式的翻譯布爾表達式的翻譯如果如果B是是a b的形式，的形式，那么代碼是：那么代碼是：if a b goto B.truegoto B.false.表達式表達式a b & c d & e f的代碼是：的代碼是：if a b goto L1goto LfalseL1:if c d goto L2goto LfalseL2:if e

46、 f goto Ltruegoto Lfalse.B B1 | B2B1.true := B.true; B1.false := newlabel; B2.true := B.true; B2.false := B.false; B.code := B1.code | gen(B1.false, :) | B2.code B ！ B1B1.true := B.false; B1.false := B.true; B.code := B1.code .B B1 & B2B1.true := newlabel; B1.false := B.false; B2.true := B.true;

47、 B2.false := B.false; B.code := B1.code | gen(B1.true, :) | B2.code B (B1 ) B1.true := B.true; B1.false := B.false; B.code := B1.code .B id1 relop id2B.code := gen(if, id1.addr, relop.op, id2.addr, goto, B.true) | gen(goto, B.false) B trueB.code := gen(goto, B.true)B falseB.code := gen(goto, B.false

48、). 給出給出x200&x!=y的三地址翻譯。的三地址翻譯。If x200 goto L2 goto LfalseL2: if x!=y goto Ltrue goto LfalseLtrue:Lfalse:. 考慮如下語句：考慮如下語句： while ab do if cd then x：= yz else x：y-z 根據(jù)前面所述，生成根據(jù)前面所述，生成代碼代碼. L1 ： if ab goto L2 goto Lnext L2 ： if cd goto L3 goto L4 L3 ： t1 ：= yz x：t1 goto L1 L4 ： t2:=yz x：t2 goto L1 L

49、next： .回填 先產(chǎn)生暫時沒有填寫目標標號的轉(zhuǎn)移指令。先產(chǎn)生暫時沒有填寫目標標號的轉(zhuǎn)移指令。 對于每一條這樣的指令作適當?shù)挠涗?，對于每一條這樣的指令作適當?shù)挠涗洠?一旦目標標號被確定下來，再將它一旦目標標號被確定下來，再將它“回填回填”到相應(yīng)的指令中。到相應(yīng)的指令中。.使用回填翻譯控制語句中的布爾表達式 （1）BB1 | B2 （把文法翻譯成什么形式） （2） | B1 & B2 B1.code B2.codeB1.false:to B1.trueto B1.falseto B2.trueto B2.false B1.code B2.codeB1.true:to B1.trueto

50、 B1.falseto B2.trueto B2.falseto B.trueto B.falseto B.trueto B.false.使用回填翻譯控制語句中的布爾表達式 （3） | ! B1 （4） | (B1) B1.codeto B1.trueto B1.falseB.codeto B.falseto B.true B1.codeto B1.trueto B1.falseB.codeto B.trueto B.false.使用回填翻譯控制語句中的布爾表達式 （5） | id1 rel id2 （6） | true （7） | false B.code if id1 relop id2

51、then goto B.true goto B.false to B.falseto B.trueB.code goto B.true to B.trueB.code goto B.false to B.false.使用回填翻譯控制語句中的布爾表達式 （1）BB1 | M B2 （2） | B1 & M B2 （3） | ! B1 （4） | (B1) （5） | id1 rel id2 （6） | true （7） | false （8）M插入非終結(jié)符號M是為了引入一個語義動作，以便在適當?shù)臅r候獲得即將產(chǎn)生的下一個(三地址代碼）四元式的索引。.翻譯模式用到如下三個函數(shù)：翻譯模式用到如

52、下三個函數(shù)： 1makelist(i)：創(chuàng)建一個僅包含創(chuàng)建一個僅包含i的新表，的新表，i 是三地址代碼數(shù)組的一個索引（下標），是三地址代碼數(shù)組的一個索引（下標），或說或說 i是三地址代碼序列的一個標號。是三地址代碼序列的一個標號。 2merge(p1，p2)：連接由指針連接由指針p1和和p2指向的指向的兩個表并且返回一個指向連接后的表的指針。兩個表并且返回一個指向連接后的表的指針。 3backpatch（p，i）：）：把把i作為目標標號回作為目標標號回填到填到p所指向的表中的每一個轉(zhuǎn)移指令中去。所指向的表中的每一個轉(zhuǎn)移指令中去。此處的此處的“表表”都是為都是為“反填反填”所拉的鏈所拉的鏈.BB

53、1 | MB2 backpatch(B1.false,M.next); B.true:=merge(B1.true,B2.true); B.false:=B2.false BB1 & MB2 backpatch(B1.true,M.next); B.true:=B2.true; B.false:=merge(B1.false,B2.false);.B! B1 B.true:=B1.false; B.false:=B1.true B ( B1 ) B.true:= B1.true; B.false:=B1.false B id1 rel id2 B.true:=nextstat; B.f

54、alse:= nextstat+1; gen(ifid1.addr rel.op id2.addrgoto); gen(goto); .B true B.true:= nextstat; gen(goto); B false B.false:= nextstat; gen(goto); M M.next:=nextstat .例 重新考慮表達式ab | cd & ef 一棵作了注釋的分析樹如下圖所示B.t=100,104B.f=103,105B.t=100B.f=101B.t=104B.f=103,105or M.q=102a bB.t=102B.f=103B.t=104B.f=105

55、andM.q=104cefd. 依次分析，得到如下三地址： 100 ： if ab goto- 101 ： goto- 102 ：if cd goto- 103 ： goto- 104 ： if ef goto- 105 ： goto- 經(jīng)過回填得到： 100 ： if ab goto L1 101 ： goto l02 102 ： if cd goto l04 103 ： goto - 104 ： if ef goto L1 105 ： goto - 當知道了條件為真時和條件為假時分別應(yīng)做哪些事時就可以進行回填。.控制流語句的翻譯模式：控制流語句的翻譯模式：1. Sif B then M1

56、S1B.codeS1.codeB.true:.B.false:to B.trueto B.falseM1處反填B.true backpatch( B.true,M.next); S.next := merge(B.false ,S1.next) .控制流語句的翻譯模式：控制流語句的翻譯模式：2. Sif B then M1 S1 N else M2 S2 B.codeS1.codeB.true:S2.codeB.false:goto S.next.S.next:to B.trueto B.falseM1處反填B.trueM2處反填B.falseN出生成 goto S.next . backpa

57、tch( B.true,M1.next); backpatch(B.false,M2.next); S.next := merge(S1.next,N.next,S2.next) N N.next := nextstat; emit(goto ) .控制流語句的翻譯模式：控制流語句的翻譯模式：2. Swhile M1 B do M2 S1B.codeS1.codeB.true:B.false:goto S.begin.S.begin:to B.falseto B.trueM1處反填S1.next生成標號S.beginM2處反填B.true. backpatch(B.true,M2.next); backpatch(S1.next,M1.next); S.next := B.false; emit(gotoM1.next) S begin L end S.next := L.next S A S.next := makelist() LL1;M S backpatch(L1.next,M.next); L.next := S.next LS L.next:=S.next . 先記錄要回填的轉(zhuǎn)移指令地址，在適當?shù)臅r候進行回填，以便賦值和布爾表達式的求值得到合適的連接，以完成程序