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

1、編譯原理 語義分析與中間代碼生成語義分析與中間代碼生成第十一講第十一講編譯原理 語義分析和中間代碼生成在編譯程序中的語義分析和中間代碼生成在編譯程序中的 邏輯位置邏輯位置語義分析與中間代碼生成語義分析與中間代碼生成詞法分析詞法分析語法分析語法分析中間代碼生成中間代碼生成中間代碼優(yōu)化中間代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成靜態(tài)語靜態(tài)語義分析義分析語義處理語義處理編譯原理 語義分析和中間代碼生成的重要數(shù)據(jù)結(jié)構(gòu)語義分析和中間代碼生成的重要數(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)表的組織已在第七講專門討論）語義分析與中間代碼生成語義分析與中間代碼生成編譯原理 語義分析語義分析 中間代碼生成中間代碼生成語義分析與中間代碼生成語義分析與中間代碼生成編譯原理 與語義分析相關(guān)的工作與語義分析相關(guān)的工作語義分析語義分析- 靜態(tài)語義檢查靜態(tài)語義檢查 編譯期間所進(jìn)行的語義編譯期間所進(jìn)行的語義檢查檢查 - 動(dòng)態(tài)語義檢查動(dòng)態(tài)語義檢查 所生成的代碼在運(yùn)行期間

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

4、域名字的作用域（scope）分析分析 建立名字的定義和使用之間聯(lián)系建立名字的定義和使用之間聯(lián)系 控制流檢查控制流檢查（flow-of-control checks） 控制流語句必須使控制轉(zhuǎn)移到合法的地方（如控制流語句必須使控制轉(zhuǎn)移到合法的地方（如 break 語句必須有合法的語句包圍它）語句必須有合法的語句包圍它） 唯一性檢查唯一性檢查（uniqueness checks） 很多場合要求對(duì)很多場合要求對(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)性 語義分析語義分析編譯原理- 類型檢查程序類型檢查程序（type checker）負(fù)責(zé)類型檢查）負(fù)責(zé)類型檢查 驗(yàn)證語言結(jié)構(gòu)是否匹配上下文所期望的類型驗(yàn)證語言結(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)行的類型檢查 類型檢查類型檢查語義分析語義

6、分析編譯原理- 以下是定義某個(gè)簡單語言的上下文無關(guān)文法以下是定義某個(gè)簡單語言的上下文無關(guān)文法 （將用于本講的設(shè)計(jì)示例）（將用于本講的設(shè)計(jì)示例）GP ： 一個(gè)簡單語言一個(gè)簡單語言語義分析語義分析編譯原理- 類型表達(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)語義分析語義分

7、析編譯原理- 類型表達(dá)式類型表達(dá)式 分四類定義分四類定義 基本數(shù)據(jù)類型表達(dá)式，積類型表達(dá)式，過程類型表達(dá)式，基本數(shù)據(jù)類型表達(dá)式，積類型表達(dá)式，過程類型表達(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á)式 舉例舉例 語義分析語義分析編譯

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

