編譯原理與技術(shù)講義-第6章41943.ppt

1、青島大學(xué)信息工程學(xué)院,編譯原理與技術(shù),第6章 符號表的組織和管理,編譯原理與技術(shù),2,主要內(nèi)容,符號表的作用 符號表的主要屬性及其作用 符號表的組織結(jié)構(gòu) 名字的作用范圍,編譯原理與技術(shù),3,6.1 符號表的作用,登記符號屬性值 在源程序的各個分析階段，編譯程序根據(jù)標識符的聲明信息收集它屬性的有關(guān)值，并把它們存放在符合表中。 每種語言規(guī)則定義了不同的符號屬性；即使是同一個語言，不同的編譯程序也可能會定義并且收集不同的屬性信息。 現(xiàn)代編程語言中一般包括常數(shù)聲明、變量聲明、類型聲明和過程/函數(shù)聲明等四類聲明。對于每類聲明，編譯程序要收集、存儲和應(yīng)用的屬性完全不同。,編譯原理與技術(shù),4,6.1 符號表

2、的作用,例6.1 C語言的變量聲明 short int a; float b = 0.0; 把標識符a聲明為短整數(shù)型，把b聲明為浮點類型，而且初始化為0。那么，編譯程序?qū)γ總€變量要記錄它的類型，以便執(zhí)行類型檢查和分配存儲，比如短整型變量i占2個字節(jié)；要記錄它在存儲器中的位置（相對位移或絕對地址），以便目標程序運行時訪問；若像b有初始值，則還需要記錄這個初始值。,編譯原理與技術(shù),5,6.1 符號表的作用,例6.2 下面是計算階乘n!的C語言的函數(shù)聲明： int factory ( int n) int t; if (n = = 0) | | n = = 1) t = 1; else t = n

3、factory (n1); return t; 對于函數(shù)factory要記錄的屬性包括：函數(shù)的名稱，各種變量如參數(shù)、返回值、局部變量及其類型，同時還要記錄函數(shù)的調(diào)用信息，以便在函數(shù)體執(zhí)行完畢以后返回到調(diào)用點，特別是對這種允許遞歸調(diào)用的函數(shù)，要為每次調(diào)用保留上面提到的所有信息。,編譯原理與技術(shù),6,6.1 符號表的作用,查找符號的屬性 符號表存放了源程序中的各種類型的信息，比如數(shù)值、變量類型、參數(shù)傳遞的地址等，在分析和翻譯源程序的過程中會被不斷地查詢。 例如，對于上述的變量聲明，如果源程序有代碼a + b時，就需要查找、計算表達式中運算數(shù)的類型和值，以便計算出表達式。 又如，在源程序中如果出現(xiàn)了

4、函數(shù)調(diào)用factory (6)，編譯程序就需要查找到factory的聲明，找到實參6的地址并傳給形參n，執(zhí)行函數(shù)factory的體，并返回值，等。,編譯原理與技術(shù),7,6.1 符號表的作用,檢查符號的合法性 例如，對于上述聲明，代碼 a = a + b，C語言的編譯將檢查變量a和b的類型，把表達式a + b的結(jié)果轉(zhuǎn)換成短整型，僅取整數(shù)部分進行賦值。 在其它強類型語言，如Pascal和Ada，表達式運算數(shù)的類型必須一致，不能進行隱式類型轉(zhuǎn)換，對于這樣的表達式a + b，編譯程序在語義分析的過程中將發(fā)現(xiàn)并報告類型錯誤的信息。 又如，面向?qū)ο笳Z言的繼承性和多態(tài)性允許同一個消息在不同的環(huán)境中調(diào)用不同的

