編譯原理陳火旺版8章8

第八章符號表8.1符號表的組織與作用一、符號表的作用

一張符號表的每一項包含兩大欄,即名字欄和信息欄。表格形式如下所示：名字欄（Name）信息欄（Information）…………第一項（入口1）第二項（入口2）第n項（入口n）

名字欄用來存放標識符或其內(nèi)部碼；信息欄包含許多子欄和標志位，用來記錄與該項名字相對應(yīng)的種種不同屬性。（5）從表中刪除一個或一組名字。在整個編譯期間，對于符號表的訪問可概括為如下幾類操作：（1）對給定名字，查詢此名是否已在表中；（2）往表中填入一個新名字；（3）對給定名字，訪問它的相關(guān)信息；（4）對給定名字，往表中填寫或更新它的某些信息;二、符號表的組織方式

1、各項各欄所占存儲單元的長度固定

2、間接方式安排名字欄poolelpmasNAMEINFORMATION?,6?,4pool4elpmas6NAMEINFORMATION??如果各種名字所需的信息（INFORMATION）空間長短不一，那么，我們可把一些共同屬性直接登記在符號表的信息欄中，而把某些特殊屬性登記在別的地方，并在信息欄中附設(shè)一指示器，指向存放特殊屬性的地方。例如：對于數(shù)組標識符專門開辟一個信息表區(qū)，即為數(shù)組信息表也稱為內(nèi)情向量表維數(shù)首地址界差d1???界差dn上界I1???上界In下界U1???下界Un內(nèi)情向量表在符號表的地址欄中存入符號表與內(nèi)情向量表連接入口地址???NAMEINFORMATIONCAT地址??a?符號表（1）把每一項置于連續(xù)的K個存儲單元中，從而給出一張K*N個存儲單元的表。

（2）把整個符號表分成M個子表，每個子表含N項。假定子表Ti的每一項所需的字數(shù)為Ki，那么，K=K1+…+Km。對于任何i,T1[i],…Tm[i]的并置就構(gòu)成符號表第i項的全部內(nèi)容。一張可容納N項的符號表在存儲器中的兩種表示方式：T1T2T3T4N1N2N3K1K2K3K4K=K1+K2+K3+K4例8.1FORTRAN符號表程序段：SUBROUTINEINCWAP(M,N)10K=M+1M=M+4N=KRETURNEND主要表格見p2258.2整理與查找一、線性表2、提高查找效率的辦法：給每一項附設(shè)一個指示器，這些指示器把所有的項按“最新最近”訪問原則連接成一條鏈，這條鏈的第一個元素所指的項是最新最近被查詢過的項，第二個元素所指的項是次新近被查詢過的項，諸如此類。每當填入新項時，總讓鏈頭指向最新項，含有這種鏈條的線性表叫做自適應(yīng)線性表。1、線性表介紹符號表的三種構(gòu)造法和處理法：線性查找、二叉樹、雜湊技術(shù)。???BC???I???XYZ???J1INFORMATIONNAME項數(shù)1234AVAILABLE線性符號表平均查找次數(shù)n/2二、對折查找與二叉樹（3）若要查找的項大于中項，則就到[n/2]+2~n的各項中去查找。在造表的同時把表格中的項按名字的“大小”順序整理排列。所謂名字的“大小”通常是指名字的內(nèi)碼二進制。對于經(jīng)順序化的表格的查找可用對折法。對折法的查找方法如下：（1）首先把要查找的項和中項（即第[n/2]+1項）作比較，若相等，則宣布查找成功。（2）若要查找的項小于中項，則繼續(xù)在1~[n/2]的各項中去查找。順序化的線性符號表???XYZ???J1???I???BCINFORMATIONNAME項數(shù)1234AVAILABLE查找次數(shù)不超過1+log2n

