天津大學編譯原理講義 - Part7語義分析及中間代碼生成

1、語義分析與中間代碼生成語義分析與中間代碼生成授課：胡靜授課：胡靜語義分析的位置和作用語義分析的位置和作用緊跟在語法分析和語法分析之后，編譯程序要做的工緊跟在語法分析和語法分析之后，編譯程序要做的工作就是進行靜態(tài)語義檢查和翻譯。作就是進行靜態(tài)語義檢查和翻譯。編譯器必須要檢查源程序是否符合源語言規(guī)定的語法編譯器必須要檢查源程序是否符合源語言規(guī)定的語法和語義要求。這種檢查稱為靜態(tài)檢查，檢查并報告程和語義要求。這種檢查稱為靜態(tài)檢查，檢查并報告程序中某些類型的錯誤。序中某些類型的錯誤。語法分析器語法分析器記號流記號流類型檢查器類型檢查器語法樹語法樹中間代碼中間代碼生成器生成器語法樹語法樹中間表示中間表示

2、靜態(tài)語義檢查靜態(tài)語義檢查靜態(tài)語義檢查通常包括：靜態(tài)語義檢查通常包括：類型檢查：如果操作符作用于不相容的操作數(shù)，編譯類型檢查：如果操作符作用于不相容的操作數(shù)，編譯器應該報錯器應該報錯控制流檢查：引起控制流從某個結(jié)構(gòu)中跳轉(zhuǎn)出來的語控制流檢查：引起控制流從某個結(jié)構(gòu)中跳轉(zhuǎn)出來的語句必須能夠決定控制流轉(zhuǎn)向的目標地址句必須能夠決定控制流轉(zhuǎn)向的目標地址唯一性檢查：有時，有的對象只能被定義一次。比如，唯一性檢查：有時，有的對象只能被定義一次。比如，同一同一case語句的標號不能相同，枚舉類型的元素不能語句的標號不能相同，枚舉類型的元素不能重復。重復。與名字相關的檢查：有時候要求同一名字在特定位置與名字相關的檢

3、查：有時候要求同一名字在特定位置出現(xiàn)兩次或多次（如，標識結(jié)構(gòu)的開始和結(jié)尾）出現(xiàn)兩次或多次（如，標識結(jié)構(gòu)的開始和結(jié)尾）摘要：語義分析摘要：語義分析檢查在詞法分析和語法分析中發(fā)現(xiàn)不了的錯誤檢查在詞法分析和語法分析中發(fā)現(xiàn)不了的錯誤范圍錯誤：范圍錯誤：變量沒有定義變量沒有定義多重定義多重定義類型錯誤類型錯誤給不同的類型進行賦值給不同的類型進行賦值使用不同數(shù)目的參數(shù)或者錯誤類型的參數(shù)對函數(shù)進行使用不同數(shù)目的參數(shù)或者錯誤類型的參數(shù)對函數(shù)進行調(diào)用調(diào)用返回語句的錯誤使用返回語句的錯誤使用語義分析語義分析類型檢查類型檢查使用類型檢查規(guī)則使用類型檢查規(guī)則靜態(tài)語義靜態(tài)語義=用形式化的框架描述類型檢查規(guī)則用形式化的框

4、架描述類型檢查規(guī)則也有控制流錯誤也有控制流錯誤必須保證必須保證break或者或者continue語句包含在語句包含在 while (或或 for)語句中語句中可以通過遍歷可以通過遍歷AST來輕松的發(fā)現(xiàn)控制流錯誤來輕松的發(fā)現(xiàn)控制流錯誤所處位置所處位置中間語言中間語言源語言的中間表示方法源語言的中間表示方法抽象語法樹抽象語法樹后綴式后綴式三地址代碼（包括三元式、四元式、間接三元式）三地址代碼（包括三元式、四元式、間接三元式）DAG圖表示圖表示后綴式后綴式后綴式表示又稱逆波蘭表示法。后綴式表示又稱逆波蘭表示法。這種表示法是：把運算量（操作數(shù)）寫在前面，把算符寫在這種表示法是：把運算量（操作數(shù)）寫在前

5、面，把算符寫在后面（后綴）。后面（后綴）。一個表達式的后綴形式可以如下定義：一個表達式的后綴形式可以如下定義：如果如果E是一個變量或常量，則是一個變量或常量，則E的后綴式是的后綴式是E自身自身如果如果E是是E1opE2形式的表達式，這里形式的表達式，這里op是任何二元操作符，則是任何二元操作符，則E的后綴式為的后綴式為E1E2op。這里。這里E1和和E2分別是分別是E1和和E2的后綴式。的后綴式。如果如果E是是(E1)形式的表達式，則形式的表達式，則E1的后綴式就是的后綴式就是E的后綴式的后綴式這種表示法用不著使用括號。這種表示法用不著使用括號。只要知道每個算符的目數(shù)，對于后綴式，無論從那一端