5、方法（函數(shù)），即調(diào)用同名但在不同的類中實現(xiàn)的方法。這就需要編譯或者運行時在方法的符號表中查詢在參數(shù)、返回數(shù)以及方法方面名字一致的實現(xiàn)。,編譯原理與技術(shù),8,6.1 符號表的作用,作為目標代碼生成階段地址分配的依據(jù) 標識符由它定義的存儲類型或它在程序中的位置來確定。 首先是要確定變量存儲的區(qū)域。例如，在Java語言中，整數(shù)的類型（以及所占用的字節(jié)）有byte（1個字節(jié)）、short（2個字節(jié)）、int（4個字節(jié)）以及l(fā)ong（8個字節(jié)），而float類型占4個字節(jié)，double類型占8個字節(jié)。又如，對寄存器變量，編譯將盡可能地把它們保留在機器的寄存器當中，以提高運行速度；而對在一個文件中定義的外

6、部變量，它們要在不同的源程序文件之間訪問，需要編譯程序把它們放在所有源程序文件都可以方便尋找到的存儲器的位置。 其次，要根據(jù)標識符出現(xiàn)的順序，決定標識符在某個存儲區(qū)域中的具體位置，而有關(guān)區(qū)域的標志及其相對位置都是作為該標識符的語義信息存放在它的符號表中的。,編譯原理與技術(shù),9,6.2 符號表的主要屬性及其作用,不同的符號類別包含了不同的屬性，由于它們的信息不同，也就導(dǎo)致了符號表的組織有較大的差別。例如，數(shù)量類型的變量名字和過程名字： 對于一個變量名要記錄其類型（如整型、實型、布爾型等）、占用的存儲字節(jié)以及相對與某個基準位置的相對位置； 對一個過程名要記錄的屬性包括參數(shù)的個數(shù)及其類型，該過程是否

7、有返回值，過程中的變量聲明，甚至過程聲明（如果像Pascal語言允許嵌套過程聲明）等信息。,編譯原理與技術(shù),10,6.2 符號表的主要屬性及其作用,符號名 符號名可以是變量名、函數(shù)名（操作名）、類型名、類對象名等 每個符號名通常由若干個（非空）的字符組成的字符串來表達，在語言中它們通常是一個變量、函數(shù)或?qū)ο蟮奈灰茦酥?，因此在符號表中的符號名作為表項的唯一區(qū)別一般是不允許重名的。 符號名與它在符號表中的位置建立起一一對應(yīng)的關(guān)系，這使得我們可以用一個符號在表中的位置來代替該符號名、訪問其信息。通常把一個標識符在符號表中的位置值稱為該標識符的內(nèi)部代碼。 在經(jīng)過分析處理的源程序中，標識符不再是一個字符

8、串而是一個表示內(nèi)部碼的整數(shù)值，這不但便于識別，而且也可以壓縮存儲和表達的長度。,編譯原理與技術(shù),11,6.2 符號表的主要屬性及其作用,符號名 語言中的符號名通常用標識符來表示。根據(jù)語言的定義，程序中出現(xiàn)的重名標識符定義將按照該標識符在程序中的作用域和可視規(guī)則進行相應(yīng)的處理。而在程序的運行過程中，符號表中的符號名始終是唯一的標志。 在一些允許操作重載、類繼承的語言中，函數(shù)名、操作名允許重名，對于重載操作的標識符，它們可以通過參數(shù)的個數(shù)與類型以及返回值的類型來區(qū)別；而對于操作的繼承，編譯器可以構(gòu)造繼承圖，同時保存類結(jié)構(gòu)，這樣就可以為每個操作和屬性找到唯一的定義。 例如，對應(yīng)不同的參數(shù)類型，可以定

