編譯技術(shù)：第05章 語義分析

1、第五章 語義分析詞法分析詞法分析中間代碼生成中間代碼生成語法分析語法分析語義分析語義分析中間代碼優(yōu)化中間代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成源程序機(jī)器代碼編譯的步驟2Zhou, ErqiangSchool of Information and Software Engineering概述程序在程序在“詞法詞法分析分析”中無錯誤中無錯誤 標(biāo)識符：符合定義規(guī)則標(biāo)識符：符合定義規(guī)則 字符串：正常結(jié)束字符串：正常結(jié)束程序在程序在“語法語法分析分析”中無錯誤中無錯誤 類：結(jié)構(gòu)正確類：結(jié)構(gòu)正確 表達(dá)式：句法正確表達(dá)式：句法正確程序程序一定合法一定合法？Zhou, Erqiang3Sch

2、ool of Information and Software Engineering概述Zhou, Erqiang4School of Information and Software EngineeringMyInterfaceMyInterface是否定義是否定義string string 類型錯誤類型錯誤string string 不支持乘法不支持乘法變量沒有聲明變量沒有聲明函數(shù)不能重復(fù)定義函數(shù)不能重復(fù)定義voidvoid類型類型 不能與不能與 整型相加整型相加class MyClass implements MyInterface string myInteger;void doSo

3、mething() int x = new string;x5 = myInteger * y;void doSomething() int fibonacci(int n) return doSomething() + fibonacci(n 1);概述靜態(tài)語義檢查靜態(tài)語義檢查 類型檢查：如操作數(shù)類型應(yīng)相容類型檢查：如操作數(shù)類型應(yīng)相容 控制流檢查：控制流檢查： 保證控制語句有合法的轉(zhuǎn)向點(diǎn)保證控制語句有合法的轉(zhuǎn)向點(diǎn) goto goto 轉(zhuǎn)入轉(zhuǎn)入casecase語句？語句？ break break語句的循環(huán)語句？語句的循環(huán)語句？Zhou, Erqiang5School of Informatio

4、n and Software Engineering概述靜態(tài)語義檢查靜態(tài)語義檢查 一致性檢查：一致性檢查： 數(shù)組維數(shù)是否正確數(shù)組維數(shù)是否正確 變量是否已經(jīng)定義變量是否已經(jīng)定義 在同一作用域中標(biāo)識符說明次數(shù)在同一作用域中標(biāo)識符說明次數(shù) case case常量不能相同等常量不能相同等Zhou, Erqiang6School of Information and Software Engineering概述語義分析保證程序有正確的意思語義分析保證程序有正確的意思驗(yàn)證前兩階段已獲取的驗(yàn)證前兩階段已獲取的各種屬性各種屬性屬性信息保存在哪里屬性信息保存在哪里？Zhou, Erqiang7School of

5、 Information and Software Engineering標(biāo)識符定義標(biāo)識符定義實(shí)體實(shí)體 實(shí)體屬性保存在實(shí)體屬性保存在符號表符號表符號表的形式符號表的形式 每個名字對應(yīng)一個表項(xiàng)每個名字對應(yīng)一個表項(xiàng) 一個表項(xiàng)包括一個表項(xiàng)包括名字域名字域和和信息域信息域名字名字屬性信息屬性信息符號表Zhou, Erqiang8School of Information and Software Engineering屬性域?qū)傩杂?多個多個子域子域及及標(biāo)志位標(biāo)志位 類型、值、存儲大小、相對地址類型、值、存儲大小、相對地址 形參標(biāo)志、說明標(biāo)志、賦值標(biāo)志形參標(biāo)志、說明標(biāo)志、賦值標(biāo)志符號表Zhou, Erq

6、iang9School of Information and Software Engineering名字域名字域 名字長度固定？名字長度固定？ 間接表技術(shù)間接表技術(shù)Zhou, Erqiang10School of Information and Software Engineering符號表x1bbstring; “abc”;第一項(xiàng)第一項(xiàng)Maxint;10第二項(xiàng)第二項(xiàng)名字域名字域?qū)傩杂驅(qū)傩杂騔hou, Erqiang11School of Information and Software Engineering符號表indexindexstring; “abc”;indexindexint;

7、10名字域名字域?qū)傩杂驅(qū)傩杂騒 1 b b M a x 43 字符串表字符串表Zhou, Erqiang12School of Information and Software Engineering符號表indexindexstring; “abc”;indexindexint;10名字域名字域?qū)傩杂驅(qū)傩杂? X 1 b b 3 M a x 字符串表字符串表名字域直接用名字域直接用“指針指針”嵌套語句如何處理？嵌套語句如何處理？0: int x = 137;1: int z = 10;2: int MyFunction(int x, int y) 3: printf(%d,%d,%dn, x

8、, y, z);4: 5: int x, z;6: z = y;7: x = z;8: 9: int y = x;10: printf(%d,%d,%dn, x, y, z);11: 12: 13: z = x + z; 14: 15: printf(%d,%d,%dn, x, y, z);16: 17: Zhou, Erqiang13School of Information and Software Engineering符號表x xint; 137z zint; 10名字域名字域?qū)傩杂驅(qū)傩杂?x xint; unknowny yint; unknownx xint; unknownz z