6、進行只要知道每個算符的目數(shù)，對于后綴式，無論從那一端進行掃描，都能對它正確的進行唯一分解掃描，都能對它正確的進行唯一分解后綴式后綴式表達式翻譯為后綴式的語義規(guī)則描述：表達式翻譯為后綴式的語義規(guī)則描述：其中其中E.code表示表示E的后綴式，的后綴式，op表示任何二元操作符，表示任何二元操作符，“|”表表示后綴形式的連接示后綴形式的連接產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則EE1 op E2E.code := E1.code | E2.code | opE(E1) E.code := E1.codeEidE.code := id圖表示法圖表示法圖表示法主要包括圖表示法主要包括DAG( Directed A

7、cyclic Graph )與抽象語法樹與抽象語法樹語法樹描述了源程序的自然層次結(jié)構(gòu)。語法樹描述了源程序的自然層次結(jié)構(gòu)。DAG以更緊湊的形式給出了相同的以更緊湊的形式給出了相同的信息。兩者不同的是：信息。兩者不同的是：在一個在一個DAG中代表公共子表達式的結(jié)點具有多個父結(jié)點中代表公共子表達式的結(jié)點具有多個父結(jié)點在一顆抽象語法樹中公共子表達式被表示為重復的子樹。在一顆抽象語法樹中公共子表達式被表示為重復的子樹。assign+a*uminusbcuminusbca:= b*-c + b*-cassign+a*uminusbcabc uminus * bc numinus *+ assign抽象語法

8、樹抽象語法樹語法樹中的邊不會顯式的出現(xiàn)在后綴表達式中，可以根據(jù)結(jié)點出現(xiàn)的順序語法樹中的邊不會顯式的出現(xiàn)在后綴表達式中，可以根據(jù)結(jié)點出現(xiàn)的順序及結(jié)點上的操作符所要求的操作數(shù)的個數(shù)來恢復。其恢復過程類似使用棧及結(jié)點上的操作符所要求的操作數(shù)的個數(shù)來恢復。其恢復過程類似使用棧對后綴表達式求值。對后綴表達式求值。如果函數(shù)如果函數(shù)mknode(op, child)和和mknode(op, left, right)盡可能返回一個指向一盡可能返回一個指向一個存在的結(jié)點的指針以代替建立新的結(jié)點，那么就會生成個存在的結(jié)點的指針以代替建立新的結(jié)點，那么就會生成DAG圖。圖。產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則Sid :=

9、ES.nptr := mknode(assign, mkleaf(id, id.place), E.nptr) 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+*uminusuminusidbidbidcidc

10、0idb1idc2uminus13*024idb5idc6uminus57*468+379ida10assign9811三地址代碼三地址代碼三地址代碼是下列一般形式的語句序列三地址代碼是下列一般形式的語句序列x := y op z其中，其中，x、y和和z是名字，常量或編譯器生成的臨時變量是名字，常量或編譯器生成的臨時變量op代表任何操作符（定點運算符、浮點運算符、邏輯運算符等）代表任何操作符（定點運算符、浮點運算符、邏輯運算符等）這里不允許組合的算術(shù)表達式，因為語句右邊只有一個操作符。這里不允許組合的算術(shù)表達式，因為語句右邊只有一個操作符。像像x+y*z這樣的表達式要翻譯為如下；這樣的表達式要

11、翻譯為如下；T1 := y * zT2 := x + T1其中其中T1 ，T2為編譯時產(chǎn)生的臨時變量。為編譯時產(chǎn)生的臨時變量。三地址代碼三地址代碼這種復雜算術(shù)表達式和嵌套控制流語句的拆解使得三這種復雜算術(shù)表達式和嵌套控制流語句的拆解使得三地址碼適用于目標代碼生成及優(yōu)化。地址碼適用于目標代碼生成及優(yōu)化。由程序計算出來的中間值的名字的使用使得三地址碼由程序計算出來的中間值的名字的使用使得三地址碼容易被重排列容易被重排列而不像后綴表達式那樣而不像后綴表達式那樣三地址碼可以看成是語法樹或三地址碼可以看成是語法樹或DAG的線性表示。的線性表示。三地址碼的得名原因是每條語句通常包含三個地址，三地址碼的得名

12、原因是每條語句通常包含三個地址，兩個是操作數(shù)地址，一個是結(jié)果地址。兩個是操作數(shù)地址，一個是結(jié)果地址。在實際的實現(xiàn)中，有程序員定義的名字被一個指向改在實際的實現(xiàn)中，有程序員定義的名字被一個指向改名字的符號表表項的指針所代替。名字的符號表表項的指針所代替。三地址碼三地址碼assign+a*uminusbcuminusbcassign+a*uminusbct1 := -ct2 := b * t1t3 := -ct4 := b * t3t5 := t2 + t4a := t5t1 := -ct2 := b * t1t3 := t2 + t2a := t3三地址語句的類型三地址語句的類型三地址語句類似于

13、匯編語言代碼。語句可以由符號標三地址語句類似于匯編語言代碼。語句可以由符號標號，而且存在各種控制流語句。號，而且存在各種控制流語句。符號標號代表存放中間代碼的數(shù)組中三地址代碼語句符號標號代表存放中間代碼的數(shù)組中三地址代碼語句的下標。下面列出本書中使用的三地址語句的種類：的下標。下面列出本書中使用的三地址語句的種類：形如形如x:= y op z的賦值語句，其中的賦值語句，其中op為二元算術(shù)算符或為二元算術(shù)算符或邏輯算符邏輯算符形如形如x:= op y的賦值語句，其中的賦值語句，其中op為一元算符。為一元算符。形如形如x:= y的復制語句，將的復制語句，將y的值賦給的值賦給x形如形如goto L的

