編譯原理第11章-語(yǔ)義分析與中間代碼生成

1、編譯原理 語(yǔ)義分析與中間代碼生成語(yǔ)義分析與中間代碼生成第十一講第十一講編譯原理 語(yǔ)義分析和中間代碼生成在編譯程序中的語(yǔ)義分析和中間代碼生成在編譯程序中的 邏輯位置邏輯位置語(yǔ)義分析與中間代碼生成語(yǔ)義分析與中間代碼生成詞法分析詞法分析語(yǔ)法分析語(yǔ)法分析中間代碼生成中間代碼生成中間代碼優(yōu)化中間代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成靜態(tài)語(yǔ)靜態(tài)語(yǔ)義分析義分析語(yǔ)義處理語(yǔ)義處理編譯原理 語(yǔ)義分析和中間代碼生成的重要數(shù)據(jù)結(jié)構(gòu)語(yǔ)義分析和中間代碼生成的重要數(shù)據(jù)結(jié)構(gòu)- 符號(hào)表符號(hào)表（symbol tables） 名字信息建立后加入名字信息建立后加入/更改符號(hào)表更改符號(hào)表 名字信息如：種類，類型，偏移

2、地址，占用空間等名字信息如：種類，類型，偏移地址，占用空間等 需要獲取名字信息時(shí)，查找符號(hào)表需要獲取名字信息時(shí)，查找符號(hào)表 符號(hào)表的組織可以體現(xiàn)名字作用域規(guī)則符號(hào)表的組織可以體現(xiàn)名字作用域規(guī)則 （符號(hào)表的組織已在第七講專門討論）（符號(hào)表的組織已在第七講專門討論）語(yǔ)義分析與中間代碼生成語(yǔ)義分析與中間代碼生成編譯原理 語(yǔ)義分析語(yǔ)義分析 中間代碼生成中間代碼生成語(yǔ)義分析與中間代碼生成語(yǔ)義分析與中間代碼生成編譯原理 與語(yǔ)義分析相關(guān)的工作與語(yǔ)義分析相關(guān)的工作語(yǔ)義分析語(yǔ)義分析- 靜態(tài)語(yǔ)義檢查靜態(tài)語(yǔ)義檢查 編譯期間所進(jìn)行的語(yǔ)義編譯期間所進(jìn)行的語(yǔ)義檢查檢查 - 動(dòng)態(tài)語(yǔ)義檢查動(dòng)態(tài)語(yǔ)義檢查 所生成的代碼在運(yùn)行期間

3、進(jìn)行的語(yǔ)義檢查所生成的代碼在運(yùn)行期間進(jìn)行的語(yǔ)義檢查 - 收集語(yǔ)義信息收集語(yǔ)義信息 為語(yǔ)義檢查收集程序的語(yǔ)義信息為語(yǔ)義檢查收集程序的語(yǔ)義信息 為代碼生成等后續(xù)階段收集程序的語(yǔ)義信息為代碼生成等后續(xù)階段收集程序的語(yǔ)義信息 有些內(nèi)容合并到有些內(nèi)容合并到“中間代碼生成中間代碼生成”部分討論部分討論 （如過(guò)程、數(shù)組聲明的語(yǔ)義處理）（如過(guò)程、數(shù)組聲明的語(yǔ)義處理）編譯原理 靜態(tài)語(yǔ)義檢查靜態(tài)語(yǔ)義檢查- 代碼生成前程序合法性檢查的最后階段代碼生成前程序合法性檢查的最后階段 靜態(tài)靜態(tài)類型檢查類型檢查（type checks） 檢查每個(gè)操作是否遵守語(yǔ)言類型系統(tǒng)的定義檢查每個(gè)操作是否遵守語(yǔ)言類型系統(tǒng)的定義 名字的作用

4、域名字的作用域（scope）分析分析 建立名字的定義和使用之間聯(lián)系建立名字的定義和使用之間聯(lián)系 控制流檢查控制流檢查（flow-of-control checks） 控制流語(yǔ)句必須使控制轉(zhuǎn)移到合法的地方（如控制流語(yǔ)句必須使控制轉(zhuǎn)移到合法的地方（如 break 語(yǔ)句必須有合法的語(yǔ)句包圍它）語(yǔ)句必須有合法的語(yǔ)句包圍它） 唯一性檢查唯一性檢查（uniqueness checks） 很多場(chǎng)合要求對(duì)很多場(chǎng)合要求對(duì) 象只能被定義一次（象只能被定義一次（如如枚舉類型的元素不能重復(fù)出現(xiàn)枚舉類型的元素不能重復(fù)出現(xiàn)） 名字的上下文相關(guān)性檢查名字的上下文相關(guān)性檢查（name-related checks） 某某 些

5、些名字的名字的多次多次出現(xiàn)之間應(yīng)該滿足一定的上下文相關(guān)性出現(xiàn)之間應(yīng)該滿足一定的上下文相關(guān)性 語(yǔ)義分析語(yǔ)義分析編譯原理- 類型檢查程序類型檢查程序（type checker）負(fù)責(zé)類型檢查）負(fù)責(zé)類型檢查 驗(yàn)證語(yǔ)言結(jié)構(gòu)是否匹配上下文所期望的類型驗(yàn)證語(yǔ)言結(jié)構(gòu)是否匹配上下文所期望的類型 為相關(guān)階段搜集及建立必要的類型信息為相關(guān)階段搜集及建立必要的類型信息 實(shí)現(xiàn)實(shí)現(xiàn)某個(gè)某個(gè)類型系統(tǒng)類型系統(tǒng)（type system）- 靜態(tài)類型檢查靜態(tài)類型檢查 編譯期間進(jìn)行的類型檢查編譯期間進(jìn)行的類型檢查- 動(dòng)態(tài)類型檢查動(dòng)態(tài)類型檢查 目標(biāo)程序運(yùn)行期間進(jìn)行的類型檢查目標(biāo)程序運(yùn)行期間進(jìn)行的類型檢查 類型檢查類型檢查語(yǔ)義分析語(yǔ)義