9、義幾個求和重載函數(shù)： int sum ( int a, int b) double sum ( double a, double b) float sum（float a, float b, float c） 當某個函數(shù)中調(diào)用到重載函數(shù)時，編譯器根據(jù)實參的類型和個數(shù)去調(diào)用相應(yīng)的函數(shù)。,編譯原理與技術(shù),12,6.2 符號表的主要屬性及其作用,符號種屬 由于語言中符號所擁有的屬性可能不同，其組織就可以采用不同的數(shù)據(jù)結(jié)構(gòu)，可以用符號的種屬來區(qū)別每個符號的基本劃分。 根據(jù)不同的語言，符號的種屬可以包括：簡單變量、結(jié)構(gòu)型變量、數(shù)組、過程、類型、類等。 可以依據(jù)符號種屬的劃分來組織符號表，一種方式是為每個

10、種屬的標識符建立一張表，這樣，可以對符號表類似地安排組織結(jié)構(gòu)、進行同樣的操作；另外一種方式把所有種屬的標識符統(tǒng)一安排在一張表中，根據(jù)符號的種屬進行條件判斷，對不同種屬的特殊型執(zhí)行不同的存儲安排和操作。,編譯原理與技術(shù),13,6.2 符號表的主要屬性及其作用,符號類型 現(xiàn)代程序語言中的一個重要構(gòu)造就是數(shù)據(jù)類型（類型），它是變量標識符的重要屬性，函數(shù)的數(shù)據(jù)類型指的是該函數(shù)返回值的數(shù)據(jù)類型。 現(xiàn)代語言通常都有如下的基本類型：整型、實型、字符型、布爾型、邏輯型等； 符號的類型屬性從源程序中該符號的定義中得到 變量符號的數(shù)據(jù)類型屬性不但決定了該變量的數(shù)據(jù)在存儲器中的存儲格式，也規(guī)定了可以對該變量施加的操

11、作運算。,編譯原理與技術(shù),14,6.2 符號表的主要屬性及其作用,符號類型 目前的大多數(shù)語言都在基本類型的基礎(chǔ)上定義復(fù)合數(shù)據(jù)類型，如數(shù)組、集合和記錄。 許多語言還允許程序員自己定義數(shù)據(jù)類型。這些復(fù)合類型的基本元素可以是基本類型，也可以是復(fù)合類型。 作為存儲變量地址的指針類型所指向的變量可以是基本的數(shù)據(jù)類型，也可以是其它任何一種復(fù)合數(shù)據(jù)類型。,每一個變量的類型是符號表中標識符屬性的重要信息。,編譯原理與技術(shù),15,6.2 符號表的主要屬性及其作用,存儲類別 大多數(shù)程序語言對變量的存儲類別采用兩種方式。 一種是用關(guān)鍵字指定，例如，在FORTRAN語言中用COMMON來定義公共存儲區(qū)域，允許不同程序

12、段都可以訪問這些數(shù)據(jù)；又如，C和C+語言規(guī)定static定義的變量屬于文件的靜態(tài)存儲變量或?qū)儆诤瘮?shù)內(nèi)部的靜態(tài)存儲變量，這些變量在編譯時分配存儲空間，如果定義時沒有初值，編譯器還需要將它們初始化為0。 另一種方式是根據(jù)定義變量的聲明在程序中的位置來決定。例如，C+規(guī)定在一個文件中定義的變量缺省為外部的，即程序的公共存儲變量；而在函數(shù)體內(nèi)缺省存儲類別關(guān)鍵字所定義的變量是內(nèi)部變量，是屬于該函數(shù)體所獨有的私有存儲變量，因而是動態(tài)地分配存儲空間。 區(qū)別符號存儲類型地屬性是編譯過程中語義處理、檢查和存儲分配的重要依據(jù)。 符號的存儲類別同時還決定了符號變量的作用域、可見性和它的生命周期等性質(zhì) 。,編譯原理與

