中間代碼生成

中間代碼生成1第1頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：概述編譯器的分析綜合模型分析部分：源程序=〉基本塊=〉中間表示綜合部分：中間表示=〉目標(biāo)程序圖8-1：中間代碼生成器的位置使用中間表示（形式）的優(yōu)點(diǎn)重置目標(biāo)比較容易可在中間表示上應(yīng)用與機(jī)器無關(guān)的代碼優(yōu)化器如何實(shí)現(xiàn)？語法制導(dǎo)翻譯2第2頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：概述中間表示后綴表示（表達(dá)式）語法樹/分析樹和DAG：圖8-2圖8-3：語法制導(dǎo)定義產(chǎn)生語法樹/DAG語法樹：mkunode和mknode每次返回新節(jié)點(diǎn)指針圖8-4：圖8-2a中語法樹的兩種表示DAG：mkunode和mknode盡可能返回現(xiàn)存節(jié)點(diǎn)指針三地址碼3第3頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成概述三地址碼聲明語句賦值語句布爾表達(dá)式4第4頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：三地址碼三地址碼的一般形式x:=yopz三地址碼是語法樹或DAG的線性表示圖8-5：圖8-2中的語法樹和DAG相對(duì)應(yīng)的三地址碼5第5頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：三地址碼三地址語句的類型（通用）x:=yopzx:=opyx:=yx:=y[i]及x[i]:=yx:=&y,x:=*y及*x:=ygotoLifxrelopygotoLp(x1,x2…xn)paramx1paramx2…paramxncallp,nreturny6第6頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：三地址碼語法制導(dǎo)翻譯生成三地址碼臨時(shí)名字成了語法樹的內(nèi)節(jié)點(diǎn)圖8-6：S屬性定義生成賦值語句的三地址碼圖8-7：為while語句生成代碼的語義規(guī)則7第7頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：三地址碼三地址語句的實(shí)現(xiàn)抽象形式：三地址語句具體實(shí)現(xiàn)：通過帶有操作符合操作數(shù)的記錄結(jié)構(gòu)來實(shí)現(xiàn)四元式三元式間接三元式8第8頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：三地址碼三地址語句的實(shí)現(xiàn)四元式帶有四個(gè)域的記錄結(jié)構(gòu)：op,arg1,arg2,resultarg1,arg2,result域的內(nèi)容正常情況下指向這些域所代表的名字在符號(hào)表表項(xiàng)的指針臨時(shí)名字在生成時(shí)一定要被寫入符號(hào)表圖8-8a：三地址語句的四元式表示9第9頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：三地址碼三地址語句的實(shí)現(xiàn)三元式為了避免臨時(shí)名字在生成時(shí)被寫入符號(hào)表中，可以通過計(jì)算臨時(shí)值的語句的位置來引用它帶有四個(gè)域的記錄結(jié)構(gòu)：op,arg1,arg2arg1,arg2指向符號(hào)表（對(duì)于程序員定義的名字或常量）的指針或者三元組結(jié)構(gòu)（對(duì)于臨時(shí)變量）的指針圖8-8b：三地址語句的三元式表示圖8-9：更多三元式表示10第10頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：三地址碼三地址語句的實(shí)現(xiàn)間接三元式列出指向三元式的指針，而不是列出三元式本身圖8-10：三地址語句的間接三元式表示11第11頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：三地址碼三地址語句的實(shí)現(xiàn)表示方法比較：間址的使用使用四元式表示，定義或使用臨時(shí)變量的三地址語句可以通過符號(hào)表直接訪問臨時(shí)變量的地址使用四元式表示，符號(hào)表在值的計(jì)算及使用之間提供了一次額外間址，有利于優(yōu)化。使用三元式表示，移動(dòng)一條定義臨時(shí)值的語句需要我們改變?cè)赼rg1及arg2數(shù)組中所有對(duì)該語句的引用，難以優(yōu)化。使用間接三元式表示，可以通過statement列表的重新排序來移動(dòng)語句。12第12頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成概述三地址碼聲明語句賦值語句布爾表達(dá)式13第13頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：聲明語句過程中的聲明語句單個(gè)過程中所有的聲明語句作為一個(gè)組來處理（Pascal,C,Fortran）使用一個(gè)全局變量offset跟蹤下一個(gè)可用的相對(duì)地址圖8-11：計(jì)算聲明語句中名字的類型和相對(duì)地址重寫產(chǎn)生式P->{offset:=0}D以便所有的動(dòng)作都出現(xiàn)在產(chǎn)生式右部的未端P->MDM->ε{offset:=0}14第14頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：聲明語句跟蹤作用域信息嵌套過程當(dāng)看到嵌套的過程時(shí)，應(yīng)暫時(shí)掛起對(duì)外圍過程聲明語句的處理假定每個(gè)過程都有一個(gè)單獨(dú)的符號(hào)表，當(dāng)遇到過程聲明D->procid;D1;S時(shí)，便創(chuàng)建一個(gè)新的符號(hào)表，并在此符號(hào)表中為D1中的聲明創(chuàng)建相應(yīng)的表項(xiàng)。新表有一個(gè)指針指回外圍過程的符號(hào)表；由id代表的名字本身是該外圍過程的局部名字。15第15頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：聲明語句跟蹤作用域信息嵌套過程圖8-12：嵌套過程的符號(hào)表圖8-13：處理嵌套過程中的聲明語句兩個(gè)棧：1）一個(gè)存放嵌套過程的外圍符號(hào)表；2）1）一個(gè)存放嵌套過程的外圍offset16第16頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：聲明語句記錄中的域名圖8-14：為記錄中的域名建立符號(hào)表記錄的布局與過程的活動(dòng)記錄的布局相似17第17頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成概述三地址碼聲明語句賦值語句布爾表達(dá)式18第18頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：賦值語句表達(dá)式的類型整型、實(shí)型、數(shù)組、記錄主要問題在符號(hào)表中查找名字存儲(chǔ)數(shù)組及記錄中的元素19第19頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：賦值語句符號(hào)表中的名字圖8-15：為賦值語句產(chǎn)生三地址碼的翻譯模式通過適當(dāng)?shù)膌ookup操作和嵌套過程的符號(hào)表指針top(tblptr)，實(shí)現(xiàn)最近嵌套作用域規(guī)則（圖8-13）臨時(shí)名字的產(chǎn)生newtemp臨時(shí)名字的重用代碼生成階段將獨(dú)立的臨時(shí)變量封裝到同一個(gè)地址20第20頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：賦值語句臨時(shí)名字的重用通過一個(gè)小數(shù)組（棧）保存臨時(shí)名字實(shí)現(xiàn)例8.1：圖8-16帶有棧臨時(shí)變量的三地址碼有些時(shí)候（如條件賦值語句）不能使用，因?yàn)榇藭r(shí)臨時(shí)名字不能以后進(jìn)先出方式指派名字，需單獨(dú)指派自己的名字一個(gè)合理策略每當(dāng)創(chuàng)建一個(gè)額外的定義或使用一個(gè)臨時(shí)名字或移動(dòng)其計(jì)算時(shí)，均創(chuàng)建一個(gè)新的名字21第21頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：賦值語句尋址數(shù)組元素圖8-17：二維數(shù)據(jù)的布局（行/列優(yōu)先）產(chǎn)生數(shù)組引用A[i1,i2…ik]的前m個(gè)下標(biāo)的Elist生成三地址碼（8-7）和（8-8）22第22頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：賦值語句尋址數(shù)組元素?cái)?shù)組元素尋址的翻譯模式：312-314頁Elist綜合屬性array：指向符號(hào)表數(shù)組名表項(xiàng)的指針Elist繼承屬性ndim：Elist的維數(shù)Limit(array,j)：array指向符號(hào)表數(shù)組名表項(xiàng)的數(shù)組的第j維的元素個(gè)數(shù)Elist.place：臨時(shí)變量，保存根據(jù)Elist的下標(biāo)表達(dá)式計(jì)算出來的值L有兩個(gè)屬性Place：（8-6）第二項(xiàng)Offset：（8-6）第一項(xiàng)例8.2：圖8-18數(shù)組賦值語句x:=A[y,z]的注釋分析樹23第23頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：賦值語句賦值語句中的類型轉(zhuǎn)換圖8-19：E->E1+E2的語義動(dòng)作24第24頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：賦值語句記錄域的訪問為每個(gè)記錄類型構(gòu)造一個(gè)符號(hào)表（參8-14），把記錄域的類型和相對(duì)地址信息記在域名字的符號(hào)表表項(xiàng)中，這樣記錄域的訪問與其它名字的訪問一樣了。25第25頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成概述三地址碼聲明語句賦值語句布爾表達(dá)式26第26頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：布爾表達(dá)式布爾表達(dá)式基本作用計(jì)算邏輯值控制流語句中的條件表達(dá)式27第27頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：布爾表達(dá)式計(jì)算邏輯值從左到右按與算術(shù)表達(dá)式相似的方式完全計(jì)算差別：布爾運(yùn)算符vs算術(shù)運(yùn)算符例8.3：表達(dá)式a<borc<dande<f圖8-20：用數(shù)值表示布爾值的翻譯模式圖8-21：表達(dá)式a<borc<dande<f的翻譯28第28頁，課件共30頁，創(chuàng)作于2023年2月第八章：中間代碼生成：布爾表達(dá)式計(jì)算邏輯值短路代碼即使不對(duì)布爾運(yùn)算符生成代碼并且不必生成整個(gè)表達(dá)式的代碼，也可以把布爾表達(dá)式翻譯成三地址碼用代碼序列中的位置表示表達(dá)式的值圖8-21：根據(jù)到達(dá)語句101還是