6、分析編譯原理- 以下是定義某個(gè)簡(jiǎn)單語(yǔ)言的上下文無(wú)關(guān)文法以下是定義某個(gè)簡(jiǎn)單語(yǔ)言的上下文無(wú)關(guān)文法 （將用于本講的設(shè)計(jì)示例）（將用于本講的設(shè)計(jì)示例）GP ： 一個(gè)簡(jiǎn)單語(yǔ)言一個(gè)簡(jiǎn)單語(yǔ)言語(yǔ)義分析語(yǔ)義分析編譯原理- 類型表達(dá)式類型表達(dá)式（type expressions） 由由基本類型基本類型，類型名字類型名字，類型變量類型變量，及，及類型構(gòu)造子類型構(gòu)造子 （type constructor）歸納定義的表達(dá)式）歸納定義的表達(dá)式- 類型系統(tǒng)類型系統(tǒng)（type systems） 將類型表達(dá)式賦給程序各個(gè)部分的將類型表達(dá)式賦給程序各個(gè)部分的規(guī)則集合規(guī)則集合 類型表達(dá)式和類型系統(tǒng)類型表達(dá)式和類型系統(tǒng)語(yǔ)義分析語(yǔ)義分

7、析編譯原理- 類型表達(dá)式類型表達(dá)式 分四類定義分四類定義 基本數(shù)據(jù)類型表達(dá)式，積類型表達(dá)式，過(guò)程類型表達(dá)式，基本數(shù)據(jù)類型表達(dá)式，積類型表達(dá)式，過(guò)程類型表達(dá)式， 專用類型表達(dá)式專用類型表達(dá)式- 基本數(shù)據(jù)類型基本數(shù)據(jù)類型表達(dá)式表達(dá)式 純量類型純量類型表達(dá)式：表達(dá)式：bool, int, real 有界數(shù)組類型表達(dá)式：有界數(shù)組類型表達(dá)式：array(I,T) T bool, int, real ；I 代表一個(gè)整數(shù)區(qū)間，如代表一個(gè)整數(shù)區(qū)間，如 1.10 指針數(shù)據(jù)類型表達(dá)式：指針數(shù)據(jù)類型表達(dá)式：pointer(T) T bool, int, real 類型表達(dá)式類型表達(dá)式 舉例舉例 語(yǔ)義分析語(yǔ)義分析編譯

8、原理- 積類型表達(dá)式積類型表達(dá)式 T1, T2, , Tn 為上述數(shù)據(jù)類型表達(dá)式；若為上述數(shù)據(jù)類型表達(dá)式；若n=0，則表示為，則表示為 - 過(guò)程類型表達(dá)式過(guò)程類型表達(dá)式 fun（T） T 是上述積類型表達(dá)式是上述積類型表達(dá)式 - 專用類型表達(dá)式專用類型表達(dá)式 type_error 專用于有類型錯(cuò)誤的程序單元專用于有類型錯(cuò)誤的程序單元 ok 專用于沒(méi)有類型錯(cuò)誤的程序單元專用于沒(méi)有類型錯(cuò)誤的程序單元 類型表達(dá)式類型表達(dá)式 舉例舉例 ( (續(xù)續(xù)) )語(yǔ)義分析語(yǔ)義分析編譯原理- 語(yǔ)法制導(dǎo)的方法語(yǔ)法制導(dǎo)的方法 將類型表達(dá)式作為屬性值賦給程序各個(gè)部分將類型表達(dá)式作為屬性值賦給程序各個(gè)部分 設(shè)計(jì)恰當(dāng)?shù)姆g模

9、式設(shè)計(jì)恰當(dāng)?shù)姆g模式 可實(shí)現(xiàn)相應(yīng)語(yǔ)言的一個(gè)類型系統(tǒng)可實(shí)現(xiàn)相應(yīng)語(yǔ)言的一個(gè)類型系統(tǒng) 類型檢查程序的設(shè)計(jì)類型檢查程序的設(shè)計(jì)語(yǔ)義分析語(yǔ)義分析編譯原理- 處理處理聲明聲明的翻譯模式的翻譯模式 語(yǔ)法制導(dǎo)的類型檢查程序語(yǔ)法制導(dǎo)的類型檢查程序 舉例舉例 V V1 ; T L.in := T.type L V.type := make_product_3 (V1.type, T.type, L.num) V V.type := T boolean T.type := bool T integer T.type := int T real T.type := real T array num of T1 T.ty

10、pe := array(1. num.lexval, T1.type) T T1 T.type := pointer(T1.type) L L1.in := L.in L1, id addtype(id.entry, L.in) ; L.num := L1.num +1 L id addtype(id.entry, L.in); L.num := 1 語(yǔ)義分析語(yǔ)義分析編譯原理- 處理處理表達(dá)式表達(dá)式的翻譯模式的翻譯模式語(yǔ)義分析語(yǔ)義分析 語(yǔ)法制導(dǎo)的類型檢查程序語(yǔ)法制導(dǎo)的類型檢查程序 舉例舉例E true E.type := bool E false E.type := bool E int E.

