天津大學(xué)編譯原理講義 - Part7語(yǔ)義分析及中間代碼生成

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

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

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

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

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

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

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

8、樹(shù)抽象語(yǔ)法樹(shù)語(yǔ)法樹(shù)中的邊不會(huì)顯式的出現(xiàn)在后綴表達(dá)式中，可以根據(jù)結(jié)點(diǎn)出現(xiàn)的順序語(yǔ)法樹(shù)中的邊不會(huì)顯式的出現(xiàn)在后綴表達(dá)式中，可以根據(jù)結(jié)點(diǎn)出現(xiàn)的順序及結(jié)點(diǎn)上的操作符所要求的操作數(shù)的個(gè)數(shù)來(lái)恢復(fù)。其恢復(fù)過(guò)程類似使用棧及結(jié)點(diǎn)上的操作符所要求的操作數(shù)的個(gè)數(shù)來(lái)恢復(fù)。其恢復(fù)過(guò)程類似使用棧對(duì)后綴表達(dá)式求值。對(duì)后綴表達(dá)式求值。如果函數(shù)如果函數(shù)mknode(op, child)和和mknode(op, left, right)盡可能返回一個(gè)指向一盡可能返回一個(gè)指向一個(gè)存在的結(jié)點(diǎn)的指針以代替建立新的結(jié)點(diǎn)，那么就會(huì)生成個(gè)存在的結(jié)點(diǎn)的指針以代替建立新的結(jié)點(diǎn)，那么就會(huì)生成DAG圖。圖。產(chǎn)生式產(chǎn)生式語(yǔ)義規(guī)則語(yǔ)義規(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)抽象語(yǔ)法樹(shù)的表示形式抽象語(yǔ)法樹(shù)的表示形式assignida+*uminusuminusidbidbidcidc

10、0idb1idc2uminus13*024idb5idc6uminus57*468+379ida10assign9811三地址代碼三地址代碼三地址代碼是下列一般形式的語(yǔ)句序列三地址代碼是下列一般形式的語(yǔ)句序列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)算符等）這里不允許組合的算術(shù)表達(dá)式，因?yàn)檎Z(yǔ)句右邊只有一個(gè)操作符。這里不允許組合的算術(shù)表達(dá)式，因?yàn)檎Z(yǔ)句右邊只有一個(gè)操作符。像像x+y*z這樣的表達(dá)式要翻譯為如下；這樣的表達(dá)式要

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

12、原因是每條語(yǔ)句通常包含三個(gè)地址，兩個(gè)是操作數(shù)地址，一個(gè)是結(jié)果地址。兩個(gè)是操作數(shù)地址，一個(gè)是結(jié)果地址。在實(shí)際的實(shí)現(xiàn)中，有程序員定義的名字被一個(gè)指向改在實(shí)際的實(shí)現(xiàn)中，有程序員定義的名字被一個(gè)指向改名字的符號(hào)表表項(xiàng)的指針?biāo)妗Ｃ值姆?hào)表表項(xiàng)的指針?biāo)?。三地址碼三地址碼assign+a*uminusbcuminusbcassign+a*uminusbct1 := -ct2 := b * t1t3 := -ct4 := b * t3t5 := t2 + t4a := t5t1 := -ct2 := b * t1t3 := t2 + t2a := t3三地址語(yǔ)句的類型三地址語(yǔ)句的類型三地址語(yǔ)句類似于

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

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

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

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

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

18、;E.code := 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

19、 E.code := 如何加入控制語(yǔ)句如何加入控制語(yǔ)句SWhile E do S1SWhile E do S1對(duì)應(yīng)的語(yǔ)義規(guī)則是：對(duì)應(yīng)的語(yǔ)義規(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:三地址語(yǔ)

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

21、x放入放入result，:=為算符。為算符。像像x:=y或或x:=-y這樣的一元操作符語(yǔ)句不使用這樣的一元操作符語(yǔ)句不使用arg2像像param這樣的運(yùn)算符僅使用這樣的運(yùn)算符僅使用arg1域。域。條件和無(wú)條件語(yǔ)句將目標(biāo)標(biāo)號(hào)存入條件和無(wú)條件語(yǔ)句將目標(biāo)標(biāo)號(hào)存入result域。域。臨時(shí)變量也要填入符號(hào)表中。臨時(shí)變量也要填入符號(hào)表中。三元式三元式為了避免把臨時(shí)變量填入符號(hào)表，我們可以通過(guò)計(jì)算為了避免把臨時(shí)變量填入符號(hào)表，我們可以通過(guò)計(jì)算這個(gè)臨時(shí)變量的語(yǔ)句的位置來(lái)引用這個(gè)臨時(shí)變量。這個(gè)臨時(shí)變量的語(yǔ)句的位置來(lái)引用這個(gè)臨時(shí)變量。這樣三地址代碼的記錄只需要三個(gè)域這樣三地址代碼的記錄只需要三個(gè)域op, arg1

22、和和arg。對(duì)于一目運(yùn)算符對(duì)于一目運(yùn)算符op, arg1和和arg2只需用其一。我們可只需用其一。我們可以隨意選用一個(gè)。以隨意選用一個(gè)。四元式舉例四元式舉例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)assig

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

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

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

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

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

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

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

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