13、技術(shù),16,6.2 符號表的主要屬性及其作用,作用域 一個標識符在程序中起作用的范圍稱為其作用域。 一般來說，定義一個符號的位置及存儲類型就決定了該符號的作用域，就是它可以出現(xiàn)的場合，可以在程序中作為參數(shù)、表達式的運算數(shù)等被引用。 C語言中外部變量的作用域是整個程序，一個外部符號的定義在整個策劃能夠許中只能出現(xiàn)一次，為了方便使用和編譯，同名標識符的其它說明可以多次出現(xiàn)。 FORTRAN語言中的COMMON變量的作用域則不是整個程序，而只能在定義這個COMMON塊的函數(shù)或過程中引用。 面向?qū)ο笳Z言，如C+，的每個類都引入了一個獨立的類域。,編譯原理與技術(shù),17,6.2 符號表的主要屬性及其作用,

14、作用域與可見性 標識符的可見性從另外一個角度說明其有效性，它與作用域有一定一致性。 標識符的作用域包含可見范圍，但是，可見范圍不會超過作用域。 可見性在理解同名是不是合法的作用域嵌套時十分直觀。對于外層塊域內(nèi)層塊定義的同名標識符，在外層作用域中，內(nèi)層所定義的標識符時不可見的，即外層所引用的是外層所定義的標識符； 同樣，在內(nèi)層作用域中，外層的標識符將被內(nèi)層的同名標識符所屏蔽，變得不可見，即外層中同名標識符的可見范圍是作用域中挖去內(nèi)層塊的范圍，在內(nèi)存塊形成了作用域洞 。,編譯原理與技術(shù),18,6.2 符號表的主要屬性及其作用,例6.3 圖6.1（b）顯示了下列程序段中變量的作用域與可見性，其中in

15、t m的作用域在括號中不可見，即這個程序塊在int m的作用域中挖了一個洞。,int m = 1; float n; float m = 3.14; n = 5.5; m+; ,編譯原理與技術(shù),19,存儲分配信息 編譯程序需要根據(jù)符號的存儲類別定義以及它們在程序中出現(xiàn)的位置和順序來確定每一個符號應(yīng)該分配的存儲區(qū)域及其具體位置。 通常情況下，編譯為每個符號分配一個相對于某個基址的相對位移，而不是絕對的內(nèi)存地址。 編譯程序中有關(guān)源程序的存儲組織和分配的問題將在第7章中詳細討論。,6.2 符號表的主要屬性及其作用,編譯原理與技術(shù),20,6.2 符號表的主要屬性及其作用,其它屬性 數(shù)組內(nèi)情向量 需要把

16、描述數(shù)組屬性的信息如數(shù)組類型、維數(shù)、每個維的上下界、數(shù)組元素的首地址等登錄在符號表中，以便確定數(shù)組在存儲器占用的空間和數(shù)組元素的確定，并且完成數(shù)組的翻譯。 記錄結(jié)構(gòu)型的成員信息 一個記錄結(jié)構(gòu)型的變量包含若干成員，每個成員的數(shù)據(jù)類型可以彼此不同，因此，一個記錄結(jié)構(gòu)型變量在存儲分配時所占空間的大小由其成員來確定，而且，對每個成員的訪問還需要它所屬成員排列次序的屬性信息。 函數(shù)或過程的形參 函數(shù)或過程的形參作為其局部變量，同時又是對外部調(diào)用的接口。每個函數(shù)或過程形參的個數(shù)、類型、排列順序都體現(xiàn)了調(diào)用函數(shù)或過程時的屬性，它們都應(yīng)該反映在符號表中，以便在過程調(diào)用的時候進行參數(shù)傳遞，并且執(zhí)行語義檢查（如處