9、int; unknowny yint; unknown核心問題：對于抽象語法樹中的核心問題：對于抽象語法樹中的被引用被引用的標(biāo)識符的標(biāo)識符 如何如何在符號表中在符號表中找出找出其對應(yīng)的屬性？其對應(yīng)的屬性？聲明：聲明：錄入錄入符號表符號表引用：引用：訪問訪問符號表符號表Zhou, Erqiang14School of Information and Software Engineering符號表x xint; 137z zint; 10名字域名字域?qū)傩杂驅(qū)傩杂騲 xint; unknowny yint; unknownx xint; unknownz zint; unknowny yint; u

10、nknown2 22 201234560 01 12 22 21 13 3 個數(shù)個數(shù)指針指針嵌套數(shù)嵌套數(shù)0246兩個并列的作用域？兩個并列的作用域？x xint; unknowny yint; unknownotherFunc(int x, int y)僅僅嵌套層次嵌套層次與與變量名變量名 是否能確定變量對應(yīng)的屬性？是否能確定變量對應(yīng)的屬性？引入引入“嵌套關(guān)系表嵌套關(guān)系表”嵌套關(guān)系表嵌套關(guān)系表與應(yīng)隨當(dāng)前訪問的代碼動態(tài)變化與應(yīng)隨當(dāng)前訪問的代碼動態(tài)變化一般用一般用棧棧實(shí)現(xiàn)實(shí)現(xiàn)Zhou, Erqiang15School of Information and Software Engineering符

11、號表x xint; 137z zint; 10名字域名字域?qū)傩杂驅(qū)傩杂騲 xint; unknowny yint; unknownx xint; unknownz zint; unknowny yint; unknown2 22 201234560 01 12 22 21 13 3 個數(shù)個數(shù)指針指針嵌套數(shù)嵌套數(shù)0246x xint; unknowny yint; unknownotherFunc(int x, int y)2 21 1 2注意：注意： 符號表中的表項(xiàng)不用刪除符號表中的表項(xiàng)不用刪除 這里只是為了說明作用域的退出這里只是為了說明作用域的退出語法制導(dǎo)翻譯Zhou, Erqiang16

12、School of Information and Software Engineering語義分析語義分析 語義檢查語義檢查 語義處理語義處理 說明語句：檢查屬性信息說明語句：檢查屬性信息 執(zhí)行語句：生成中間代碼執(zhí)行語句：生成中間代碼注意：注意： 根據(jù)所要生成的根據(jù)所要生成的“低級語言低級語言” （LLVM、匯編、機(jī)器）、匯編、機(jī)器） 說明語句需要翻譯成說明語句需要翻譯成該語言該語言對應(yīng)的代碼對應(yīng)的代碼語法制導(dǎo)翻譯Zhou, Erqiang17School of Information and Software Engineering語義分析語義分析 語義檢查語義檢查 語義處理語義處理 說明

13、語句：檢查屬性信息說明語句：檢查屬性信息 執(zhí)行語句：生成中間代碼執(zhí)行語句：生成中間代碼分析方法分析方法 語法制導(dǎo)的翻譯方法語法制導(dǎo)的翻譯方法 即在語法分析時不建立即在語法分析時不建立AST，而是直接生成中間代碼，而是直接生成中間代碼適用于文法比較簡單的語言適用于文法比較簡單的語言建立建立AST是目前編譯器的是目前編譯器的標(biāo)準(zhǔn)標(biāo)準(zhǔn)步驟步驟語法制導(dǎo)翻譯Zhou, Erqiang18School of Information and Software Engineering分析過程分析過程 每個每個產(chǎn)生式產(chǎn)生式配上一個配上一個語義子程序語義子程序 當(dāng)對產(chǎn)生式進(jìn)行當(dāng)對產(chǎn)生式進(jìn)行推導(dǎo)推導(dǎo)或或歸約歸約時時

14、 調(diào)用相應(yīng)的語義程序調(diào)用相應(yīng)的語義程序 進(jìn)行語義分析進(jìn)行語義分析將將 語法分析語法分析 與與 語義分析混在一起語義分析混在一起代碼很難維護(hù)代碼很難維護(hù)語法制導(dǎo)翻譯Zhou, Erqiang19School of Information and Software Engineering語義子程序語義子程序 完成語義檢查、語義處理完成語義檢查、語義處理 檢查：類型、控制流、一致性檢查：類型、控制流、一致性 處理：記錄信息、生成中間代碼處理：記錄信息、生成中間代碼 核心是生成中間代碼核心是生成中間代碼語法制導(dǎo)翻譯（示例1）Zhou, Erqiang20School of Information an