31、表達(dá)式時(shí)，才遞歸的為它的子節(jié)點(diǎn)生成代碼。子節(jié)點(diǎn)生成代碼。不復(fù)制變量不復(fù)制變量 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é)符相似的，對(duì)于其他的條件表達(dá)式也有類似的轉(zhuǎn)移：相似的，對(duì)于其他的條件表達(dá)式也有類似的轉(zhuǎn)移： if, while, switch例子例子 t = T (a+b

32、)*c 操作數(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)生代碼對(duì)于對(duì)于e1 = a+b, 兩個(gè)操作數(shù)都是終結(jié)符兩個(gè)操作數(shù)都是終結(jié)符t1 = T e1 的代碼是：的代碼是：t1 = a+b最終結(jié)果：最終結(jié)果：t1 = a + bt = t1 * c對(duì)操作數(shù)和結(jié)果使用同一個(gè)臨時(shí)變量對(duì)操作數(shù)和結(jié)果使用同一個(gè)臨時(shí)變量轉(zhuǎn)換：轉(zhuǎn)換：t = T e1 OP e2 為：為：t = T e1 t1 = T e2 t = t OP t1例子：例子：t = T (a+b)

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

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

35、) then 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 語(yǔ)句語(yǔ)句 T while (e) s 語(yǔ)句表達(dá)式語(yǔ)句表達(dá)式語(yǔ)句區(qū)塊語(yǔ)句區(qū)塊 t = T s1; s2; ; sN 語(yǔ)句區(qū)塊的結(jié)果值語(yǔ)句區(qū)塊的結(jié)果值=序列中最后一條語(yǔ)句的值序列中最后一條語(yǔ)句的值賦值語(yǔ)句賦值語(yǔ)句 t = T v = e 賦值語(yǔ)句的結(jié)果值賦值語(yǔ)句的結(jié)果值=賦值表達(dá)式的值賦值表達(dá)式的值說(shuō)明語(yǔ)句說(shuō)明語(yǔ)句聲明語(yǔ)句引起的翻譯動(dòng)作聲明語(yǔ)句引起的翻譯動(dòng)作當(dāng)過(guò)程或程序塊內(nèi)

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

37、et，跟蹤下一個(gè)可用的相對(duì)地址，跟蹤下一個(gè)可用的相對(duì)地址過(guò)程過(guò)程enter(name, type, offset)為名字建立符號(hào)表表項(xiàng)為名字建立符號(hào)表表項(xiàng)綜合屬性綜合屬性type和和width說(shuō)明非終結(jié)符說(shuō)明非終結(jié)符T的類型及寬度（或該類型的對(duì)象所占用的類型及寬度（或該類型的對(duì)象所占用的內(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

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

39、N D1 ;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的動(dòng)作用于初始化棧的動(dòng)作用于初始化棧tblptr，將，將相對(duì)地址相對(duì)地址0壓入棧壓

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

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

42、，當(dāng)作用于程，當(dāng)作用于name時(shí)，需要時(shí)，需要先檢查先檢查name是否已經(jīng)在符號(hào)是否已經(jīng)在符號(hào)表中定義過(guò)了。表中定義過(guò)了。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.plac

43、e E-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ù)的存儲(chǔ)塊中，數(shù)組元素可以如果數(shù)組元素存放在連續(xù)的存儲(chǔ)塊中，數(shù)組元素可以迅速的訪問(wèn)。每個(gè)數(shù)組元素的寬度是迅速的訪問(wèn)。每個(gè)數(shù)組元素的寬度是w，則，則一維數(shù)組一維數(shù)組Ai的地址：的地址：base+(i-low)*w二維數(shù)組二維數(shù)組Ai1,i2的地址：的地

44、址：base + (i1-low1)*n2+i2-low2)*w，可以改寫(xiě)為可以改寫(xiě)為(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ù)組名與最左邊的下標(biāo)表達(dá)式連在一起。使得產(chǎn)生式允許將數(shù)組名與最左邊的下標(biāo)表達(dá)式連在一起。使得產(chǎn)生式允許將符號(hào)表中指向數(shù)組名表項(xiàng)的指針作為將符號(hào)表中指向數(shù)組名表項(xiàng)的指針作為Elist的綜合屬性的綜合屬性array進(jìn)行傳遞。進(jìn)行傳遞。(i1n2+i2)n3+i3)

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

46、值。(1) 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.o

47、ffset 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) ElistEl

48、ist1 ,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) LEl

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

50、(3) 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 := r

51、ealendelse 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 := r

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

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

54、布爾表達(dá)式翻譯成地址代碼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 g

55、oto 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

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

57、置求值，因此我們置E1.false為為E2的代碼的第一條指令的的代碼的第一條指令的標(biāo)號(hào)，而標(biāo)號(hào)，而E2的真假出口可以分別與的真假出口可以分別與E的真假出口相同。的真假出口相同。產(chǎn)生式產(chǎn)生式語(yǔ)義規(guī)則語(yǔ)義規(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.fals

58、e:= 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.

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

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