編譯原理與技術(shù)PPT課件

1、第第7 7章章 中間代碼生成中間代碼生成編譯原理與技術(shù)編譯原理與技術(shù) 介紹幾種常用的中間表示： 后綴表示、圖形表示和三地址代碼 用語法制導(dǎo)定義和翻譯方案來說明源語言的各種構(gòu)造怎樣被翻譯成中間形式 7 7 中間代碼生成中間代碼生成內(nèi)容提要內(nèi)容提要分析器靜態(tài)檢查器中間代碼生成器中間代碼記號流代碼生成器7.1 7.1 中間語言中間語言第第7 7章章 中間代碼生成中間代碼生成7.1.1 后綴表示 E E op E | uop E | (E) | id | num表達式E的后綴表示可以如下歸納定義：表達式E后綴式EididnumnumE1 op E2E1 E2 opuop EE uop(E)E7.1 7

2、.1 中間語言中間語言 后綴表示不需要括號(8 - 5) + 2 的后綴表示是8 5 - 2 + 后綴表示的最大優(yōu)點是便于計算機處理表達式計算棧輸入串8 5 - 2 +85 - 2 +8 5- 2 +32 +3 2+5 后綴表示也可以拓廣到表示賦值語句和控制語句，但很難用棧來描述控制語句的計算7.1 7.1 中間語言中間語言7.1.2 圖形表示 語法樹是一種圖形化的中間表示 有向無環(huán)圖也是一種中間表示7.1 7.1 中間語言中間語言assigna+bcduminus(b) DAGDirected Acyclical Graphsassigna+bcdcduminus(a) 語法樹 a = (

3、- b + c d ) + c d 的圖形表示構(gòu)造賦值語句語法樹的語法制導(dǎo)定義修改構(gòu)造結(jié)點的函數(shù)可生成有向無環(huán)圖7.1 7.1 中間語言中間語言產(chǎn) 生 式 語 義 規(guī) 則S id = E S.nptr = mkNode( assign, mkLeaf (id, id.entry), E.nptr) E E1 + E2 E.nptr = mkNode( +, E1.nptr, E2.nptr) E E1 E2E.nptr = mkNode( , E1.nptr, E2.nptr) E - E1E.nptr = mkUNode( uminus, E1.nptr) E (E1) E.nptr = E

4、1.nptr F id E.nptr = mkLeaf (id, id.entry) 7.1.3 三地址代碼一般形式：x = y op z 例 表達式x + y z翻譯成的三地址語句序列是t1 = y z t2 = x + t1 7.1 7.1 中間語言中間語言 三地址代碼是語法樹或DAG的一種線性表示 例a = ( - b + c d ) + c d語法樹的代碼t1 = - bt2 = c dt3 = t1 + t2t4 = c dt5 = t3 + t4a = t57.1 7.1 中間語言中間語言assigna+bcdcduminusDAG的代碼t1 = - bt2 = c dt3 = t

5、1 + t2t4 = t3 + t2a = t4assigna+bcduminus本書常用的三地址語句 賦值語句 x = y op z， x = op y， x = y 無條件轉(zhuǎn)移 goto L 條件轉(zhuǎn)移 if x relop y goto L 過程調(diào)用 param x 和 call p , n 過程返回 return y 索引賦值 x = yi 和 xi = y 地址和指針賦值 x = &y，x = y 和 x = y7.1 7.1 中間語言中間語言7.1.4 靜態(tài)單賦值形式 一種便于某些代碼優(yōu)化的中間表示 和三地址代碼的主要區(qū)別 所有賦值指令都是對不同名字的變量的賦值三地址代碼靜態(tài)

6、單賦值形式p = a +bp1 = a +b q = p - cq1 = p1 - c p = q dp2 = q1 d p = e - pp3 = e - p2 q = p + q q2 = p3 + q17.1 7.1 中間語言中間語言 一個變量在不同路徑上都定值的解決辦法if (flag) x = 1; else x = 1;y = x a;改成if (flag) x1 = 1; else x2 = 1;x3 = (x1, x2);/由flag的值決定用x1還是x2y = x x3;7.1 7.1 中間語言中間語言7.2 7.2 聲明語句聲明語句第第7 7章章 中間代碼生成中間代碼生成本