15、d Software Engineering計(jì)算器程序的語法制導(dǎo)翻譯計(jì)算器程序的語法制導(dǎo)翻譯L E print(E.val); E E1+T E.val = E1.val + T.val ; E T E.val = T.val ;T T1*F T.val = T1.val * F.val ;T F T.val = F.val ;F (E) F.val = E.val ;F digit F.val = digit.lexval ;語法制導(dǎo)翻譯（示例1）Zhou, Erqiang21School of Information and Software Engineering3*F5TFE+TF4E

16、TL E E E1+TE TT T1*FT F F (E)F digit3*5+4 的的語法語法分析過程分析過程語法制導(dǎo)翻譯（示例1）Zhou, Erqiang22School of Information and Software Engineeringdigit.lexval =3F.val = digit.lexval T.val =F.valdigit.lexval =5F.val:=5T.val =15*E.val =15+digit.lexval =4F.val =4T.val =4E.val =19print(19)3*5+4 的的語義語義分析過程分析過程L E print(E

17、val)E E1+T E val = E1 val + T valE T E val = T valT T1*F T val = T1 val * F valT F T val = F valF (E) F val = E valF digit F val = digit lexval語法制導(dǎo)翻譯Zhou, Erqiang23School of Information and Software Engineering在分析過程中必須保存語義值在分析過程中必須保存語義值 “ “類型類型”、“種屬種屬”、“地址地址”等等種屬種屬 常量、簡單變量、數(shù)組、函數(shù)、標(biāo)號、常量、簡單變量、數(shù)組、函數(shù)、標(biāo)號、

18、語義值語義值 X.type、X.category、X.address、語法制導(dǎo)翻譯（示例2）Zhou, Erqiang24School of Information and Software Engineering如果采用自底向上的如果采用自底向上的LRLR分析法分析法X XABABY YCDCDZ ZXYXY狀態(tài)棧狀態(tài)棧符號棧符號棧語義棧語義棧B BA A B B的語義值的語義值A(chǔ) A的語義值的語義值 語法制導(dǎo)翻譯（示例2）Zhou, Erqiang25School of Information and Software Engineering如果采用自底向上的如果采用自底向上的LRLR分析

19、法分析法X XABABY YCDCDZ ZXYXY狀態(tài)棧狀態(tài)棧符號棧符號棧語義棧語義棧X X X X的語義值的語義值 如果采用自底向上的如果采用自底向上的LRLR分析法分析法X XABABY YCDCDZ ZXYXYD D的語義值的語義值C C的語義值的語義值X X的語義值的語義值 D DC CX X 語法制導(dǎo)翻譯（示例2）Zhou, Erqiang26School of Information and Software Engineering狀態(tài)棧狀態(tài)棧符號棧符號棧語義棧語義棧如果采用自底向上的如果采用自底向上的LRLR分析法分析法X XABABY YCDCDZ ZXYXY Y Y的語義值的

20、語義值X X的語義值的語義值 Y YX X 語法制導(dǎo)翻譯（示例2）Zhou, Erqiang27School of Information and Software Engineering狀態(tài)棧狀態(tài)棧符號棧符號棧語義棧語義棧如果采用自底向上的如果采用自底向上的LRLR分析法分析法X XABABY YCDCDZ ZXYXY Y Y的語義值的語義值X X的語義值的語義值 Y YX X 語法制導(dǎo)翻譯（示例2）Zhou, Erqiang28School of Information and Software Engineering狀態(tài)棧狀態(tài)棧符號棧符號棧語義棧語義棧如果采用自底向上的如果采用自底向上的

21、LRLR分析法分析法X XABABY YCDCDZ ZXYXY Z Z的語義值的語義值 Z Z 語法制導(dǎo)翻譯（示例2）Zhou, Erqiang29School of Information and Software Engineering狀態(tài)棧狀態(tài)棧符號棧符號棧語義棧語義棧語法制導(dǎo)翻譯（示例總結(jié)）Zhou, Erqiang30School of Information and Software Engineering產(chǎn)生式產(chǎn)生式 用下標(biāo)區(qū)別產(chǎn)生式中相同非終結(jié)符用下標(biāo)區(qū)別產(chǎn)生式中相同非終結(jié)符例如將產(chǎn)生式例如將產(chǎn)生式 EE+E 表示為表示為 EE1+E2 3 3個個E的語義值的語義值 如如E.V

22、AL，E1.VAL和和E2.VAL語法制導(dǎo)翻譯（示例總結(jié)）Zhou, Erqiang31School of Information and Software Engineering產(chǎn)生式的語義動作產(chǎn)生式的語義動作 寫在產(chǎn)生式后的花括號內(nèi)寫在產(chǎn)生式后的花括號內(nèi)例如例如 EE1+E2 E.VAL = E1.VAL+E2.VAL ET E.VAL = T.VAL 語法制導(dǎo)翻譯（示例總結(jié)）Zhou, Erqiang32School of Information and Software Engineering編譯時僅編譯時僅常量常量的值可以確定的值可以確定 對大多數(shù)歸約對大多數(shù)歸約 語義程序需要生成相