11、type := int E real E.type := real E id E.type := if lookup_type() = nil then type_error else lookup_type( 編譯原理語(yǔ)義分析語(yǔ)義分析E E1 op E2 E.type := if E1.type=real and E2.type=real then real else if E1.type=int and E2.type=int then int else type_error E E1 rop E2 E.type := if E1.type=real and E

12、2.type=real then bool else if E1.type=int and E2.type=int then bool else type_error E E1 E2 E.type := if E2.type= int and E1.type=array(s, t) then t else type_error E E1 E.type := if E1.type= pointer(t) then t else type_error - 處理處理表達(dá)式表達(dá)式的翻譯模式的翻譯模式 語(yǔ)法制導(dǎo)的類型檢查程序語(yǔ)法制導(dǎo)的類型檢查程序 舉例舉例編譯原理- 處理處理語(yǔ)句、過(guò)程聲明及程序語(yǔ)句、過(guò)

13、程聲明及程序的翻譯模式的翻譯模式語(yǔ)義分析語(yǔ)義分析 語(yǔ)法制導(dǎo)的類型檢查程序語(yǔ)法制導(dǎo)的類型檢查程序 舉例舉例S id := E S.type := if lookup_type (id.entry) = E.type then ok else type_error S if E then S1 S.type := if E.type=bool then S1.type else type_error S if E then S1 else S2 S.type := if E.type=bool and S1.type = ok and S2.type = ok then ok else type_

14、error S while E then S1 S.type := if E.type=bool then S1.type else type_error S S1 ; S2 S.type := if S1.type = ok and S2.type = ok then ok else type_error S break S.type := ok 編譯原理語(yǔ)義分析語(yǔ)義分析S call id ( A ) S.type := if match (lookup_type (), A.type) then ok else type_error F F1 ; id ( V ) S add

15、type(id.entry, fun (V.type); F.type := if F1.type = ok and S.type = ok then ok else type_error F F.type := ok A A1 , E A.type := make_product_2 (A1.type, E.type) A A.type := P D ; S P.type := if D.type = ok and S.type = ok then ok else type_error D V ; F D.type := F.type - 處理處理語(yǔ)句、過(guò)程聲明及程序語(yǔ)句、過(guò)程聲明及程序的翻

16、譯模式的翻譯模式 （續(xù)）（續(xù)） 語(yǔ)法制導(dǎo)的類型檢查程序語(yǔ)法制導(dǎo)的類型檢查程序 舉例舉例編譯原理- 增加處理：增加處理：break 只能在某個(gè)循環(huán)語(yǔ)句內(nèi)部只能在某個(gè)循環(huán)語(yǔ)句內(nèi)部語(yǔ)義分析語(yǔ)義分析 語(yǔ)法制導(dǎo)的類型檢查程序語(yǔ)法制導(dǎo)的類型檢查程序 舉例舉例P D ; S.break := 0 S P.type := if D.type = ok and S.type = ok then ok else type_error S if E then S1 .break := S.break S1 S.type := if E.type=bool then S1.type else type_error S

17、 if E then S1 .break := S.break S1 else S2 .break := S.break S2 S.type := if E.type=bool and S1.type = ok and S2.type = ok then ok else type_error 編譯原理語(yǔ)義分析語(yǔ)義分析S while E then S1.break := 1 S1 S.type := if E.type=bool then S1.type else type_error S S1 .break := S.break S1 ; S2 .break := S.break S2 S.t

18、ype := if S1.type = ok and S2.type = ok then ok else type_error S break S.type := if S.break = 1 then ok else type_error F F1 ; id ( V ) S.break := 0 S addtype(id.entry, fun (V.type); F.type := if F1.type = ok and S.type = ok then ok else type_error - 增加處理：增加處理：break 只能在某個(gè)循環(huán)語(yǔ)句內(nèi)部（續(xù)）只能在某個(gè)循環(huán)語(yǔ)句內(nèi)部（續(xù)） 語(yǔ)法制

19、導(dǎo)的類型檢查程序語(yǔ)法制導(dǎo)的類型檢查程序 舉例舉例編譯原理- 靜態(tài)作用域靜態(tài)作用域 通過(guò)符號(hào)表實(shí)現(xiàn)通過(guò)符號(hào)表實(shí)現(xiàn) （參見(jiàn)第七講）（參見(jiàn)第七講）- 動(dòng)態(tài)作用域動(dòng)態(tài)作用域 通過(guò)運(yùn)行時(shí)活動(dòng)記錄實(shí)現(xiàn)通過(guò)運(yùn)行時(shí)活動(dòng)記錄實(shí)現(xiàn) （參見(jiàn)下一講）（參見(jiàn)下一講） 作用域分析作用域分析語(yǔ)義分析語(yǔ)義分析編譯原理中間代碼生成中間代碼生成- 源程序的不同表示形式源程序的不同表示形式- 作用作用 源語(yǔ)言和目標(biāo)語(yǔ)言之間的橋梁，避開(kāi)二源語(yǔ)言和目標(biāo)語(yǔ)言之間的橋梁，避開(kāi)二者者 之間較大的語(yǔ)義跨度，之間較大的語(yǔ)義跨度，使編譯程序的邏輯使編譯程序的邏輯 結(jié)構(gòu)更加簡(jiǎn)單明確結(jié)構(gòu)更加簡(jiǎn)單明確 利于編譯程序的重定向利于編譯程序的重定向 利于進(jìn)行

20、與目標(biāo)機(jī)無(wú)關(guān)的優(yōu)化利于進(jìn)行與目標(biāo)機(jī)無(wú)關(guān)的優(yōu)化 中間代碼中間代碼編譯原理中間代碼生成中間代碼生成- 有有不同層次不同目的之分不同層次不同目的之分- 中間代碼舉例中間代碼舉例 AST（Abstract syntax tree，抽象語(yǔ)法樹(shù)抽象語(yǔ)法樹(shù)） TAC（Three-address code,三地址碼，四元式三地址碼，四元式） P-code （特別用于特別用于 Pasal 語(yǔ)言實(shí)現(xiàn)語(yǔ)言實(shí)現(xiàn)） Bytecode（Java 編譯器的輸出編譯器的輸出, Java 虛擬機(jī)的輸入虛擬機(jī)的輸入） SSA（Static single assignment form，靜態(tài)單賦值形式靜態(tài)單賦值形式） 中間代碼的形

21、式中間代碼的形式編譯原理中間代碼生成中間代碼生成- 算術(shù)表達(dá)式算術(shù)表達(dá)式 A + B * ( C - D ) + E / ( C - D ) N TAC （三地址碼）表示（三地址碼）表示 (1) ( - C D T1 ) T1 := C - D (2) ( * B T1 T2) T2 := B * T1 (3) ( + A T2 T3) T3 := A + T2 (4) ( - C D T4) 或或 T4 := C - D (5) ( T4 N T5) T5 := T4 N (6) ( / E T5 T6) T6 := E / T5 (7) (+ T3 T6 T7) T7 := T3 + T6

22、 中間代碼舉例中間代碼舉例編譯原理中間代碼生成中間代碼生成- 算術(shù)表達(dá)式算術(shù)表達(dá)式 A + B * ( C - D ) + E / ( C - D ) N AST（抽象語(yǔ)法樹(shù)抽象語(yǔ)法樹(shù)）表示）表示 中間代碼舉例中間代碼舉例+/A*E-BDC-DCN編譯原理中間代碼生成中間代碼生成- 算術(shù)表達(dá)式算術(shù)表達(dá)式 A + B * ( C - D ) + E / ( C - D ) N DAG（Directed Acyclic Graph,有向無(wú)圈圖，改進(jìn)型有向無(wú)圈圖，改進(jìn)型 AST） 中間代碼舉例中間代碼舉例+/A*EB-DCN編譯原理中間代碼生成中間代碼生成- 靜態(tài)單賦值形式靜態(tài)單賦值形式 中間代碼舉

23、例中間代碼舉例編譯原理中間代碼生成中間代碼生成- 語(yǔ)法制導(dǎo)的方法語(yǔ)法制導(dǎo)的方法 例：例：生成抽象語(yǔ)法樹(shù)生成抽象語(yǔ)法樹(shù) 中間代碼生成中間代碼生成S id := ES if E then S1S while E do S1 S S1 ; S2E idE E1 + E2 E E1 E2E ( E1 ) S.ptr := mknode(assign, mkleaf(id.entry), E.ptr) S.ptr := mknode(if_then, E.ptr, S1.ptr) S.ptr := mknode(while_do, E.ptr, S1.ptr) S.ptr := mknode(seq ,

24、 S1.ptr , S2.ptr) E.ptr := mkleaf(id.entry) E.ptr := mknode(+ , E1.ptr , E2.ptr) E.ptr := mknode( , E1.ptr , E2.ptr) E.ptr := E1.ptr mknode: 構(gòu)造內(nèi)部結(jié)點(diǎn)構(gòu)造內(nèi)部結(jié)點(diǎn)Mkleaf : 構(gòu)造葉子結(jié)點(diǎn)構(gòu)造葉子結(jié)點(diǎn)編譯原理中間代碼生成中間代碼生成- 順序的語(yǔ)句序列順序的語(yǔ)句序列 其其語(yǔ)句語(yǔ)句一般具有如下一般具有如下形式形式 x := y op z (op 為操作符，為操作符，y 和和 z 為操作數(shù)，為操作數(shù)， x 為結(jié)果為結(jié)果) 三地址碼三地址碼TAC編譯原理中

25、間代碼生成中間代碼生成 課程后續(xù)部分用到的課程后續(xù)部分用到的 TAC 語(yǔ)句類型語(yǔ)句類型 賦值語(yǔ)句賦值語(yǔ)句 x := y op z （op 代表二元算術(shù)代表二元算術(shù)/邏輯運(yùn)算）邏輯運(yùn)算） 賦值語(yǔ)句賦值語(yǔ)句 x := op y （op 代表一元運(yùn)算）代表一元運(yùn)算） 復(fù)寫語(yǔ)句復(fù)寫語(yǔ)句 x := y （y 的值賦值給的值賦值給 x） 無(wú)條件跳轉(zhuǎn)語(yǔ)句無(wú)條件跳轉(zhuǎn)語(yǔ)句 goto L （無(wú)條件跳轉(zhuǎn)至標(biāo)號(hào)（無(wú)條件跳轉(zhuǎn)至標(biāo)號(hào) L） 條件跳轉(zhuǎn)語(yǔ)句條件跳轉(zhuǎn)語(yǔ)句if x rop y goto L （rop 代表關(guān)系運(yùn)算）代表關(guān)系運(yùn)算） 標(biāo)號(hào)語(yǔ)句標(biāo)號(hào)語(yǔ)句 L : （定義標(biāo)號(hào)（定義標(biāo)號(hào) L） 過(guò)程調(diào)用語(yǔ)句序列過(guò)程調(diào)用語(yǔ)句序

26、列 param x1 param xn call p,n 過(guò)程返回語(yǔ)句過(guò)程返回語(yǔ)句 return y （y 可選，存放返回值）可選，存放返回值） 下標(biāo)賦值語(yǔ)句下標(biāo)賦值語(yǔ)句 x := yi 和和 xi := y （前者表示將地（前者表示將地 址址 y 起第起第i個(gè)存儲(chǔ)單元的值賦給個(gè)存儲(chǔ)單元的值賦給 x，后者類似）后者類似） 指針賦值語(yǔ)句指針賦值語(yǔ)句 x := *y 和和 *x := y編譯原理中間代碼生成中間代碼生成- 語(yǔ)義屬性語(yǔ)義屬性 id.place : id 對(duì)應(yīng)的存儲(chǔ)位置對(duì)應(yīng)的存儲(chǔ)位置 E.place : 用來(lái)存放用來(lái)存放 E 的值的存儲(chǔ)位置的值的存儲(chǔ)位置 E.code : E 求值的求

27、值的 TAC 語(yǔ)句序列語(yǔ)句序列 S.code : 對(duì)應(yīng)于對(duì)應(yīng)于 S 的的 TAC 語(yǔ)句序列語(yǔ)句序列 - 語(yǔ)義函數(shù)語(yǔ)義函數(shù)/過(guò)程過(guò)程 gen : 生成一條生成一條 TAC 語(yǔ)句語(yǔ)句 newtemp : 在符號(hào)表中新建一個(gè)從未使用過(guò)的名字，在符號(hào)表中新建一個(gè)從未使用過(guò)的名字， 并返回該名字的存儲(chǔ)位置并返回該名字的存儲(chǔ)位置 | 是是TAC 語(yǔ)句序列之間的語(yǔ)句序列之間的鏈接運(yùn)算鏈接運(yùn)算 賦值語(yǔ)句及算數(shù)表達(dá)式的語(yǔ)法制導(dǎo)翻譯賦值語(yǔ)句及算數(shù)表達(dá)式的語(yǔ)法制導(dǎo)翻譯編譯原理中間代碼生成中間代碼生成- 翻譯模式翻譯模式 賦值語(yǔ)句及算數(shù)表達(dá)式的語(yǔ)法制導(dǎo)翻譯賦值語(yǔ)句及算數(shù)表達(dá)式的語(yǔ)法制導(dǎo)翻譯S id := E S.co

28、de := E.code | gen(id .place := E.place) E id E.place := id .place E int E.place := newtemp; E.code := gen (E.place := int .val) E real E.place := newtemp; E.code := gen (E.place := real .val) E E1 + E2 E.place := newtemp; E.code := E1.code | E2.code | gen (E.place := E1.place + E2.place) E E1 E2 E.

29、place := newtemp; E.code := E1.code | E2.code | gen (E.place := E1.place E2.place) E -E1 E.place := newtemp; E.code := E1.code | gen (E.place := uminus E1.place) E (E1) E.place := E1.place ; E.code := E1.code 編譯原理中間代碼生成中間代碼生成- 語(yǔ)義屬性語(yǔ)義屬性 : id 的詞法名字（符號(hào)表中的名字）的詞法名字（符號(hào)表中的名字） T.type : 類型屬性類型屬性 （綜合屬

30、性）（綜合屬性） T.width，V.width : 數(shù)據(jù)寬度（字節(jié)數(shù)）數(shù)據(jù)寬度（字節(jié)數(shù)） L.offset : 列表中第一個(gè)變量的偏移地址列表中第一個(gè)變量的偏移地址 L.type : 變量列表被申明的類型變量列表被申明的類型 （繼承屬性）（繼承屬性） L.num : 變量列表中變量的個(gè)數(shù)變量列表中變量的個(gè)數(shù) - 語(yǔ)義函數(shù)語(yǔ)義函數(shù)/過(guò)程過(guò)程 enter (, t, o) ：將符號(hào)表中將符號(hào)表中 所對(duì)應(yīng)表所對(duì)應(yīng)表 項(xiàng)的項(xiàng)的 type 域置為域置為 t，offset 域置為域置為 o 說(shuō)明語(yǔ)句的語(yǔ)法制導(dǎo)翻譯說(shuō)明語(yǔ)句的語(yǔ)法制導(dǎo)翻譯編譯原理中間代碼生成中間代碼生成- 翻譯

31、模式翻譯模式 說(shuō)明語(yǔ)句的語(yǔ)法制導(dǎo)翻譯說(shuō)明語(yǔ)句的語(yǔ)法制導(dǎo)翻譯V V1 ; T L.type := T.type; L.offset := V1.width ; L.width := T.width L V.type := make_product_3 (V1.type, T.type, L.num); V.width := V1 .width + L.num T.width V V.type := ; V.width := 0 T boolean T.type := bool ; T.width := 1 T integer T.type := int ; T.width := 4 T real

32、 T.type := real ; T.width := 8 T array num of T1 T.type := array(1. num.lexval, T1.type) ; T.width := num.val T1.width T T1 T.type := pointer(T1.type) ; T.width := 4 L L1. type := L. type ; L1. offset := L. offset ; L1. width := L. width ; L1 , id enter (, L. type, L. offset + L1.num L. width

33、) ; L.num := L1.num +1 L id enter (, L. type, L. offset) ; L.num := 1編譯原理中間代碼生成中間代碼生成- 數(shù)組說(shuō)明數(shù)組說(shuō)明 參考前頁(yè)的翻譯模式，可了解（一維）數(shù)組說(shuō)明的翻譯參考前頁(yè)的翻譯模式，可了解（一維）數(shù)組說(shuō)明的翻譯 思想思想. 至于符號(hào)表中一般情況下是如何組織數(shù)組說(shuō)明信至于符號(hào)表中一般情況下是如何組織數(shù)組說(shuō)明信 息的，隨后將會(huì)討論息的，隨后將會(huì)討論. 數(shù)組說(shuō)明和數(shù)組元素引用的語(yǔ)法制導(dǎo)翻譯數(shù)組說(shuō)明和數(shù)組元素引用的語(yǔ)法制導(dǎo)翻譯 T array num of T1 T.type := array(1. num.l

34、exval, T1.type) ; T.width := num.val T1.width .L L1. type := L. type ; L1. offset := L. offset ; L1. width := L. width ; L1 , id enter (, L. type, L. offset + L1.num L. width) ; L.num := L1.num +1 L id enter (, L. type, L. offset) ; L.num := 1編譯原理中間代碼生成中間代碼生成- 數(shù)組引用數(shù)組引用 數(shù)組說(shuō)明和數(shù)組元素引用的語(yǔ)法制導(dǎo)

35、翻譯數(shù)組說(shuō)明和數(shù)組元素引用的語(yǔ)法制導(dǎo)翻譯S E1E2 := E3 S.code := E2 .code | E3 .code | gen (E1 .place E2 .place := E3 .place) E E1E2 E.place := newtemp; E.code := E2.code | gen (E.place := E1.place E2.place ) 編譯原理中間代碼生成中間代碼生成- 數(shù)組的內(nèi)情向量數(shù)組的內(nèi)情向量（dove vector） 在處理數(shù)組時(shí)，通常會(huì)將數(shù)組的有關(guān)信息記錄在一些單在處理數(shù)組時(shí)，通常會(huì)將數(shù)組的有關(guān)信息記錄在一些單 元中，稱為元中，稱為“內(nèi)情向量?jī)?nèi)情向

36、量”. 對(duì)于靜態(tài)數(shù)組，內(nèi)情向量可放對(duì)于靜態(tài)數(shù)組，內(nèi)情向量可放在在 符號(hào)表中；對(duì)于可變數(shù)組，運(yùn)行時(shí)建立相應(yīng)的內(nèi)情向量符號(hào)表中；對(duì)于可變數(shù)組，運(yùn)行時(shí)建立相應(yīng)的內(nèi)情向量 例：例： 對(duì)于靜態(tài)數(shù)組說(shuō)明對(duì)于靜態(tài)數(shù)組說(shuō)明 Al1:u1,l2:u2,ln:un ，可以在符，可以在符 號(hào)表中建立如下形式的內(nèi)情向量號(hào)表中建立如下形式的內(nèi)情向量: 數(shù)組說(shuō)明和數(shù)組元素引用的語(yǔ)法制導(dǎo)翻譯數(shù)組說(shuō)明和數(shù)組元素引用的語(yǔ)法制導(dǎo)翻譯l1u1l2u2lnuntypeanCli : 第第 i 維的下界維的下界ui : 第第 i 維的上界維的上界type: 數(shù)組元素的類型數(shù)組元素的類型a: 數(shù)組首元素的地址數(shù)組首元素的地址n: 數(shù)組維

37、數(shù)數(shù)組維數(shù)C: 隨后解釋隨后解釋編譯原理中間代碼生成中間代碼生成- 數(shù)組元素的地址計(jì)算數(shù)組元素的地址計(jì)算 例：例：對(duì)于靜態(tài)數(shù)組對(duì)于靜態(tài)數(shù)組 Al1:u1,l2:u2,ln:un ，若數(shù)組布局采，若數(shù)組布局采 用行優(yōu)先的連續(xù)布局，數(shù)組首元素的地址為用行優(yōu)先的連續(xù)布局，數(shù)組首元素的地址為 a，則數(shù)組，則數(shù)組 元素元素Ai1,i2,in 的地址的地址 D 可以如下計(jì)算可以如下計(jì)算: D = a + (i1-l1)(u2-l2)(u3-l3) (un-ln) + (i2-l2)(u3-l3)(u4-l4) (un-ln) + (in-1-ln-1)(un-ln) + (in-ln) 數(shù)組說(shuō)明和數(shù)組元素

38、引用的語(yǔ)法制導(dǎo)翻譯數(shù)組說(shuō)明和數(shù)組元素引用的語(yǔ)法制導(dǎo)翻譯重新整理后得重新整理后得: D = a C + V ，其中，其中 C = ( (l1 (u2-l2) +l2) )(u3-l3) + l3) )(u4-l4) + l n-1) )(un-ln) + ln V = (i1 (u2-l2) +i2) )(u3-l3) + i3) )(u4-l4) + i n-1) )(un-ln) + in （這里的（這里的 C 即為前頁(yè)內(nèi)情向量中的即為前頁(yè)內(nèi)情向量中的 C）編譯原理中間代碼生成中間代碼生成- 直接對(duì)布爾表達(dá)式求值直接對(duì)布爾表達(dá)式求值例如例如 : 可以用數(shù)值可以用數(shù)值“1” 表示表示 true