14、無條件跳轉(zhuǎn)語句，即下一條將被執(zhí)行的的無條件跳轉(zhuǎn)語句，即下一條將被執(zhí)行的語句是帶有標號語句是帶有標號L的三地址語句的三地址語句三地址語句的類型三地址語句的類型下面列出本書中使用的三地址語句的種類：下面列出本書中使用的三地址語句的種類：形如形如if x relop y goto L或或 if a goto L的條件跳轉(zhuǎn)語句。的條件跳轉(zhuǎn)語句。第一種形式使用關系運算符號第一種形式使用關系運算符號relop（等）等）第二種第二種a為布爾變量或常量為布爾變量或常量用于過程調(diào)用的語句用于過程調(diào)用的語句param x和和call p, n，以及返回語句，以及返回語句return y。源程序中的過程調(diào)用源程序中

15、的過程調(diào)用p(x1,x2,xn)：param x1param x2param xncall p, n n表示實參個數(shù)。表示實參個數(shù)。return y中中y為過程返回的一個值為過程返回的一個值三地址語句的類型三地址語句的類型下面列出本書中使用的三地址語句的種類：下面列出本書中使用的三地址語句的種類：形如形如x := yi及及xi := y的索引賦值。的索引賦值。形如形如x := &y, x := *y和和*x := y的地址和指針賦值。的地址和指針賦值。設計中間代碼形式時，運算符的選擇是非常重要的。設計中間代碼形式時，運算符的選擇是非常重要的。算符種類應足以用來實現(xiàn)源語言中的運算。算符種類應足以

16、用來實現(xiàn)源語言中的運算。一個小型算符集合較易于在新的目標機器上實現(xiàn)。一個小型算符集合較易于在新的目標機器上實現(xiàn)。局限的指令集合會使某些源語言運算表示成中間形式局限的指令集合會使某些源語言運算表示成中間形式時代碼加長，需要在目標代碼生成時做較多的優(yōu)化工時代碼加長，需要在目標代碼生成時做較多的優(yōu)化工作。作。生成三地址碼的生成三地址碼的S-S-屬性文法屬性文法S具有綜合屬性具有綜合屬性S.code，代表賦值語句，代表賦值語句S的三地址碼的三地址碼非終結(jié)符非終結(jié)符E有如下性質(zhì)：有如下性質(zhì)：E.place表示存放表示存放E值的名字值的名字E.code表示對表示對E求值的三地址語句序列求值的三地址語句序列

17、函數(shù)函數(shù)newtemp的功能是每次調(diào)用它時，將返回一個不的功能是每次調(diào)用它時，將返回一個不同臨時變量的名字。如同臨時變量的名字。如T1,T2,.用用gen(x := y + z)表示生成三地址語句表示生成三地址語句x:=y+z。在實際實現(xiàn)中，三地址碼可能被送到輸出文件中，而在實際實現(xiàn)中，三地址碼可能被送到輸出文件中，而不是生成不是生成code屬性。屬性。生成三地址碼的生成三地址碼的S-S-屬性文法屬性文法產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則Sid := ES.code := E.code | gen(id.place := E.place) EE1 + E2E.place := newtemp;E.c

18、ode := E1.code | E2.code | gen(E.place := E1.place + E2.place) EE1 * E2E.place := newtemp;E.code := E1.code | E2.code | gen(E.place := E1.place * E2.place) E- E1E.place := newtemp;E.code := E1.code | gen(E.place := uminus E1.place) E(E1)E.place := E1.place E.code := E1.codeEidE.place := id.place E.c

19、ode := 如何加入控制語句如何加入控制語句SWhile E do S1SWhile E do S1對應的語義規(guī)則是：對應的語義規(guī)則是：S.begin := newlabel;S.after := newlabel;S.code := gen(S.begin :) | E.code | gen(if E.place = 0 goto S.after) | S1.code | gen(goto S.begin) | gen(S.after :)E.codeif E.place = 0 goto S.afterS1.codegoto S.beginS.begin:S.after:三地址語句的實現(xiàn)

20、三地址語句的實現(xiàn)三地址語句是中間代碼的一種抽象形式。三地址語句是中間代碼的一種抽象形式。這些語句可以以帶有操作符和操作數(shù)域的記錄來實現(xiàn)。這些語句可以以帶有操作符和操作數(shù)域的記錄來實現(xiàn)。四元式、三元式及簡介三元式是三種這樣的表示。四元式、三元式及簡介三元式是三種這樣的表示。四元式四元式一個四元式是帶有四個域的記錄結(jié)構(gòu)，這四個域分別一個四元式是帶有四個域的記錄結(jié)構(gòu)，這四個域分別稱為稱為op, arg1, arg2及及result。域域op包含一個代表運算符的內(nèi)部碼包含一個代表運算符的內(nèi)部碼三地址語句三地址語句x:=y op z通過將通過將y放入放入arg1，z放入放入arg2，并且將并且將x放入放

21、入result，:=為算符。為算符。像像x:=y或或x:=-y這樣的一元操作符語句不使用這樣的一元操作符語句不使用arg2像像param這樣的運算符僅使用這樣的運算符僅使用arg1域。域。條件和無條件語句將目標標號存入條件和無條件語句將目標標號存入result域。域。臨時變量也要填入符號表中。臨時變量也要填入符號表中。三元式三元式為了避免把臨時變量填入符號表，我們可以通過計算為了避免把臨時變量填入符號表，我們可以通過計算這個臨時變量的語句的位置來引用這個臨時變量。這個臨時變量的語句的位置來引用這個臨時變量。這樣三地址代碼的記錄只需要三個域這樣三地址代碼的記錄只需要三個域op, arg1和和ar

