編譯原理簡明教程（第3版）-課件 第11章 面向?qū)ο笳Z言的編譯

新工科建設(shè)·計算機類系列教材

免費提供編譯原理1學(xué)分：編譯原理簡明教程（第3版）馮秀芳

崔冬華

王會青

主編電子工業(yè)出版社

2024年出版課程教材6目錄第一章概述第二章形式語言理論基礎(chǔ)第三章自動機理論基礎(chǔ)第四章詞法分析第五章語法分析—自頂向下分析方法第六章語法分析—自底向上分析方法第七章語義分析及中間代碼的生成第八章代碼優(yōu)化第九章目標(biāo)代碼的生成第十章符號表和出錯處理第十一章面向?qū)ο笳Z言的編譯第十二章

并行編譯技術(shù)第十三章

軟件構(gòu)造32024/11/64學(xué)習(xí)目標(biāo)11面向?qū)ο笳Z言的編譯

了解和掌握面向?qū)ο蟮幕靖拍睢㈩惡统蓡T的屬性構(gòu)造以及面向?qū)ο缶幾g器的特性了解和掌握面向?qū)ο笳Z言的編譯了解和掌握面向?qū)ο蟮膭討B(tài)存儲分配

目錄11.1概述11.2面向?qū)ο笳Z言的語法結(jié)構(gòu)11.3面向?qū)ο蟮膭討B(tài)存儲分配511.1概述611.1.1面向?qū)ο笳Z言的基本特征對象之間通過消息相互通信封裝繼承多態(tài)性

11.1概述711.1.2類和成員的屬性構(gòu)造聲明類的文法規(guī)則：

(1)dec→classdec(2)classdec→classclass_id{memberspec}|classclass_id:class_id{memberspec}(3)memberspec→memberdecmemberspec|memberdec(4)memberdec→accessspec:typevar;|accessspec:funcdec;(5)accessspec→private|protected|public(6)type→comtype|classtype(7)classtype→ID(8)var→ID|ObjDef(9)funcdec→typeID(paramlist);|typeID(paramlist)funcbody;|ID(paramlist);|ID(paramlist)procbody;類名的屬性和結(jié)構(gòu)

8

類名的特有屬性包括種類、繼承鏈和類的成員集。(1)種類：種類屬性用于區(qū)分有效類、延遲類、繼承類、基類等。如果一個類定義的全部成員中至少有一個成員尚未被具體實現(xiàn)，該類就是一個不能用來創(chuàng)建對象的類，我們稱之為延遲類。如果一個類定義中的全部成員都已經(jīng)按照某種方式具體實現(xiàn)，該類就是一個可以用來創(chuàng)建對象的類，我們稱之為有效類。類名的屬性和結(jié)構(gòu)

9

類名的特有屬性包括種類、繼承鏈和類的成員集。(2)繼承鏈：對于繼承類來說，可以有若干個父類(被直接繼承的類)，并且它們在類的定義中的次序必須是嚴格確定的

。類名的屬性和結(jié)構(gòu)

10

這兩個成員集的具體實現(xiàn)有兩種方式：①這些成員(包括屬性和方法)名的符號表項與它們的類名的符號表項放在一張符號表中，而這兩個成員集中存放的是指向各自對應(yīng)的符號表項的指針；②每個類構(gòu)造兩張子符號表，即類的屬性成員符號表和類的方法成員符號表，這兩個成員集中存放這些成員名的符號表項。類名的特有屬性包括種類、繼承鏈和類的成員集。(3)類成員集：類具有屬性成員和方法成員，可以用兩張成員表來表示。類成員名的屬性及其結(jié)構(gòu)

11

類的定義中，屬性成員是某個類型的實例，這種屬性成員的類型有兩種方式：其一，定義該屬性成員的類型在包含該成員的類型之外的另一個類型中進行定義；其二，定義該屬性成員的類型在包含該成員的類型之內(nèi)的一個嵌套的類型定義。如果屬性成員的類型嵌套定義在屬性成員所在的類中，屬性的結(jié)構(gòu)就會出現(xiàn)嵌套的情況，為了避免下推處理，當(dāng)一個類中有多個嵌套類型定義的屬性成員時，這些局部定義的類型名的符號表項可以組成一張符號表，類成員名的屬性及其結(jié)構(gòu)

12

類成員的特有屬性如下。①類成員的導(dǎo)入屬性。通常，類中的成員包括從父類繼承的成員和該類自定義的成員，當(dāng)從父類中繼承的成員被重定義或重命名時，需要給出相應(yīng)的標(biāo)志。類成員名的屬性及其結(jié)構(gòu)

13

②類成員的訪問權(quán)限屬性。類成員被外部對象訪問的權(quán)限有三種：類的公有成員、類的私有成員和類的保護成員。屬性和方法的私有性是由編譯器的類型檢查階段來保證的，在類的成員符號表項中，一個域用來指出該成員的訪問權(quán)限。類成員名的屬性及其結(jié)構(gòu)

14