7、節(jié)介紹 為局部名字建立符號表條目 為它分配存儲單元 符號表中包含名字的類型和分配給它的存儲單元的相對地址等信息7.2 7.2 聲明聲明語句語句7.2.1 過程中的聲明計算被聲明名字的類型和相對地址P offset = 0 D; SD D ; D D id : T enter ( id.lexeme, T.type, offset);offset = offset + T.width T integer T.type = integer; T.width = 4 T real T.type = real; T.width = 8 T array num of T1T.type = array (

8、num.val, T1.type);T.width = num.val T1.widthT T1 T.type = pointer (T1.type); T.width = 4 7.2 7.2 聲明聲明語句語句7.2.2 作用域信息的保存 所討論語言的文法P D; SD D ; D | id : T | proc id ; D ; S 7.2 7.2 聲明聲明語句語句sort var a:; x:; readarray var i:; exchange quicksort var k, v:; partition var i, j:;圖6.14的程序參數(shù)被略去7.2 7.2 聲明聲明語句語句e

9、xchangereadarrayxa表 頭空sortquicksort指向readarraypartitionvk表 頭quicksortreadarrayi表 頭exchange表 頭指向exchangepartitionsort readarray exchange quicksort partition 符號表的特點 各過程有各自的符號表 符號表之間有雙向鏈 構(gòu)造符號表時需要符號表棧 構(gòu)造符號表需要偏移記錄棧 語義動作用到的函數(shù)mkTable(previous) /創(chuàng)立新表enter(table, name, type, offset) /增加新的id條目addWidth(table,

10、width) /將表大小寫入表中enterProc(table, name, newtable) /添加新的表條目7.2 7.2 聲明聲明語句語句P M D ; S addWidth (top (tblptr), top (offset); pop(tblptr); pop (offset) M t = mkTable (nil);push(t, tblprt); push (0, offset) D D1 ; D2D proc id ; N D1; S t = top(tblptr);addWidth(t, top(offset) ); pop(tblptr); pop(offset);en

11、terProc(top(tblptr), id.lexeme, t) D id : T enter(top(tblptr), id.lexeme, T.type, top(offset);top(offset) = top(offset) + T.width N t = mkTable(top(tblptr) );push(t, tblptr); push(0, offset) 7.2 7.2 聲明聲明語句語句7.2.3 記錄的域名T record D end記錄類型單獨建符號表，作為類型表達式的主要部分，域的相對地址從0開始T record L D endT.type = record (t

12、op(tblptr) ); T.width = top(offset); pop(tblptr); pop(offset) L t = mkTable(nil); push(t, tblprt); push(0, offset) 7.2 7.2 聲明聲明語句語句record a : ; r : record i : ; . . . end; k : ;end7.3 7.3 賦值語句賦值語句第第7 7章章 中間代碼生成中間代碼生成7.3.1 符號表中的名字S id := E p = lookup(id.lexeme);if p != nil thenemit ( p, = , E.place)e

13、lse 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(id.lexeme);if p != nil then E.place = p else error 7.3 7.3 賦值語句賦值語句7.3.2 數(shù)組元素的地址計算一維數(shù)組A的第i個元素的地址計算base + ( i -

14、 low ) w 變換成i w + (base - low w)減少了運行時的計算7.3 7.3 賦值語句賦值語句二維數(shù)組A: array1.2, 1.3 of T 列為主A1, 1, A2, 1, A1, 2, A2, 2, A1, 3, A2, 3 行為主A1, 1, A1, 2, A1, 3, A2, 1, A2, 2, A2, 3Ai1, i2的地址：base + (i1-low1)n2 + (i2-low2 )w (其中n2=high2-low2+1)變換成 (i1n2 )+i2)w + base-(low1n2)+low2)w7.3 7.3 賦值語句賦值語句A1, 1 A1, 2

15、A1, 3A2, 1 A2, 2 A2, 3i1i2A1, 1 A1, 2 A2, 1 A2, 2 多維數(shù)組下標(biāo)變量Ai1, i2, ., ik的地址表達式( ( ( (i1n2+i2)n3+i3) )nk+ik)w + base(low1n2+low2)n3+low3) )nk+lowk)w7.3 7.3 賦值語句賦值語句7.3.3 數(shù)組元素地址計算的翻譯方案 下標(biāo)變量訪問的產(chǎn)生式L id Elist | idElist Elist, E | E不便于在處理下標(biāo)表達式時到符號表取信息 為便于寫語義動作，改成等價的L Elist | idElist Elist, E | id E7.3 7.3

