編譯原理第七章中間代碼生成

1、第七章第七章 中間代碼生成中間代碼生成本章內(nèi)容本章內(nèi)容介紹幾種常用的中間表示介紹幾種常用的中間表示：后綴表示、圖后綴表示、圖形表示和三地址代碼形表示和三地址代碼用語法制導(dǎo)定義和翻譯方案的方法來說明用語法制導(dǎo)定義和翻譯方案的方法來說明程序設(shè)計(jì)語言的結(jié)構(gòu)怎樣被翻譯成中間形式程序設(shè)計(jì)語言的結(jié)構(gòu)怎樣被翻譯成中間形式 分析分析器器靜態(tài)靜態(tài)檢查檢查器器中間中間代碼代碼生成生成 器器中間中間代碼代碼記號記號流流代碼代碼生成生成器器 抽象語法樹抽象語法樹 后綴式后綴式 DAG圖表示圖表示 三地址代碼（包括三元式、四元式、間接三地址代碼（包括三元式、四元式、間接三元式）三元式）7.1 中中 間間 語語 言言后綴

2、式后綴式 后綴式表示又稱逆波蘭表示法。后綴式表示又稱逆波蘭表示法。 這種表示法是：把運(yùn)算量（操作數(shù)）寫在前面，把算符寫在這種表示法是：把運(yùn)算量（操作數(shù)）寫在前面，把算符寫在后面（后綴）。后面（后綴）。 一個(gè)表達(dá)式的后綴形式可以如下定義：一個(gè)表達(dá)式的后綴形式可以如下定義： 如果如果E是一個(gè)變量或常量，則是一個(gè)變量或常量，則E的后綴式是的后綴式是E自身自身 如果如果E是是E1 op E2形式的表達(dá)式，這里形式的表達(dá)式，這里op是任何二元操作符，則是任何二元操作符，則E的后的后綴式為綴式為E1E2op。這里。這里E1和和E2分別是分別是E1和和E2的后綴式。的后綴式。 如果如果E是是(E1)形式的表

3、達(dá)式，則形式的表達(dá)式，則E1的后綴式就是的后綴式就是E的后綴式的后綴式 只要知道每個(gè)算符的目數(shù)，對于后綴式，無論從那一端進(jìn)行只要知道每個(gè)算符的目數(shù)，對于后綴式，無論從那一端進(jìn)行掃描，都能對它正確的進(jìn)行唯一分解掃描，都能對它正確的進(jìn)行唯一分解后綴式后綴式 表達(dá)式翻譯為后綴式的語義規(guī)則描述：表達(dá)式翻譯為后綴式的語義規(guī)則描述： 其中其中E.code表示表示E的后綴式，的后綴式，op表示任何二元操作符表示任何二元操作符，“|”表示后綴形式的連接表示后綴形式的連接產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則EE1 op E2E.code = E1.code | E2.code | opE(E1) E.code = E1

4、.codeEidE.code = id圖表示法圖表示法 圖表示法主要包括圖表示法主要包括DAG( Directed Acyclic Graph )與抽象語法與抽象語法樹樹 語法樹描述了源程序的自然層次結(jié)構(gòu)。語法樹描述了源程序的自然層次結(jié)構(gòu)。DAG以更緊湊的形式以更緊湊的形式給出了相同的信息。兩者不同的是：給出了相同的信息。兩者不同的是： 在一個(gè)在一個(gè)DAG中代表公共子表達(dá)式的結(jié)點(diǎn)具有多個(gè)父結(jié)點(diǎn)中代表公共子表達(dá)式的結(jié)點(diǎn)具有多個(gè)父結(jié)點(diǎn) 在一顆抽象語法樹中公共子表達(dá)式被表示為重復(fù)的子樹。在一顆抽象語法樹中公共子表達(dá)式被表示為重復(fù)的子樹。assign+a*uminusbcuminusbca= b*-c