17、理函數(shù)名的重載）。 在面相對象語言中，還必須把一個類或其超類所定義同名方法存放在一個方法表中，指向每個方法的實現(xiàn)操作，以便實現(xiàn)面相對象的繼承性質(zhì)。,編譯原理與技術(shù),21,6.3 符號表的組織結(jié)構(gòu),符號表的整體組織結(jié)構(gòu) 符號名欄目也叫主欄，其內(nèi)容是源程序中出現(xiàn)的標識符，它是區(qū)分每個表項的關(guān)鍵碼。 對于保留字、類型、函數(shù)，它們的名字（標識符）就是符號表的關(guān)鍵碼； 對于語言中的保留字，它們本身就是表項中的關(guān)鍵碼； 對于語言中操作符，如乘冪“*”、賦值號“:=、+=”或者FORTRAN中的拼寫操作“.GT.”，其字符或字符串就作為該操作符表項的關(guān)鍵碼。,編譯原理與技術(shù),22,6.3 符號表的組織結(jié)構(gòu),

18、編譯程序?qū)Ψ柋淼目傮w組織可以有3種形式 假設(shè)有下列三種類型的符號及其屬性：,編譯原理與技術(shù),23,6.3 符號表的組織結(jié)構(gòu),第一種（如圖6.3所示）： 根據(jù)符號類型進行分類，把屬性完全相同的那些符號安排在一張表中 這樣就構(gòu)造出許多不同的符號表，每個表的信息欄目中屬性個數(shù)和結(jié)構(gòu)完全一樣，而且每個表項的屬性欄目都是等長、有效。這種單個符號表的管理和操作都比較方便，空間使用效率也高。 缺點是一個編譯程序要同時管理若干個不同類型的符號表，符號表分得太散，對不同類型符號表中的共同屬性必須設(shè)置重復(fù)的管理機制，增加了符號表管理的工作量和復(fù)雜度。,編譯原理與技術(shù),24,6.3 符號表的組織結(jié)構(gòu),第二種（如圖

19、6.4所示）： 把語言中的所有符號都組織在一張符號表中。 優(yōu)點是總體管理符號表集中、單一，不同類型符號中的相同屬性得到了一致的管理和處理。 為了完整地存放所有屬性就導(dǎo)致每個表項所包含的屬性個數(shù)不一樣，出現(xiàn)不等長的表項，這就極大地提高了符號表管理和處理的復(fù)雜性。 為了保持表項等長，把所有符號的全部屬性都作為符號表中信息欄目的屬性，這樣的組織有助于減低符號表的管理和處理的復(fù)雜性。但是對于不同類型的符號，可能增加了無用的屬性空間，從而降低編譯程序的空間使用效率。例如，對于第二類符號，單一組織的符號表中就超過一般的屬性不需要，極大地浪費存儲空間。,編譯原理與技術(shù),25,6.3 符號表的組織結(jié)構(gòu),第三種

20、是前兩種的折衷形式。 根據(jù)屬性的相似程度把符號表分成若干類型，每個類型組織成一張表，每張表中記錄的符號都有很多相同的屬性。 這種組織方式在管理的復(fù)雜程度和空間的使用效率方面都取得了上述兩種組織的這種效果。 而且，可以根據(jù)目標系統(tǒng)的體系結(jié)構(gòu)和編譯程序設(shè)計者的經(jīng)驗，對符號表的分類進行選擇和調(diào)整。例如，可以將上面的類型一和類型三的符號合成一張表，類型二構(gòu)成一個單獨的符號表。,編譯原理與技術(shù),26,6.3 符號表的組織結(jié)構(gòu),關(guān)鍵碼域的組織,符號表的關(guān)鍵碼域就是符號本身，它可以是語言的保留字、操作符，也可以是標識符，如變量名、常數(shù)名、函數(shù)名、類型名、類名等程序結(jié)構(gòu)。 語言文法的詞法對各種符號都有嚴格的定