39、; 用數(shù)值用數(shù)值“0” 表示表示 false;采用與算術(shù)表達(dá)式類似的方法對(duì)布爾表達(dá)式進(jìn)行求值采用與算術(shù)表達(dá)式類似的方法對(duì)布爾表達(dá)式進(jìn)行求值- 通過(guò)控制流體現(xiàn)布爾表達(dá)式的語(yǔ)義通過(guò)控制流體現(xiàn)布爾表達(dá)式的語(yǔ)義方法方法：通過(guò)轉(zhuǎn)移到程序中的某個(gè)位置來(lái)表示布爾表達(dá)式：通過(guò)轉(zhuǎn)移到程序中的某個(gè)位置來(lái)表示布爾表達(dá)式的求值結(jié)果的求值結(jié)果 優(yōu)點(diǎn)優(yōu)點(diǎn)：方便實(shí)現(xiàn)：方便實(shí)現(xiàn)控制流語(yǔ)句中控制流語(yǔ)句中布爾表達(dá)式的翻譯布爾表達(dá)式的翻譯?？梢缘玫匠？梢缘玫蕉搪范搪罚╯hort-circuit）代碼，而避免不必要的）代碼，而避免不必要的求值，如：在已知求值，如：在已知 E1 為真時(shí)，不必再對(duì)為真時(shí)，不必再對(duì)E1 E2 中的中的 E