22、g。對于一目運算符對于一目運算符op, arg1和和arg2只需用其一。我們可只需用其一。我們可以隨意選用一個。以隨意選用一個。四元式舉例四元式舉例oparg1arg2result(0)uminuscT1(1)*bT1T2(2)uminuscT3(3)*bT3T4(4)+T2T4T5(5)assignT5aoparg1arg2(0)uminusc(1)*b0(2)uminusc(3)*b2(4)+13(5)assigna4a := b * -c + b * -c三元式舉例三元式舉例oparg1arg2(0)=xi(1)assign(0)yoparg1arg2(0)=yi(1)assignx(0

23、)xi := yx := yi間接三元式間接三元式為了便于代碼優(yōu)化處理，有時不直接使用三元式表，為了便于代碼優(yōu)化處理，有時不直接使用三元式表，而是另設一張指示器（稱為間接碼表），它將運算的而是另設一張指示器（稱為間接碼表），它將運算的先后順序列出有關三元式在三元表中的位置。先后順序列出有關三元式在三元表中的位置。換句話說，我們用一張間接碼表輔以三元式表的辦法換句話說，我們用一張間接碼表輔以三元式表的辦法來表示中間代碼。這種表示方法稱為間接三元式。來表示中間代碼。這種表示方法稱為間接三元式。間接三元式舉例間接三元式舉例X:=(A+B)*C Y:=D(A+B)oparg1arg2(11)+AB(1

24、2)*(11)C(13):=X(12)(14)D(11)(15):=Y(14)間接代碼間接代碼(11)(12)(13)(11)(14)(15)(11)(12)(13)(11)(14)(15)當在代碼優(yōu)化過程中需要調(diào)整運算順序時，當在代碼優(yōu)化過程中需要調(diào)整運算順序時，只需重新安排間接碼表，無需改動三元式只需重新安排間接碼表，無需改動三元式表表對于間接三元式表示，語義規(guī)則中應增添對于間接三元式表示，語義規(guī)則中應增添產(chǎn)生間接碼表的動作，并且在向三元式表產(chǎn)生間接碼表的動作，并且在向三元式表填進一個三元式之前，必須先查看一下此填進一個三元式之前，必須先查看一下此式是否已在其中，就無須填入。式是否已在其中

25、，就無須填入。表示方法比較：間址的使用表示方法比較：間址的使用三元式與四元式的差異可以看作在表示中引入了多少間址。三元式與四元式的差異可以看作在表示中引入了多少間址。使用四元式表示，定義或使用臨時變量的三地址語句可通過符號使用四元式表示，定義或使用臨時變量的三地址語句可通過符號表直接訪問該臨時變量的地址表直接訪問該臨時變量的地址使用四元式的一個更重要的好處體現(xiàn)在優(yōu)化編譯器中。在三元式使用四元式的一個更重要的好處體現(xiàn)在優(yōu)化編譯器中。在三元式中，如果要移動一條臨時值的語句需要改變中，如果要移動一條臨時值的語句需要改變arg1和和arg2數(shù)組中對數(shù)組中對該語句的引用。該語句的引用。間接三元式?jīng)]有上述

26、問題。間接三元式?jīng)]有上述問題。間接三元式看上去和四元式非常相似，他們都需要大約相同間接三元式看上去和四元式非常相似，他們都需要大約相同的存儲空間，并且對代碼重新排序的效率相同。的存儲空間，并且對代碼重新排序的效率相同。對于普通三元式，必須將對那些臨時變量的存儲分配推遲到對于普通三元式，必須將對那些臨時變量的存儲分配推遲到代碼生成階段。代碼生成階段。三地址代碼三地址代碼三地址代碼：三地址代碼：a = b OP c最多有三個地址最多有三個地址 (可以少于三個可以少于三個)通常寫成四元組：通常寫成四元組：(a, b, c, OP)例子：例子：例子例子怎么翻譯怎么翻譯對于有嵌套的語言結(jié)構(gòu)：對于有嵌套的

27、語言結(jié)構(gòu)：嵌套的嵌套的if和和while語句語句需要一個算法來進行翻譯需要一個算法來進行翻譯解決方案：解決方案：從從AST描述開始描述開始對對AST中的每個結(jié)點定義翻譯方法中的每個結(jié)點定義翻譯方法遍歷遍歷AST中的每一個結(jié)點的翻譯中的每一個結(jié)點的翻譯表達式的翻譯表達式的翻譯二元操作符二元操作符t = T e1 OP e2 (數(shù)學運算符和關系比較數(shù)學運算符和關系比較符號符號)一元操作符一元操作符: t = T OP e 布爾表達式的翻譯布爾表達式的翻譯 t = T e1 OR e2 對于最為選擇的對于最為選擇的OR表達式，只有表達式，只有e1是是false的時候才的時候才去計算去計算e2OROR

28、作為判斷條件的翻譯作為判斷條件的翻譯 Short-circuit OR: t = T e1 SC-OR e2 ANDAND作為判斷條件的翻譯作為判斷條件的翻譯 Short-circuit AND: t = T e1 SC-AND e2 數(shù)組和數(shù)據(jù)域的訪問數(shù)組和數(shù)據(jù)域的訪問嵌套的表達式嵌套的表達式對表達式結(jié)構(gòu)需要反復的翻譯對表達式結(jié)構(gòu)需要反復的翻譯語句的翻譯語句的翻譯語句序列：語句序列：T s1; s2; ; sN 賦值語句賦值語句給變量賦值：給變量賦值：T v = e 給數(shù)組賦值：給數(shù)組賦值：T ve1 = e2 If-Then-ElseIf-Then-Else的翻譯的翻譯 T if (e)