5、 + b*-cassign+a*uminusbcabc uminus * bc numinus *+ assign抽象語法樹抽象語法樹 構(gòu)造賦值語句語法樹的語法制導(dǎo)定義：構(gòu)造賦值語句語法樹的語法制導(dǎo)定義： 如果函數(shù)如果函數(shù)mknode(op, child)和和mknode(op, left, right)盡可能返回一個(gè)指向已經(jīng)存在結(jié)點(diǎn)的指針以代替建立盡可能返回一個(gè)指向已經(jīng)存在結(jié)點(diǎn)的指針以代替建立新的結(jié)點(diǎn)，那么就會生成新的結(jié)點(diǎn)，那么就會生成DAG圖。圖。產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則Sid = ES.nptr = mknode(assign, mkleaf(id, id.place), E.npt

6、r) EE1 + E2E.nptr = mknode(+ , E1.nptr, E2.nptr) EE1 * E2E.nptr = mknode(* , E1.nptr, E2.nptr)E- E1E.nptr = mknode(uminus, E1.nptr) E(E1)E.nptr = E1.nptr EidE.nptr = mkleaf(id , id.place)抽象語法樹的表示形式抽象語法樹的表示形式assignida+*uminusuminusidbidbidcidc0idb1idc2uminus13*024idb5idc6uminus57*468+379ida10assign98

7、11a= b*-c + b*-c三地址代碼三地址代碼 三地址代碼是下列形式的語句序列三地址代碼是下列形式的語句序列x = y op z其中，其中，x、y和和z是名字，常量或編譯器生成的臨時(shí)變量是名字，常量或編譯器生成的臨時(shí)變量op代表任何操作符（定點(diǎn)運(yùn)算符、浮點(diǎn)運(yùn)算符、邏輯運(yùn)算代表任何操作符（定點(diǎn)運(yùn)算符、浮點(diǎn)運(yùn)算符、邏輯運(yùn)算符等）符等） 像像x+y*z這樣的表達(dá)式要翻譯為這樣的表達(dá)式要翻譯為:T1 = y * zT2 = x + T1其中其中T1 ，T2為編譯時(shí)產(chǎn)生的臨時(shí)變量。為編譯時(shí)產(chǎn)生的臨時(shí)變量。三地址語句的類型三地址語句的類型 三地址語句類似于匯編語言代碼。語句可以有三地址語句類似于匯編

8、語言代碼。語句可以有符號標(biāo)號，而且存在各種控制流語句。符號標(biāo)號，而且存在各種控制流語句。 本書中使用的三地址語句：本書中使用的三地址語句： 形如形如x= y op z的賦值語句，其中的賦值語句，其中op為二元算術(shù)算符為二元算術(shù)算符或邏輯算符或邏輯算符 形如形如x= op y的賦值語句，其中的賦值語句，其中op為一元算符。為一元算符。 形如形如x= y的賦值語句，將的賦值語句，將y的值賦給的值賦給x 形如形如goto L的無條件跳轉(zhuǎn)語句，即下一條將被執(zhí)行的無條件跳轉(zhuǎn)語句，即下一條將被執(zhí)行的語句是帶有標(biāo)號的語句是帶有標(biāo)號L的三地址語句的三地址語句三地址語句的類型三地址語句的類型 形如形如if x

9、relop y goto L或或 if a goto L的條件跳轉(zhuǎn)語句。的條件跳轉(zhuǎn)語句。 第一種形式使用關(guān)系運(yùn)算符號第一種形式使用關(guān)系運(yùn)算符號relop（等）等） 第二種第二種a為布爾變量或常量為布爾變量或常量 用于過程調(diào)用的語句用于過程調(diào)用的語句param x和和call p, n，以及返回語句，以及返回語句return y。源程序中的過程調(diào)用。源程序中的過程調(diào)用p(x1,x2,xn)： param x1 param x2 param x2 call p, n n表示實(shí)參個(gè)數(shù)。表示實(shí)參個(gè)數(shù)。return y中中y為過程返回的一個(gè)值為過程返回的一個(gè)值 形如形如x = yi及及xi = y的索引