40、2進(jìn)行求值；同樣，在已知進(jìn)行求值；同樣，在已知 E1 為假時(shí)，不必再對(duì)為假時(shí)，不必再對(duì) E1 E2中的中的E2 進(jìn)行求值進(jìn)行求值 布爾表達(dá)式的語(yǔ)法制導(dǎo)翻譯布爾表達(dá)式的語(yǔ)法制導(dǎo)翻譯編譯原理中間代碼生成中間代碼生成- 直接對(duì)布爾表達(dá)式求值直接對(duì)布爾表達(dá)式求值 布爾表達(dá)式的語(yǔ)法制導(dǎo)翻譯布爾表達(dá)式的語(yǔ)法制導(dǎo)翻譯E E1 E2 E E1 E2E E1E ( E1 ) E id1 rop id2E trueE false E.place := newtemp; E.code := E1.code | E2.code | gen (E.place := E1.place or E2.place) E.pla

41、ce := newtemp; E.code := E1.code | E2.code | gen (E.place := E1.place and E2.place) E.place := newtemp; E.code := E1.code | gen (E.place := not E1.palce) E.place := E1.place ; E.code := E1.code E.place := newtemp; E.code := gen ( if id1.place rop.op id2.place goto nextstat+3) | gen (E.place := 0) |