29、then s1 else s2 If-ThenIf-Then的翻譯的翻譯T if (e) then s While While 語句語句 T while (e) s Switch Switch 語句語句T switch (e) case v1: s1, , case vN: sN 調(diào)用和返回語句調(diào)用和返回語句 T call f(e1, e2, , eN) T return e 嵌套語句嵌套語句和表達式的翻譯類似，需要遞歸的翻譯和表達式的翻譯類似，需要遞歸的翻譯效率問題效率問題增加效率的技術(shù)增加效率的技術(shù)如何增加效率：如何增加效率：1. 減少臨時變量的使用減少臨時變量的使用2.不產(chǎn)生多個臨近的指

30、示標簽不產(chǎn)生多個臨近的指示標簽3.將條件表達式編碼成控制流將條件表達式編碼成控制流不復制變量不復制變量基本算法：基本算法：轉(zhuǎn)換規(guī)則遞歸的遍歷表達式，直到遇到終結(jié)符（變量轉(zhuǎn)換規(guī)則遞歸的遍歷表達式，直到遇到終結(jié)符（變量和數(shù)字）和數(shù)字）然后對變量來說，將然后對變量來說，將t = Tv翻譯成翻譯成 t = v對內(nèi)容來說，將對內(nèi)容來說，將 t = Tn翻譯成翻譯成 t = n更好的算法：更好的算法：在終結(jié)符之前的層次上終止遞歸在終結(jié)符之前的層次上終止遞歸需要在每個階段都判斷表達式是不是終結(jié)符需要在每個階段都判斷表達式是不是終結(jié)符只有當結(jié)點是非終結(jié)符的表達式時，才遞歸的為它的只有當結(jié)點是非終結(jié)符的表達式時

31、，才遞歸的為它的子節(jié)點生成代碼。子節(jié)點生成代碼。不復制變量不復制變量 t = T e1 OP e2 t1 = T e1 , 如果如果e1是非終結(jié)符是非終結(jié)符t2 = T e2 ,如果如果e2是非終結(jié)符是非終結(jié)符t = x1 OP x2這里：這里：x1 = t1, 如果如果e1是非終結(jié)符是非終結(jié)符x1 = e1, 如果如果e1是終結(jié)符是終結(jié)符x2 = t2, 如果如果e2是非終結(jié)符是非終結(jié)符x2 = e2, 如果如果e2是終結(jié)符是終結(jié)符相似的，對于其他的條件表達式也有類似的轉(zhuǎn)移：相似的，對于其他的條件表達式也有類似的轉(zhuǎn)移： if, while, switch例子例子 t = T (a+b)*c

32、操作數(shù)操作數(shù)e1 = a+b, 是非終結(jié)符是非終結(jié)符操作數(shù)操作數(shù)e2 = c, 是終結(jié)符是終結(jié)符轉(zhuǎn)換：轉(zhuǎn)換：t1 = T e1 t = t1 * c為為t1 = T e1 遞歸的產(chǎn)生代碼遞歸的產(chǎn)生代碼對于對于e1 = a+b, 兩個操作數(shù)都是終結(jié)符兩個操作數(shù)都是終結(jié)符t1 = T e1 的代碼是：的代碼是：t1 = a+b最終結(jié)果：最終結(jié)果：t1 = a + bt = t1 * c對操作數(shù)和結(jié)果使用同一個臨時變量對操作數(shù)和結(jié)果使用同一個臨時變量轉(zhuǎn)換：轉(zhuǎn)換：t = T e1 OP e2 為：為：t = T e1 t1 = T e2 t = t OP t1例子：例子：t = T (a+b)*c t

33、 = a + bt = t * c 重復使用臨時變量重復使用臨時變量想法：在轉(zhuǎn)換想法：在轉(zhuǎn)換t = T e1 OP e2 中：中：t = T e1 , t = T e2 , t = t OP t在在e1的轉(zhuǎn)換中使用過的臨時變量可以在的轉(zhuǎn)換中使用過的臨時變量可以在e2的轉(zhuǎn)換中重的轉(zhuǎn)換中重復使用。復使用。臨時變量計算中間值，因此他們的生命期是有限的臨時變量計算中間值，因此他們的生命期是有限的算法：算法：使用臨時變量的棧使用臨時變量的棧這符合轉(zhuǎn)換函數(shù)這符合轉(zhuǎn)換函數(shù)t=Te的遞歸調(diào)用。的遞歸調(diào)用。所有在棧里的臨時變量都是活躍的所有在棧里的臨時變量都是活躍的臨時變量的再使用臨時變量的再使用實現(xiàn)方法：使用

34、計數(shù)器實現(xiàn)方法：使用計數(shù)器c來實現(xiàn)棧。來實現(xiàn)棧。臨時變量臨時變量t(0), ,t(c)是活躍的是活躍的臨時變量臨時變量t(c+1), t(c+2), 可以被再使用可以被再使用進棧意味著增加進棧意味著增加c, 出棧意味著減少出棧意味著減少c在轉(zhuǎn)換在轉(zhuǎn)換t(c) = T e1 OP e2 例子例子在控制流中對在控制流中對BooleanBoolean進行編碼進行編碼T if ( ab SC-AND cd ) then x = y; can we do better?在控制流中對在控制流中對BooleanBoolean進行編碼進行編碼 Consider T if ( ab SC-AND cd ) th