10、賦值。的索引賦值。 形如形如x = &y, x = *y和和*x = y的地址和指針賦值。的地址和指針賦值。三地址語句的實(shí)現(xiàn)三地址語句的實(shí)現(xiàn) 三地址語句是中間代碼的一種抽象形式。三地址語句是中間代碼的一種抽象形式。 這些語句可以以帶有操作符和操作數(shù)域的記錄這些語句可以以帶有操作符和操作數(shù)域的記錄來實(shí)現(xiàn)。四元式、三元式及間接三元式是三種來實(shí)現(xiàn)。四元式、三元式及間接三元式是三種這樣的表示。這樣的表示。四元式四元式 一個(gè)四元式是帶有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)一個(gè)四元式是帶有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域分別稱為域分別稱為op, arg1, arg2及及result。 域域op包含一個(gè)代表運(yùn)算符的內(nèi)部碼包含

11、一個(gè)代表運(yùn)算符的內(nèi)部碼 三地址語句三地址語句x=y op z通過將通過將y放入放入arg1，z放入放入arg2，并且將，并且將x放入放入result，=為算符。為算符。 像像x=y或或x=-y這樣的一元操作符語句不使用這樣的一元操作符語句不使用arg2 像像param這樣的運(yùn)算符僅使用這樣的運(yùn)算符僅使用arg1域。域。 條件和無條件語句將目標(biāo)標(biāo)號存入條件和無條件語句將目標(biāo)標(biāo)號存入result域。域。 臨時(shí)變量也要填入符號表中。臨時(shí)變量也要填入符號表中。三元式三元式 為了避免把臨時(shí)變量填入符號表，可以通過計(jì)為了避免把臨時(shí)變量填入符號表，可以通過計(jì)算臨時(shí)值語句的位置來引用該臨時(shí)變量。算臨時(shí)值語句的

12、位置來引用該臨時(shí)變量。 這樣三地址代碼的記錄只需要三個(gè)域這樣三地址代碼的記錄只需要三個(gè)域op, arg1和和arg。 對于單目運(yùn)算符對于單目運(yùn)算符op, arg1和和arg2只需用其一。只需用其一。四元式四元式/三元式三元式舉例舉例oparg1arg2result(0)uminuscT1(1)*bT1T2(2)uminuscT3(3)*bT3T4(4)+T2T4T5(5)assignT5aoparg1arg2(0)uminusc(1)*b(0)(2)uminusc(3)*b(2)(4)+(1)(3)(5)assigna(4)a = b * -c + b * -c三元式三元式三元式舉例三元式舉例

13、oparg1arg2(0)=xi(1)assign(0)yoparg1arg2(0)=yi(1)assignx(0)xi = yx = yi間接三元式間接三元式 為了便于代碼優(yōu)化處理，有時(shí)不直接使用三元為了便于代碼優(yōu)化處理，有時(shí)不直接使用三元式表，而是另設(shè)一張指示器（稱為間接碼表）式表，而是另設(shè)一張指示器（稱為間接碼表），它將運(yùn)算的先后順序列出有關(guān)三元式在三元，它將運(yùn)算的先后順序列出有關(guān)三元式在三元表中的位置。表中的位置。 即，用一張間接碼表輔以三元式表來表示中間即，用一張間接碼表輔以三元式表來表示中間代碼。這種表示方法稱為間接三元式。代碼。這種表示方法稱為間接三元式。間接三元式舉例間接三元式

14、舉例 X=(A+B)*C Y=D(A+B)oparg1arg2(1)+AB(2)*(1)C(3)=X(2)(4)D(1)(5)=Y(4)間接代碼間接代碼(1)(2)(3)(1)(4)(5)(1)(2)(3)(1)(4)(5)當(dāng)在代碼優(yōu)化過程中需要調(diào)整運(yùn)算順序當(dāng)在代碼優(yōu)化過程中需要調(diào)整運(yùn)算順序時(shí)，只需重新安排間接碼表，無需改動時(shí)，只需重新安排間接碼表，無需改動三元式表三元式表對于間接三元式表示，語義規(guī)則中應(yīng)增對于間接三元式表示，語義規(guī)則中應(yīng)增添產(chǎn)生間接碼表的動作，并且在向三元添產(chǎn)生間接碼表的動作，并且在向三元式表填進(jìn)一個(gè)三元式之前，必須先查看式表填進(jìn)一個(gè)三元式之前，必須先查看一下此式是否已在其中