二叉樹的形成過程如下：令第一個碰到的名字作為“根”結(jié)點，它的左、右指示器均置為空，當要加入新結(jié)點時，首先把它和根結(jié)點的值作比較，小者放在右枝上，大者放在左枝上。如果根結(jié)點的左（右）枝已成子樹，則讓新結(jié)點和子樹的根再作比較。重復上述步驟，直至把新結(jié)點插入使它成為二叉樹的一個端末結(jié)點（葉）為止。把符號表組織成一棵二叉樹(二叉排序樹）令每項是一個結(jié)點，每個結(jié)點附設(shè)兩個指示器欄，一欄為LEFT（左枝），令一欄為RIGHT（右枝）。每個結(jié)點的主欄內(nèi)碼值被看成是代表該結(jié)點的值。要求：任何結(jié)點P右枝的所有結(jié)點值均應(yīng)小于結(jié)點P的值，而左枝的任何結(jié)點值均應(yīng)大于結(jié)點P的值。???I???BC???XYZ???J1INFORMATIONNAME項數(shù)1234AVAILABLEJ1根LEFTRIGHT00?0XYZ00BC0?0I0?三、雜湊技術(shù)

1、假定有一個足夠大的區(qū)域，這個區(qū)域用來填寫一張含N項的符號表。構(gòu)造一個地址函數(shù)H，對任何名字，H函數(shù)的取值于0至N-1之間。即不論對此項查表或填表，都能從H函數(shù)中獲得它在表中的位置。2、對地址函數(shù)H有兩點要求：（1）函數(shù)的計算要簡單、高效；（2）函數(shù)值能比較均勻的分布在0至N-1之間。3、構(gòu)造函數(shù)H的辦法：直接地址法、數(shù)字分析法、平方取中法、折疊法、除留余數(shù)法、隨機數(shù)法4、解決地址沖突的辦法：開放地址法、再哈希法、鏈地址法、建立一個公共溢出區(qū)3、填入一個新的項的過程：（1）先計算出H函數(shù)的值h（在0與N-1之間），將HASHTABLE[h]的值賦給P（若未曾有雜湊值為h的項名填入過，則將P置空）。（2）然后將HASHTABLE[h]置為AVAILABLE，再把新名及其鏈接指示器的值P填進指針所指向的符號表位置。

4、使用此方法的查表過程如下：首先計算出此項的函數(shù)H的值等于h，然后就指示器HASHTABLE[h]所指的項鏈逐一按序查找（線性查找）雜湊技術(shù)：使用一張雜湊鏈表通過間接方式查添符號表。將具有相同雜湊值符號名連成一串，便于線性查找。雜湊表是一個可容納N個指示器值的一維數(shù)組，它的每個元素的初值全為null。符號表除了通常包含的欄外，還增設(shè)了一鏈接欄，他把所有持有相同雜湊值的符號名連接成一條鏈。（見下頁）availableSYM1H（SYM1）=hp=HASHTABLE[h]=nullHASHTABLE[h]=AVAVILABLE=n1SYM1null…

…01hN-1雜湊表符號表……

……

……………LinkInformationNamen1n2n3n1nullavailableSYM2H（SYM2）=hp=HASHTABLE[h]=n1HASHTABLE[h]=AVAVILABLE=n2n2SYM2n1SYM3H（SYM3）=hp=HASHTABLE[h]=n2HASHTABLE[h]=AVAVILABLE=n3n3SYM3n2availableavailable8.3名字的作用范圍對于過程嵌套結(jié)構(gòu)型的程序設(shè)計語言，每層過程中說明的名字只局限于該過程，離開了所在的過程就無意義了。也就是說，同一個標識符，具有不同的性質(zhì)，要求分配不同的存儲空間。這樣，如何組織符號表，使得同一個標識符在不同的作用域中能得到正確的引用，而不會產(chǎn)生混亂。通常實現(xiàn)最近嵌套作用域規(guī)則的辦法是：對每個過程指定一個唯一的編號，即過程的順序號，以便跟蹤過程里的局部名字。在符號表中，表示局部名字用一個二元組：<名字,過程編號>對一個名字查找符號表是:只有當表項中的名字其字符逐個匹配,并且該記錄相關(guān)的編號和當前所處理的過程的編號匹配時,才能確定查找成功.Pascal的符號表組織

1、在Pascal程序中標識符的作用域是包含說明該標識符的一個最小分程序。具體的概括為如下幾點：（1）如果一個標識符在某一分程序首部已作說明，則不論此分程序是否含有內(nèi)層分程序，也不論內(nèi)分程序在嵌套多少層，只要在內(nèi)層分程序未再次對該標識符加以說明，則此標識符在整個分程序中均有定義，且有相同的屬性。（2）程序中的標號局限于定義該標號的最小分程序。（3）由于Pascal程序中的過程可具有嵌套的結(jié)構(gòu)，因此，可將每一過程說明都假想為一個分程序。出現(xiàn)在過程體中的非形式參數(shù)，依其在相應(yīng)的過程體中被說明與否，確定它們對過程而言是局部變量還是非局部變量，而形式參數(shù)則總是局限于相應(yīng)的過程體的。PASCAL程序中的標識符（或標號）的作用域，總是與說明（定義）這些標識符的分程序的層次相聯(lián)系的。參見P232（1）

針對符號表設(shè)計為棧符號表，新名字出現(xiàn)總是從棧頂填入。為了保證從內(nèi)層向外層查，查找操作從符號表的棧頂往底部查找。2、對于嵌套結(jié)構(gòu)型程序設(shè)計語言（Pascal）的特點，可采用如下

辦法：（2）過程的嵌套層次表（display），是引入的一個顯示層次關(guān)系表。其作用是為了描述過程的嵌套層次，指出當前正處理的各嵌套的過程（或函數(shù)）相應(yīng)的子符號表在棧符號表中的起始位置（相對地址）。（3）在信息欄中引入一個指針域（previous)，用來鏈接它在同一個過程內(nèi)的下一名字在表中的下標（相對位置）。每一層最后一個域名字，指針域之值為0。這樣每當需要查找個新名字時，就能通過display表找出當前正在處理的最內(nèi)層的過程及所有外層的子符號表在棧符號表中的位置。然后通過指針域可以找到同一個過程內(nèi)的所有被說明的名字。例：procedure…//B1vara,b:real;procedure…//B2varc,d:real;procedure…//B3vare,f:real;begin…end;begin…end;begin…end;

…

…

…

…

…

…

…

…

PreviousInformationName1110987654321棧符號表DISPLAYabtopsp1levellevel20B2cdtopsp4level3050B3eftopsp7level6080P232例子8.4符號表的內(nèi)容

（1）類型（整、實、雙實、布爾、字符、復、標號或指針等）；（2）種屬（簡單變量、數(shù)組或記錄結(jié)構(gòu)等）；（3）長度（所需的存儲單元數(shù)）；（4）相對數(shù)（存儲單元相對地址）；（5）若為數(shù)組