35、en x = y; If t = ab is false, program branches to label L2 T if(e) then s1 else s2 T if(e) then s While While 語句語句 T while (e) s 語句表達式語句表達式語句區(qū)塊語句區(qū)塊 t = T s1; s2; ; sN 語句區(qū)塊的結(jié)果值語句區(qū)塊的結(jié)果值=序列中最后一條語句的值序列中最后一條語句的值賦值語句賦值語句 t = T v = e 賦值語句的結(jié)果值賦值語句的結(jié)果值=賦值表達式的值賦值表達式的值說明語句說明語句聲明語句引起的翻譯動作聲明語句引起的翻譯動作當過程或程序塊內(nèi)部的聲明

36、語句被考察的時候，我們當過程或程序塊內(nèi)部的聲明語句被考察的時候，我們需要為需要為局部局部于該過程的名字分配存儲空間。于該過程的名字分配存儲空間。對每個局部名字，都將在符號表中創(chuàng)建一個表項，對每個局部名字，都將在符號表中創(chuàng)建一個表項，填寫類型、相對存儲地址等相關信息填寫類型、相對存儲地址等相關信息相對地址指相對于靜態(tài)數(shù)據(jù)區(qū)基址或活動記錄基址的偏相對地址指相對于靜態(tài)數(shù)據(jù)區(qū)基址或活動記錄基址的偏移量移量單個過程中的聲明語句單個過程中的聲明語句允許嵌套過程中的聲明語句允許嵌套過程中的聲明語句單個過程中的聲明語句單個過程中的聲明語句變量和過程設計變量和過程設計設置全局變量：設置全局變量：offset，跟

37、蹤下一個可用的相對地址，跟蹤下一個可用的相對地址過程過程enter(name, type, offset)為名字建立符號表表項為名字建立符號表表項綜合屬性綜合屬性type和和width說明非終結(jié)符說明非終結(jié)符T的類型及寬度（或該類型的對象所占用的類型及寬度（或該類型的對象所占用的內(nèi)存數(shù)。的內(nèi)存數(shù)。Poffset:=0 DDD;DDid:Tenter(, T.type, offset); offset:=offset + T.width TintegerT.type := integer; T.width := 4 TrealT.type := real; T.width := 8