21、義。 保留字和操作符的名字一般是只有唯一的拼寫方法，而且不能用當作其它用途的用戶定義的標識符。標識符通常是以字母開頭的、長度確定或不限長度的字母和數(shù)字組成的字符串。 如果語言對標識符的長度有限制，可以讓符號表中關(guān)鍵碼域有標識符允許的最大長度以容納語言的整個標識符單詞。 但是，如果語言對標識符的長度不加限制，或者為了避免最大標識符長度過大而浪費存儲空間，通常的做法是另外設(shè)立一個存放標識符單詞的字符數(shù)組，在符號表的名字欄目中僅給出標識符單詞在這個數(shù)組中的首地址和符號長度的二元組。這樣，符號表的關(guān)鍵碼域可以有一致的大小，而且，同時也可以節(jié)省存儲空間。,編譯原理與技術(shù),27,6.3 符號表的組織結(jié)構(gòu),

22、例6.4 假定有標識符student、name、birthday、code、p，它們依次存放在上述的標識符單詞數(shù)組中，其間沒有間隔標志，這樣的符號表結(jié)構(gòu)如圖6.6所示 。,t,u,d,e,n,t,n,a,m,e,b,i,r,t,h,d,a,y,c,o,d,e,p,s,編譯原理與技術(shù),28,6.3 符號表的組織結(jié)構(gòu),不等長域的組織,上述對標識符不限長度的處理是組織符號名的一種間接方式，這種方式可以推廣到屬性域不相等的情形。我們可以把一些共同屬性直接記錄在符號表的信息欄，把某些特殊的屬性記錄在其它地方，并且在符號表的信息欄中增設(shè)一個指針，指向這個存放特殊屬性值的位置。 例6.5 圖6.7示意了通過

23、符號表訪問內(nèi)情向量的組織結(jié)構(gòu)，符號表有兩個數(shù)組array1和array2，它們分別有n維和1維。,編譯原理與技術(shù),29,6.3 符號表的組織結(jié)構(gòu),符號表的操作 對于給定符號，查詢此名字是否在符號表中； 對于給定符號，在符號表中訪問它的屬性信息； 對于給定符號，在符號表中更新它的屬性信息； 在符號表中插入一個新的符號及其相關(guān)信息； 刪除一個或一組無用的表項。,編譯原理與技術(shù),30,6.3 符號表的組織結(jié)構(gòu),插入、查找、更新和刪除的函數(shù)可以說明如下： procedure insert (token.entry: Addess; type: Typekind); 把入口是entry的符號token的

24、類型type插入符號表。類似地也可以插入其它信息，如變量的值，譬如 procedure setvalue (variable.entry: Addess; value: Valuetype); 對在符號表入口的變量variable設(shè)置值value。 function lookup (entry: Addess): Typekind; 查找符號表中入口是entry的標識符，返回它的類型。 function getvalue (entry: Addess): Valuekind; 得到符號表中入口是entry的標識符的數(shù)值。 function delete (entry: Addess): Boo

25、lean; 把入口是entry的表項從符號表中刪除，如果成功則返回真值true，不成功則為假值false。,編譯原理與技術(shù),31,6.3 符號表的組織結(jié)構(gòu),三種常見的符號表的結(jié)構(gòu)： 線性表、搜索樹和散列表組織 線性表組織是按照符號被掃描到的先后順序填寫各個表項，可以用一個多維數(shù)組或多個一維數(shù)組來存放符號的信息。 線性表需要兩個指針來方便管理和操作：一個指針指向該符號表的開始位置，另一個指針指向符號表的下一個可用位置。 線性表是最基本的數(shù)據(jù)結(jié)構(gòu)，可以方便、直接地實現(xiàn)上述的插入、查找和刪除三種基本操作，而且每種的操作時間都是符號表大小的線性函數(shù)，對于有N個表項的符號表，這些操作的平均時間都是N/2