23、應(yīng)的中間代碼語義程序需要生成相應(yīng)的中間代碼中間代碼如何表示？中間代碼如何表示？ 三地址代碼、抽象語法樹、三地址代碼、抽象語法樹、LLVM指令等指令等 語義變量和語義函數(shù)Zhou, Erqiang33School of Information and Software Engineering語義值的表示語義值的表示 X.type、X.category、X.address、常用語義變量常用語義變量1) 1) : : 語義變量，與終結(jié)符語義變量，與終結(jié)符i i相關(guān)聯(lián)相關(guān)聯(lián) 表示表示 i 對應(yīng)的標(biāo)識符字符串對應(yīng)的標(biāo)識符字符串i i 具體表示什么？具體表示什么？ id.id語義變量和語義函數(shù)

24、Zhou, Erqiang34School of Information and Software Engineering2) 2) E.place: : 語義變量，與語義變量，與非終結(jié)符非終結(jié)符E E相關(guān)聯(lián)相關(guān)聯(lián) 表示變量表示變量E 在在符號表的位置符號表的位置 或或整數(shù)編碼整數(shù)編碼( (臨時變量臨時變量) ) 采用采用變量名變量名或或臨時變量臨時變量名表示名表示產(chǎn)生式：產(chǎn)生式：EE1+E2 emit( E.place, E1.place, op, E2.place) 語句：語句： a = b + c 生成的三地址代碼：生成的三地址代碼： t1 = b + c； a = t1 ;表示非終結(jié)符

25、表示非終結(jié)符E E 對應(yīng)變量對應(yīng)變量 的的地址地址 及及 相應(yīng)的值相應(yīng)的值語義變量和語義函數(shù)Zhou, Erqiang35School of Information and Software Engineering3) 3) newtemp(): :語義函數(shù)語義函數(shù) 產(chǎn)生一個新的臨時變量產(chǎn)生一個新的臨時變量 返回其地址返回其地址 即：符號表的位置即：符號表的位置 采用臨時變量名表示：采用臨時變量名表示：t t1 1, t, t2 2, , 語義變量和語義函數(shù)Zhou, Erqiang36School of Information and Software Engineering4) 4) en

26、try( i ): : 語義函數(shù)語義函數(shù) 對對名字為名字為i i的變量查符號表，的變量查符號表， 返回返回i i在在符號表中的位置符號表中的位置 采用采用變量名變量名表示表示 未查到，未查到，則則 ？ 表示該變量沒有定義表示該變量沒有定義返回返回名字為名字為i i的變量的的變量的地址地址和和對應(yīng)的值對應(yīng)的值語義變量和語義函數(shù)Zhou, Erqiang37School of Information and Software Engineering5) 5) emit(RESULT, ARG1, oper, ARG2) 或或 emit(oper, ARG1, ARG2, RESULT) 語義函數(shù)語

27、義函數(shù) 產(chǎn)生四元式并填入四元式表中產(chǎn)生四元式并填入四元式表中 同時四元式編號增加同時四元式編號增加1 1簡單賦值語句的翻譯Zhou, Erqiang38School of Information and Software Engineering簡單賦值語句簡單賦值語句 只有簡單變量只有簡單變量 變量類型相同變量類型相同E id 歸約時，歸約時，i id d 的語義信息已經(jīng)獲取的語義信息已經(jīng)獲取 歸約后，歸約后，i id d 的語義需要傳遞給的語義需要傳遞給 E E E.place = entry( id.NAME ); 查找出錯？查找出錯？A id:=EE (E1)E -E1 E E1 op

28、E2E idop+ | - | * | /簡單賦值語句的翻譯Zhou, Erqiang39School of Information and Software EngineeringE id P = entry( ); if (P != 0) E.place = P; else error(); A id:=EE (E1)E -E1 E E1 op E2E idop+ | - | * | /簡單賦值語句的翻譯Zhou, Erqiang40School of Information and Software EngineeringE E1 op E2 E.place = newt

29、emp(); emit(E.place, E1.place, op, E2.place) E -E1 E.place = newtemp(); emit(E.place, uminus, E1.place) 為什么需要為什么需要newtemp()?newtemp()?A id:=EE (E1)E -E1 E E1 op E2E idop+ | - | * | /簡單賦值語句的翻譯Zhou, Erqiang41School of Information and Software EngineeringE (E1) E.place = E1.place;A id := E P = entry( i

30、) ; if ( P != 0 ) emit( P, =, E.place) else error(); A id:=EE (E1)E -E1 E E1 op E2E idop+ | - | * | /簡單賦值語句的翻譯示例Zhou, Erqiang42School of Information and Software Engineeringa:= -b*(c+d)的歸約過程的歸約過程 ida := -idb * (idc + idd) ida := -E1 * (idc + idd)* ida := E2 * (E3 + E4) ida := E2 * (E5) ida :=