③類成員的延遲屬性。如果一個類定義的全部成員中至少有一個成員尚未被具體實現(xiàn)，該類就是一個不能用來創(chuàng)建對象的類，我們稱之為延遲類，尚未被具體實現(xiàn)的成員，我們稱之為延遲成員。在成員符號表項中用一個域指出該成員是類的延遲成員，還是類的有效成員。11.1.3面向?qū)ο缶幾g程序的特點

15

詞法和語法分析

由于類本身是一種數(shù)據(jù)類型，它也作為符號表中的一個表項，但面向?qū)ο蠼＞哂休^高的抽象層次，其語義處理與語法分析的關(guān)系更密切，整個分析流程、編譯程序內(nèi)部數(shù)據(jù)結(jié)構(gòu)的組織和運行時的環(huán)境都和傳統(tǒng)的編譯程序有一定差別。語義分析

由于類及其對象具有的封裝、繼承、多態(tài)性等語言特征，不僅使靜態(tài)語義分析更為復(fù)雜，也使運行時環(huán)境更為復(fù)雜。

內(nèi)存管理

11.2面向?qū)ο笳Z言的語法結(jié)構(gòu)1611.2.1單一繼承

1．屬性編譯在僅支持單繼承的語言中，每個類最多只能繼承一個父類，子類不僅可以訪問該類中定義的新方法，還可以訪問父類中的方法?？梢圆捎孟旅鎯煞N方式處理。①簡單的前綴技術(shù)來處理。如果類B是由類A擴展得到的，則將類B中從父類A繼承過來的屬性放在類B符號表的開始處，并保持這些屬性與類A符號表中相同的順序；而類B中定義的特有屬性放在繼承屬性的后面。②在符號表中，對子類進行處理時，僅給出在子類中直接定義的屬性，而對父類中定義的成員，則通過在子類的符號表項中增加指向父類的指針來表示，當(dāng)需要對父類屬性進行相關(guān)處理時，可根據(jù)此指針獲取父類的相關(guān)信息。11.2面向?qū)ο笳Z言的語法結(jié)構(gòu)1711.2.1單一繼承

2．方法編譯編譯一個方法類似于編譯一個過程：方法被轉(zhuǎn)換成駐存在指令空間中一個特定地址的機器代碼。在語義分析階段，每個對象的符號表項中有一個指向其類符號表的指針，每個類的符號表有一個指向其父類的指針和一張方法的鏈表，每一個方法都有一個地址。①對于靜態(tài)方法，一些面向?qū)ο笳Z言允許將方法聲明為靜態(tài)的，調(diào)用c.f(

)(其中c是類C的對象)時執(zhí)行的機器代碼取決于變量c的類型。

②對于動態(tài)方法，如果類B中的方法f是從父類A中繼承的，且類B對方法f進行了重載，則編譯期間，調(diào)用f時無法確定是類B的一個對象還是類A的一個對象。為了解決該問題，類符號表必須包含一個向量，該向量中每個方法名對應(yīng)一個方法實例。

11.2面向?qū)ο笳Z言的語法結(jié)構(gòu)1811.2.2多重繼承在支持多重繼承的語言中，一個類可以有多個直接父類。使用多重繼承的目的在于使一個對象同時具有多個對象的表達能力。

例如，假定有類M包含屬性m1、m2和方法f1、f2，類E包含屬性e1和方法f3、f4，類T繼承了類M和類E，但增加了屬性t1，并且重新定義了方法f2、f4，增加了方法f5。

11.2面向?qū)ο笳Z言的語法結(jié)構(gòu)1911.2.3多態(tài)性當(dāng)類B繼承類A并且該語言允許“類B的指針”類型的指針能夠賦值給一個“類A的指針”類型的變量時，那么該語言支持多態(tài)性。多態(tài)性的實現(xiàn)要求一種新的操作，即指針supertyping，它將指向子類B對象的指針轉(zhuǎn)換為指向其父類A對象的指針。假定類A有屬性a1、a2和方法f1、f2，類B是類A的子類，類B通過增加屬性b1和方法f3來擴展A類，例如：ClassB*b=…;ClassA*a=b;在上面的語句中，第二行代碼被翻譯成ClassA*a=covert_ptr_to_B_to_ptr_to_A(b);11.2面向?qū)ο笳Z言的語法結(jié)構(gòu)2011.2.4動態(tài)綁定

動態(tài)綁定是語言處理多態(tài)的機制，類的成員函數(shù)的行為能根據(jù)調(diào)用它的對象類型自動做出適應(yīng)性調(diào)整，而且調(diào)整發(fā)生在程序運行時。假定類A包含屬性a1、a2和方法f1、f2，類B是類A的子類，類B增加屬性b1和方法f3，并重載類A中的方法f2。例如：

a:A；

b:B；a是多態(tài)引用，因而根據(jù)多態(tài)引用規(guī)則：a可引用類B的對象，對方法f2的動態(tài)綁定情況如下：

a.f2(

)引用類A的對象時，綁定類A定義的方法f2；當(dāng)執(zhí)行a:=b之后，綁定類B重新定義的方法f2。

b.f2(

)只能綁定類B重新定義的方法f2。11.2面向?qū)ο笳Z言的語法結(jié)構(gòu)2111.2.4動態(tài)綁定

