編譯原理中間代碼生成.ppt

machunyan 西北工業(yè)大學軟件與微電子學院 1 詞法分析程序 語法分析程序 語義分析程序 中間代碼生成 代碼優(yōu)化程序 目標代碼生成 源代碼 目標代碼 常數(shù)表 符號表 錯誤處理器 編譯器邏輯結(jié)構(gòu)的組成 machunyan 西北工業(yè)大學軟件與微電子學院 2 第6章代碼生成 6 1中間代碼概覽 6 2基本的代碼生成技術(shù) 6 3數(shù)據(jù)結(jié)構(gòu)引用的代碼生成 6 4控制語句和邏輯表達式的代碼生成 6 5過程和函數(shù)調(diào)用的代碼生成 machunyan 西北工業(yè)大學軟件與微電子學院 3 6 1中間代碼概覽 編譯程序的任務(wù)是把源程序翻譯成等價的目標程序 所謂等價 是指兩者之間的語法結(jié)構(gòu)不同 但它們表述的功能和結(jié)果是完全相同的 即語義相同 中間代碼 也稱中間語言 是復雜性介于源程序和目標程序之間的一種機內(nèi)表達形式 它是編譯程序產(chǎn)生的中間臨時結(jié)果 中間代碼程序同源程序和目標程序的關(guān)系也同樣是等價的 即結(jié)構(gòu)不同 但語義相同 machunyan 西北工業(yè)大學軟件與微電子學院 4 盡管源程序可以直接翻譯成目標語言 但使用與機器無關(guān)的中間代碼形式具有如下優(yōu)點 使編譯程序的算法清晰 便于分工 修改 維護和移植等 中間代碼使編譯器更容易重定向 不同機器上的編譯器可以在已有前端的基礎(chǔ)上附加一個適合這這臺新機器的后端來生成 可以在中間代碼上進行與機器無關(guān)的代碼優(yōu)化 優(yōu)化過程實際上是對程序的操作過程 對程序進行操作必須首先把程序轉(zhuǎn)換成其結(jié)構(gòu)便于操作的數(shù)據(jù) 而中間代碼正是為此設(shè)計的一種程序的數(shù)據(jù)結(jié)構(gòu)表示 兩種常見的中間代碼的普遍形式 三地址碼和P 代碼 6 1中間代碼概覽 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 5 6 1 1三地址碼 6 1 2用于實現(xiàn)三地址碼的數(shù)據(jù)結(jié)構(gòu) 6 1 3P 代碼 6 1中間代碼概覽 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 6 6 1 1三地址碼 續(xù) 相應(yīng)的三地址碼為 t1 2 at2 b 3t3 t1 t2 三地址碼是下列一般形式的語句序列 x yopz其中 x y及z是名字 常量或編譯器生成的臨時變量 op代表任何操作符 例6 1 算術(shù)表達式的2 a b 3 語法樹如下 machunyan 西北工業(yè)大學軟件與微電子學院 7 6 1 1三地址碼 續(xù) 三地址碼是語法樹的從左到右的線性化表示 三地址碼的生成所依據(jù)的是語言的語義規(guī)則 為適應(yīng)標準程序語言的使用結(jié)構(gòu) 在具體為每個結(jié)構(gòu)生成三地址碼時 必須為每個結(jié)構(gòu)改變?nèi)刂反a的形式 例如 為了生成數(shù)組引用的三地址碼可以引入兩個新的三地址指令 獲取數(shù)組元素值的三地址指令 t2 a t1 給數(shù)組元素賦值的三地址指令 a t2 t1 machunyan 西北工業(yè)大學軟件與微電子學院 8 6 1 1三地址碼 6 1 2用于實現(xiàn)三地址碼的數(shù)據(jù)結(jié)構(gòu) 6 1 3P 代碼 6 1中間代碼概覽 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 9 6 1 2用于實現(xiàn)三地址碼的數(shù)據(jù)結(jié)構(gòu) 三地址碼是中間代碼的一種抽象形式 在編譯器中 這些語句可以以帶有操作符和操作數(shù)域的記錄來實現(xiàn) 三地址碼常見的實現(xiàn)有四元式和三元式 四元式是帶有四個域的記錄結(jié)構(gòu) 即op arg1 arg2 result 可以寫成 op arg1 arg2 result arg1 arg2及result域的內(nèi)容正常情況下是指這些域所代表的名字在符號表表項的指針 臨時名字result在生成時一定要被填入符號表 四元式之間的聯(lián)系是通過臨時變量實現(xiàn)的 便于優(yōu)化處理 machunyan 西北工業(yè)大學軟件與微電子學院 10 三元式 為了避免臨時名字被填入符號表中 可以通過臨時值的語句位置來引用臨時變量 可以用只包含三個域的記錄表示 即用三元式來表示 三元式之間的聯(lián)系是通過三元式編號實現(xiàn)的 對三元式表變動較為困難 花費較大的代價 6 1 2用于實現(xiàn)三地址碼的數(shù)據(jù)結(jié)構(gòu) 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 11 例6 2 6 1中算術(shù)表達式 2 a b 3 的三地址碼 t1 2 at2 b 3t3 t1 t2四元式實現(xiàn) 2 a t1 b 3 t2 t1 t2 t3 三元式實現(xiàn) 0 2 a 1 b 3 2 0 1 6 1 2用于實現(xiàn)三地址碼的數(shù)據(jù)結(jié)構(gòu) 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 12 6 1 1三地址碼 6 1 2用于實現(xiàn)三地址碼的數(shù)據(jù)結(jié)構(gòu) 6 1 3P 代碼 6 1中間代碼概覽 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 13 6 1 3P 代碼 在20世紀70年代和60年代早期 P 代碼作為由許多Pascal編譯器產(chǎn)生的標準目標匯編代碼被設(shè)計成稱作P 機器 P machine 的假想棧機器 Stackmachine 的實際代碼 P 機器在不同的平臺上由不同的解釋器實現(xiàn) 該思想使得pascal編譯器變得容易移植 只需對新平臺重寫P 機器解釋器即可 machunyan 西北工業(yè)大學軟件與微電子學院 14 例6 3 算術(shù)表達式 2 a b 3 的P 代碼如下 ldc2 loadconstant2loda loadvalueofvariableampi integermultiplicationlodb loadvalueofvariablebldc3 loadconstant3sbi integersubtractionadi integeraddition 6 1 3P 代碼 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 15 6 1中間代碼概覽 6 2基本的代碼生成技術(shù) 6 3數(shù)據(jù)結(jié)構(gòu)引用的代碼生成 6 4控制語句和邏輯表達式的代碼生成 6 5過程和函數(shù)調(diào)用的代碼生成 第6章代碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 16 6 2基本的代碼生成技術(shù) 6 2 1作為合成屬性的中間代碼或目標代碼生成方法 6 2 2實際的代碼生成方法 6 2 3從中間代碼生成目標代碼 machunyan 西北工業(yè)大學軟件與微電子學院 17 6 2 1作為合成屬性的中間代碼或目標代碼生成方法 中間代碼生成 或直接目標代碼生成 可被看作屬性計算 這類似于第5章中研究的許多屬性問題 假如將生成的代碼看作一個字符串屬性 每條指令用換行符分隔 這個代碼就成了一個合成屬性并能用屬性文法定義 并且能在語法分析期間直接生成或者通過語法樹的后序遍歷生成 machunyan 西北工業(yè)大學軟件與微電子學院 18 例6 4 為表達式文法exp id exp aexpaexp aexp factor factorfactor exp num id寫出計算三地址碼的屬性文法 tacode屬性 表示文法的三地址碼屬性 name屬性 表示參與三地址碼運算的標示符 常量或編譯器生成的臨時變量 用 表示所連的符號串換行表示 表示相連的符號串之間用空格相隔 6 2 1作為合成屬性的中間代碼或目標代碼生成方法 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 19 exp tacode t1 x 3x t1 exp tacode t1 x 3 6 2 1作為合成屬性的中間代碼或目標代碼生成方法 續(xù) 表達式x x 3的tacode屬性計算 machunyan 西北工業(yè)大學軟件與微電子學院 20 exp1 id exp2 exp aexp 文法規(guī)則 語義規(guī)則 exp1 name exp2 name exp1 tacode exp2 tacode id strval exp2 name exp name aexp name exp tacode aexp tacode 6 2 1作為合成屬性的中間代碼或目標代碼生成方法 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 21 aexp1 aexp2 factor aexp1 name newtemp aexp1 tacode aexp2 tacode factor tacode aexp1 name aexp2 name factor name 6 2 1作為合成屬性的中間代碼或目標代碼生成方法 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 22 aexp factor factor exp factor num factor id 文法規(guī)則 語義規(guī)則 aexp name factor name aexp tacode factor tacode factor name exp name factor tacode exp tacode factor name num strval factor tacode factor name id strval factor tacode 6 2 1作為合成屬性的中間代碼或目標代碼生成方法 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 23 exp tacode t1 x 3x t1 根據(jù)上述屬性文法 表達式 x x 3 4的tacode屬性計算如右 factor exp exp aexp factor factor num 3 aexp factor exp factor aexp id x id x num 4 exp tacode t1 x 3 aexp tacode t1 x 3x t1t2 t1 4 6 2 1作為合成屬性的中間代碼或目標代碼生成方法 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 24 其中語義動作使用函數(shù)emit 將三地址語句輸出到文件中 為其產(chǎn)生三地址碼的翻譯模式如下 對于表達式文法exp id exp aexpaexp aexp factor factorfactor exp num id 對于將文法符號同屬性相關(guān)聯(lián)的上下文無關(guān)文法 也可以將語義動作 包含在 中 插入產(chǎn)生式右部的某個位置 6 2 1作為合成屬性的中間代碼或目標代碼生成方法 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 25 exp1 id exp2 exp aexp aexp1 aexp2 factor exp1 name exp2 nameemit id strval exp2 name exp name aexp name aexp1 name newtemp emit aexp1 name aexp2 name factor name 6 2 1作為合成屬性的中間代碼或目標代碼生成方法 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 26 aexp factor factor exp factor num factor id factor name exp name aexp name factor name factor name id strval factor name num strval 6 2 1作為合成屬性的中間代碼或目標代碼生成方法 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 27 為表達式文法exp exp term exp term termterm term factor factorfactor exp number寫出計算三地址碼的屬性文法 tacode屬性 表示文法的三地址碼屬性name屬性 表示相應(yīng)的標示符 常量或編譯器生成的臨時變量 6 2 1作為合成屬性的中間代碼或目標代碼生成方法 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 28 6 2 1作為合成屬性的中間代碼或目標代碼生成方法 6 2 2實際的代碼生成方法 6 2 3從中間代碼生成目標代碼 自學內(nèi)容 6 2基本的代碼生成技術(shù) machunyan 西北工業(yè)大學軟件與微電子學院 29 6 2 2實際的代碼生成方法 實際代碼生成的基本算法由下面的遞歸過程描述 用于二叉樹 但容易將其推廣到節(jié)點子樹多于2的情況 voidgenCode T treenode ifTisnotnil generatecodetoprepareforcodeofleftchildofT genCode leftchildofT generatecodetoprepareforcodeofrightchildofT genCode rightchildofT generatecodetoimplementtheactionofT 注 中間代碼生成所依據(jù)的是語言的語義規(guī)則 即在遍歷樹生成代碼之前 應(yīng)該首先規(guī)定各節(jié)點對應(yīng)代碼生成的語義規(guī)則 machunyan 西北工業(yè)大學軟件與微電子學院 30 對于上述簡單表達式文法exp id exp aexpaexp aexp factor factorfactor exp num id考慮其三地址碼的代碼生成過程實現(xiàn) 6 2 2實際的代碼生成方法 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 31 例6 5 表達式 x x 3 4相應(yīng)的語法樹如下 x 4 x 3 生成的相應(yīng)的三地碼如下 t1 x 3x t1t2 t1 4 6 2 2實際的代碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 32 typedefenum Plus Assign Optype typedefenum OpKind ConstKind IdKind NodeKind typedefstructstreenode NodeKindkind Optypeop structstreenode lchild rchild char strval STreeNode typedefSTreeNode SyntaxTree 簡單算術(shù)表達式抽象語法樹的C語言定義 每個節(jié)點都有個名字屬性 用該節(jié)點的strval域來存儲其名字 假設(shè)數(shù)字也當作字符串保存在strval域中 6 2 2實際的代碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 33 leftoperand rightoperand 上述表達式的語法樹結(jié)構(gòu)和節(jié)點中間代碼的生成規(guī)則如下 t1 t leftchild strval t rightchild strval t strval t1 6 2 2實際的代碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 34 leftoperand t strval t leftchild strval 6 2 2實際的代碼生成 續(xù) t strval t leftchild strval 生成的三地址碼 賦值運算 machunyan 西北工業(yè)大學軟件與微電子學院 35 中間代碼生成的輔助函數(shù) emit 函數(shù)emit 將三地址語句輸出到文件中 Newtemp 函數(shù)Newtemp 產(chǎn)生一個臨時名字系列t1 t2 t3 6 2 2實際的代碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 36 VoidgenCode SyntaxTreet if t NULL switch t kind caseOpKind switch t op casePlus genCode t lchild genCode t rchild t strval newtemp emit t strval t lchild strval t rchild strval break 簡單算術(shù)表達式的三地址碼生成過程的實現(xiàn) 6 2 2實際的代碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 37 caseAssign genCode t lchild emit t strval t lchild strval t strval t lchild strval break default emit error break 6 2 2實際的代碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 38 break caseConstKind break caseIdKind break default emit error break 6 2 2實際的代碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 39 x 4 x 3 根據(jù)上述三地址碼的生成過程 表達式 x x 3 4相應(yīng)的三地碼如下 t1 x 3x t1t2 t1 4 6 2 2實際的代碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 40 6 2基本的代碼生成技術(shù) 6 2 1作為合成屬性的中間代碼或目標代碼生成方法 6 2 2實際的代碼生成方法 6 2 3從中間代碼生成目標代碼 自學內(nèi)容 machunyan 西北工業(yè)大學軟件與微電子學院 41 6 2 3從中間代碼生成目標代碼 續(xù) 如果編譯器從一棵語法樹產(chǎn)生了中間代碼 下一步就是產(chǎn)生最后的目標代碼 通常在對中間代碼的進一步處理之后 目標代碼的生成相當復雜 特別是當中間代碼高度抽象 且只包含了很少或根本沒包含目標機器和運行時環(huán)境的信息 在上述情況下 目標代碼的生成必須支持變量和臨時變量的實際定位 并增加支持運行時環(huán)境所必需的代碼 現(xiàn)在僅討論這個處理的通用技術(shù) machunyan 西北工業(yè)大學軟件與微電子學院 42 通常 從中間代碼到目標代碼的生成涉及了兩個標準技術(shù) 宏擴展 macroexpansion 和靜態(tài)模擬 宏擴展涉及到用一系列等效的目標代碼指令代替每一種中間代碼指令 靜態(tài)模擬包括中間代碼效果的直線模擬和生成匹配這些效果的目標代碼 6 2 3從中間代碼生成目標代碼 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 43 用宏擴展來完成將三地址碼到P 代碼的翻譯 例如一個三地址指令a b c可翻譯成如下的P 代碼指令序列 ldaalodb orldcbifbisaconstlodc orldccifcisaconstadisto 6 2 3從中間代碼生成目標代碼 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 44 用靜態(tài)模擬來完成將P 代碼到三地址碼的翻譯 例如 表達式 x x 3 4的P 代碼如下 ldaxlodxldc3adistnldc4adi執(zhí)行一個P 機器棧的靜態(tài)模擬用以發(fā)現(xiàn)P 代碼的三地址碼等效式 6 2 3從中間代碼生成目標代碼 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 45 3 棧頂 x x的地址 現(xiàn)在當處理adi操作時 產(chǎn)生三地址指令t1 x 3棧的狀態(tài)為 假定前三條P 代碼語句執(zhí)行后 棧的狀態(tài)如下 棧頂 t1 x的地址 6 2 3從中間代碼生成目標代碼 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 46 下一條stn指令翻譯為如下的三地址指令 x t1棧變成 下一條指令ldc4將常量4壓入棧 最后指令adi生成三地址指令 t2 t1 4棧變成 6 2 3從中間代碼生成目標代碼 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 47 第6章代碼生成 6 1中間代碼概覽 6 2基本的代碼生成技術(shù) 6 3數(shù)據(jù)結(jié)構(gòu)引用的中間代碼生成 6 4控制語句和邏輯表達式的中間代碼生成 6 5過程和函數(shù)調(diào)用的中間代碼生成 machunyan 西北工業(yè)大學軟件與微電子學院 48 6 3數(shù)據(jù)結(jié)構(gòu)引用的中間代碼生成 6 3 1地址計算 6 3 2數(shù)組引用的三地址碼生成 6 3 3記錄結(jié)構(gòu)和指針引用 自學內(nèi)容 machunyan 西北工業(yè)大學軟件與微電子學院 49 6 3 1地址計算 為了定位實際地址 對于數(shù)組 記錄域和指針引用的中間代碼生成通常需要執(zhí)行地址計算 引入用于地址計算的三地址碼 假設(shè)把2存放在變量x所在位置加上10個字節(jié)的地址處 用三地址碼表示如下 t1 x 10 t1 2 machunyan 西北工業(yè)大學軟件與微電子學院 50 6 3數(shù)據(jù)結(jié)構(gòu)引用的代碼生成 6 3 1地址計算 6 3 2數(shù)組引用的三地址碼生成 6 3 3記錄結(jié)構(gòu)和指針引用 自學內(nèi)容 machunyan 西北工業(yè)大學軟件與微電子學院 51 6 3 2數(shù)組引用的三地址碼生成 例6 6 C數(shù)組引用a i 的地址是 base address a i sizeof int 賦值語句 t2 a t1 翻譯成如下的三地址碼 t3 t1 elem size a t4 a t3t2 t4 賦值語句 a t2 t1翻譯成如下的三地址碼 t3 t2 elem size a t4 a t3 t4 t1 返回數(shù)組元素所占字節(jié)數(shù) machunyan 西北工業(yè)大學軟件與微電子學院 52 考慮一維數(shù)組引用的簡單算術(shù)表達式文法exp subs exp aexpaexp aexp factor factorfactor exp num subssubs id id exp 對應(yīng)的三地址碼的生成過程實現(xiàn) 6 3 2數(shù)組引用的三地址碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 53 表達式 a i 1 2 a j 的語法樹結(jié)構(gòu)如下 i 1 a 2 a j 6 3 2數(shù)組引用的三地址碼生成 續(xù) t1 i 1 t2 t1 elem size a t3 a t2 t4 j elem size a t5 a t4 t6 t5 2 t3 2 machunyan 西北工業(yè)大學軟件與微電子學院 54 typedefenum OpKind ConstKind IdKind NodeKind typedefenum Plus Assign Subs Optype typedefstructstreenode NodeKindkind Optypeop structstreenode lchild rchild char strval STreeNode typedefSTreeNode SyntaxTree 其語法樹的c語言定義如下 6 3 2數(shù)組引用的三地址碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 55 leftoperand rightoperand t1 t leftchild strval t rightchild strvalt strval t1t leftchild strval t rightchild strvalt strval t rightchild strval 6 3 2數(shù)組引用的三地址碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 56 t1 t lchild strval elem size t strval t2 t strval t1t strval t2 subs id exp 6 3 2數(shù)組引用的三地址碼生成 續(xù) id 根節(jié)點進一步參與運算的名字屬性 machunyan 西北工業(yè)大學軟件與微電子學院 57 表達式 a i 1 2 a j 的語法樹結(jié)構(gòu)如下 i 1 a 2 a j t1 i 1 t2 t1 elem size a t3 a t2 t4 j elem size a t5 a t4 t6 t5 2 t3 2 6 3 2數(shù)組引用的三地址碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 58 數(shù)組引用的算術(shù)表達式文法對應(yīng)的三地址碼的生成過程實現(xiàn) VoidgenCode SyntaxTreet if t NULL switch t kind caseOpKind switch t op casePlus genCode t lchild genCode t rchild t strval newtemp emit t strval t lchild strval t rchild strval break 6 3 2數(shù)組引用的三地址碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 59 caseAssign genCode t lchild genCode t rchild emit t lchild strval t rchild strval t strval t rchild strval break 6 3 2數(shù)組引用的三地址碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 60 caseSubs genCode t lchild temp1 newtemp emit temp1 t lchild strval elem size t strval temp2 newtemp emit temp2 6 3 2數(shù)組引用的三地址碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 61 break caseConstKind break caseIdKind break default emit error break 6 3 2數(shù)組引用的三地址碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 62 根據(jù)上述三地址碼的生成過程 表達式 a i 1 2 a j 相應(yīng)的三地碼如下 t1 i 1 t2 t1 elem size a t3 a t2 t4 j elem size a t5 a t4 t6 t5 2 t3 2 6 3 2數(shù)組引用的三地址碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 63 subscriptexp1 subscriptexp2 6 3 2數(shù)組引用的三地址碼生成 續(xù) 思考題 撰寫下述簡單算術(shù)表達式文法對應(yīng)的三地址碼生成的遞歸程序 exp subs exp aexpaexp aexp factor factorfactor exp num subssubs id id exp exp 二維下標運算的語法樹 machunyan 西北工業(yè)大學軟件與微電子學院 64 6 3數(shù)據(jù)結(jié)構(gòu)引用的代碼生成 6 3 1地址計算 6 3 2數(shù)組引用的三地址碼生成 6 3 3記錄結(jié)構(gòu)和指針引用 自學內(nèi)容 machunyan 西北工業(yè)大學軟件與微電子學院 65 6 3 3記錄結(jié)構(gòu)和指針引用 計算記錄結(jié)構(gòu)的域地址提出了一個同計算下標數(shù)組地址相同的問題 首先 計算結(jié)構(gòu)變量的基地址 然后 找到域偏移量 兩者相加得到結(jié)果地址 例如 考慮C語言聲明 typedefstructrec inti charc intj Rec Recx machunyan 西北工業(yè)大學軟件與微電子學院 66 第一個參數(shù)是結(jié)構(gòu)變量名 第二個參數(shù)是域名 函數(shù)的返回值是x j的偏移量 6 3 3記錄結(jié)構(gòu)和指針引用 續(xù) 用于域地址計算的三地址碼 為了計算x j的地址并存入臨時變量t1 使用如下的三地址指令 t1 被翻譯成如下的三地址碼 t1 x field offset x j t2 x field offset x i t1 t2 machunyan 西北工業(yè)大學軟件與微電子學院 67 6 3 3記錄結(jié)構(gòu)和指針引用 續(xù) 對于指針引用 例如假設(shè)x被定義成整型指針 int x 假設(shè)i是一個普通整型變量 C賦值語句 x i 翻譯成三地址指令 x i賦值語句i x 翻譯成三地址指令i x machunyan 西北工業(yè)大學軟件與微電子學院 68 C變量聲明如下 typedefstructtreeNode intval structtreeNode lchild rchild TreeNode TreeNode p 6 3 3記錄結(jié)構(gòu)和指針引用 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 69 現(xiàn)在考慮兩個典型的賦值p lchild p p p rchild 這些語句翻譯成三地址碼如下 t1 p field offset p lchild t1 pt2 p field offset p rchild p t2 6 3 3記錄結(jié)構(gòu)和指針引用 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 70 第6章代碼生成 6 1中間代碼概覽 6 2基本的代碼生成技術(shù) 6 3數(shù)據(jù)結(jié)構(gòu)引用的代碼生成 6 4控制語句和邏輯表達式的代碼生成 6 5過程和函數(shù)調(diào)用的代碼生成 machunyan 西北工業(yè)大學軟件與微電子學院 71 6 4控制語句和邏輯表達式的代碼生成 6 4 1if和while語句的代碼生成6 4 2邏輯表達式的代碼生成 自學內(nèi)容 6 4 3if和while語句的代碼生成過程舉例 machunyan 西北工業(yè)大學軟件與微電子學院 72 6 4 1if和while語句的代碼生成 考慮下面兩種if和while語句 他們的語法結(jié)構(gòu)在很多不同的語言中都是相似的 現(xiàn)在給出的是類C語法 if stmt if exp stmt if exp stmtelsestmtwhile stmt while exp stmtIf和while語句代碼生成的主要問題 將結(jié)構(gòu)化的控制特性翻譯成涉及轉(zhuǎn)移的非結(jié)構(gòu)化等價物 以被目標代碼直接實現(xiàn) machunyan 西北工業(yè)大學軟件與微電子學院 73 編譯器通常以一種標準次序安排if和while語句的中間代碼生成 這種次序可以高效地使用轉(zhuǎn)移子集 而且這種轉(zhuǎn)移子集是目標系統(tǒng)所允許的 將if語句翻譯為中間代碼的典型代碼排列如下 6 4 1if和while語句的代碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 74 if stmt if exp stmt if exp stmtelsestmt 真 if語句生成的中間代碼的典型排列 machunyan 西北工業(yè)大學軟件與微電子學院 75 為了生成控制語句的三地址碼 引入如下的三地址碼指令 產(chǎn)生標號的三地址語句 label 例如 labelL1 labelL2 當測試條件為假時轉(zhuǎn)移的三地址語句 if false goto例如 if falset1gotoL1無條件轉(zhuǎn)移的三地址語句 goto 例如 gotoL1 6 4 1if和while語句的代碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 76 if語句生成下面的代碼模式 求邏輯表達式E的值的三地址碼序列if falset1gotoL1 true情況下執(zhí)行的三地址碼序列g(shù)otoL2labelL1 false情況下執(zhí)行的三地址碼序列l(wèi)abelL2 if語句后的代碼 if stmt if E S1 if E S1elseS2 6 4 1if和while語句的代碼生成 續(xù) 將while語句翻譯為中間代碼的典型代碼排列如下 machunyan 西北工業(yè)大學軟件與微電子學院 77 6 4 1if和while語句的代碼生成 續(xù) while stmt while exp stmt machunyan 西北工業(yè)大學軟件與微電子學院 78 while stmt while exp stmt 真 6 4 1while語句生成代碼的典型排列 machunyan 西北工業(yè)大學軟件與微電子學院 79 while語句生成下面的代碼模式 labelL1 求邏輯表達式E的值的三地址碼序列if falset1gotoL2 while循環(huán)體的代碼執(zhí)行序列g(shù)otoL1labelL2 While語句后的代碼 while stmt while E S 6 4 1if和while語句的代碼生成 續(xù) 下述是do while語句的簡化語法dowhile stmt dostmtwhile exp 請給出do while語句生成中間代碼 三地址碼 的翻譯模式 machunyan 西北工業(yè)大學軟件與微電子學院 80 6 4 1if和while語句的代碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 81 6 4控制語句和邏輯表達式的代碼生成 6 4 1if和while語句的代碼生成6 4 2邏輯表達式的代碼生成 自學內(nèi)容 6 4 3if和while語句的代碼生成過程樣例 表示邏輯表達式的值第一種方法可以用1表示真 用0表示假 邏輯表達從左到右按與算術(shù)表達式類似的方式完全計算 例如 aorbandnotc將被翻譯成如下三地址序列 t1 notct2 bandt1t3 aort2 machunyan 西北工業(yè)大學軟件與微電子學院 82 6 4 2邏輯表達式的代碼生成 對于a b這樣的關(guān)系表達式等價于條件語句ifa b1else0ifa b1else0被翻譯成如下的三地碼序列 if falsea bgotoL1t1 0gotoL2labelL1t1 1labelL2 machunyan 西北工業(yè)大學軟件與微電子學院 83 6 4 2邏輯表達式的代碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 84 例如表達式a borc dande f的翻譯 試給出邏輯表達式文法E EorE EandE notE E idreropid true false用數(shù)值表示邏輯值的三地址碼生成過程實現(xiàn) 其中rerop代表比較算符 or的優(yōu)先級最低 其次是and 最后是not 6 4 2邏輯表達式的代碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 85 表示邏輯表達式的值的第二種方法是通過控制流 即用程序到達的位置來表示邏輯表達式的值 例如 對于表達式EorE 如果確定了E是真 那么可以肯定整個表達式都是真 而不必再去計算E 詳細資料參見 編譯原理李建中姜守旭P316 6 4 2邏輯表達式的代碼生成 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 86 6 4控制語句和邏輯表達式的代碼生成 6 4 1if和while語句的代碼生成6 4 2邏輯表達式的代碼生成6 4 3if和while語句的代碼生成過程樣例 machunyan 西北工業(yè)大學軟件與微電子學院 87 6 4 3if和while語句的代碼生成過程樣例 用如下簡化的文法展示一個控制語句的代碼生成過程 stmt if stmt while stmt break otherif stmt if exp stmt if exp stmtelsestmtwhile stmt while exp stmtexp true false machunyan 西北工業(yè)大學軟件與微電子學院 88 6 4 3if和while語句的代碼生成過程樣例 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 89 下面的C聲明 用來為上述文法實現(xiàn)一棵抽象語法樹typedefenum ExpKind IfKind WhileKind BreakKind OtherKind NodeKind typedefstructstreenode NodeKindkind structstreenode child 3 intval usedwithExpKind char strval STreeNode typedefSTreeNode SyntaxTree 6 4 3if和while語句的代碼生成過程樣例 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 90 例如語句if true while true if false breakelseother有如下的語法樹 6 4 3if和while語句的代碼生成過程樣例 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 91 上述簡單控制語句的三地址碼生成過程實現(xiàn) voidgenCode SyntaxTree char lab1 lab2 if t NULL switch t kind caseExpKind t strval newtemp if t val 0 emit t strval false elseemit t strval true 6 4 3if和while語句的代碼生成過程樣例 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 92 caseIfKind genCode t child 0 lab1 genLabel emit if false t child 0 strval goto lab1 genCode t child 1 if t child 2 NULL lab2 genLabel emit goto lab2 emit label lab1 if t child 2 NULL genCode t child 2 emit label lab2 break 無參過程返回標號名 L1 L2 6 4 3if和while語句的代碼生成過程樣例 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 93 caseWhileKind lab1 genLabel emit label lab1 genCode t child 0 Lab2 genLabel emit if false t child 0 strval goto lab2 genCode t child 1 emit goto lab1 emit label lab2 break 6 4 3if和while語句的代碼生成過程樣例 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 94 caseBreakKind emit goto break caseOtherKind emit Other break default emit Error break 6 4 3if和while語句的代碼生成過程樣例 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 95 上述簡單控制語句的三地址碼生成過程實現(xiàn) voidgenCode SyntaxTreet char label char lab1 lab2 if t NULL switch t kind caseExpKind t strval newtemp if t val 0 emit t strval false elseemit t strval true 初值為空 6 4 3if和while語句的代碼生成過程樣例 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 96 caseIfKind genCode t child 0 label lab1 genLabel emit if false t child 0 strval goto lab1 genCode t child 1 label if t child 2 NULL lab2 genLabel emit goto lab2 emit label lab1 if t child 2 NULL genCode t child 2 label emit label lab2 break 無參過程返回標號名 L1 L2 6 4 3if和while語句的代碼生成過程樣例 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 97 caseWhileKind lab1 genLabel emit label lab1 genCode t child 0 label Lab2 genLabel emit if false t child 0 strval goto lab2 genCode t child 1 lab2 emit goto lab1 emit label lab2 break 6 4 3if和while語句的代碼生成過程樣例 續(xù) Lab2傳遞給break語句 machunyan 西北工業(yè)大學軟件與微電子學院 98 caseBreakKind emit goto label break caseOtherKind emit Other break default emit Error break 6 4 3if和while語句的代碼生成過程樣例 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 99 根據(jù)代碼生成的遞歸過程描述 語句if true while true if false breakelseother生成的三地址碼 t3 false if falset3gotoL4 gotoL3 gotoL5 labelL4 other labelL5 labelL2 t2 true if falset2gotoL3 gotoL2 labelL3 t1 true if falset1gotoL1 labelL1 Break語句對應(yīng)的三地址碼 6 4 3if和while語句的代碼生成過程樣例 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 100 第6章代碼生成 6 1中間代碼概覽 6 2基本的代碼生成技術(shù) 6 3數(shù)據(jù)結(jié)構(gòu)引用的代碼生成 6 4控制語句和邏輯表達式的代碼生成 6 5過程和函數(shù)調(diào)用的代碼生成 machunyan 西北工業(yè)大學軟件與微電子學院 101 6 5過程和函數(shù)調(diào)用的代碼生成 6 5 1過程和函數(shù)的中間代碼6 5 2函數(shù)定義和調(diào)用的代碼生成過程 自學內(nèi)容 函數(shù)定義包括函數(shù)名 參數(shù)和函數(shù)代碼 函數(shù)定義的中間代碼必須包括一條標志開始的指令 稱函數(shù)代碼的入口點 entrypoint 一條標志結(jié)束的指令 稱為函數(shù)返回點 returnpoint 翻譯模式如下 EntryinstructionReturninstruction machunyan 西北工業(yè)大學軟件與微電子學院 102 6 5 1過程和函數(shù)的中間代碼 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 103 例如 考慮C函數(shù)定義intf intx inty returnx y 1 翻譯成如下的三地址碼 entryft1 x yt2 t1 1returnt2 返回 6 5 1過程和函數(shù)的中間代碼 續(xù) 入口指令需要給出一個函數(shù)入口點的名字 類似于label指令 引入entry作為函數(shù)入口的三地址指令 例如 entryf引入return作為三地址返回指令 假如有返回值 必須給出返回值的名字 例如 returnt1 machunyan 西北工業(yè)大學軟件與微電子學院 104 6 5 1過程和函數(shù)的中間代碼 續(xù) 函數(shù)調(diào)用首先產(chǎn)生參數(shù)的實際值 然后轉(zhuǎn)去執(zhí)行函數(shù)代碼 函數(shù)調(diào)用的中間代碼必須有一條指令指示參數(shù)計算的開始 為調(diào)用而準備的 然后實際調(diào)用指令指示已經(jīng)構(gòu)成了參數(shù) 到函數(shù)代碼的實際轉(zhuǎn)移可以發(fā)生了 翻譯模式如下 Begin argument computationinstructionCallinstruction machunyan 西北工業(yè)大學軟件與微電子學院 105 6 5 1過程和函數(shù)的中間代碼 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 106 例如 假如上例中的函數(shù)f已經(jīng)在C中定義 調(diào)用f 2 3 4 翻譯成三地址碼如下 begin argst1 2 3argt1arg4callf 返回 6 5 1過程和函數(shù)的中間代碼 續(xù) 函數(shù)調(diào)用引入3個不同的三地址指令 一個標志參數(shù)計算的起點 引入begin args一個被用于重復說明參數(shù)值名字的指令arg調(diào)用指令 簡單寫成call machunyan 西北工業(yè)大學軟件與微電子學院 107 6 5 1過程和函數(shù)的中間代碼 續(xù) machunyan 西北工業(yè)大學軟件與微電子學院 108 6 5過程和函數(shù)調(diào)用的代碼生成 6 5 1過程和函數(shù)的中間代碼6 5 2函數(shù)定義和調(diào)用的代碼生成過程 自學內(nèi)容 machunyan 西北工業(yè)大學軟件與微電子學院 109 函數(shù)定義和調(diào)用的文法如下 program decl listexpdecl list decl listdecl decl fnid param list expparam list param list id idexp exp exp call num idcall id arg list arg list arg list exp exp 6 5 2函數(shù)定義和調(diào)用的代碼生成過程 machunyan 西北工業(yè)大學軟件與微