42、gen (goto nextstat+2) | gen (E.place := 1) E.place := newtemp; E.code := gen(E.place := 1) E.place := newtemp; E.code := gen(E.place := 0) nextstat 返回輸出代碼序列返回輸出代碼序列中下一條中下一條 TAC 語(yǔ)句的下標(biāo)語(yǔ)句的下標(biāo)編譯原理中間代碼生成中間代碼生成- 通過(guò)控制流體現(xiàn)布爾表達(dá)式的語(yǔ)義通過(guò)控制流體現(xiàn)布爾表達(dá)式的語(yǔ)義 例例 : 布爾表達(dá)式布爾表達(dá)式 E = ab or cd and ef 可能翻譯為如可能翻譯為如 下下TAC 語(yǔ)句序列（采用短路

43、代碼，語(yǔ)句序列（采用短路代碼，E.true 和和E.false 分別代表分別代表 E 為真和假時(shí)對(duì)應(yīng)于程序中的位置，可用為真和假時(shí)對(duì)應(yīng)于程序中的位置，可用 標(biāo)號(hào)體現(xiàn)）：標(biāo)號(hào)體現(xiàn)）： if ab goto E.true goto label1 label1: if cd goto label2 goto E.false label2: if ef goto E.true goto E.false 布爾表達(dá)式的語(yǔ)法制導(dǎo)翻譯布爾表達(dá)式的語(yǔ)法制導(dǎo)翻譯編譯原理中間代碼生成中間代碼生成- 翻譯布爾表達(dá)式至短路代碼（翻譯布爾表達(dá)式至短路代碼（L-翻譯模式）翻譯模式） 布爾表達(dá)式的語(yǔ)法制導(dǎo)翻譯布爾表達(dá)式的語(yǔ)法