Java語言包括了一種擴展，這種擴展由所謂的接口組成。接口與類相似，由許多方法說明組成，但接口只有常量和抽象的方法。接口不能像對象那樣實例化，但可以聲明接口類型的Java變量，并從它們的接口聲明中調(diào)用方法，該Java變量實質(zhì)上就是指向?qū)ο蟮闹羔?。編譯程序必須為類所實現(xiàn)的每一個接口建立單獨的符號表，每個符號表只包含該接口聲明中方法的入口，由入口引用對象類型的方法。

11.3面向?qū)ο蟮膭討B(tài)存儲分配2211.3.1對象的存儲區(qū)管理方式對象的存儲管理采用了3種模型：靜態(tài)存儲區(qū)管理、棧式存儲區(qū)管理、堆式存儲區(qū)管理。在靜態(tài)模型中，程序裝入或開始執(zhí)行時為所有對象一次分配所有空間，一個實體在整個軟件運行過程中最多只能與一個運行時對象聯(lián)系。在棧式模型中，一個實體在運行時可以相繼與多個對象聯(lián)系，它以先進后出的方式分配和釋放對象。在堆式模式中，存儲分配是完全動態(tài)的，對象通過顯式的請求動態(tài)創(chuàng)建，堆式模型最具有通用性，它是面向?qū)ο蟮挠嬎闼枰摹?1.3面向?qū)ο蟮膭討B(tài)存儲分配2311.3.2靜態(tài)模型和棧式模型廢棄單元的回收在靜態(tài)模型下，每個對象只與一個實體聯(lián)系，執(zhí)行時只要實體存在，就要保留對象的空間，因此一般情況下靜態(tài)模型不存在廢棄單元回收的問題，在棧式模型下，與某一實體聯(lián)系的對象可以在棧中分配。在分程序結(jié)構(gòu)的語言中，聲明實體的同時為對象分配空間，整個程序可以只使用一個棧。例如，每當(dāng)執(zhí)行一次函數(shù)調(diào)用時，就將該函數(shù)運行所需的所有局部變量進棧，在棧頂為該函數(shù)建立運行的工作區(qū)，并且每當(dāng)一個函數(shù)執(zhí)行結(jié)束時，它在棧頂?shù)墓ぷ鲄^(qū)退棧，該函數(shù)運行所占用的空間得到了釋放，釋放的空間回收后可提供給下次調(diào)用的函數(shù)使用。11.3面向?qū)ο蟮膭討B(tài)存儲分配2411.3.3堆式模型廢棄單元的回收

堆中分配且通過任何程序變量形成的指針鏈都無法到達的對象稱為不可到達的對象。不可到達的對象是廢棄單元，需要回收。廢棄單元的回收不是由編譯器完成的，而是由運行時系統(tǒng)完成的，運行時系統(tǒng)是與編譯好的代碼連接在一起的一些支持程序。廢棄單元回收技術(shù)主要有：標(biāo)記-清掃技術(shù)引用計數(shù)技術(shù)復(fù)制式收集分代收集11.3面向?qū)ο蟮膭討B(tài)存儲分配2511.3.3堆式模型廢棄單元的回收1、標(biāo)記-清掃技術(shù)實體和堆分配的對象構(gòu)成了一個有向圖，每一個實體是圖中的一個根。如果從某個根節(jié)點r出發(fā)，存在由有向邊r→…→n組成的一條路徑，則稱這個結(jié)點n是可到達的對象，圖搜索算法可以標(biāo)記出所有可到達的對象。2、引用計數(shù)技術(shù)每一個對象都設(shè)置了一個統(tǒng)計量，用于對該對象的引用進行計數(shù)，該統(tǒng)計量稱為對象的引用計數(shù)。它與每個對象存儲在一起，當(dāng)該引用計數(shù)為0時，對象可以被回收。

引用計數(shù)技術(shù)實現(xiàn)簡單，但它存在兩個主要的問題。①無法回收構(gòu)成環(huán)的垃圾；②增加引用計數(shù)所需的操作代價(時間和空間)非常大。11.3面向?qū)ο蟮膭討B(tài)存儲分配2611.3.3堆式模型廢棄單元的回收

3、復(fù)制式收集堆中的可到達部分是一個有向圖，堆中的對象是圖中的結(jié)點，指針是圖中的邊，每一個原對象在圖中是一個根。復(fù)制式垃圾收集遍歷這個圖(稱為源空間)，并在堆的新區(qū)域(稱為目標(biāo)空間)建立一個同構(gòu)的副本。副本目標(biāo)空間是緊湊的，它占據(jù)連續(xù)的、不含碎片的存儲單元。原來指向源空間的所有的根在復(fù)制之后變成指向目標(biāo)空間副本，在此之后，整個源空間便成為不可達的。11.3面向?qū)ο蟮膭討B(tài)存儲分配2711.3.3堆式模型廢棄單元的回收

4、分代收集將堆劃分成若干“代”，最年輕的(即最近分配的)對象屬于G0代，所有屬于G1代的對象都比G0