編譯原理課件第八章

1、第八章 符號表編譯過程中編譯程序需要不斷匯集和反復查證出現在源程序中各種名字的屬性和特征等有關信息。這些信息通常記錄在一張或幾張符號表中。符號表的每一項包含兩部分，一部分是名字（標識符），另一部分是此名字的有關信息。每個名字的有關信息一般指種屬（如簡單變量、數組、過程等）、類型（如整、實、布爾等）等等。這些信息將使用于語義檢查、產生中間代碼以及最終生成目標代碼等不同階段 。編譯過程中，每當掃描器識別出一個單詞后，編譯程序就查閱符號表，看它是否已在其中。如果它是一個新名就將它填進表里。它的有關信息將在詞法分析和語法-語義分析過程中陸續(xù)填入符號表中所登記的信息在編譯的不同階段都要用到。在語義分析中

2、，符號表所登記的內容將用于語義檢查（如檢查一個名字的使用和原先的說明是否相一致）和產生中間代碼。在目標代碼生成階段，當對符號名進行地址分配時，符號表是地址分配的依據。對于一個多遍掃描的編譯程序，不同遍所用的符號表也往往各有不同。因為每遍所關心的信息各有差異。 符號表的組織和使用概括地說，一張符號表的每一項（或稱入口）包含兩大欄（或稱區(qū)段，字域），即名字欄和信息欄。表格的形式是：名字欄（NAME） 信息欄（INFORMATION） 第1項（入口1） 第2項（入口2） 第n項（入口n） 信息欄通常包含許多子欄和標志位，用來記錄相應名字的種種不同屬性。由于查填符號表一般都是通過匹配名字來實現的。名字

3、欄也稱主欄。主欄的內容稱為關鍵字（key word）。符號表雖然原則上說，使用一張統(tǒng)一的符號表也就夠了，但是，許多編譯程序按名字的不同種屬分別使用許多符號表，如常數表、變量名表、過程名表等等。這是因為，不同種屬名字的相應信息往往不同，并且信息欄的長度也各有差異的緣故。因而，按不同種屬建立不同的符號表在處理上常常是比較方便的 。對于編譯程序的符號表來說，它所涉及的基本操作大致可歸納為五類：1、對給定名字，確定此名是否在其中；2、填入新名；3、對給定名字，訪問它的有關信息；4、對給定名字，填寫或更新它的某些信息；5、刪除一個或一組無用的項。 符號表符號表最簡單的組織方式是讓各項各欄所占的存儲單元的

4、長度都是固定的。這種項欄長度固定的表格易于組織、填寫和查找。對于這種表格，每一欄的內容可直接填寫在有關的區(qū)段里。例如，有些語言規(guī)定標識符的長度不得超過8個字符，于是，我們就可以用兩個機器字作為主欄（假定每個機器字可容四個字符）每個名字直接填寫在主欄中。若標識長度不到8個字符，則用空白符補足。這種直接填寫式的表格形式如下： 符號表NAMEINFORMATIONSAMPLEWEIGHT符號表有許多語言對標識符的長度幾乎不加限制，或者說，標識符的長度范圍甚寬。譬如說，最長可容許由100個字符組成的名字。在這種情況下，如果每項都用25個字作主欄，則勢必會大量浪費存儲空間。因此，最好用一個獨立的字符串數

5、組，把所有標識符都存放在其中，在符號表的主欄放一個指示器和一個整數。指示器指出標識符在字符串數組中的位置；整數代表此標識符的長度。這樣，符號表的結構就如下圖所示 。符號表LOOPSAMPLEWEIGHTNAMEINFORMATION 6符號表字符串數組 符號表項的排列與查找符號表作為一個多元組，表中元組之間的排列組織是構造符號表的重要成分。在編譯程序的整個工作過程中，符號表被頻繁也用來建立表項，找查表項，填充和引用表項的屬性。因此表項的排列組織對該系統(tǒng)運行的效率起著十分重要的作用。在“數據結構”技巧的討論中提供了很多有關多元組表格的組織方法和它們有關的操作算法。而在編譯程序中，符號表項的組織傳

6、統(tǒng)上采用三種構造方法。即線性法，二分法及散列法。1、線性組織 這種方法規(guī)定符號表項中按它的符號被掃描到的先后順序建立。例如有一程序中出現符號的情況如下：abadcb符號屬性habdcP線性組織2、排序組織及二分法 語言中任何符號都是由一個或幾個字符拼寫而成的，在機器中是用字符代碼（通常是ASCII或EBCDIC代碼）表達。因每一個符號在機器內都是由這種字符代碼串來表示。排序組織的符號表，就是在符號表中的表項按其符號的字符代碼串（可以看成一個整數值）的值的大小從大到?。ɑ驈男〉酱螅┡帕械?。對上述中的符號出現情況按排序組織得到的符號表將如圖。排序表符號屬性habcdP散列組織 對于表格處理來說，根

7、本問題在于如何保證查表與填表兩方面的工作都能高效地進行。對于線性表來說，填表快，查表慢。而對于二分法而言，則填表慢，查表快。雜湊法是一種爭取查表、填表兩方面都能高速進行的統(tǒng)一技術。這種辦法是：假定有一個足夠大的區(qū)域，這個區(qū)域是以填寫一張含N項的符號表。我們希望構造一個地址函數H，對任何名字SYM，H（SYM）取值于0至N1之間。這就是說，不論對SYM查表或填表，我們都希望能從H（SYM）獲得它的表中的位置。例如，我們用無符號整數作為項名，令N=17，把H（SYM）定義為SYMN的余數。那么，名字09將被置于表中的第9項，34 將被置于表中的第0項，171將被置于表中的第1項 。散列組織對于地址

8、函數H有兩點要求：第一，函數的計算要簡單、高效；第二，函數值能比較均勻地分布在0至N1之間。例如，若取N為質數，把H（SYM）定義為SYMN的余數就是一個相當理想的函數。構造函數H的辦法很多，通常是將符號名的編碼雜湊成0N1間的某一個值。因此，地址函數H也常常稱為雜湊函數。 散列組織注意，雜湊函數的選擇往往和具體計算機系統(tǒng)的字符編碼有關。如果是對數目確定的已知符號名，我們可以通過試驗，精挑細選，構造出一個一一對應函數。如果雜湊函數是用來產生用戶的標識符表的，由于用戶使用標識是隨機的，而且標識符的個數也是無限的（雖然在一個源程序中所有的標識符的全體是有限的），因此，企圖構造一一對應的函數當然是徒

9、勞的。在這種情況下，除了希望函數值的分布比較均勻之外，我們還應設法解決“地址沖突”的問題。散列組織以N=17，H（SYM）為SYMN的余數為例，由于H（05）= H（22）=5，若表格的第5項已為05所占，那么，后來的22應放在哪里呢？散列組織散列組織解決地址沖突的辦法很多。我們這里只介紹一種最簡單的線性查填解決法。這種辦法的填表過程是：對任何名字SYM，令H（SYM）=h，若第h項為空，則直接把SYM填入。若h項不空，則看第h+1（mod N）項，為空則填入，否則繼續(xù)考察第h+2（mod N）項，如此反復，直至或者把SYM填為第h+i（mod N）項；或者到達h+N=h（mod N）（說明表區(qū)已滿），無法再填入。查表過程與此相仿：令H（SYM）=h，若第h項為空，則說明