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

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

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

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

4、和回填。 指針類型主要用在賦值語句和作為過程的參數(shù)時(shí)使用。它和一般類型檢查類似。首先判斷是否是指針類型，然后把它們所指向的目標(biāo)類型的指針進(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語言來講就是指針類型的分配。 動(dòng)態(tài)存儲(chǔ)管理的基本問題是系統(tǒng)如何

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

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

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

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