16、 賦值語句賦值語句 所有產(chǎn)生式S L := EE E + EE (E )E LL Elist L idElist Elist, EElist id E7.3 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; Elist Elist1, E t = newTemp(); m = Elist1.ndim + 1;emit (t, =, Elist1.place, , limit(Elist1.ar

17、ray, m); );emit (t, =, t, +, E.place); Elist.array = Elist1.array;Elist.place = t; Elist.ndim = m; L Elist L.place = newTemp();emit (L.place, =, base(Elist.array), -, invariant(Elist.array);L.offset = newTemp();emit (L.offset, =, Elist.place, , width(Elist.array); 7.3 7.3 賦值語句賦值語句E L if L.offset = n

18、ull then / L是簡單變量 /E.place = L.place;else E.place = newTemp();emit (E.place, =, L.place, , L.offset, ); E E1 + E2 E.place = newTemp();emit (E.place, =, E1.place , +, E2.place); E ( E1 ) E.place = E1.place; S L := E if L.offset = null then / L是簡單變量 /emit (L.place, =, E.place);else emit (L.place , , L

19、.offset, , =, E.place); 7.3 7.3 賦值語句賦值語句7.3 7.3 賦值語句賦值語句S:=L.place = xL.offset = nullxE.place = 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,

20、 z 的注釋分析樹t1 = y 20 t1 = t1 + z t2 = c t3 = t1 4t4 = t2 t3 x = t4 注：c =A 84 A10, 20考慮C語言中數(shù)組double a1020，寫出計算aij、ai+1和a+i的三地址中間代碼 a: pointer(array(20,double) ai: pointer(double) aij: double7.3 7.3 賦值語句賦值語句例題例題aij: t1=i*20 t2=t1+j t3=t2*8 t4=at3ai+1: t1=i*20 t2=t1*8 t3=a+t2 t4=1*8 t5=t3+t4a+i: t1=a t2=

21、20*8 t3=t2*i t4=t1+t37.3.4 類型轉(zhuǎn)換 例x = y + i j（x和y的類型是real，i和j的類型是integer）中間代碼t1 = i int jt2 = inttoreal t1 t3 = y real+ t2 x = t37.3 7.3 賦值語句賦值語句E E1 + E2 E.place = newTemp();if E1.type = integer & E2.type = integer then emit (E.place, =, E1.place, int+, E2.place);E.type = integer; elseif E1.type

22、 = integer & E2.type = real then u = newTemp();emit (u, =, inttoreal, E1.place);emit (E.place, =, u, real+, E2.place);E.type = real; . . .7.3 7.3 賦值語句賦值語句7.4 7.4 布爾表達式布爾表達式和控制流語句和控制流語句第第7 7章章 中間代碼生成中間代碼生成7.4.1 布爾表達式 布爾表達式有兩個基本目的 計算邏輯值 在控制流語句中用作條件表達式 本節(jié)所用的布爾表達式文法B B or B | B and B | not B | ( B )

23、| E relop E | true | false7.4 7.4 布爾表達式布爾表達式和控制流語句和控制流語句 布爾表達式的完全計算 值的表示數(shù)值化 其計算類似于算術(shù)表達式的計算 布爾表達式的“短路”計算 B1 or B2定義成if B1 then true else B2 B1 and B2定義成if B1 then B2 else false 用控制流來實現(xiàn)計算，即用程序中的位置來表示值，因為布爾表達式通常用來決定控制流走向 兩種不同計算方式會導(dǎo)致程序的結(jié)果不一樣7.4 7.4 布爾表達式布爾表達式和控制流語句和控制流語句7.4.2 控制流語句的翻譯S if B then S1| if

24、B then S1 else S2| while B do S1| S1; S2 7.4 7.4 布爾表達式布爾表達式和控制流語句和控制流語句7.4 7.4 布爾表達式布爾表達式和控制流語句和控制流語句B.codeS1.codeB.true:. . .指向B.true指向B.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

25、:(c) while-doS1.codeS2.codeS1.next:. . .(d) S1; S2B.false:如果給如果給If-then添加添加false標(biāo)號，當(dāng)它嵌入其它語句時，標(biāo)號，當(dāng)它嵌入其它語句時，可能會可能會產(chǎn)生冗余跳轉(zhuǎn)指令產(chǎn)生冗余跳轉(zhuǎn)指令S if B then S1 B.true = newLabel(); B.false = S.next; S1.next = S.next; S.code = B.code | gen(B.true, :) | S1.code 7.4 7.4 布爾表達式布爾表達式和控制流語句和控制流語句B.codeS1.codeB.true:. . .指向

26、B.true指向B.false(a) if-thenS if B then S1 else S2 B.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 7.4 7.4 布爾表達式布爾表達式和控制流語句和控制流語句B.codeS1.codeB.true:. . .指向B.true指向B.falseB.false: g

27、oto S.nextS2.code(b) if-then-elseS 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) 7.4 7.4 布爾表達式布爾表達式和控制流語句和控制流語句B.codeS1.codeB.true:. . .指向B.true指向B.falsegoto S.beginS.begi

28、n:(c) while-doS S1; S2 S1.next = newLabel(); S2.next = S.next; S.code = S1.code | gen(S1.next, :) | S2.code 7.4 7.4 布爾表達式布爾表達式和控制流語句和控制流語句S1.codeS2.codeS1.next:. . .(d) S1; S27.4.3 布爾表達式的控制流翻譯如果B是 a b 的形式，那么代碼是：if a b goto B.truegoto B.false 例 表達式 a b or c d and e f 的代碼是：if a b goto Ltruegoto L1L1:i

29、f c d goto L2goto LfalseL2:if e f goto Ltruegoto Lfalse7.4 7.4 布爾表達式布爾表達式和控制流語句和控制流語句B B1 or B2 B1.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 B1 B1.true = B.false; B1.false = B.true; B.code = B1.code 7.4 7.4 布爾表達式布爾

30、表達式和控制流語句和控制流語句B B1 and B2 B1.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 = B.false; B.code = B1.code 7.4 7.4 布爾表達式布爾表達式和控制流語句和控制流語句B E1 relop E2 B.code = E1.code | E2.code |gen(if, E1.pla

31、ce, relop.op, E2.place, goto, B.true) |gen(goto, B.false) B true B.code = gen(goto, B.true)B false B.code = gen(goto, B.false)7.4 7.4 布爾表達式布爾表達式和控制流語句和控制流語句7.4.4 開關(guān)語句的翻譯switch Ebegincase V1: S1case V2: S2. . .case Vn-1: Sn-1default: Snend7.4 7.4 布爾表達式布爾表達式和控制流語句和控制流語句 分支數(shù)較少時t = E的代碼| Ln-2:if t != Vn

32、-1 goto Ln-1if t != V1 goto L1|Sn -1的代碼S1的代碼|goto nextgoto next| Ln-1:Sn的代碼L1:if t != V2 goto L2| next:S2的代碼|goto next|L2:. . .|. . . |7.4 7.4 布爾表達式布爾表達式和控制流語句和控制流語句 分支較多時，將分支測試代碼集中在一起，便于生成較好的分支測試代碼t = E的代碼| Ln:Sn的代碼goto test|goto nextL1:S1的代碼| test:if t = V1 goto L1goto next|if t = V2 goto L2L2:S2的

33、代碼|. . .goto next|if t = Vn-1 goto Ln-1. . .|goto LnLn-1: Sn -1的代碼| next:goto next|7.4 7.4 布爾表達式布爾表達式和控制流語句和控制流語句 中間代碼增加一種case語句，便于代碼生成器對它進行特別處理 test: case V1L1case V2L2. . .case Vn-1Ln-1case tLn next: 7.4 7.4 布爾表達式布爾表達式和控制流語句和控制流語句一個生成： 用二分查找確定該執(zhí)行的分支 直接找到該執(zhí)行的分支的例子見第8章習(xí)題7.4.5 過程調(diào)用的翻譯S call id (Elist

34、)Elist Elist, EElist E 過程調(diào)用id(E1, E2, , En)的中間代碼結(jié)構(gòu)E1.place = E1的代碼E2.place = E2的代碼. . .En.place = En的代碼param E1.placeparam E2.place. . .param En.placecall id.place, n7.4 7.4 布爾表達式布爾表達式和控制流語句和控制流語句S call id (Elist) 為長度為n的隊列中的每個E.place， emit(param, E.place); emit(call, id.plase, n) Elist Elist, E 把E.p

35、lace放入隊列末尾 Elist E 將隊列初始化，并讓它僅含E.place 7.4 7.4 布爾表達式布爾表達式和控制流語句和控制流語句Pascal語言的標(biāo)準(zhǔn)將for語句for v := initial to final do stmt定義成和下面的代碼序列有同樣的含義：begint1 := initial; t2 := final;if t1= t2 then beginv := t1; stmt;while v t2 do beginv := succ(v); stmtendendend7.4 7.4 布爾表達式布爾表達式和控制流語句和控制流語句例題例題1 1for v := initial to final do stmt能否定義成和下面的代碼序列有同樣的含義？begint1 := initial; t2 := final;v := t1;while v t2 goto L1v = t1L2:stmtif v = t2 goto L1v = v + 1goto L2L1: 7.4 7.4 布爾表達式布爾表達式和控制流語句和控制流語句例題例題1 1C語言的for語句有下列形式for ( e1 ; e2 ; e3 ) stmt它和e1;while ( e2 ) do beginstmt;