31、E2 * E6 ida := E7 AA id:=EE (E1)E -E1 E E1 op E2E idop+ | - | * | /E -E1 E.place = newtemp(); emit(E.place, uminus, E1.place) + id)#簡單賦值語句的翻譯示例Zhou, Erqiang43School of Information and Software Engineering ia := -ib * (ic + id)# := -ib * (ic + id)#ia -ib * (ic + id)#ia:= ib * (ic + id)#ia:= - * (ic +

32、 id)#ia:= -ib * (ic + id)#ia:= -E1 # # # # b 語義棧語義棧符號棧符號棧輸入串輸入串E i P = entry( ); if (P != 0) E.place = P; else error(); * (ic + id)#ia:= E2 # t1 t1 = uminus b (ic + id)#ia:= E2* # t1 ic + id)#ia:= E2*( # t1 + id)#ia:= E2*(ic # t1 #ia:= E2*(E3 # t1 c id)#ia:= E2*(E3+ # t1 c )#ia:= E2*(E3+id #

33、t1 c 1)i i 表示表示 idid簡單賦值語句的翻譯示例Zhou, Erqiang44School of Information and Software Engineering語義棧語義棧符號棧符號棧輸入串輸入串t1 = uminus b )#ia:= E2*(E3+id # t1 c )#ia:= E2*(E3+E4 # t1 c d )#ia:= E2*(E5 # t1 t2E E1 op E2 E.place = newtemp(); emit(E.place, E1.place, op, E2.place) t2 = c + d #ia:= E2*(E5) # t1 t2 E

34、(E1) E.place = E1.place; #ia:= E2*E6 # t1 t2 #ia:= E7 # t3t3 = t1 * t2 A i := E P = entry( ) ; if ( P != 0 ) emit( P, =, E.place) else error(); #A #aa = t3 2)3)4)1)簡單賦值語句的翻譯Zhou, Erqiang45School of Information and Software Engineering簡單賦值語句簡單賦值語句 只有簡單變量只有簡單變量 變量類型相同變量類型相同變量類型不同呢？變量類型不同呢？ 整型與實(shí)型

35、運(yùn)算整型與實(shí)型運(yùn)算 允許？結(jié)果類型？允許？結(jié)果類型？簡單賦值語句的翻譯Zhou, Erqiang46School of Information and Software Engineering類型轉(zhuǎn)換方法類型轉(zhuǎn)換方法(整型轉(zhuǎn)實(shí)型整型轉(zhuǎn)實(shí)型) 對表達(dá)式對表達(dá)式 E E 增加語義屬性增加語義屬性E.typeE.type 引進(jìn)類型轉(zhuǎn)換指令引進(jìn)類型轉(zhuǎn)換指令(t, i2r, x) i i2 2r r為一元運(yùn)算為一元運(yùn)算 x x為整型值為整型值 t t為轉(zhuǎn)換后實(shí)型值為轉(zhuǎn)換后實(shí)型值 修改修改EEE E1 1 op E op E2 2的語義子程序的語義子程序簡單賦值語句的翻譯Zhou, Erqiang47Sc

36、hool of Information and Software EngineeringE E1 op E2 t1 = newtemp(); E.Type = REAL; /默認(rèn)類型默認(rèn)類型 if (E1.Type = INT & E2.Type = INT) emit(E.place, E1.place, opi, E2.place); E.Type = INT; else if(E1.Type = REAL & E2.Type = REAL) emit(E.place, E1.place, opr, E2.place);enum c_type REAL, INT, 簡單賦值語句的翻譯Zho

37、u, Erqiang48School of Information and Software Engineering else if(E1.Type = INT & E2.Type = REAL) t2 = newtemp(); emit( t2, itr, E1.place); emit( t1, t2, opr, E2.place); else if(E1.Type = REAL & E2.Type = INT) t2 = newtemp(); emit( t2, itr, E2.place); emit( t1, E2.place, opr, t2); else error(); E.P

38、lace = t1; 簡單賦值語句的翻譯Zhou, Erqiang49School of Information and Software Engineering問題：問題： 變量的信息變量的信息何時何時記錄到符號表？記錄到符號表？ 處理執(zhí)行語句？處理執(zhí)行語句？ 處理說明語句？處理說明語句？ 記錄屬性信息（填表）記錄屬性信息（填表）簡單說明語句的翻譯Zhou, Erqiang50School of Information and Software Engineering簡單說明語句的文法簡單說明語句的文法 DD1;D2id:T T integerrealarraynum of T1T1非終結(jié)符

