CML指針類(lèi)型編譯程序的設(shè)計(jì)與實(shí)現(xiàn).pdf

1、本文主要介紹了如何在CMI語(yǔ)言中實(shí)現(xiàn)帶指針類(lèi)型的編譯器。 指針類(lèi)型在編譯器中的實(shí)現(xiàn)主要涉及到語(yǔ)法分析、語(yǔ)義分析、中間代碼生成以及存儲(chǔ)空間的管理。 采用自頂向下的方法的一種：LL(1)分析方法。 針對(duì)指針類(lèi)型在語(yǔ)法分析階段主要工作： 指針類(lèi)型的定義在語(yǔ)法是否正確； 指針變量的使用在語(yǔ)法上是否正確。 指針類(lèi)型定義的分析是建立在普通類(lèi)型定義分析的基礎(chǔ)之上，處理的規(guī)則很簡(jiǎn)易，如果在類(lèi)型定義時(shí)是指針

2、類(lèi)型，向前看TOKEN必須是標(biāo)識(shí)符。指針變量的使用的分析很簡(jiǎn)單，對(duì)于指針變量的使用，前面必定是一個(gè)標(biāo)識(shí)符，不管它是變量標(biāo)識(shí)符還是域名標(biāo)識(shí)符，變量標(biāo)識(shí)符和域名標(biāo)識(shí)符只是決定了該指針類(lèi)型是一個(gè)普通的指針類(lèi)型，還是一個(gè)記錄類(lèi)型中的一項(xiàng)。 在詞法分析和語(yǔ)法分析之后，編譯器要進(jìn)行的工作就是語(yǔ)義上的分析。在語(yǔ)義分析時(shí)要結(jié)合各種符號(hào)表技術(shù)以進(jìn)行查找。要判斷指針類(lèi)型在語(yǔ)義上是否正確，主要要解決以下問(wèn)題： 指針類(lèi)型的定義在語(yǔ)義上是否正確；

3、 指針變量的使用在語(yǔ)義上是否正確。 指針變量語(yǔ)義上的檢查主要工作在于首先檢查該變量是否是指針類(lèi)型，如果是指針類(lèi)型，它的用法在語(yǔ)義上正確嗎?對(duì)于第一個(gè)問(wèn)題，該變量是指針類(lèi)型嗎?這個(gè)問(wèn)題很好解決，只要在符號(hào)表中進(jìn)行查找，如果找到且是指針類(lèi)型，表明正確，其余均為錯(cuò)誤。指針變量的使用在語(yǔ)義上是否正確要進(jìn)行迭代，即每次循環(huán)在變量后面如果有'^'就把該符號(hào)消耗掉，同時(shí)在符號(hào)表中檢查它是否是指針類(lèi)型。另外在這個(gè)階段，還需要涉及超前聲明

4、和回填。 指針類(lèi)型主要用在賦值語(yǔ)句和作為過(guò)程的參數(shù)時(shí)使用。它和一般類(lèi)型檢查類(lèi)似。首先判斷是否是指針類(lèi)型，然后把它們所指向的目標(biāo)類(lèi)型的指針進(jìn)行比較，如果相同，就表明是等價(jià)的，否則報(bào)錯(cuò)。 存儲(chǔ)空間的管理主要由棧式分配和堆式分配兩種方法。本文主要對(duì)堆式分配進(jìn)行了介紹。堆區(qū)空間主要用于存放動(dòng)態(tài)申請(qǐng)空間變量的值。凡是動(dòng)態(tài)申請(qǐng)的空間都分配到堆區(qū)中，對(duì)于我們的CML語(yǔ)言來(lái)講就是指針類(lèi)型的分配。 動(dòng)態(tài)存儲(chǔ)管理的基本問(wèn)題是系統(tǒng)如何