44、制導(dǎo)翻譯E E1.true := E.true; E1.false := newlabel E1 E2.true := E.true; E2.false := E.false E2 E.code := E1 .code | gen (E1.false :) | E2 .code E E1.false := E.false; E1.true := newlabel E1 E2.false := E.false; E2.true := E.true E2 E.code := E1 .code | gen (E1.true :) | E2 .code E E1.true := E.false; E1

45、.false := E.true E1 E.code := E1.code E ( E1.true := E.true; E1.false := E.false E1 ) E.code := E1.code E id1 rop id2 E.code := gen (if id1.place rop.op id2.place goto E.true ) | gen (goto E. false) E true E.code := gen (goto E.true) E false E.code := gen (goto E. false) 編譯原理中間代碼生成中間代碼生成- if-then 語(yǔ)句

46、（語(yǔ)句（L 翻譯模式）翻譯模式） S if E.true := newlable；E.false := S.next Ethen S1.next := S.next S1 S.code := E.code | gen(E.true :) | S1.code 條件語(yǔ)句的語(yǔ)法制導(dǎo)翻譯條件語(yǔ)句的語(yǔ)法制導(dǎo)翻譯E.codeS1.codeE.true:E.false:to E.trueto E.falsenewlable 返回一個(gè)新的語(yǔ)句標(biāo)號(hào)返回一個(gè)新的語(yǔ)句標(biāo)號(hào)S.next 屬性表示屬性表示 S 之后要執(zhí)行的之后要執(zhí)行的首條首條 TAC 語(yǔ)句的標(biāo)號(hào)語(yǔ)句的標(biāo)號(hào)編譯原理中間代碼生成中間代碼生成- if-the

47、n-else 語(yǔ)句（語(yǔ)句（L 翻譯模式）翻譯模式） 條件語(yǔ)句的語(yǔ)法制導(dǎo)翻譯條件語(yǔ)句的語(yǔ)法制導(dǎo)翻譯E.codeS1.codeE.true:E.false:goto S.nextto E.trueto E.faseS2.codeS.next:S if E.true := newlable;E.false := newlable E then S1.next := S.next S1else S2.next := S.next S2 S.code := E.code | gen(E.true :) | S1.code | gen(goto S.next) |gen(E.false :) |S2.co

48、de 編譯原理中間代碼生成中間代碼生成 循環(huán)語(yǔ)句的語(yǔ)法制導(dǎo)翻譯循環(huán)語(yǔ)句的語(yǔ)法制導(dǎo)翻譯- while 語(yǔ)句（語(yǔ)句（L 翻譯模式）翻譯模式）E.codeS1.codeS1.next :E.false:goto S1.nextto E.trueto E.falseE.true:S while E.true := newlable;E.false := S.next E do S1.next := newlableS1 S.code := gen(S1.next :)| E.code | gen(E.true :)| S1.code| gen(goto S1.next) 編譯原理中間代碼生成中間代碼生

49、成 復(fù)合語(yǔ)句的語(yǔ)法制導(dǎo)翻譯復(fù)合語(yǔ)句的語(yǔ)法制導(dǎo)翻譯- 順序復(fù)合語(yǔ)句（順序復(fù)合語(yǔ)句（L 翻譯模式）翻譯模式） S S1.next := newlable S1 ; S2.next := S.next S2 S.code := S1.code | gen(S1.next :) | S2.code S1.codeS2.codeS.next:S1.next:編譯原理中間代碼生成中間代碼生成- 翻譯模式翻譯模式 含含 break 語(yǔ)句的語(yǔ)法制導(dǎo)翻譯語(yǔ)句的語(yǔ)法制導(dǎo)翻譯P D ; S.next := newlable; S.break := newlable S gen(S.next :) S if E.tr

50、ue := newlable; E.false := S.next E then S1.next := S.next; S1.break := S.break S1 S.code := E.code | gen(E. true :) | S1.code S if E.true := newlable; E.false := newlable E then S1.next := S.next; S1.break := S.break S1 else S2.next := S.next; S2.break := S.break S2 S.code := E.code | gen(E.true :)

51、 | S1.code | gen(goto S.next) | gen(E.false :) | S2.code 編譯原理中間代碼生成中間代碼生成S while E.true := newlable; E.false := S.next E do S1.next := newlable; S1.break := S.next S1 S.code := gen(S1.next :) | E.code | gen(E.true :) | S1.code | gen(goto S1.next) S S1.next := newlable; S1.break := S.break S1 ； S2.ne

52、xt := S.next; S2.break := S.break S2 S.code := S1.code | gen(S1.next :) | S2.code S break ; S.code := gen(goto S.break) - 翻譯模式翻譯模式 （續(xù)）（續(xù)） 含含 break 語(yǔ)句的語(yǔ)法制導(dǎo)翻譯語(yǔ)句的語(yǔ)法制導(dǎo)翻譯編譯原理中間代碼生成中間代碼生成 拉鏈與代碼回填拉鏈與代碼回填（backpatching）- 另一種控制流中間代碼生成技術(shù)另一種控制流中間代碼生成技術(shù) 比較：前面的方法采用比較：前面的方法采用 L-屬性文法屬性文法/翻譯模式翻譯模式 下面的方法采用下面的方法采用 S-屬