39、非終結(jié)符D D產(chǎn)生一系列產(chǎn)生一系列 i id d:T:T形式的說明語句形式的說明語句簡單說明語句的翻譯Zhou, Erqiang51School of Information and Software EngineeringDD1;D2id:TT integerrealarraynum of T1 T1翻譯的主要工作翻譯的主要工作 “不產(chǎn)生不產(chǎn)生”中間代碼中間代碼 負(fù)責(zé)填表負(fù)責(zé)填表 填表的內(nèi)容？填表的內(nèi)容？ 類型類型 簡單說明語句的翻譯Zhou, Erqiang52School of Information and Software Engineering關(guān)于關(guān)于存儲位置存儲位置 變量的存放區(qū)

40、域變量的存放區(qū)域全局變量、靜態(tài)全局變量、靜態(tài)局部變量全局變量、靜態(tài)全局變量、靜態(tài)局部變量 靜態(tài)存儲區(qū)靜態(tài)存儲區(qū) 如果沒有手工初始化，則由編譯器初始化為如果沒有手工初始化，則由編譯器初始化為0 0局部變量局部變量 棧區(qū)；如不初始化，值不可知棧區(qū)；如不初始化，值不可知 函數(shù)被調(diào)用時，在棧區(qū)分配內(nèi)存，返回后消函數(shù)被調(diào)用時，在棧區(qū)分配內(nèi)存，返回后消失失簡單說明語句的翻譯Zhou, Erqiang53School of Information and Software Engineering函數(shù)棧幀函數(shù)棧幀(stack frame)(stack frame) 函數(shù)的每次執(zhí)行都獨(dú)立的對應(yīng)一個棧函數(shù)的每次執(zhí)

41、行都獨(dú)立的對應(yīng)一個棧 當(dāng)前被執(zhí)行函數(shù)對應(yīng)的棧在當(dāng)前被執(zhí)行函數(shù)對應(yīng)的棧在棧幀的頂部棧幀的頂部 通過通過基址指針基址指針 與與 變量的偏移變量的偏移訪問臨時變量訪問臨時變量 void MyFunction()void MyFunction() int a, b, c; int a, b, c; a = 10; a = 10; b = 5; b = 5; c = 2; c = 2;_MyFunction:_MyFunction: push push ebp ; ebp ; 保存保存“基址指針基址指針” ebpebp mov mov ebp, esp ; ebp, esp ; “基址指針基址指針” e

42、bpebp指向棧頂指向棧頂 sub sub esp, 12 ; esp, 12 ; 在棧中為臨時變量分配空間在棧中為臨時變量分配空間mov ebp - 4, 10 ; mov ebp - 4, 10 ; 將將1010保存至變量保存至變量 a amov ebp - 8, 5 ; location of bmov ebp - 8, 5 ; location of bmov ebp - 12, 2 ; location of cmov ebp - 12, 2 ; location of c簡單說明語句的翻譯Zhou, Erqiang54School of Information and Softwa

43、re Engineering函數(shù)每次運(yùn)行，局部變量的函數(shù)每次運(yùn)行，局部變量的地址地址如何確定？如何確定？ 起始地址：起始地址：offsetoffset，針對當(dāng)前棧，初值為，針對當(dāng)前棧，初值為0 0 變量的變量的“寬度寬度”：widthwidth，因類型而定，因類型而定下一個變量地址：下一個變量地址：offset+widthoffset+width簡單說明語句的翻譯Zhou, Erqiang55School of Information and Software Engineeringoffsetoffset初始值為初始值為0 0 何時進(jìn)行初始化？何時進(jìn)行初始化？DD1;D2i:TT integ

44、errealarraynum of T1 T1每個函數(shù)運(yùn)行時有自己棧幀每個函數(shù)運(yùn)行時有自己棧幀 對每個函數(shù)的對每個函數(shù)的變量聲明時變量聲明時進(jìn)行初始化進(jìn)行初始化 如何體現(xiàn)在文法上？如何體現(xiàn)在文法上？int fun1() a: int; b: real; c: int;int fun2() d: int; e: real; f: int;簡單說明語句的翻譯方案Zhou, Erqiang56School of Information and Software Engineering文法改造文法改造 SMD M DD1;D2i:T T integerrealarraynum of T1 T1語義子程

45、序語義子程序 SMD M offset = 0;簡單說明語句的翻譯方案Zhou, Erqiang57School of Information and Software EngineeringDD1;D2i:T DD1;D2 Di:T enter(,T.type,offset); offset:=offset+T.width T integerrealarraynum of T1 T1 Tinteger T.type:=integer; T.width:=2 Treal T.type:=real; T.width:=4 enter( Name, Type, Offset ) 將將語

46、義信息語義信息記入符號表記入符號表簡單說明語句的翻譯方案Zhou, Erqiang58School of Information and Software EngineeringT integerrealarraynum of T1 T1 Tarraynum of T1 T.type := (array, num.val, T1.type); T.width:=num.val * T1.width; TT1 T.type:= (pointer, T1.type ); T.width:=4 ; 常見說明語句的翻譯(一)Zhou, Erqiang59School of Information an