26、左右（算法時間復(fù)雜性為(N)）。 由于線性表無需附加空間，比較節(jié)省存儲。如果編譯器對處理時間要求不高，或者符號個數(shù)不大（如關(guān)鍵字），符號表就可以采用線性表結(jié)構(gòu)。,編譯原理與技術(shù),32,6.3 符號表的組織結(jié)構(gòu),搜索樹結(jié)構(gòu) 搜索樹可以在構(gòu)造符號表的同時，按照符號名的字典順序把表項整理排列，提高符號表查找操作的速度。 這樣就可以采用折半查找的方式，加快搜索的速度。 對于有N個表項的符號表，每次查找最多只需要做logN次比較（因此這種查找法也叫對數(shù)查找法）。 但是，由于符號表在編譯過程中是邊填寫邊引用，動態(tài)地建立、更新以及刪除表項，這樣，每增加和刪除一個表項都需要對符號表進行重新排序，這同樣浪費時間

27、。 因此，搜索樹結(jié)構(gòu)不適合用于構(gòu)造符號表，除了需要額外的空間構(gòu)造搜索樹以外，整體而言，它們實現(xiàn)這三類操作效率不是最優(yōu)，而且刪除操作的實現(xiàn)過于復(fù)雜。,編譯原理與技術(shù),33,6.3 符號表的組織結(jié)構(gòu),符號表處理的關(guān)鍵問題 散列組織統(tǒng)一了查詢與插入操作技術(shù)，相對來說具有較高的時空效率，為上述三種操作提供的時間基本上是常數(shù)。 特別是散列表結(jié)構(gòu)符合編譯過程邊填寫邊引用符號表的特性，是實現(xiàn)符號表的最佳數(shù)據(jù)結(jié)構(gòu)，在實踐中的使用最多。,線性表結(jié)構(gòu)填表快，查詢慢；搜索樹結(jié)構(gòu)查詢快，填表慢。,如何保證查詢與插入表項這兩個基本操作的都能高效地完成。,編譯原理與技術(shù),34,6.3 符號表的組織結(jié)構(gòu),散列方法 散列方法

28、在表項的存儲位置與它的關(guān)鍵碼之間建立一個確定的對應(yīng)函數(shù)關(guān)系（哈希函數(shù)，雜湊函數(shù)，hash），使每個關(guān)鍵碼symbol與散列結(jié)構(gòu)（散列表，哈希表，雜湊表）中的唯一的存儲位置相對應(yīng)，即hash(symbol)。 在搜索時，首先對表項的關(guān)鍵碼用哈希函數(shù)計算出對應(yīng)的表項的存儲位置，在散列表中按此位置取出表項進行比較，若關(guān)鍵碼相等，則搜索成功。 在填入表項時，依同樣函數(shù)計算存儲位置，并按此位置存放表項。由于使用這種方法進行搜索時不必多次比較關(guān)鍵碼，因此搜速速度比較快，可以到達逼近具有此關(guān)鍵碼的表項的實際存放地址。,編譯原理與技術(shù),35,6.3 符號表的組織結(jié)構(gòu),對哈希函數(shù)的基本要求 計算簡單、高效； 函

29、數(shù)值能均勻地分布在1和N之間， 對不同的關(guān)鍵碼都返回一個代表存儲位置的不同值。 構(gòu)造哈希函數(shù)的算法有許多，例如，若取N為素數(shù)，就可以定義哈希函數(shù)為symbol/N的余數(shù)，其中symbol是某個符號的代碼。由于語言中的標識符可以相互區(qū)別，它們的代碼值都是不同的。,編譯原理與技術(shù),36,6.3 符號表的組織結(jié)構(gòu),散列沖突的解決 不同的關(guān)鍵碼經(jīng)過雜湊運算以后，有可能得到相同的雜湊值，這種現(xiàn)象稱為散列沖突。 一種常用的方法是鏈地址法。 把有N個地址的散列表改為N個桶，桶號與散列地址一一對應(yīng)，第i（1iN）個桶號即為第i個散列地址，每個桶則是一個線性鏈表（稱為同義詞表），鏈表中的表項具有相同的散列函數(shù)值