38、Tarraynumof T1T.type := array(num.val, T1.type); T.width :=num.val * T1.widthTT1T.type := pointer(T1.type); T.width := 4Poffset:=0 DPMDD offset:=0允許嵌套過程中的聲明語句允許嵌套過程中的聲明語句PMDaddwidth(top(tblptr),top(offset); pop(tblptr); pop(offset)Mt=mktable(nil); push(t, tblptr);push(0, offset) DD1;D2Dproc id; N D1

39、 ;S t := top(tblptr); addwidth(t, top(offset); pop(tblptr); pop(offset); enterproc(top(tblptr), , t) Did :Tenter(top(tblptr),,T.type, top(offset); top(offset := top(offset) + T.widthN t:= mktable(top(tblptr); push(t, tblptr), push(0,offset)M的動作用于初始化棧的動作用于初始化棧tblptr，將，將相對地址相對地址0壓入棧壓入棧of

40、fset當出現(xiàn)一個過程聲明時，當出現(xiàn)一個過程聲明時，N的動作的動作和和M的動作基本相同的動作基本相同對每個變量聲明，不改變對每個變量聲明，不改變tblptr，但是要改變但是要改變offset的棧頂指針。的棧頂指針。記錄中的域名記錄中的域名當看到關鍵字當看到關鍵字record之后，與標記之后，與標記L相關聯(lián)的動作為相關聯(lián)的動作為域名創(chuàng)建一個新的符號表。指向該符號表的指針被壓域名創(chuàng)建一個新的符號表。指向該符號表的指針被壓入棧入棧tblptr，相對地址，相對地址0被壓入棧被壓入棧offset。Trecord D endTrecord L D endT.type := record (top(tblp

41、tr); T.width:=top(offset); pop(tblptr); pop(offset)Lt=mktable(nil); push(t, tblptr);push(0, offset) 賦值語句賦值語句賦值語句賦值語句賦值語句中表達式的類型賦值語句中表達式的類型整型整型實型實型數(shù)組數(shù)組記錄記錄將賦值語句轉(zhuǎn)換為三地址碼要做的工作將賦值語句轉(zhuǎn)換為三地址碼要做的工作在符號表中查找名字在符號表中查找名字存取數(shù)組及記錄中的元素存取數(shù)組及記錄中的元素符號表中的名字符號表中的名字lookup 操作支持最近嵌套原操作支持最近嵌套原則。則。其上下文是由前面定義的過其上下文是由前面定義的過程，當作用

42、于程，當作用于name時，需要時，需要先檢查先檢查name是否已經(jīng)在符號是否已經(jīng)在符號表中定義過了。表中定義過了。PMDMDD1;D2| Dproc id; N D1 ;S | Did :TN Sid := Ep:=lookup(); if p nuil then emit(p := E.place) else errorEE1 + E2E.place := newtemp; emit(E.place := E1.place + E2.place E E1 * E2E.place := newtemp; emit(E.place := E1.place * E2.place E-

43、E1 E.place := newtemp; emit(E.place := uminus E1.place E (E1)emit(E.place := E1.place Eidp := lookup(); if p nil then E.place := p; else error尋址數(shù)組元素尋址數(shù)組元素如果數(shù)組元素存放在連續(xù)的存儲塊中，數(shù)組元素可以如果數(shù)組元素存放在連續(xù)的存儲塊中，數(shù)組元素可以迅速的訪問。每個數(shù)組元素的寬度是迅速的訪問。每個數(shù)組元素的寬度是w，則，則一維數(shù)組一維數(shù)組Ai的地址：的地址：base+(i-low)*w二維數(shù)組二維數(shù)組Ai1,i2的地址：的地址：ba

44、se + (i1-low1)*n2+i2-low2)*w，可以改寫為可以改寫為(i1*n2)+i2)*w+(base-(low1*n2)+low2)*w)多維數(shù)組多維數(shù)組Ai1,i2, ik的地址：的地址：(i1n2+i2)*n3+i3)nk+ik)*w+base-(low1n2+low2)*n3+low3)nk+lowk)*w將數(shù)組名與最左邊的下標表達式連在一起。使得產(chǎn)生式允許將數(shù)組名與最左邊的下標表達式連在一起。使得產(chǎn)生式允許將符號表中指向數(shù)組名表項的指針作為將符號表中指向數(shù)組名表項的指針作為Elist的綜合屬性的綜合屬性array進行傳遞。進行傳遞。(i1n2+i2)n3+i3)nm+i

45、m)使用如下遞歸公式計算：使用如下遞歸公式計算：e1 = i1em = em-1*nm+imL有兩個屬性，有兩個屬性，L.place和和L.offset，當，當L是簡單名字時，是簡單名字時，L.place是指向符號表中該名字表項的指針，而是指向符號表中該名字表項的指針，而L.offset是是nullLidElist | idElistElist, E | ELElist | idElistElist, E | idE數(shù)組元素尋址的翻譯模式數(shù)組元素尋址的翻譯模式如果如果L是簡單名字，則生成一般的賦值，否則生成對是簡單名字，則生成一般的賦值，否則生成對L所指位置的索引賦值。所指位置的索引賦值。(1

46、) SL := E if L.offset = null thenemit(L.place := E.place); else emit(L.place L.offset := E.place)(2) EE1 + E2E.place := newtemp; emit(E.place := E1.place + E2.place)(3) E(E1)E.place := E1.place(4) ELif L.offset =null thenE.place := L.place else beginE.place := newtemp;emit(E.place := L.place L.offse

47、t 0 end(1) SL := E(2) EE + E(3) E(E)(4) EL(5) LElist(6) Lid(7) ElistElist,E(8) Elist idE數(shù)組元素尋址的翻譯模式數(shù)組元素尋址的翻譯模式(5) LElist L.place := newtemp; L.offset := newtemp; emit(L.place := c(Elist.array) emit(L.offset := Elist.place * width(Elist.array)(6) LidL.place := id.place; L.offset :=null(7) ElistElist1

48、 ,E)t:=E.place := E1.place m := Elist1.ndim +1; emit(t := Elist1.place * limit(Elist1.arry,m); emit(t := t + E.place); Elist.array := Elist1.array; Elist.place := t; Elist.ndim :=m(8) ElistidEElist.arry := id.place; Elist.place := E.place; Elist.ndim :=1(1) SL := E(2) EE + E(3) E(E)(4) EL(5) LElist(

49、6) Lid(7) ElistElist,E(8) Elist idE賦值語句中的類型轉(zhuǎn)換賦值語句中的類型轉(zhuǎn)換變量和常量有許多不同的類型，因而編譯器或者拒絕變量和常量有許多不同的類型，因而編譯器或者拒絕某種混合類型的操作，或者生成適當?shù)膹娭疲愋娃D(zhuǎn)某種混合類型的操作，或者生成適當?shù)膹娭疲愋娃D(zhuǎn)換）指令。換）指令。假設有兩種類型：假設有兩種類型：EE1 + E2E.type := if E1.type = integer and E2.type= integer then integer else real賦值語句中的類型轉(zhuǎn)換賦值語句中的類型轉(zhuǎn)換(1) SL := E(2) EE + E(3)

50、E(E)(4) EL(5) LElist(6) Lid(7) ElistElist,E(8) Elist idEE.Place := newtemp;if E1.type = integer and E2.type = integer then begin emit(E.place := E1.place int+ E2.place); E.type := integerendelse if E1.type = real and E2.type = real then begin emit(E.place := E1.place real+ E2.place); E.type := reale

51、ndelse if E1.type = integer and E2.type = real then begin u:=newtemp; emit(u := inttoreal E1.place; emit(E.place := u real+ E2.place); E.type := realendelse if E1.type = real and E2.type = integer then begin u:=newtemp; emit(u := inttoreal E2.place; emit(E.place := E1.place real+ u); E.type := reale

52、ndelse E.type := type_error;布爾表達式的翻譯布爾表達式的翻譯布爾表達式的作用布爾表達式的作用用作計算邏輯值用作計算邏輯值用作控制語句（如用作控制語句（如if語句，語句，while語句等）語句等）布爾表達式和關系表達式布爾表達式和關系表達式布爾表達式是用布爾運算符作用到布爾變量或關系表布爾表達式是用布爾運算符作用到布爾變量或關系表達式上而組成的。（達式上而組成的。（not、and、or）關系表達式是有關系運算符連接的算術(shù)表達式關系表達式是有關系運算符連接的算術(shù)表達式布爾表達式值的計算布爾表達式值的計算如同計算算術(shù)表達式一樣，一步不差的從表達式各部如同計算算術(shù)表達式一樣

53、，一步不差的從表達式各部分的值計算出整個表達式的值分的值計算出整個表達式的值采用優(yōu)化措施計算布爾表達式的值采用優(yōu)化措施計算布爾表達式的值計算計算A or B時，如果時，如果A為真，則不用計算為真，則不用計算B，結(jié)果為真，結(jié)果為真計算計算A and B時，如果時，如果A為假，不用計算為假，不用計算B，結(jié)果為假，結(jié)果為假一般的計算公式如下：一般的計算公式如下：A or B：if A then true else BA and B：if A then B else falsenot A：if A then false else true用上述兩種方法把布爾表達式翻譯成地址代碼用上述兩種方法把布爾表達

54、式翻譯成地址代碼EE1 or E2E.place := newtemp; emit(E.place := E1.place or E2.place E E1 and E2E.place := newtemp; emit(E.place := E1.place and E2.place Enot E1E.place := newtemp; emit(E.place := not E1.place E (E1)E.place := E1.place Eid1 relop id2E.place := newtemp;emit(if id1.place relop.op id2.place goto

55、nextstat+3);emit(E.place := 0);emit(goto nextstat+2);emit(E.place := 1)EidE.plece := id.placeab or cd and ef100: if ab goto 103107: T2:=1101: T1 := 0108: if ef goto 111102: goto 104109: T3:=0103: T1:= 1110: goto 112104: if cc or bc goto L2goto L1L1: if bd goto L2goto L3L2:(S1的三地址碼序列的三地址碼序列)goto Lnes

56、tL3:(S2的三地址碼序列的三地址碼序列)Lnext:產(chǎn)生布爾表達式三地址代碼的語義規(guī)則產(chǎn)生布爾表達式三地址代碼的語義規(guī)則函數(shù)函數(shù)newlabel產(chǎn)生新的符號標號產(chǎn)生新的符號標號if E then S1 else S2。假定假定E形如形如ab，則將生成如下，則將生成如下E的代碼：的代碼：if ab goto E.truegoto E.false對于上述翻譯的討論：對于上述翻譯的討論：如果如果E為為E1 or E2，如果，如果E1為真，則立即可知為真，則立即可知E為真，為真，于是于是E1.true與與E.true是相同的；若是相同的；若E1為假，則必須對為假，則必須對E2求值，因此我們置求值，

57、因此我們置E1.false為為E2的代碼的第一條指令的的代碼的第一條指令的標號，而標號，而E2的真假出口可以分別與的真假出口可以分別與E的真假出口相同。的真假出口相同。產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則EE1 or E2E1.true:= E.true;E1.false:= newlabel;E2.true:= E.true;E2.false:= E.false;E.code:= E1.code | gen(E1.false :) | E2.codeEE1 and E2E1.true:= newlabel;E1.false:= E.false;E2.true:= E.true;E2.false:=

58、E.false;E.code:= E1.code | gen(E1.true :) | E2.codeEnot E1E1.true:= E.false;E1.false:= E.true;E.code:= E1.codeE(E1)E1.true:= E.true;E1.false:= E.false;E.code:= E1.codeEid1 relop id2E.code :=gen(if id1.place relop.op id2.place goto E.true) | gen(goto E.false)EtrueE.code:= gen(goto E.true)EfalseE.code

59、:= gen(goto E.false)類型檢查類型檢查類型檢查概述類型檢查概述編譯器必須要檢查源程序是否符合源語言規(guī)定的語法編譯器必須要檢查源程序是否符合源語言規(guī)定的語法和語義要求。這種檢查稱為靜態(tài)檢查，檢查并報告程和語義要求。這種檢查稱為靜態(tài)檢查，檢查并報告程序中某些類型的錯誤，包括：序中某些類型的錯誤，包括：類型檢查：如果操作符作用于不相容的操作數(shù)，編譯類型檢查：如果操作符作用于不相容的操作數(shù)，編譯器應該報錯器應該報錯控制流檢查：引起控制流從某個結(jié)構(gòu)中跳轉(zhuǎn)出來的語控制流檢查：引起控制流從某個結(jié)構(gòu)中跳轉(zhuǎn)出來的語句必須能夠決定控制流轉(zhuǎn)向的目標地址句必須能夠決定控制流轉(zhuǎn)向的目標地址唯一性檢查：

60、有時，有的對象只能被定義一次。唯一性檢查：有時，有的對象只能被定義一次。與名字相關的檢查：有時候要求同一名字在特定位置與名字相關的檢查：有時候要求同一名字在特定位置出現(xiàn)兩次或多次出現(xiàn)兩次或多次類型檢查概述類型檢查概述前面描述的一些工作可以并入其他活動中。前面描述的一些工作可以并入其他活動中。唯一性檢查可以在將名字信息填入符號表時進行。唯一性檢查可以在將名字信息填入符號表時進行。一些靜態(tài)檢查和中間代碼生成同語法分析結(jié)合在一起一些靜態(tài)檢查和中間代碼生成同語法分析結(jié)合在一起代碼生成器需要類型檢查器所收集的信息代碼生成器需要類型檢查器所收集的信息重載，可能伴隨有強制類型轉(zhuǎn)換，以便編譯器把操作重載，可能