47、d Software Engineering說明語句的形式說明語句的形式 int a, b, c ; real d, e, f ;文法文法 D integer namelist ;real namelist ; namelist namelist, ii改寫改寫: S MD M DD,iinteger ireal i常見說明語句的翻譯(二)Zhou, Erqiang60School of Information and Software Engineering說明語句的形式說明語句的形式 a, b, c : int; d, e, f: real;文法文法 Dnamelist integer ;

48、 | namelist real ; namelistnamelist, i | i需引進(jìn)語義變量需引進(jìn)語義變量 隊(duì)列隊(duì)列 namelist.QUEUE 存放變量名存放變量名對控制語句的翻譯Zhou, Erqiang61School of Information and Software Engineering三種語句級控制結(jié)構(gòu)：三種語句級控制結(jié)構(gòu)： 順序、選擇、重復(fù)順序、選擇、重復(fù)順序：指令指針自動加一順序：指令指針自動加一 以獲取下一條指令以獲取下一條指令選擇和重復(fù)：顯示修改指令指針的值選擇和重復(fù)：顯示修改指令指針的值 以獲取下一條指令以獲取下一條指令對控制語句的翻譯Zhou, Erqia

49、ng62School of Information and Software Engineering常見控制語句常見控制語句 條件轉(zhuǎn)移條件轉(zhuǎn)移 “if B then S” “if B then S1 else S2” 循環(huán)循環(huán) while語句語句 for語句語句控制語句中簡單布爾表達(dá)式的翻譯Zhou, Erqiang63School of Information and Software Engineering控制語句中的控制語句中的布爾表達(dá)式布爾表達(dá)式 if B then S if B then S else S while B do S是是 選擇選擇語句語句 和和 迭代迭代語句語句 的早期

50、句柄的早期句柄控制語句中簡單布爾表達(dá)式的翻譯Zhou, Erqiang64School of Information and Software Engineering文法及其分析文法及其分析 Bi （i為為true、false或邏輯變量）或邏輯變量） Bi1 rop i2 (i 為變量或者常量，為變量或者常量，rop為為關(guān)系運(yùn)算關(guān)系運(yùn)算符符)表達(dá)式為真或假，分別轉(zhuǎn)移到不同的地址表達(dá)式為真或假，分別轉(zhuǎn)移到不同的地址 轉(zhuǎn)移到轉(zhuǎn)移到“真真出口出口” 和和“假假出口出口” 分別對應(yīng)相應(yīng)的分別對應(yīng)相應(yīng)的“轉(zhuǎn)移代碼轉(zhuǎn)移代碼” 歸約時產(chǎn)生兩個三地址代碼歸約時產(chǎn)生兩個三地址代碼控制語句中簡單布爾表達(dá)式的翻譯Z

51、hou, Erqiang65School of Information and Software Engineering涉及到兩類地址：涉及到兩類地址： 本身地址本身地址 和和 目標(biāo)地址目標(biāo)地址本身的地址本身的地址 產(chǎn)生的兩個產(chǎn)生的兩個“轉(zhuǎn)移指令轉(zhuǎn)移指令”的地址（編號）的地址（編號）目標(biāo)地址目標(biāo)地址 轉(zhuǎn)移指令的一部分轉(zhuǎn)移指令的一部分 何時能確定目標(biāo)地址？何時能確定目標(biāo)地址？ 布爾表達(dá)式歸約時能否確定下來？布爾表達(dá)式歸約時能否確定下來？ YN控制語句中簡單布爾表達(dá)式的翻譯Zhou, Erqiang66School of Information and Software EngineeringBS

52、if B then S1 else S2if B then SBS1S2YN布爾表達(dá)式歸約到布爾表達(dá)式歸約到B時還未處理時還未處理S的代碼的代碼歸約時目標(biāo)地址歸約時目標(biāo)地址未知未知 需要記錄轉(zhuǎn)移指令的地址需要記錄轉(zhuǎn)移指令的地址 以便回填目標(biāo)地址以便回填目標(biāo)地址控制語句中簡單布爾表達(dá)式的翻譯Zhou, Erqiang67School of Information and Software Engineering歸約時的動作歸約時的動作 1）產(chǎn)生兩個轉(zhuǎn)移指令）產(chǎn)生兩個轉(zhuǎn)移指令 真真出口出口 和和 假假出口出口 2）記錄兩轉(zhuǎn)移指令的地址）記錄兩轉(zhuǎn)移指令的地址 引入兩個語義變量引入兩個語義變量 B.T