5、應(yīng)用戶(hù)提出的“請(qǐng)求”分配內(nèi)存?又如何回收那些用戶(hù)不再使用而“釋放”的內(nèi)存，以備于新的“請(qǐng)求”產(chǎn)生時(shí)重新進(jìn)行分配?對(duì)于響應(yīng)用戶(hù)提出的分配內(nèi)存的請(qǐng)求，只需要在堆區(qū)中查找滿(mǎn)足要求的空間即可，對(duì)于釋放，在釋放空間時(shí)要進(jìn)行相鄰空閑空間的合并，以減少碎片。這就要求在進(jìn)行釋放時(shí)，要進(jìn)行相鄰空間的檢查，看是否是自由空間，如果是，就進(jìn)行合并，如果不是，則簡(jiǎn)單的釋放。具體有4種情況： 釋放塊的左、右鄰區(qū)均為占用塊，此時(shí)只要作簡(jiǎn)單的釋放即可。

6、 釋放的左鄰區(qū)為空閑塊，而右鄰區(qū)為占用塊：由于釋放塊的頭部和左鄰空閑塊的底毗鄰，因此只要改變左鄰空閑塊的結(jié)點(diǎn)；增加結(jié)點(diǎn)的size域的值且重新設(shè)置結(jié)點(diǎn)。 釋放的右鄰區(qū)為空閑塊，而左鄰區(qū)為占用塊。由于釋放塊的底部和右鄰空閑塊的頭部毗鄰，因此，當(dāng)表中結(jié)點(diǎn)由原來(lái)的右鄰空閑塊變成合并后的大空閑塊時(shí)，結(jié)點(diǎn)的底部位置不變，但頭部要變，由此，鏈表中的指針也要變。 釋放塊的左、右塊均為空閑塊：為使三個(gè)空閑塊成為一個(gè)大的結(jié)點(diǎn)留在可利用空間表

7、中，只要增加左鄰空閑塊的space容量，同時(shí)在鏈表中刪除右鄰空閑塊的結(jié)點(diǎn)即可。 在本文中沒(méi)有涉及垃圾回收的問(wèn)題。垃圾回收是更現(xiàn)代的語(yǔ)言如JAVA、C＃的一個(gè)重要特征。垃圾收集中大量的工作都由垃圾算法來(lái)完成。任何一種垃圾收集算法都必須做兩件基本的工作：首先，它必須檢測(cè)到垃圾對(duì)象的存在；其次，它必須回收垃圾對(duì)象所占據(jù)的堆空間，并將堆空間歸還給系統(tǒng)，讓?xiě)?yīng)用程序能夠繼續(xù)使用。一般來(lái)說(shuō)，實(shí)現(xiàn)垃圾檢測(cè)的方式是：定義一組根結(jié)點(diǎn)，并從根結(jié)點(diǎn)出發(fā)

8、檢查其他結(jié)點(diǎn)的可到達(dá)性。如果存在一條引用路徑，使得執(zhí)行中的程序能夠從根結(jié)點(diǎn)出發(fā)訪(fǎng)問(wèn)到被檢查的對(duì)象，則該對(duì)象就是“可到達(dá)”的。所有從根結(jié)點(diǎn)可到達(dá)的對(duì)象都被認(rèn)為是“活”對(duì)象，而不可到達(dá)的對(duì)象則認(rèn)為是垃圾，因?yàn)樗鼈儾粫?huì)再對(duì)程序未來(lái)的執(zhí)行造成任何影響。 將活對(duì)象和垃圾區(qū)分開(kāi)來(lái)有兩種算法：引用計(jì)數(shù)和遍歷。引用計(jì)數(shù)型垃圾收集器會(huì)在堆上的每個(gè)對(duì)象中保存一個(gè)計(jì)數(shù)器，用這個(gè)計(jì)數(shù)器來(lái)記錄指向該對(duì)象的引用個(gè)數(shù)，并以此來(lái)區(qū)分活對(duì)象和垃圾對(duì)象。另一方面遍