15、，就無須填入。一下此式是否已在其中，就無須填入。7.2 聲聲 明明 語語 句句 為局部名字建立符號表?xiàng)l目為局部名字建立符號表?xiàng)l目 為它分配存儲單元為它分配存儲單元 符號表中包含名字的類型和分配給它的存儲符號表中包含名字的類型和分配給它的存儲單元的相對地址等信息單元的相對地址等信息7.2 聲聲 明明 語語 句句7.2.1 過程中的聲明過程中的聲明計(jì)算被聲明名字的類型和相對地址計(jì)算被聲明名字的類型和相對地址P offset = 0D SD D ; D D id : Tenter ( , T.type, offset);offset = offset + T.width T integ

16、er T.type = integer; T.width = 4 T real T.type = real; T.width = 8 T array num of T1T.type = array (num.val, T1.type);T.width = num.val T1.widthT T1 T.type = pointer (T1.type); T.width = 4 7.2 聲聲 明明 語語 句句7.2.2 作用域信息的保存作用域信息的保存 所討論語言的文法所討論語言的文法P D SD D ; D | id : T | proc id ; D ; S 語義動作用到的函數(shù)語義動作用到的函

17、數(shù)mktable(previous)enter(table, name, type, offset) addwidth(table, width)enterproc(table, name, newtable)7.2 聲聲 明明 語語 句句P M D S addwidth (top (tblptr), top (offset) ); pop(tblptr); pop(offset) M t = mktable (nil);push(t, tblptr); push (0, offset) D D1 ; D2D proc id ; N D1; S t = top(tblptr); addwidt