53、記錄真出口的地址記錄真出口的地址 B.F記錄假出口的地址記錄假出口的地址控制語句中簡單布爾表達(dá)式的翻譯Zhou, Erqiang68School of Information and Software Engineering翻譯方案翻譯方案B i 轉(zhuǎn)移指令：轉(zhuǎn)移指令： ip: if b goto 0; ip+1: goto 0; 記錄轉(zhuǎn)移指令的地址，以便回填目標(biāo)地址記錄轉(zhuǎn)移指令的地址，以便回填目標(biāo)地址 B.T = ip; B.F = ip+1; 控制語句中簡單布爾表達(dá)式的翻譯Zhou, Erqiang69School of Information and Software Engineerin

54、g翻譯方案翻譯方案B i B.T = ip; B.F = ip+1; emit( if b goto 0 ); emit( goto 0 ); 控制語句中簡單布爾表達(dá)式的翻譯Zhou, Erqiang70School of Information and Software Engineering翻譯方案翻譯方案B i1 rop i2 B.T = ip; B.F = ip+1; emit( if i1 rop i2 goto 0); emit( goto 0 ); 選擇語句的翻譯Zhou, Erqiang71School of Information and Software Engineeri

55、ng文法文法 S if B then S1 S if B then S1 else S2YNBSBS1S2YN選擇語句的翻譯Zhou, Erqiang72School of Information and Software EngineeringS if B then S歸約到歸約到B B時，產(chǎn)生兩條指令時，產(chǎn)生兩條指令 B.T: if B goto 0; B.F: goto 0;問題：何時回填這兩條指令？問題：何時回填這兩條指令？ B.T: S的第一條指令地址確定時的第一條指令地址確定時 B.F: “S的最后一條指令地址的最后一條指令地址確定確定時時”YNBS選擇語句的翻譯Zhou, Erq

56、iang73School of Information and Software EngineeringS if B then S1中間代碼結(jié)構(gòu)中間代碼結(jié)構(gòu) B.T: if B goto 0 B.F : goto 0 /語句語句S S1 1對應(yīng)的中間代碼對應(yīng)的中間代碼YNBSB_TrueB_True:after_S1:S_EndB.F 指令中的目標(biāo)地址指令中的目標(biāo)地址一定是一定是S1之后的代碼嗎？之后的代碼嗎？選擇語句的翻譯Zhou, Erqiang74School of Information and Software Engineering B.T: if B goto 0 B.F : g

57、oto 0 /語句語句S S1 1對應(yīng)的中間代碼對應(yīng)的中間代碼 /語句語句S S2 2對應(yīng)的中間代碼對應(yīng)的中間代碼B_True:S2_First:S2_FirstB_Truegoto S_Endif B1 then S1 else S2 after_S2:S_End 一定是一定是S2之后的代碼嗎？之后的代碼嗎？選擇語句的翻譯Zhou, Erqiang75School of Information and Software Engineeringif B1 then if B2 then S1 else S2 else S3if B1 then if B2 then S1 else S2 els

58、e S3S1之后的之后的goto S_End 未必指向未必指向S2之后的代碼之后的代碼這又意味著什么呢？這又意味著什么呢？ 在在“控制語句控制語句”歸約到歸約到S S后后 部分部分指令中的指令中的最終轉(zhuǎn)移地址最終轉(zhuǎn)移地址仍不確定仍不確定 選擇語句的翻譯Zhou, Erqiang76School of Information and Software Engineering S if B then S1 S if B then S1 else S2引入語義變量引入語義變量S.ChainS.Chain 記錄條件語句歸約后記錄條件語句歸約后未完成指令未完成指令的地址的地址 未完成指令缺少未完成指令缺

59、少哪個哪個地址？地址？ S S1 1和和S S2 2都有相應(yīng)的都有相應(yīng)的 未完成指令未完成指令“鏈鏈”翻譯的關(guān)鍵是如何處理這些鏈翻譯的關(guān)鍵是如何處理這些鏈 處理方法？處理方法？選擇語句的翻譯Zhou, Erqiang77School of Information and Software Engineering多個鏈的多個鏈的轉(zhuǎn)移地址相同轉(zhuǎn)移地址相同 引入語義函數(shù)引入語義函數(shù) merge(P1, P2) 合并兩個鏈為一個，返回新鏈合并兩個鏈為一個，返回新鏈P P2 2當(dāng)當(dāng)轉(zhuǎn)移地址確定轉(zhuǎn)移地址確定后，回填轉(zhuǎn)移指令后，回填轉(zhuǎn)移指令 引入語義函數(shù)引入語義函數(shù)backpatch(P, address)

60、 將將address 回填到鏈回填到鏈P P中的所有指令中的所有指令選擇語句的翻譯Zhou, Erqiang78School of Information and Software Engineering S if B then S1 B B為假為假BS1?B B為真為真S S1 1的第一條指令編號的第一條指令編號用以回填真出口用以回填真出口需要拉鏈需要拉鏈選擇語句的翻譯Zhou, Erqiang79School of Information and Software Engineering if B then if B2 then S1 B B2 2為假為假B B2 2為真為真B B1 1為