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

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

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

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

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

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

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

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

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