18、h(t, top(offset); pop(tblptr); pop(offset); enterproc(top(tblptr), , t) Did : T enter(top(tblptr), , T.type, top(offset); top(offset) = top(offset) + T.width N t = mktable(top(tblptr) ); push(t, tblptr); push(0, offset) *7.3 賦賦 值值 語語 句句7.3.1 符號表中的名字符號表中的名字S id = E p = lookup();i

19、f p nil thenemit ( p, =, E.place)else error E E1 + E2 E.place = newtemp; emit (E.place, =, E1.place, +, E2.place) E E1 E.place = newtemp; emit (E.place, =, uminus, E1.place) E (E1) E.place = E1.place E id p = lookup();if p nil then E.place = p else error 7.3 賦賦 值值 語語 句句7.3.2 臨時(shí)名字的重新使用臨時(shí)名字的重新使

20、用 大量臨時(shí)變量的使用對優(yōu)化有利大量臨時(shí)變量的使用對優(yōu)化有利 大量臨時(shí)變量會增加符號表管理的負(fù)擔(dān)大量臨時(shí)變量會增加符號表管理的負(fù)擔(dān) 也會增加運(yùn)行時(shí)臨時(shí)數(shù)據(jù)占的空間也會增加運(yùn)行時(shí)臨時(shí)數(shù)據(jù)占的空間7.3 賦賦 值值 語語 句句7.3.3 數(shù)組元素的地址計(jì)算數(shù)組元素的地址計(jì)算一維數(shù)組一維數(shù)組A的第的第i個(gè)元素的地址計(jì)算個(gè)元素的地址計(jì)算base + ( i low ) w7.3 賦賦 值值 語語 句句7.3.3 數(shù)組元素的地址計(jì)算數(shù)組元素的地址計(jì)算一維數(shù)組一維數(shù)組A的第的第i個(gè)元素的地址計(jì)算個(gè)元素的地址計(jì)算base + ( i low ) w 重寫成重寫成i w + (base low w)可減少了運(yùn)

21、行時(shí)的計(jì)算量可減少了運(yùn)行時(shí)的計(jì)算量7.3 賦賦 值值 語語 句句二維數(shù)組二維數(shù)組 列為主列為主A1, 1, A2, 1, A1, 2, A2, 2, A1, 3, A2, 37.3 賦賦 值值 語語 句句二維數(shù)組二維數(shù)組 列為主列為主A1, 1, A2, 1, A1, 2, A2, 2, A1, 3, A2, 3 行為主行為主A1, 1, A1, 2, A1, 3, A2, 1, A2, 2, A2, 37.3 賦賦 值值 語語 句句二維數(shù)組二維數(shù)組 列為主列為主A1, 1, A2, 1, A1, 2, A2, 2, A1, 3, A2, 3 行為主行為主A1, 1, A1, 2, A1, 3

22、, A2, 1, A2, 2, A2, 3base + ( (i1 low1) n2 + (i2 low2 ) ) w（其中其中n2 = high2 low2 + 1）7.3 賦賦 值值 語語 句句二維數(shù)組二維數(shù)組 列為主列為主A1, 1, A2, 1, A1, 2, A2, 2, A1, 3, A2, 3 行為主行為主A1, 1, A1, 2, A1, 3, A2, 1, A2, 2, A2, 3base + ( (i1 low1) n2 + (i2 low2 ) ) w（其中其中n2 = high2 low2 + 1）( (i1 n2 ) + i2 ) w + (base ( (low1

23、n2 ) + low2 ) w)7.3 賦賦 值值 語語 句句多維數(shù)組多維數(shù)組Ai1, i2, ., ik 的地址表達(dá)式的地址表達(dá)式( ( ( (i1 n2 + i2 ) n3 + i3 ) ) nk + ik) w + base ( ( ( (low1 n2 + low2) n3 + low3) ) nk + lowk ) w7.3 賦賦 值值 語語 句句7.3.4 數(shù)組元素地址計(jì)算的翻譯方案數(shù)組元素地址計(jì)算的翻譯方案下標(biāo)變量訪問的產(chǎn)生式下標(biāo)變量訪問的產(chǎn)生式L id Elist | idElist Elist, E | E改成改成L Elist | idElist Elist, E | id

24、 E7.3 賦賦 值值 語語 句句所有產(chǎn)生式所有產(chǎn)生式S L = EE E + EE (E )E LL Elist L idElist Elist, EElist id E7.3 賦賦 值值 語語 句句L id L.place = id.place; L.offset = null 7.3 賦賦 值值 語語 句句L id L.place = id.place; L.offset = null Elist id E Elist.place = E.place; Elist.ndim = 1; Elist.array = id.place 7.3 賦賦 值值 語語 句句L id L.place =

25、 id.place; L.offset = null Elist id E Elist.place = E.place; Elist.ndim = 1; Elist.array = id.place Elist Elist1, E t = newtemp; m = Elist1.ndim + 1; emit (t, =, Elist1.place, , limit(Elist1.array, m) ); emit (t, =, t, +, E.place); Elist.array = Elist1.array; Elist.place = t; Elist.ndim = m7.3 賦賦 值值

26、 語語 句句L id L.place = id.place; L.offset = null Elist id E Elist.place = E.place; Elist.ndim = 1; Elist.array = id.place Elist Elist1, E t = newtemp; m = Elist1.ndim + 1; emit (t, =, Elist1.place, , limit(Elist1.array, m) ); emit (t, =, t, +, E.place); Elist.array = Elist1.array; Elist.place = t; Eli

27、st.ndim = mL Elist L.place = newtemp; emit (L.place, =, base(Elist.array), ,invariant (Elist.array) ); L.offset = newtemp; emit (L.offset, =, Elist.place, , w) 7.3 賦賦 值值 語語 句句E Lif L.offset = null then / L是簡單變量是簡單變量 / E.place = L.place else begin E.place = newtemp; emit (E.place, =, L.place, , L.off

28、set, ) end 7.3 賦賦 值值 語語 句句E Lif L.offset = null then / L是簡單變量是簡單變量 / E.place = L.place else begin E.place = newtemp; emit (E.place, =, L.place, , L.offset, ) end E E1 + E2E.place = newtemp;emit (E.place, =, E1.place , +, E2.place) 7.3 賦賦 值值 語語 句句E Lif L.offset = null then / L是簡單變量是簡單變量 / E.place = L

29、.place else begin E.place = newtemp; emit (E.place, =, L.place, , L.offset, ) end E E1 + E2E.place = newtemp;emit (E.place, =, E1.place , +, E2.place) E (E1 )E.place = E1.place 7.3 賦賦 值值 語語 句句E Lif L.offset = null then / L是簡單變量是簡單變量 / E.place = L.place else begin E.place = newtemp; emit (E.place, =,

30、 L.place, , L.offset, ) end E E1 + E2E.place = newtemp;emit (E.place, =, E1.place , +, E2.place) E (E1 )E.place = E1.place S L = Eif L.offset = null then / L是簡單變量是簡單變量 /emit (L.place, = , E.place)else emit (L.place , , L.offset, , =, E.place) 7.3 賦賦 值值 語語 句句S=L.place = xL.offset = nullxE.place = t4L

31、.place = t2L.offset = t3Elist.place = t1Elist.ndim = 2Elist.array = A,Elist.place = yElist.ndim = 1Elist.array = AE.place = zL.place = zL.offset = nullE.place = yL.place = yL.offset = nullAzy x = A y, z 的注釋分析樹的注釋分析樹7.3 賦賦 值值 語語 句句S=L.place = xL.offset = nullxE.place = t4L.place = t2L.offset = t3Elis

32、t.place = t1Elist.ndim = 2Elist.array = A,Elist.place = yElist.ndim = 1Elist.array = AE.place = zL.place = zL.offset = nullE.place = yL.place = yL.offset = nullAzy x = A y, z 的注釋分析樹的注釋分析樹t1 = y 20 t1 = t1 + z 7.3 賦賦 值值 語語 句句S=L.place = xL.offset = nullxE.place = t4L.place = t2L.offset = t3Elist.plac

33、e = t1Elist.ndim = 2Elist.array = A,Elist.place = yElist.ndim = 1Elist.array = AE.place = zL.place = zL.offset = nullE.place = yL.place = yL.offset = nullAzy x = A y, z 的注釋分析樹的注釋分析樹t1 = y 20 t1 = t1 + z t2 =A 84 t3 = 4 t1 7.3 賦賦 值值 語語 句句S=L.place = xL.offset = nullxE.place = t4L.place = t2L.offset =

34、 t3Elist.place = t1Elist.ndim = 2Elist.array = A,Elist.place = yElist.ndim = 1Elist.array = AE.place = zL.place = zL.offset = nullE.place = yL.place = yL.offset = nullAzy x = A y, z 的注釋分析樹的注釋分析樹t1 = y 20 t1 = t1 + z t2 =A 84 t3 = 4 t1 t4 = t2 t3 7.3 賦賦 值值 語語 句句S=L.place = xL.offset = nullxE.place =

35、t4L.place = t2L.offset = t3Elist.place = t1Elist.ndim = 2Elist.array = A,Elist.place = yElist.ndim = 1Elist.array = AE.place = zL.place = zL.offset = nullE.place = yL.place = yL.offset = nullAzy x = A y, z 的注釋分析樹的注釋分析樹t1 = y 20 t1 = t1 + z t2 =A 84 t3 = 4 t1 t4 = t2 t3 x = t4 7.4 布爾表達(dá)式和控制流語句布爾表達(dá)式和控制

36、流語句布爾表達(dá)式有兩個(gè)基本目的布爾表達(dá)式有兩個(gè)基本目的 計(jì)算邏輯值計(jì)算邏輯值 在控制流語句中用作條件表達(dá)式在控制流語句中用作條件表達(dá)式7.4 布爾表達(dá)式和控制流語句布爾表達(dá)式和控制流語句布爾表達(dá)式有兩個(gè)基本目的布爾表達(dá)式有兩個(gè)基本目的 計(jì)算邏輯值計(jì)算邏輯值 在控制流語句中用作條件表達(dá)式在控制流語句中用作條件表達(dá)式布爾表達(dá)式的完全計(jì)算布爾表達(dá)式的完全計(jì)算布爾表達(dá)式的布爾表達(dá)式的“短路短路”計(jì)算計(jì)算B1 or B2 定義成定義成 if B1 then true else B2B1 and B2 定義成定義成 if B1 then B2 else false7.4 布爾表達(dá)式和控制流語句布爾表達(dá)式和

37、控制流語句7.4.1 布爾表達(dá)式的翻譯布爾表達(dá)式的翻譯B B or B | B and B | not B | ( B ) | id relop id | true | falsea b的翻譯的翻譯100: if a b goto 103101: t = 0102: goto 104103: t = 1104:7.4 布爾表達(dá)式和控制流語句布爾表達(dá)式和控制流語句B B1 or B2 B.place = newtemp; emit (B.place, =, B1.place, or B2.place) B id1 relop id2B.place = newtemp; emit (if, id1

38、.place, relop.op, id2.place, goto, nextstat+3 ); emit (B.place, =, 0 ); emit (goto, nextstat + 2 ); emit (B.place, =, 1 ) 7.4 布爾表達(dá)式和控制流語句布爾表達(dá)式和控制流語句7.4.2 控制流語句的翻譯控制流語句的翻譯S if B then S1| if B then S1 else S2| while B do S1| S1; S2 7.4 布爾表達(dá)式和控制流語句布爾表達(dá)式和控制流語句B.codeS1.codeB.true:. . .指向指向B.true指向指向B.fal

39、se(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; S27.4 布爾表達(dá)式和控制流語句布爾表達(dá)式和控制流語句S if B then S1B.true = newlabel; B.false = S.next; S1.nex

40、t = S.next; S.code = B.code | gen(B.true, :) | S1.code B.codeS1.codeB.true:. . .指向指向B.true指向指向B.false(a) if-then7.4 布爾表達(dá)式和控制流語句布爾表達(dá)式和控制流語句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) |

41、gen(B.false, :) | S2.code B.codeS1.codeB.true:. . .指向指向B.true指向指向B.falseB.false:goto S.nextS2.code(b) if-then-else7.4 布爾表達(dá)式和控制流語句布爾表達(dá)式和控制流語句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(go

42、to, S.begin) B.codeS1.codeB.true:. . .指向指向B.true指向指向B.falsegoto S.beginS.begin:(c) while-do7.4 布爾表達(dá)式和控制流語句布爾表達(dá)式和控制流語句S S1; S2S.code = S1.code | gen(S1.next, :) | S2.code S1.codeS2.codeS1.next:. . .(d) S1; S27.4 布爾表達(dá)式和控制流語句布爾表達(dá)式和控制流語句7.4.3 布爾表達(dá)式的控制流翻譯布爾表達(dá)式的控制流翻譯如果如果B是是a b的形式，的形式，那么代碼是：那么代碼是：if a b go

43、to B.truegoto B.false7.4 布爾表達(dá)式和控制流語句布爾表達(dá)式和控制流語句表達(dá)式表達(dá)式a b or c d and e f的代碼是：的代碼是：if a b goto Ltruegoto L1L1:if c d goto L2goto LfalseL2:if e f goto Ltruegoto Lfalse7.4 布爾表達(dá)式和控制流語句布爾表達(dá)式和控制流語句B B1 or B2B1.true = B.true; B1.false = newlabel; B2.true = B.true; B2.false = B.false; B.code = B1.code | gen(

44、B1.false, :) | B2.code 7.4 布爾表達(dá)式和控制流語句布爾表達(dá)式和控制流語句B B1 or 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 not B1B1.true = B.false; B1.false = B.true; B.code = B1.code 7.4 布爾表達(dá)式和控制流語句布爾表達(dá)式和控制流語句B B1 and B2B1.true = newlabel

45、; B1.false = B.false; B2.true = B.true; B2.false = B.false; B.code = B1.code | gen(B1.true, :) | B2.code 7.4 布爾表達(dá)式和控制流語句布爾表達(dá)式和控制流語句B B1 and B2B1.true = newlabel; B1.false = B.false; B2.true = B.true; B2.false = B.false; B.code = B1.code | gen(B1.true, :) | B2.code B (B1 ) B1.true = B.true; B1.false

46、= B.false; B.code = B1.code 7.4 布爾表達(dá)式和控制流語句布爾表達(dá)式和控制流語句B id1 relop id2B.code = gen(if, id1.place, relop.op, id2.place, goto, B.true) | gen(goto, B.false) 7.4 布爾表達(dá)式和控制流語句布爾表達(dá)式和控制流語句B id1 relop id2B.code = gen(if, id1.place, relop.op, id2.place, goto, B.true) | gen(goto, B.false) B trueB.code = gen(got

47、o, B.true)B falseB.code = gen(goto, B.false)布爾表達(dá)式的語法制導(dǎo)定義布爾表達(dá)式的語法制導(dǎo)定義B B1 or B2B1.true = B.true; B1.false = newlabel; B2.true = B.true; B2.false = B.false; B.code = B1.code | gen(B1.false, :) | B2.codeB not B1B1.true = B.false; B1.false = B.true; B.code = B1.codeB B1 and B2B1.true = newlabel; B1.fals

48、e = B.false; B2.true = B.true; B2.false = B.false; B.code = B1.code | gen(B1.true, :) | B2.codeB (B1 ) B1.true = B.true; B1.false = B.false; B.code = B1.codeB id1 relop id2B.code = gen(if, id1.place, relop.op, id2.place, goto, B.true) |gen(goto, B.false)B trueB.code = gen(goto, B.true）B falseB.code

49、= gen(goto, B.false)控制流語句的語法制導(dǎo)定義控制流語句的語法制導(dǎo)定義S if B then S1B.true = newLabel;B.false = S.next;S1.next = S.next;S.code = B.code | gen(B.true, :) | S1.code 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,

50、 S.next) | gen(B.false, :) | S2.codeS 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.beginS S1; S2S.code = S1.code | gen(S1.next, :) | S2.code例例 考慮語句考慮語句 while ab do if cd then x=y+z else

51、 x=y-z7.4 布爾表達(dá)式和控制流語句布爾表達(dá)式和控制流語句7.4.4 開關(guān)語句的翻譯開關(guān)語句的翻譯switch Ebegincase V1: S1case V2: S2. . .case Vn - 1: Sn 1default: Snend7.4 布爾表達(dá)式和控制流語句布爾表達(dá)式和控制流語句 分支數(shù)較少時(shí)分支數(shù)較少時(shí)t = E的代碼的代碼 | Ln-2: if t != Vn-1 goto Ln-1 if t != V1 goto L1 | Sn -1的代碼的代碼 S1的代碼的代碼 | goto nextgoto next | Ln-1: Sn的代碼的代碼 L1:if t != V2 g

52、oto L2 | next: S2的代碼的代碼goto nextL2:. . . . . 7.4 布爾表達(dá)式和控制流語句布爾表達(dá)式和控制流語句 分支較多時(shí)，將分支測試代碼集中在一起，便于生分支較多時(shí)，將分支測試代碼集中在一起，便于生成較好的分支測試代碼成較好的分支測試代碼t = E的代碼的代碼| Ln: Sn的代碼的代碼goto test | goto nextL1:S1的代碼的代碼 |test: if t = V1 goto L1 goto next| if t = V2 goto L2 L2:S2的代碼的代碼 | . . .goto next|if t = Vn-1 goto Ln-1. . . |goto LnLn-1: Sn -1的代碼的代碼 | next:goto next