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