版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
中間代碼生成
中間代碼生成(一)?運(yùn)行時(shí)刻環(huán)境概要?存儲(chǔ)組織和幀棧設(shè)計(jì)方法運(yùn)行時(shí)刻環(huán)境?目標(biāo)程序的代碼放置在代碼區(qū)?靜態(tài)區(qū)、堆區(qū)、棧區(qū)分別放置不同類型生命期的數(shù)據(jù)值?實(shí)踐中，棧是由低地址向高地址增長，而堆是由高地址向低地址增長存儲(chǔ)分配的典型方式?運(yùn)行時(shí)刻環(huán)境概要?存儲(chǔ)組織和幀棧設(shè)計(jì)方法運(yùn)行時(shí)刻環(huán)境?靜態(tài)分配O
編譯器在編譯時(shí)刻就可以做出存儲(chǔ)分配決定，
不需要考慮程序運(yùn)行時(shí)刻的情形O
全局變量?動(dòng)態(tài)分配O
棧式存儲(chǔ)：和過程的調(diào)用/返回同步進(jìn)行分配和回收，值的生命期和過程生命期相同O
堆存儲(chǔ)：數(shù)據(jù)對(duì)象比創(chuàng)建它的過程調(diào)用更長壽?手工進(jìn)行回收：C++/C…?垃圾回收機(jī)制:Java/C#/Python…靜態(tài)和動(dòng)態(tài)存儲(chǔ)分配?過程調(diào)用(過程活動(dòng))在時(shí)間上總是嵌套的O
后調(diào)用的先返回O
因此用棧式分配來分配過程活動(dòng)所需內(nèi)存空間?程序運(yùn)行的所有過程活動(dòng)可以用樹表示O
每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)過程活動(dòng)O
根結(jié)點(diǎn)對(duì)應(yīng)于main過程的活動(dòng)O
過程p的某次活動(dòng)對(duì)應(yīng)的結(jié)點(diǎn)的所有子結(jié)點(diǎn)：此次活動(dòng)所調(diào)用的各個(gè)過程活動(dòng)(從左向右，表示
調(diào)用的先后順序)活動(dòng)樹?程序：P277，圖7-2?過程調(diào)用(返回)序列和活
動(dòng)樹的前序(后序)遍歷對(duì)應(yīng)?假定當(dāng)前活動(dòng)對(duì)應(yīng)結(jié)點(diǎn)N，那么所有尚未結(jié)束的活動(dòng)對(duì)應(yīng)于N及其祖先結(jié)點(diǎn)?；顒?dòng)樹的例子(1)?過程調(diào)用和返回由控制棧進(jìn)行管理?每個(gè)活躍的活動(dòng)對(duì)應(yīng)于棧中的一個(gè)活動(dòng)記錄?活動(dòng)記錄按照活動(dòng)的開始時(shí)間，從棧底到棧頂排列活動(dòng)記錄?a[11]為全局變量?main沒有局部變量?r有局部變量i?q的局部變量i，和參數(shù)m,n運(yùn)行時(shí)刻棧的例子?調(diào)用代碼序列(calling
sequence)為活動(dòng)
記錄分配空間，填寫記錄中的信息?返回代碼序列(return
sequence)恢復(fù)機(jī)
器狀態(tài)，使調(diào)用者繼續(xù)運(yùn)行?調(diào)用代碼序列會(huì)分割到調(diào)用者和被調(diào)用者中O
根據(jù)源語言、目標(biāo)機(jī)器、操作系統(tǒng)的限制，可以有不同的分割方案O
把代碼盡可能放在被調(diào)用者中調(diào)用代碼序列?數(shù)據(jù)方面O
能夠把參數(shù)正確地傳遞給被調(diào)用者O
能夠把返回值傳遞給調(diào)用者?控制方面O
能夠正確轉(zhuǎn)到被調(diào)用過程的代碼開始位置O
能夠正確轉(zhuǎn)回調(diào)用者的調(diào)用位置(的下一條指令)?調(diào)用代碼序列和活動(dòng)記錄的布局相關(guān)調(diào)用/返回代碼序列的要求?調(diào)用者和被調(diào)用者之間傳遞的值放在被調(diào)用者活動(dòng)記錄的開始位置?固定長度的項(xiàng)放在中間位置O
控制鏈、訪問鏈、機(jī)器狀態(tài)字段?早期不知道大小的項(xiàng)在活動(dòng)記錄尾部?棧頂指針(top_sp)通常指向固定長度字段的末端活動(dòng)記錄的布局原則?調(diào)用代碼序列(Calling
sequence)O
調(diào)用者計(jì)算實(shí)在參數(shù)的值O
將返回地址和原top_sp存放到被調(diào)用者的活動(dòng)記錄中。調(diào)用者增加top_sp的值(越過了局部數(shù)據(jù)、臨時(shí)變量、被調(diào)用者的參數(shù)、機(jī)器狀態(tài)字段)O
被調(diào)用者保存寄存器值和其他狀態(tài)字段O
被調(diào)用者初始化局部數(shù)據(jù)、開始運(yùn)行?返回代碼序列(Return
sequence)O
被調(diào)用者將返回值放到和參數(shù)相鄰的位置O
恢復(fù)top_sp和寄存器，跳轉(zhuǎn)到返回地址調(diào)用代碼序列的例子調(diào)用者/被調(diào)用者的活動(dòng)記錄?看一個(gè)實(shí)際的例子棧中的變長數(shù)據(jù)?如果數(shù)據(jù)對(duì)象的生命期局限于過程活動(dòng)的
生命期，就可以分配
在運(yùn)行時(shí)刻棧中O
變長數(shù)組也可以放在棧中?
top指向?qū)嶋H的棧頂?top_sp用于尋找頂層記錄的定長字段棧中的變長數(shù)據(jù)?沒有嵌套過程時(shí)的數(shù)據(jù)訪問O
C語言中，每個(gè)函數(shù)能夠訪問的變量?函數(shù)的局部變量：相對(duì)地址已知，且存放在當(dāng)前活動(dòng)記錄內(nèi)，top_sp指針加上相對(duì)地址即可訪問?全局變量：在靜態(tài)區(qū)，地址在編譯時(shí)刻可知O
很容易將C語言的函數(shù)作為參數(shù)進(jìn)行傳遞?參數(shù)中只需包括函數(shù)代碼的開始地址。?在函數(shù)中訪問非局部變量的模式很簡單，不需要考慮過程是如何激活的非局部數(shù)據(jù)的訪問(無嵌套過程)?
PASCAL中，如果過程A的聲明中包含了過程B的聲明，那么B可以使用在A中聲明的變量。?當(dāng)B的代碼運(yùn)行時(shí)，如果它使用的是A中的變量。那么這個(gè)變量指向運(yùn)行棧中最上層的同名變量。?
但是，我們不能通過嵌套層次直接得到A的活動(dòng)記錄的相對(duì)位置，必須通過訪問鏈訪問非局部數(shù)據(jù)的訪問(嵌套聲明過程)A的活動(dòng)記錄C的活動(dòng)記錄B的活動(dòng)記錄A的活動(dòng)記錄B的活動(dòng)記錄void
A(){int
void
{}
voidC();B();}當(dāng)A調(diào)用C，C又調(diào)用B時(shí):x,y;
B()
int
b;
x
=
b+y;當(dāng)A直接調(diào)用B時(shí):C(){B();}?ML是一種函數(shù)式語言．變量一旦被聲明并初始化就不會(huì)在改變，只有少數(shù)幾個(gè)例外．?定義變量并設(shè)定它們不可更改的初始值的語句有如下形式val<name>=(expression)?函數(shù)使用如下語法進(jìn)行定義fun<name>(<arguments>)=<body>?使用下列形式的let語句來定義函數(shù)體let<list
of
definitions>in<statements>
end其中，定義通常是val或fun語句．每個(gè)這樣的定義的作用域包括從該定義之后直到in為止的所
有定義，及直到end為止的所有語句．函數(shù)可嵌套地定義．如函數(shù)p的函數(shù)體可能包括一個(gè)let語句，而該語句又包含了另一個(gè)函數(shù)q的
定義．
一個(gè)支持嵌套聲明的例子?嵌套深度是正文概念，可以根據(jù)源程序靜態(tài)地確定O
不內(nèi)嵌于任何其他過程中的過程，嵌套深度為1O
嵌套在深度為i的過程中的過程，深度為i+1深度為1sort深度為2
readArray，exchange，
quicksort深度為3
partition嵌套深度?訪問鏈O
當(dāng)被調(diào)用過程需要其他地方的某個(gè)數(shù)據(jù)時(shí)需要使用訪問鏈進(jìn)行定位O
如果過程p在聲明時(shí)嵌套在過程q的聲明中，
那么p的活動(dòng)記錄中的訪問鏈指向最上層的q的活動(dòng)記錄O
從棧頂活動(dòng)記錄開始，訪問鏈形成了一個(gè)鏈路，嵌套深度沿著鏈路逐一遞減訪問鏈?設(shè)深度為np
的過程p訪問變量x，而變量x在
深度為nq
的過程中聲明，那么O
np-nq在編譯時(shí)刻已知O
從當(dāng)前活動(dòng)記錄出發(fā)，沿訪問鏈前進(jìn)np-nq次
找到的活動(dòng)記錄中的x就是要找的變量位置O
x相對(duì)于這個(gè)活動(dòng)記錄的偏移量在編譯時(shí)刻已訪問鏈知訪問鏈的例子?當(dāng)過程q調(diào)用過程p時(shí)，訪問鏈的變化O
p的深度大于q：根據(jù)作用域規(guī)則，p必然在q中直接定義；那么p的訪問鏈指向當(dāng)前活動(dòng)記錄?s調(diào)用q(1,9)O
遞歸調(diào)用(p=q)：新活動(dòng)記錄的訪問鏈等于當(dāng)
前記錄的訪問鏈?q(1,9)調(diào)用q(1,3)O
p的深度小于等于q的深度：此時(shí)必然有過程r，p直接在r中定義，而q嵌套在r中；p的訪問鏈指向訪問鏈的維護(hù)(直接調(diào)用過程)棧最高的r的活動(dòng)記錄?p調(diào)用exchange訪問鏈的維護(hù)：訪問鏈的定義+作用域規(guī)則?在傳遞過程指針參數(shù)時(shí)，過程型參數(shù)中不僅包含過程的代碼指針，還包括正確的訪
問鏈訪問鏈的維護(hù)(過程指針型參數(shù))?用訪問鏈訪問數(shù)據(jù)時(shí)，訪問開銷和嵌套深度差有關(guān)?使用顯示表可以提高效率，訪問開銷為常量?顯示表：數(shù)組d為每個(gè)嵌套深度保留一個(gè)指針O
指針d[i]指向棧中最高的、嵌套深度為i的活動(dòng)記錄。O
如果程序p中訪問嵌套深度為i的過程q中聲明的變量x，那么d[i]直接指向相應(yīng)的(必然是q的)活動(dòng)記錄?
注意：i在編譯時(shí)刻已知?顯示表的維護(hù)O
調(diào)用過程p時(shí)，在p的活動(dòng)記錄中保存d[np]的值，并將d[np]設(shè)置為當(dāng)前活動(dòng)記錄。O
從p返回時(shí)，恢復(fù)d[np]的值。顯示表q(1,9)調(diào)用
q(1,3)時(shí)，
q的深度為2q(1,3)調(diào)用p，
p的深度為3顯示表的例子q調(diào)用e，e
的深度為2?堆空間O
用于存放生命周期不確定、或生存到被明確刪除為止的數(shù)據(jù)對(duì)象O例如：new生成的對(duì)象可以生存到被delete為止O
malloc申請(qǐng)的空間生存到被free為止?存儲(chǔ)管理器O
分配/回收堆區(qū)空間的子系統(tǒng)O
根據(jù)語言而定?C、C++需要手動(dòng)回收空間?Java可以自動(dòng)回收空間(垃圾收集)堆管理?基本功能O
分配：為每個(gè)內(nèi)存請(qǐng)求分配一段連續(xù)的、適當(dāng)大小的堆空間?首先從空閑的堆空間分配?如果不行則從操作系統(tǒng)中獲取內(nèi)存、增加堆空間O
回收：把被回收的空間返回空閑空間緩沖池，以滿足其他內(nèi)存需求?評(píng)價(jià)存儲(chǔ)管理器的特性O(shè)
空間效率：使程序需要的堆空間最小，即減小碎片O
程序效率：充分運(yùn)用內(nèi)存系統(tǒng)的層次，提高效率O
低開銷：使分配/收回內(nèi)存的操作盡可能高效存儲(chǔ)管理器存儲(chǔ)管理器?局部性大部分程序表現(xiàn)出高度的局部性–程序的大部分運(yùn)行時(shí)間花費(fèi)在相對(duì)較小的一部分代碼中(此時(shí)可能只涉及固定的一小部分?jǐn)?shù)據(jù))。程序中的局部性?隨著程序分配/回收內(nèi)存，堆區(qū)逐漸被割裂成為若干空閑存儲(chǔ)塊(窗口，hole)和已用存儲(chǔ)塊的交錯(cuò)?分配一塊內(nèi)存時(shí)，通常是把一個(gè)窗口的一部分分配出去，其余部分成為更小的塊?回收時(shí)，被釋放的存儲(chǔ)塊被放回緩沖池。通常要把連續(xù)的窗口接合成為更大的窗口堆空間的碎片問題已分配空間碎片?Best-FitO
總是將請(qǐng)求的內(nèi)存分配在滿足請(qǐng)求的最小的窗口中O
好處：可以將大的窗口保留下來，應(yīng)對(duì)更大的請(qǐng)求?First-FitO
總是將對(duì)象放置在第一個(gè)能夠容納請(qǐng)求的窗口中O
放置對(duì)象時(shí)花費(fèi)時(shí)間較少，但是總體性能較差O
但是first-fit的分配方法通常具有較好的數(shù)據(jù)局部性?同一時(shí)間段內(nèi)的生成的對(duì)象經(jīng)常被分配在連續(xù)的空間內(nèi)堆空間分配方法?設(shè)定不同大小的空閑塊規(guī)格，相同規(guī)格的塊放在同一容器中?較小的(較常用的)尺寸設(shè)置較多的容器?比如GNU的C編譯器將所有存儲(chǔ)塊對(duì)齊到8字節(jié)邊界O
空閑塊的尺寸大小?16,24,32,40,…,512?大于512的按照對(duì)數(shù)劃分：每個(gè)容器的最小尺寸是前一個(gè)容器的最小尺寸的兩倍?荒野塊：可以擴(kuò)展的內(nèi)存塊O
分配方法?對(duì)于小尺寸的請(qǐng)求，直接在相應(yīng)容器中找?大尺寸的請(qǐng)求，在適當(dāng)?shù)娜萜髦袑ふ疫m當(dāng)?shù)目臻e塊?可能需要分割內(nèi)存塊?可能需要從荒野塊中分割出更多的塊使用容器的堆管理方法?當(dāng)回收一個(gè)塊時(shí)，可以把這個(gè)塊和相鄰的塊接合起來，構(gòu)成更大的塊?支持相鄰塊接合的數(shù)據(jù)結(jié)構(gòu)O
邊界標(biāo)記：在每一塊存儲(chǔ)塊的兩端，
分別設(shè)置一個(gè)free/used位；相鄰的位置上存放字節(jié)
總數(shù)O
雙重鏈接的、嵌入式的空閑塊列表：
列表的指針存放在空閑塊中、用雙向指針的方式記錄了有哪些空閑塊管理和接合空閑空間?相鄰的存儲(chǔ)塊A、B、CO
當(dāng)回收B時(shí)，通過對(duì)free/used位的查詢，可以知道B左邊的A是空閑的，而C不空閑。O
同時(shí)還可以知道A、B合并為長度為300的塊O
修改雙重鏈表，把A替換為A、B接合后的空閑塊?注意：雙重鏈表中一個(gè)結(jié)點(diǎn)的前驅(qū)并不一定是它鄰近的塊例子?兩大問題O
內(nèi)存泄露：未能刪除不可能再被引用的數(shù)據(jù)O
懸空指針引用：引用已被刪除的數(shù)據(jù)?其他問題O
空指針訪問/數(shù)組越界訪問?解決方法O
自動(dòng)存儲(chǔ)管理O
正確的編程模式處理手工存儲(chǔ)管理?對(duì)象所有者(Object
ownership)O
每個(gè)對(duì)象總是有且只有一個(gè)所有者(指向此對(duì)象的指針)；只有通過Owner才能夠刪除這個(gè)對(duì)象O當(dāng)Owner消亡時(shí)，這個(gè)對(duì)象要么也被刪除，要么已
經(jīng)被傳遞給另一個(gè)owner?語句v=new
ClassA；創(chuàng)建的對(duì)象的所有者為v?即將對(duì)v進(jìn)行賦值的時(shí)刻(v的值即將消亡)O
要么v已經(jīng)不是它所指對(duì)象的所有者；比如g=v可以把v的ownership傳遞給gO
要么需要在返回/賦值之前，執(zhí)行delete
v操作O
編程時(shí)需要了解各個(gè)指針在不同時(shí)刻是否ownerO
防止內(nèi)存泄漏，避免多次刪除對(duì)象。不能解決懸空指針問題正確的編程模式(1)?引用計(jì)數(shù)O
每個(gè)動(dòng)態(tài)分配的對(duì)象附上一個(gè)計(jì)數(shù)：記錄有多少個(gè)指針指向這個(gè)對(duì)象O
在賦值/返回/參數(shù)傳遞時(shí)維護(hù)引用計(jì)數(shù)的一致性O(shè)
在計(jì)數(shù)變成0之時(shí)刪除這個(gè)對(duì)象O
可以解決懸空指針問題；但是在遞歸數(shù)據(jù)結(jié)構(gòu)中仍然可能引起內(nèi)存泄漏O
需要較大的運(yùn)行時(shí)刻開銷?基于區(qū)域的分配O
將一些生命期相同的對(duì)象分配在同一個(gè)區(qū)域中O
整個(gè)區(qū)域同時(shí)刪除正確的編程模式(2)中間代碼生成(二)?中間表示?類型與聲明?表達(dá)式的翻譯?控制流與回填運(yùn)行時(shí)刻環(huán)境?靜態(tài)類型檢查和中間代碼生成的過程都可以用語法制導(dǎo)的翻譯來描述和實(shí)現(xiàn)?對(duì)于抽象語法樹這種中間表示的生成，
第五章已經(jīng)介紹過編譯器前端的邏輯結(jié)構(gòu)?每條指令右側(cè)最多有一個(gè)運(yùn)算符O
一般情況可以寫成x=y
op
z?允許的運(yùn)算分量O
名字：源程序中的名字作為三地址代碼的地址O
常量：源程序中出現(xiàn)或生成的常量O
編譯器生成的臨時(shí)變量三地址代碼(1)?指令集合
(1)O
運(yùn)算/賦值指令：x=y
op
z
x
=opyO復(fù)制指令：x=yO
無條件轉(zhuǎn)移指令：gotoLO
條件轉(zhuǎn)移指令：if
x
goto
L
ifFalsexgoto
LO
條件轉(zhuǎn)移指令：if
x
relop
ygotoL三地址代碼(2)?指令集合(2)O
過程調(diào)用/返回?param
x1//設(shè)置參數(shù)?
paramx2?
…?
paramxn?call
p,n//調(diào)用子過程p，n為參數(shù)個(gè)數(shù)O
帶下標(biāo)的復(fù)制指令：x=y[i]x[i]=y?注意：i表示離開數(shù)組位置第i個(gè)字節(jié)，而不是數(shù)組的第i個(gè)元素O
地址/指針賦值指令：三地址代碼(3)?
x=&yx=*y*x=y?語句O
do
i=i+1;while(a[i]<v)；三地址代碼實(shí)例?在實(shí)現(xiàn)時(shí)，可以使用四元式/三元式/間接三元式來表示三地址指令?四元式：可以實(shí)現(xiàn)為紀(jì)錄(或結(jié)構(gòu))?格式(字段)：op
arg1arg2resultO
op:運(yùn)算符的內(nèi)部編碼O
arg1,arg2,result是地址O
x=y+z+y
z
x?單目運(yùn)算符不使用arg2?param運(yùn)算不使用arg2和result?條件轉(zhuǎn)移/非條件轉(zhuǎn)移將目標(biāo)標(biāo)號(hào)放在result字段三地址指令的四元式表示方法?賦值語句：a=b*-c+b*-c四元式的例子?三元式(triple)op
arg1arg2?使用三元式的位置來引用三元式的運(yùn)算結(jié)果?x[i]=y需要拆分為兩個(gè)三元式O
求x[i]的地址，然后再賦值?x=y
op
z需要拆分為(這里？是編號(hào))O
(?)op
y
zO
=x
??問題：在優(yōu)化時(shí)經(jīng)常需要移動(dòng)/刪除/添加三元式，導(dǎo)致三元式的移動(dòng)三元式表示三元式的例子?包含了一個(gè)指向三元式的指針的列表?我們可以對(duì)這個(gè)列表進(jìn)行操作，完成優(yōu)化功能；操作時(shí)不需要修改三元式中的參數(shù)間接三元式?SSA中的所有賦值都是針對(duì)不同名的變量?對(duì)于同一個(gè)變量在不同路徑中定值的情況，可以使用φ函數(shù)來合并不同的定值O
if(flag)x=-1;else
x=1;y
=x*aO
if(flag)x1=-1;else
x2
=1;x3=φ(x1,x2)；靜態(tài)單賦值(SSA)y=x3*a?語法樹中，公共子表達(dá)式每出現(xiàn)一次，就有一個(gè)對(duì)應(yīng)的子樹?表達(dá)式的有向無環(huán)圖(Directed
AcyclicGraph,DAG)能夠指出表達(dá)式中的公共子表達(dá)式，更簡潔地表示表達(dá)式表達(dá)式的有向無環(huán)圖?可以用和構(gòu)造抽象語法樹一樣的SDD來構(gòu)造DAG構(gòu)造?
不同的處理O
在函數(shù)Leaf和Node每次被調(diào)用時(shí)，構(gòu)造新節(jié)點(diǎn)前先檢查是否已存在同樣的節(jié)點(diǎn)，如果已經(jīng)存在，則返回這個(gè)已有的節(jié)點(diǎn)DAG構(gòu)造?
構(gòu)造過程示例?中間表示?類型與聲明?表達(dá)式的翻譯?控制流與回填運(yùn)行時(shí)刻環(huán)境?類型檢查(TypeChecking)O
利用一組規(guī)則來檢查運(yùn)算分量的類型和運(yùn)算符的預(yù)期類型是否匹配?類型信息的用途O
查錯(cuò)、確定名字需要的內(nèi)存空間、計(jì)算數(shù)組元素的地址、類型轉(zhuǎn)換、選擇正確的運(yùn)算符?主要內(nèi)容O
確定名字的類型O
變量的存儲(chǔ)空間布局(相對(duì)地址)類型和聲明?類型系統(tǒng)O
給每一個(gè)組成部分賦予一個(gè)類型表達(dá)式O
通過一組邏輯規(guī)則來表示這些類型表達(dá)式必須滿足的條件?可發(fā)現(xiàn)錯(cuò)誤、提高代碼效率、確定臨時(shí)變量的大小…類型檢查和轉(zhuǎn)換?類型綜合O
根據(jù)子表達(dá)式的類型構(gòu)造出表達(dá)式的類型if
f的類型為st
t且x的類型為sthen
f(x)的類型為t?類型推導(dǎo)O
根據(jù)語言結(jié)構(gòu)的使用方式來確定該結(jié)構(gòu)的類型：if
f(x)是一個(gè)表達(dá)式then對(duì)于某些類型α,β；f的類型為αtβ且x的類類型系統(tǒng)的分類型為α?假設(shè)在表達(dá)式x*i中，x為浮點(diǎn)數(shù)、i為整數(shù)，則結(jié)果應(yīng)該是浮點(diǎn)數(shù)O
x和i使用不同的二進(jìn)制表示方式O
浮點(diǎn)*和整數(shù)*使用不同的指令?t1=(float)i?t2=xfmult1?類型轉(zhuǎn)換比較簡單時(shí)的SDDO
E
t
E1+E2{if(E1.type=integer
and
E2.type=integer)E.type
=integer;else
if(E1.type=float
and
E2.type=integer)E.type
=float;}O
這個(gè)規(guī)則沒有考慮生成類型轉(zhuǎn)換代碼類型轉(zhuǎn)換?編譯器自動(dòng)完成的轉(zhuǎn)換為隱式轉(zhuǎn)換，程序員用代碼指定的轉(zhuǎn)換為顯式轉(zhuǎn)換類型的widening和narrowing?函數(shù)Max求的是兩個(gè)參數(shù)在拓寬層次結(jié)構(gòu)中
的最小公共祖先?Widen函數(shù)已經(jīng)生成了
必要的類型轉(zhuǎn)換代碼處理類型轉(zhuǎn)換的SDT?通過查看參數(shù)來解決函數(shù)重載問題?E
t
f(E1){if
f.typeset={si
t
ti
|1<=i<=k}
andE1.type=skthen
E.type=
tk函數(shù)/運(yùn)算符的重載}?類型表達(dá)式(type
expression)：表示類型的結(jié)構(gòu)O
基本類型O
類名O
類型構(gòu)造算子作用于類型?array[數(shù)字，類型表達(dá)式]?record[字段/類型對(duì)的列表](可以用符號(hào)表表示)O
函數(shù)類型構(gòu)造算子t
：參數(shù)類型t結(jié)果類型O笛卡爾積：sX
tO
可以包含取值為類型表達(dá)式的變量類型表達(dá)式?類型例子O
元素個(gè)數(shù)為3X4的二維數(shù)組O
數(shù)組的元素的記錄類型O
該記錄類型中包含兩個(gè)字段:
x和y,其類型分別是float和integer?類型表達(dá)式O
array[3,
array[4,record[(x,float),(y,integer)]]]類型表達(dá)式的例子?不同的語言有不同的類型等價(jià)的定義?結(jié)構(gòu)等價(jià)O
或者它們是相同的基本類型O
或者是相同的構(gòu)造算子作用于結(jié)構(gòu)等價(jià)的類型而得到的。O
或者一個(gè)類型是另一個(gè)類型表達(dá)式的名字?名等價(jià)O
類型名僅僅代表其自身類型等價(jià)?變量的類型可以確定變量需要的內(nèi)存O
即類型的寬度O
可變大小的數(shù)據(jù)結(jié)構(gòu)只需要考慮指針?函數(shù)的局部變量總是分配在連續(xù)的區(qū)間O
因此給每個(gè)變量分配一個(gè)相對(duì)于這個(gè)區(qū)間開始處的相對(duì)地址?變量的類型信息保存在符號(hào)表中局部變量名的存儲(chǔ)布局計(jì)算類型和寬度的SDT?綜合屬性：type,width?全局變量t和w用于將類型和寬度信息從B傳遞到C
t
εO
相當(dāng)于C的繼承屬性，因?yàn)榭偸峭ㄟ^拷貝來傳遞，所以在SDT中只賦值一次，也可以把t和w替換為C.t和C.w計(jì)算類型和寬度的SDT?綜合屬性：type,width?全局變量t和w用于將類型和寬度信息從B傳遞到C→εO
相當(dāng)于C的繼承屬性，因?yàn)榭偸峭ㄟ^拷貝來傳遞，所以在SDT中只賦值一次，也可以把t和w替換為C.t和C.w計(jì)算類型和寬度的SDTSDT運(yùn)行的例子?輸入：int[2][3]?含義O
D生成一個(gè)聲明列表O
T生成不同的類型O
B生成基本類型int/floatO
C表示分量，生成[num]序列O
注意record中包含了各個(gè)字段的聲明，字段聲明
和變量聲明的文法一致?文法聲明?除了確定類型和類型寬度，還有什么語義需要處理？O
符號(hào)表中的位置聲明序列的SDT?在處理一個(gè)過程/函數(shù)時(shí)，局部變量應(yīng)該放到單獨(dú)的符號(hào)表中去?這些變量的內(nèi)存布局獨(dú)立O
相對(duì)地址從0開始O
假設(shè)變量的放置和聲明的順序相同?SDT的處理方法O
變量offset記錄當(dāng)前可用的相對(duì)地址O每“分配”一個(gè)變量，offset的值增加相應(yīng)的值?top.put(id.lexeme,T.type,offset)O
在當(dāng)前符號(hào)表(位于棧頂)中創(chuàng)建符號(hào)表?xiàng)l目，記錄標(biāo)識(shí)符的類型，偏移量聲明序列的SDT
(1)?我們可以把offset看作D的繼承屬性O(shè)
D.offset表示D中第一個(gè)變量的相對(duì)地址O
P
t
{D.offset=0}
DO
D
t
T
id;{D1.offset=D.offset
+T.width;}
D1聲明序列的SDT
(2)?Ttrecord‘{‘D‘}’?為每個(gè)記錄創(chuàng)建單獨(dú)的符號(hào)表O
首先創(chuàng)建一個(gè)新的符號(hào)表，壓到棧頂O
然后處理對(duì)應(yīng)于字段聲明的D，字段都被加入到新符號(hào)表中O最后根據(jù)棧頂?shù)姆?hào)表構(gòu)造出record類型表達(dá)式；
符號(hào)表出棧記錄字段的處理?中間表示?類型與聲明?表達(dá)式的翻譯?控制流與回填運(yùn)行時(shí)刻環(huán)境?將表達(dá)式翻譯成三地址指令序列?表達(dá)式的SDDO
屬性code表示代碼O
addr表示存放表達(dá)式結(jié)果的地址
(臨時(shí)變量)O
new
Temp()可以生成一個(gè)臨時(shí)變量O
gen(…)生成一個(gè)指令表達(dá)式代碼的SDD表達(dá)式代碼的SDD?主屬性code滿足增量式翻譯的條件?
注意O
top.get(…)從棧頂符號(hào)表開始，逐個(gè)向下尋找id的信息O
這里的gen發(fā)出相應(yīng)的代碼增量式翻譯方案?數(shù)組元素存儲(chǔ)在一塊連續(xù)的存儲(chǔ)空間中，以方便快速的訪問它們?n個(gè)數(shù)組元素是0,1,…,n-1進(jìn)行順序編號(hào)的?假設(shè)每個(gè)數(shù)組元素寬度是w，那么數(shù)組A的第i個(gè)元素的開始地址為base+i*w,base是A[0]的相對(duì)地址。?推廣到二維或多維數(shù)組。A[i1][i2]表示第i1行第i2個(gè)
元素。假設(shè)一行的寬度是w1
，同一行中每個(gè)元素
的寬度是w2
，
A[i1][i2]的相對(duì)地址是base+i1
*w1+i2
*w2?
對(duì)于k維數(shù)組A[i1][i2]…[ik]，推廣Obase+i1
*w1+i2
*w2+…+ik
*wk數(shù)組元素的尋址?根據(jù)第j維上的數(shù)組元素的個(gè)數(shù)nj和該數(shù)組每個(gè)元素的寬度w進(jìn)行計(jì)算的，如二維數(shù)組A[i1][i2]的地址base+(i1
*n2+i2)*w?于k維數(shù)組A[i1][i2]…[ik]的地址base+((…(i1
*n2+i2)*n3+i3)…)*nk+ik)*w?有時(shí)下標(biāo)不一定從0開始，比如一維數(shù)組編號(hào)low,low+1,…,high，此時(shí)base是A[low]的相對(duì)地址。計(jì)算A[i]的地址變成base+(i-low)*w?預(yù)先計(jì)算技術(shù)O
改寫成i*w+c的形式，其中c=base-low*w可以在編譯時(shí)刻預(yù)先計(jì)算出來，計(jì)算A[i]的相對(duì)地址只要計(jì)算i*w再加上c就可以了數(shù)組元素的尋址(續(xù))
?按行存放策略和按列存放策略可以推廣到多維數(shù)組中數(shù)組元素的尋址(續(xù))?上述地址的計(jì)算是按行存放的?為數(shù)組引用生成代碼要解決的主要問題O
數(shù)組引用的文法和地址計(jì)算相關(guān)聯(lián)?假定數(shù)組編號(hào)從0開始，基于寬度來計(jì)算相對(duì)地址?數(shù)組引用相關(guān)文法O
非終結(jié)符號(hào)L生成一個(gè)數(shù)組名字加上一個(gè)下標(biāo)表達(dá)式序列數(shù)組引用的翻譯?非終結(jié)符號(hào)L的三個(gè)綜合屬性O(shè)
L.addr指示一個(gè)臨時(shí)變量，計(jì)算數(shù)組引用的偏移量O
L.array是一個(gè)指向數(shù)組名字對(duì)應(yīng)的符號(hào)表?xiàng)l
目的指針，L.array.base為該數(shù)組的基地址O
L.type是L生成的子數(shù)組的類型，對(duì)于任何數(shù)
組類型t，其寬度由t.width給出，t.elem給出其數(shù)組元素的類型數(shù)組引用生成代碼的翻譯方案數(shù)組引用生成代碼的翻譯方案核心是確定數(shù)組引用的地址?
基于數(shù)組引用的翻譯方案，表達(dá)式c+a[i][j]的注釋語法樹及三地址代碼序列?假設(shè)a是一個(gè)2*3的整數(shù)數(shù)組，c、i、j都是整數(shù)O
那么a的類型是array(2,array(3,integer)),a的寬度是24O
a[i]的類型是array(3,integer)，寬度是12O
a[i][j]的類型是整型數(shù)組引用翻譯示例?中間表示?類型與聲明?表達(dá)式的翻譯?控制流與回填運(yùn)行時(shí)刻環(huán)境?if-else語句，while語句?翻譯目標(biāo)：控制流語句翻譯?if-else語句，while語句?需要將語句的翻譯和布爾表達(dá)式的翻譯結(jié)合在一起?布爾表達(dá)式是被用作語句中改變控制流的條件表達(dá)式，通常用來O
改變控制流。布爾表達(dá)式的值由程序到達(dá)的某個(gè)位置隱含地指出。O
計(jì)算邏輯值。可以使用帶有邏輯運(yùn)算符的三地址指令進(jìn)行求值。?布爾表達(dá)式的使用意圖要根據(jù)其語法上下文確定O
跟在關(guān)鍵字if后面的表達(dá)式用來改變控制流O
一個(gè)賦值語句右部的表達(dá)式用來計(jì)算一個(gè)邏輯值O
可以使用兩個(gè)不同的非終結(jié)符號(hào)或其它方法來區(qū)分這兩種使用控制流語句翻譯?將布爾運(yùn)算符作用在布爾變量或關(guān)系表達(dá)式上，構(gòu)成布爾表
達(dá)式?引入新的非終結(jié)符號(hào)B表示布爾表達(dá)式?布爾運(yùn)算符:&&、||、
!?關(guān)系表達(dá)式E1rel
E2?關(guān)系運(yùn)算符：<、<=、=、!=、>、>=?其中布爾運(yùn)算符&&和||是左結(jié)合的，優(yōu)先級(jí)||最低，其次是&&，！最高?表示布爾表達(dá)式的文法布爾表達(dá)式?B1||B2,B1為真，則不用求B2也能斷定整個(gè)表達(dá)式為真?B1&&B2,B1為假，則整個(gè)表達(dá)式肯定為假?如果某些程序設(shè)計(jì)語言允許這種高效的求值方式，則編譯器可以優(yōu)化布爾表達(dá)式的求值過程，只要已經(jīng)求值部分足以確定整個(gè)表達(dá)式的值就可以了。布爾表達(dá)式的高效求值?布爾運(yùn)算符&&、||、!被翻譯成跳轉(zhuǎn)指令。
由跳轉(zhuǎn)位置隱含的指出布爾表達(dá)式的值。?if(x<100||x>200&&x!=y)x=0;短路(跳轉(zhuǎn))代碼?B和S有綜合屬性code，表示翻譯得到的三地址代碼。?B的繼承屬性true和false
，S的繼承屬性next，表示跳轉(zhuǎn)
的位置。?
S.true是一個(gè)地址，用于存放了B為真時(shí)控制流轉(zhuǎn)向的指令標(biāo)號(hào)，S.false同理?S.next也是一個(gè)地址，用于存放緊跟在S代碼之后的指控制流語句翻譯?
語句及文法令標(biāo)號(hào)?B和S有綜合屬性code，表示翻譯得到的三地址代碼。?B的繼承屬性true和false
，S的繼承屬性next，表示跳轉(zhuǎn)控制流語句翻譯?
語句及文法的位置。?幾個(gè)核心函數(shù)回顧：O
newlabel
函數(shù)：生成一個(gè)用于存放標(biāo)號(hào)的臨
時(shí)變量L，返回變量地址；O
label(X)函數(shù)：將下一條指令的標(biāo)號(hào)復(fù)制給參控制流語句翻譯分析數(shù)X；翻譯S→if(B)S1,創(chuàng)建B.true標(biāo)號(hào)，并指向S1的第一條指令。
翻譯S→if(B)S1else
S2,B為
真時(shí)，跳轉(zhuǎn)到S1代碼的第一條指令；當(dāng)B為假時(shí)跳轉(zhuǎn)到S2代碼的第一條指令。然后，控制流從S1或S2轉(zhuǎn)到緊跟在S的代碼后面的三地址指令，該指令由繼承屬性S.next指定。while語句中有個(gè)begin局部變量……控制流語句翻譯分析????布爾表達(dá)式B被翻譯成三地址
指令，生成的條件或無條件轉(zhuǎn)
移指令反映B的值。B→E1
rel
E2，直接翻譯成三地址比較指令，跳轉(zhuǎn)到正確位置。B→B1||B2,如果B1為真，B
一定為真，所以B1.true和B.true相同。如果B1為假，那
就要對(duì)B2求值。因此B1.false
指向B2的代碼開始的位置。B2
的真假出口分別等于B的真假
出口?！紶柋磉_(dá)式的控制流翻譯及分析????控制流語句及布爾表達(dá)式翻譯?布爾表達(dá)式翻譯，a<bif
a<b
goto
B.truegoto
B.false?控制流語句翻譯if(x<100||x>200&&x!=y)x=0;布爾表達(dá)式及控制流語句翻譯示例?在上面的例子中g(shù)otoL3是冗余的?X>200翻譯成
?可以替換成O
減少了一條goto指令O引入一個(gè)特殊標(biāo)號(hào)“fall”(穿越，fallthrough)，表示
不要生成任何跳轉(zhuǎn)指令。?S→if(B)S1
的新語義規(guī)則?對(duì)于if-else和while語句的規(guī)則也將B.true設(shè)為fall避免冗余的goto指令利用“穿越”修改布爾表達(dá)式的語義規(guī)則
注意B.true=fall時(shí)，還得為B1
.true
new一個(gè)labelB1
.false=if(B.false=fall)newlabel()else
B.falseB1
.true=fallB2
.true=B.trueB2
.false=B.falseB.code=if(B.false=fall)then
B1
.code||B2
.code||label(B1
.false)elseB1
.code||B2
.codeB
→B1&&B2帶“穿越”的語義規(guī)則使用標(biāo)號(hào)fall的控制流語句翻譯示例?if(x<100||x>200&&
x!=y)x=0;?改變控制流，跳轉(zhuǎn)O
剛剛前面重點(diǎn)討論，用非終結(jié)符號(hào)B表示此種功能的布爾表達(dá)式以示區(qū)別?
求值O
如x=true,x=a<b?統(tǒng)一處理O使用不同的代碼生成函數(shù)處理表達(dá)式的兩種角色。E.n對(duì)應(yīng)于抽象
語法樹上的表達(dá)式節(jié)點(diǎn)。兩個(gè)函數(shù)：?
jump,對(duì)于出現(xiàn)在S→while(E)S1中的E，調(diào)用E.n.jump(t,f)?
rvalue,對(duì)于出現(xiàn)在S→id=E中的E，在節(jié)點(diǎn)E.n上調(diào)用rvalue。如果E是算術(shù)表達(dá)式，按照算術(shù)表達(dá)式的翻譯生成代碼。如果E是布爾表達(dá)式，如E1&E2，首先為E生成跳轉(zhuǎn)代碼，然后在跳轉(zhuǎn)代碼的真假出口分別將true或false賦給一個(gè)新的臨時(shí)變量t。布爾表達(dá)式的兩個(gè)功能?賦值語句x=a<b&&c<d示例?為布爾表達(dá)式和控制流語句生成目標(biāo)代碼的關(guān)鍵問題：某些跳轉(zhuǎn)指令應(yīng)該跳轉(zhuǎn)到哪里?例如：if(B)SO
按照短路代碼的翻譯方法，B的代碼中有一些跳轉(zhuǎn)指令在B為假時(shí)執(zhí)行，O
這些跳轉(zhuǎn)指令的目標(biāo)應(yīng)該跳過S對(duì)應(yīng)的代碼,生成這些指令時(shí)，S的代碼尚未生成，因此目標(biāo)不
溫馨提示
- 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- JJF 2201-2025膠體金免疫層析分析儀校準(zhǔn)規(guī)范
- JJF 2197-2025頻標(biāo)比對(duì)器校準(zhǔn)規(guī)范
- 健身俱樂部合同范本
- 分成合同范本上樣
- 蝦皮合作合同范本
- 代家出租民房合同范本
- 企業(yè)股票承銷合同范本
- 加盟福田汽車合同范本
- 全新拖拉機(jī)買賣合同范本
- 獸藥欠賬銷售合同范本
- 2025年湘教版二年級(jí)美術(shù)下冊(cè)計(jì)劃與教案
- GB/T 4706.30-2024家用和類似用途電器的安全第30部分：廚房機(jī)械的特殊要求
- 2024年岳陽職業(yè)技術(shù)學(xué)院單招職業(yè)技能測試題庫及答案解析
- 消防安全管理制度完整版完整版
- 《朝天子詠喇叭》教學(xué)設(shè)計(jì)
- 《金融學(xué)基礎(chǔ)》實(shí)訓(xùn)手冊(cè)
- 稅收基礎(chǔ)知識(shí)考試題庫
- 1t燃?xì)庹羝仩t用戶需求(URS)(共13頁)
- 廣發(fā)證券分支機(jī)構(gòu)人員招聘登記表
- 機(jī)電一體化系統(tǒng)設(shè)計(jì)課件姜培剛[1]
- 《質(zhì)量管理小組活動(dòng)準(zhǔn)則》2020版_20211228_111842
評(píng)論
0/150
提交評(píng)論