30、。 若出現(xiàn)了沖突，即一個表項的散列值所對應(yīng)的地址已經(jīng)被占據(jù)，則需把這個表項放到該桶的鏈尾或鏈首。,編譯原理與技術(shù),37,6.3 符號表的組織結(jié)構(gòu),.,addr,.,HashTable,1,h,n,名字,.,sym1,sym2,.,sym,SymbolTable,a2,addr,a3,屬性1,.,.,屬性j,.,.,屬性m,.,.,hash(),鏈表指針,.,null,a2,.,a3,.,.,next,.,.,如何在符號表中使用散列表技術(shù),對于每個符號表增加一個地址鏈項（初始化為null）； 建立一個散列表（桶），它是一個含n個符號表入口地址的一維數(shù)組，每個散列表的表項初始化為null，表示散列

31、函數(shù)值所對應(yīng)的符號表的表項沒有占用。 對符號表的操作實際上就是通過散列函數(shù)間接地操作符號表。,編譯原理與技術(shù),38,6.3 符號表的組織結(jié)構(gòu),通過散列函數(shù)間接地操作符號表,符號表中填入一個新的sym符號 （1）首先對于符號sym用散列函數(shù)hash在散列表HashTable中查找出它在符號表SymbolTable中的位置h：hash(sym)返回的值在1n之間，令指針ptr := HashTableh；否則p := hull。 （2）如果ptr 為null，則把sym的信息填在SymbolTableptr所對應(yīng)的一個符號表的表項中。 如果ptr不是null，則表示出現(xiàn)了沖突： 首先在符號表中得到

32、下一個新的可用的項（地址用next表示）， 接著在散列表中把同義詞表的表頭改為next， 然后填寫這個新得到符號表的表項內(nèi)容：把鏈表指針由null改成SymbolTableptr的鏈表指針，填寫sym的其它屬性值。,編譯原理與技術(shù),39,6.4 名字的作用范圍,名字的聲明和作用域 程序語言中的聲明是把信息聯(lián)系到名字（標識符）的一種語法結(jié)構(gòu)。 編程語言中一般包括5類聲明： 常量聲明、變量聲明、類型聲明和過程/函數(shù)聲明以及類聲明 常量聲明把值聯(lián)解到名字 。 類型聲明把名字綁定到新構(gòu)造的類型或者為已經(jīng)存在的名字創(chuàng)建一個別名。 變量聲明通常把名字綁定到一個類型，同時還隱式地綁定了其它屬性。 一個聲明起

33、作用的程序部分稱為該聲明的作用域。過程中出現(xiàn)的名字，如果是在該過程的一個聲明的作用域內(nèi)，就稱為局部于該過程的；否則叫做非局部的。,編譯原理與技術(shù),40,6.4 名字的作用范圍,先聲明后使用是一條在大多數(shù)程序中普遍采用的規(guī)則，它要求一個名字的聲明在程序的正文中在它的引用之前。 這條規(guī)則允許編譯器一邊分析程序一邊建立符號表： 一旦在程序代碼中遇到了名字引用才執(zhí)行符號表的查找操作； 如果查找失敗，就出現(xiàn)了違反先聲明后使用的規(guī)則，編譯器就能發(fā)出一個適當?shù)腻e誤消息。 所以，這條規(guī)則允許一遍掃描的編譯構(gòu)造。,編譯原理與技術(shù),41,6.4 名字的作用范圍,塊結(jié)構(gòu)與符號表的分層次管理 塊結(jié)構(gòu)是現(xiàn)代程序語言的普通構(gòu)造，它是程序中可以包含聲明的任何程序構(gòu)造。 在Pascal語言中，主程序和過程/函數(shù)聲明是塊結(jié)構(gòu)； C語言中，函數(shù)聲明以及花括號內(nèi)的復(fù)合語句表示塊結(jié)構(gòu)。 Java語言中的包package把一組相關(guān)的類封裝在一起，也構(gòu)成塊結(jié)構(gòu)。 作用域服從最近嵌套規(guī)