53、性文法屬性文法/翻譯模式翻譯模式編譯原理中間代碼生成中間代碼生成 拉鏈與代碼回填拉鏈與代碼回填- 語(yǔ)義屬性語(yǔ)義屬性 E.truelist : “真鏈真鏈”，鏈表中的元素表示，鏈表中的元素表示 一系列跳轉(zhuǎn)語(yǔ)一系列跳轉(zhuǎn)語(yǔ) 句的地址，這些跳轉(zhuǎn)語(yǔ)句的目標(biāo)標(biāo)號(hào)是體現(xiàn)布句的地址，這些跳轉(zhuǎn)語(yǔ)句的目標(biāo)標(biāo)號(hào)是體現(xiàn)布 爾表達(dá)式爾表達(dá)式 E 為為“真真”的標(biāo)號(hào)的標(biāo)號(hào) E. falselist : “假鏈假鏈”，鏈表中的元素表示，鏈表中的元素表示 一系列跳轉(zhuǎn)語(yǔ)一系列跳轉(zhuǎn)語(yǔ) 句的地址，這些跳轉(zhuǎn)語(yǔ)句的目標(biāo)標(biāo)號(hào)是體現(xiàn)布句的地址，這些跳轉(zhuǎn)語(yǔ)句的目標(biāo)標(biāo)號(hào)是體現(xiàn)布 爾表達(dá)式爾表達(dá)式 E 為假的標(biāo)號(hào)為假的標(biāo)號(hào) S. nextlis

54、t : “next 鏈鏈”，鏈表中的元素表示，鏈表中的元素表示 一系列跳轉(zhuǎn)一系列跳轉(zhuǎn) 語(yǔ)句的地址，這些跳轉(zhuǎn)語(yǔ)句的目標(biāo)標(biāo)號(hào)是在執(zhí)語(yǔ)句的地址，這些跳轉(zhuǎn)語(yǔ)句的目標(biāo)標(biāo)號(hào)是在執(zhí) 行序列中緊跟在行序列中緊跟在 S 之后的下條之后的下條TAC語(yǔ)句的標(biāo)號(hào)語(yǔ)句的標(biāo)號(hào)編譯原理中間代碼生成中間代碼生成 拉鏈與代碼回填拉鏈與代碼回填- 語(yǔ)義函數(shù)語(yǔ)義函數(shù)/過(guò)程過(guò)程 makelist(i) : 創(chuàng)建只有一個(gè)結(jié)點(diǎn)創(chuàng)建只有一個(gè)結(jié)點(diǎn) i 的表，對(duì)應(yīng)存放目標(biāo)的表，對(duì)應(yīng)存放目標(biāo) TAC 語(yǔ)句數(shù)組的一個(gè)下標(biāo)語(yǔ)句數(shù)組的一個(gè)下標(biāo) merge(p1,p2) : 連接兩個(gè)鏈表連接兩個(gè)鏈表 p1 和和 p2 ，返回結(jié)果鏈表，返回結(jié)果鏈表 ba

55、ckpatch(p,i) : 將鏈表將鏈表 p 中每個(gè)元素所指向的跳轉(zhuǎn)語(yǔ)句中每個(gè)元素所指向的跳轉(zhuǎn)語(yǔ)句 的標(biāo)號(hào)置為的標(biāo)號(hào)置為 i nextstm : 下一條下一條TAC 語(yǔ)句的地址語(yǔ)句的地址 emit () : 輸出一條輸出一條TAC 語(yǔ)句，并使語(yǔ)句，并使 nextstm 加加1 編譯原理中間代碼生成中間代碼生成 拉鏈與代碼回填拉鏈與代碼回填- 處理處理布爾表達(dá)式的翻譯模式布爾表達(dá)式的翻譯模式E E1 M E2 E E1 M E2E E1 backpatch(E1.falselist,M.gotostm) ; E.truelist := merge(E1.truelist, E2.truelis

56、t) ; E.falselist := E2.falselist backpatch(E1.truelist,M.gotostm) ; E.falselist := merge(E1.falselist, E2.falselist) ; E.truelist := E2.truelist E.truelist := E1.falselist ; E.falselist := E1.truelist 注注: 這里可以規(guī)定產(chǎn)生式的優(yōu)先級(jí)依次遞增來(lái)解決沖突問(wèn)題這里可以規(guī)定產(chǎn)生式的優(yōu)先級(jí)依次遞增來(lái)解決沖突問(wèn)題 （下同）（下同）編譯原理中間代碼生成中間代碼生成 拉鏈與代碼回填拉鏈與代碼回填- 處理處理布

57、爾表達(dá)式的翻譯模式布爾表達(dá)式的翻譯模式 （續(xù)）（續(xù)）E ( E1 ) E id1 rop id2E trueE falseM E.truelist := E1.truelist ; E.falselist := E1.falselist E.truelist := makelist ( nextstm); E.falselist := makelist ( nextstm+1); emit ( if id1.place rop.op id2.place goto _ ); emit (goto _) E.truelist := makelist ( nextstm); emit (goto _

58、) E.falselist := makelist ( nextstm); emit (goto _) M.gotostm := nextstm 編譯原理中間代碼生成中間代碼生成 拉鏈與代碼回填拉鏈與代碼回填- 布爾表達(dá)式布爾表達(dá)式 E = ab cd ef 的翻譯的翻譯示意示意（0）if ab goto _ orE.truelist=0,4E.falselist=3,5andM.gotostm=2M.gotostm=4E.truelist=4E.falselist=3,5E.truelist=0E.falselist=1abE.truelist=2E.falselist=3cdE.truel

59、ist=4E.falselist=5ef（1）goto _ （3）goto _（2）if cd goto _（4）if ef goto _（5）goto _(4)(2)編譯原理中間代碼生成中間代碼生成 拉鏈與代碼回填拉鏈與代碼回填- 處理?xiàng)l件處理?xiàng)l件語(yǔ)句的翻譯模式語(yǔ)句的翻譯模式S if E then M S1 backpatch(E.truelist,M.gotostm) ; S.nextlist := merge(E.falselist, S1.nextlist) S if E then M1 S1 N else M2 S2 backpatch(E.truelist, M1.gotostm)

60、 ; backpatch(E.falselist, M2.gotostm) ; S.nextlist := merge(S1.nextlist, merge(N.nextlist, S2.nextlist) ) M M.gotostm := nextstm N N.nextlist := makelist(nextstm); emit(goto _) 編譯原理中間代碼生成中間代碼生成 拉鏈與代碼回填拉鏈與代碼回填- 處理循環(huán)、復(fù)合處理循環(huán)、復(fù)合的翻譯模式的翻譯模式S while M1 E do M2 S1 backpatch(S1.nextlist, M1.gotostm) ; backpat