9、式設(shè)計(jì)恰當(dāng)?shù)姆g模式 可實(shí)現(xiàn)相應(yīng)語言的一個(gè)類型系統(tǒng)可實(shí)現(xiàn)相應(yīng)語言的一個(gè)類型系統(tǒng) 類型檢查程序的設(shè)計(jì)類型檢查程序的設(shè)計(jì)語義分析語義分析編譯原理- 處理處理聲明聲明的翻譯模式的翻譯模式 語法制導(dǎo)的類型檢查程序語法制導(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 語義分析語義分析編譯原理- 處理處理表達(dá)式表達(dá)式的翻譯模式的翻譯模式語義分析語義分析 語法制導(dǎo)的類型檢查程序語法制導(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( 編譯原理語義分析語義分析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á)式的翻譯模式的翻譯模式 語法制導(dǎo)的類型檢查程序語法制導(dǎo)的類型檢查程序 舉例舉例編譯原理- 處理處理語句、過程聲明及程序語句、過

13、程聲明及程序的翻譯模式的翻譯模式語義分析語義分析 語法制導(dǎo)的類型檢查程序語法制導(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 編譯原理語義分析語義分析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 - 處理處理語句、過程聲明及程序語句、過程聲明及程序的翻

16、譯模式的翻譯模式 （續(xù)）（續(xù)） 語法制導(dǎo)的類型檢查程序語法制導(dǎo)的類型檢查程序 舉例舉例編譯原理- 增加處理：增加處理：break 只能在某個(gè)循環(huán)語句內(nèi)部只能在某個(gè)循環(huán)語句內(nèi)部語義分析語義分析 語法制導(dǎo)的類型檢查程序語法制導(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 編譯原理語義分析語義分析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)語句內(nèi)部（續(xù)）只能在某個(gè)循環(huán)語句內(nèi)部（續(xù)） 語法制

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

20、與目標(biāo)機(jī)無關(guān)的優(yōu)化利于進(jìn)行與目標(biāo)機(jī)無關(guān)的優(yōu)化 中間代碼中間代碼編譯原理中間代碼生成中間代碼生成- 有有不同層次不同目的之分不同層次不同目的之分- 中間代碼舉例中間代碼舉例 AST（Abstract syntax tree，抽象語法樹抽象語法樹） TAC（Three-address code,三地址碼，四元式三地址碼，四元式） P-code （特別用于特別用于 Pasal 語言實(shí)現(xiàn)語言實(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（抽象語法樹抽象語法樹）表示）表示 中間代碼舉例中間代碼舉例+/A*E-BDC-DCN編譯原理中間代碼生成中間代碼生成- 算術(shù)表達(dá)式算術(shù)表達(dá)式 A + B * ( C - D ) + E / ( C - D ) N DAG（Directed Acyclic Graph,有向無圈圖，改進(jìn)型有向無圈圖，改進(jìn)型 AST） 中間代碼舉例中間代碼舉例+/A*EB-DCN編譯原理中間代碼生成中間代碼生成- 靜態(tài)單賦值形式靜態(tài)單賦值形式 中間代碼舉

23、例中間代碼舉例編譯原理中間代碼生成中間代碼生成- 語法制導(dǎo)的方法語法制導(dǎo)的方法 例：例：生成抽象語法樹生成抽象語法樹 中間代碼生成中間代碼生成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)編譯原理中間代碼生成中間代碼生成- 順序的語句序列順序的語句序列 其其語句語句一般具有如下一般具有如下形式形式 x := y op z (op 為操作符，為操作符，y 和和 z 為操作數(shù)，為操作數(shù)， x 為結(jié)果為結(jié)果) 三地址碼三地址碼TAC編譯原理中

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

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

27、值的 TAC 語句序列語句序列 S.code : 對(duì)應(yīng)于對(duì)應(yīng)于 S 的的 TAC 語句序列語句序列 - 語義函數(shù)語義函數(shù)/過程過程 gen : 生成一條生成一條 TAC 語句語句 newtemp : 在符號(hào)表中新建一個(gè)從未使用過的名字，在符號(hào)表中新建一個(gè)從未使用過的名字， 并返回該名字的存儲(chǔ)位置并返回該名字的存儲(chǔ)位置 | 是是TAC 語句序列之間的語句序列之間的鏈接運(yùn)算鏈接運(yùn)算 賦值語句及算數(shù)表達(dá)式的語法制導(dǎo)翻譯賦值語句及算數(shù)表達(dá)式的語法制導(dǎo)翻譯編譯原理中間代碼生成中間代碼生成- 翻譯模式翻譯模式 賦值語句及算數(shù)表達(dá)式的語法制導(dǎo)翻譯賦值語句及算數(shù)表達(dá)式的語法制導(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 編譯原理中間代碼生成中間代碼生成- 語義屬性語義屬性 : 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ù) - 語義函數(shù)語義函數(shù)/過程過程 enter (, t, o) ：將符號(hào)表中將符號(hào)表中 所對(duì)應(yīng)表所對(duì)應(yīng)表 項(xiàng)的項(xiàng)的 type 域置為域置為 t，offset 域置為域置為 o 說明語句的語法制導(dǎo)翻譯說明語句的語法制導(dǎo)翻譯編譯原理中間代碼生成中間代碼生成- 翻譯

31、模式翻譯模式 說明語句的語法制導(dǎo)翻譯說明語句的語法制導(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ù)組說明數(shù)組說明 參考前頁的翻譯模式，可了解（一維）數(shù)組說明的翻譯參考前頁的翻譯模式，可了解（一維）數(shù)組說明的翻譯 思想思想. 至于符號(hào)表中一般情況下是如何組織數(shù)組說明信至于符號(hào)表中一般情況下是如何組織數(shù)組說明信 息的，隨后將會(huì)討論息的，隨后將會(huì)討論. 數(shù)組說明和數(shù)組元素引用的語法制導(dǎo)翻譯數(shù)組說明和數(shù)組元素引用的語法制導(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ù)組說明和數(shù)組元素引用的語法制導(dǎo)

35、翻譯數(shù)組說明和數(shù)組元素引用的語法制導(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)情向量內(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ù)組說明對(duì)于靜態(tài)數(shù)組說明 Al1:u1,l2:u2,ln:un ，可以在符，可以在符 號(hào)表中建立如下形式的內(nèi)情向量號(hào)表中建立如下形式的內(nèi)情向量: 數(shù)組說明和數(shù)組元素引用的語法制導(dǎo)翻譯數(shù)組說明和數(shù)組元素引用的語法制導(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ù)組說明和數(shù)組元素

38、引用的語法制導(dǎo)翻譯數(shù)組說明和數(shù)組元素引用的語法制導(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 即為前頁內(nèi)情向量中的即為前頁內(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)行求值- 通過控制流體現(xiàn)布爾表達(dá)式的語義通過控制流體現(xiàn)布爾表達(dá)式的語義方法方法：通過轉(zhuǎn)移到程序中的某個(gè)位置來表示布爾表達(dá)式：通過轉(zhuǎn)移到程序中的某個(gè)位置來表示布爾表達(dá)式的求值結(jié)果的求值結(jié)果 優(yōu)點(diǎn)優(yōu)點(diǎn)：方便實(shí)現(xiàn)：方便實(shí)現(xiàn)控制流語句中控制流語句中布爾表達(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á)式的語法制導(dǎo)翻譯布爾表達(dá)式的語法制導(dǎo)翻譯編譯原理中間代碼生成中間代碼生成- 直接對(duì)布爾表達(dá)式求值直接對(duì)布爾表達(dá)式求值 布爾表達(dá)式的語法制導(dǎo)翻譯布爾表達(dá)式的語法制導(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 語句的下標(biāo)語句的下標(biāo)編譯原理中間代碼生成中間代碼生成- 通過控制流體現(xiàn)布爾表達(dá)式的語義通過控制流體現(xiàn)布爾表達(dá)式的語義 例例 : 布爾表達(dá)式布爾表達(dá)式 E = ab or cd and ef 可能翻譯為如可能翻譯為如 下下TAC 語句序列（采用短路

43、代碼，語句序列（采用短路代碼，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á)式的語法制導(dǎo)翻譯布爾表達(dá)式的語法制導(dǎo)翻譯編譯原理中間代碼生成中間代碼生成- 翻譯布爾表達(dá)式至短路代碼（翻譯布爾表達(dá)式至短路代碼（L-翻譯模式）翻譯模式） 布爾表達(dá)式的語法制導(dǎo)翻譯布爾表達(dá)式的語法

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 語句

46、（語句（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 條件語句的語法制導(dǎo)翻譯條件語句的語法制導(dǎo)翻譯E.codeS1.codeE.true:E.false:to E.trueto E.falsenewlable 返回一個(gè)新的語句標(biāo)號(hào)返回一個(gè)新的語句標(biāo)號(hào)S.next 屬性表示屬性表示 S 之后要執(zhí)行的之后要執(zhí)行的首條首條 TAC 語句的標(biāo)號(hào)語句的標(biāo)號(hào)編譯原理中間代碼生成中間代碼生成- if-the

47、n-else 語句（語句（L 翻譯模式）翻譯模式） 條件語句的語法制導(dǎo)翻譯條件語句的語法制導(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)語句的語法制導(dǎo)翻譯循環(huán)語句的語法制導(dǎo)翻譯- while 語句（語句（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ù)合語句的語法制導(dǎo)翻譯復(fù)合語句的語法制導(dǎo)翻譯- 順序復(fù)合語句（順序復(fù)合語句（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 語句的語法制導(dǎo)翻譯語句的語法制導(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 語句的語法制導(dǎo)翻譯語句的語法制導(dǎo)翻譯編譯原理中間代碼生成中間代碼生成 拉鏈與代碼回填拉鏈與代碼回填（backpatching）- 另一種控制流中間代碼生成技術(shù)另一種控制流中間代碼生成技術(shù) 比較：前面的方法采用比較：前面的方法采用 L-屬性文法屬性文法/翻譯模式翻譯模式 下面的方法采用下面的方法采用 S-屬

53、性文法屬性文法/翻譯模式翻譯模式編譯原理中間代碼生成中間代碼生成 拉鏈與代碼回填拉鏈與代碼回填- 語義屬性語義屬性 E.truelist : “真鏈真鏈”，鏈表中的元素表示，鏈表中的元素表示 一系列跳轉(zhuǎn)語一系列跳轉(zhuǎn)語 句的地址，這些跳轉(zhuǎn)語句的目標(biāo)標(biāo)號(hào)是體現(xiàn)布句的地址，這些跳轉(zhuǎn)語句的目標(biāo)標(biāo)號(hào)是體現(xiàn)布 爾表達(dá)式爾表達(dá)式 E 為為“真真”的標(biāo)號(hào)的標(biāo)號(hào) E. falselist : “假鏈假鏈”，鏈表中的元素表示，鏈表中的元素表示 一系列跳轉(zhuǎn)語一系列跳轉(zhuǎn)語 句的地址，這些跳轉(zhuǎn)語句的目標(biāo)標(biāo)號(hào)是體現(xiàn)布句的地址，這些跳轉(zhuǎn)語句的目標(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) 語句的地址，這些跳轉(zhuǎn)語句的目標(biāo)標(biāo)號(hào)是在執(zhí)語句的地址，這些跳轉(zhuǎn)語句的目標(biāo)標(biāo)號(hào)是在執(zhí) 行序列中緊跟在行序列中緊跟在 S 之后的下條之后的下條TAC語句的標(biāo)號(hào)語句的標(biāo)號(hào)編譯原理中間代碼生成中間代碼生成 拉鏈與代碼回填拉鏈與代碼回填- 語義函數(shù)語義函數(shù)/過程過程 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 語句數(shù)組的一個(gè)下標(biāo)語句數(shù)組的一個(gè)下標(biāo) merge(p1,p2) : 連接兩個(gè)鏈表連接兩個(gè)鏈表 p1 和和 p2 ，返回結(jié)果鏈表，返回結(jié)果鏈表 ba

55、ckpatch(p,i) : 將鏈表將鏈表 p 中每個(gè)元素所指向的跳轉(zhuǎn)語句中每個(gè)元素所指向的跳轉(zhuǎn)語句 的標(biāo)號(hào)置為的標(biāo)號(hào)置為 i nextstm : 下一條下一條TAC 語句的地址語句的地址 emit () : 輸出一條輸出一條TAC 語句，并使語句，并使 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í)依次遞增來解決沖突問題這里可以規(guī)定產(chǎn)生式的優(yōu)先級(jí)依次遞增來解決沖突問題 （下同）（下同）編譯原理中間代碼生成中間代碼生成 拉鏈與代碼回填拉鏈與代碼回填- 處理處理布

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件語句的翻譯模式語句的翻譯模式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