編譯原理：第9章 符號表管理技術

1、第9章 符號表管理技術 在編譯的各個階段經(jīng)常要收集、使用出現(xiàn)在源程序中的各種信息，通常把這些信息用一些表格進行記錄、存儲和管理，如常量表、數(shù)組信息表等等，這些表統(tǒng)稱為符號表。 符號表的作用 保存各類標識符的屬性 檢查語義的正確性 作為目標代碼生成階段地址分配的依據(jù) 符號表的作用是通過插入和檢索符號表中記錄的標識符屬性來實現(xiàn)的。這些屬性(如名字、類型、維數(shù)等)在聲明語句中可直接找到，有些可根據(jù)程序中標識符出現(xiàn)的上下文間接地獲得。 在編譯時，源程序中每出現(xiàn)一次標識符，就要與符號表打一次交道，主要工作是查表和存取操作，因此，與符號表的交互占據(jù)了大量的編譯時間。所以，如何有效地操作符號表直接影響編譯的

2、效率。 第9章 符號表管理技術符號表的作用 檢查語義的正確性 上下文敏感成分的分析實質上是語法分析的內容。但我們的語法分析是以上下文無關文法為基礎的，沒有考慮上下文敏感成分的處理，所以必須在語義分析時加以考慮。 屬于上下文敏感的語法規(guī)定包括： 標識符通常先定義后使用，但在同一個塊中，標識符不應重復定義； 實參表中的實參個數(shù)與類型必須與相應形參表中的形參個數(shù)與類型一致； 表達式中運算對象的類型必須與運算符相容，等等。第9章 符號表管理技術符號表的作用 作為目標代碼生成階段地址分配的依據(jù)。 對于變量標識符，在目標代碼生成時需要確定其存儲分配的位置。主要依據(jù)符號變量的存儲類別及被定義的位置來確定。何

3、時建立和訪問符號表 有的編譯程序中，符號表在詞法分析階段創(chuàng)建，符號表此時只含有標識符的名字，其它屬性要在語義分析階段填入。 當從源程序中識別出一個標識符時，就以此名字查符號表，若表中尚無此登記項，則將該名字列入表中。 語法分析階段只檢查源程序語法的正確性，一般不使用符號表。 符號表可在詞法分析時創(chuàng)建，也可在語義分析時創(chuàng)建。何時建立和訪問符號表 有的編譯程序，只在語義分析時才創(chuàng)建符號表。在語義分析階段，遇到聲明語句時會根據(jù)標識符的類別、名字屬性創(chuàng)建符號表記錄。同時對源程序代碼需要檢查語義的正確性。 在符號表中記錄的標識符的屬性信息會在代碼生成階段用于產(chǎn)生目標代碼的指令序列。 因此，直到語義分析和

4、代碼生成階段，許多與變量有關的屬性才能夠相繼填入符號表。 總之，如果在詞法分析階段創(chuàng)建符號表，只能在符號表中將標識符的名字填入符號表，而其他屬性則要在語義分析和代碼生成階段填入。如果在語義分析階段創(chuàng)建符號表，那么與符號表打交道的就僅局限于語義分析和代碼生成部分。 符號表的組織和內容 符號表的管理程序應該具有快速查找、快速刪除、易于使用、易于維護的特點。符號表具體包含哪些內容，屬性的種類和多少在一定程度上取決于程序設計語言的性質。 符號表基本上都是由一些表項組成的二維表格，每個表項可分為兩部分：第一部分是名字域，用來存放符號的名字；第二部分是屬性域，用來記錄與該名字相對應的各種屬性和特征。 符號

5、表的組織和內容 幾種主要屬性通常是需要的。1名字2符號類型3符號存儲類別4符號的作用域及可視性5符號變量的存儲分配信息（目標地址）6符號的其它屬性符號表管理技術名字：名字必須常駐在表中，因為它是在語義分析和代碼生成中識別一個具體標識符的依據(jù)。在符號表的組織中，一個要解決的重要問題是標識符長度的可變問題。對標識符名字的處理要考慮語言中對標識符長度的規(guī)定是定長還是不定長。根據(jù)標識符的定義特點，通常采用的存儲方法有兩種： . 定長存貯方法，即為標識符名字域規(guī)定一個寬度，標識符按左對齊方式存放在其中，特點是簡單且存取速度快，缺點是空間利用率低，標識符長度不能超過名字域的寬度。 . 集中存貯方法，即開辟

6、一個存放所有標識符的緩沖區(qū)，而在標識符名字域中只存放標識符在緩沖區(qū)中的偏移地址和標識符的長度。特點是存貯效率高，標識符無長度限制，但存取效率低。ComputerX1FORM1 名字位置 名字長度 其它屬性 1892175圖1 集中存貯方法符號表 目標地址：標識符主要作為變量名字。程序中每個變量都必須有一個相應的目標地址，該地址是為該變量分配的內存地址(可能是相對的)。 當聲明一個變量時，就要為該變量分配內存地址，并將其分配的地址填入符號表中。當該變量在程序的其它處被引用時，可以從符號表中查詢該地址，并填入存取該變量值的目標代碼中。 對于采用靜態(tài)存儲分配的語言(如FIRTRAN)，分配的地址是按

7、連續(xù)的順序分配的。 對于采用動態(tài)存儲分配的語言，每個程序塊內的變量連續(xù)分配，這是一個相對地址，運行時還要根據(jù)該程序塊分配的數(shù)據(jù)區(qū)的起始地址和變量的相對地址計算出變量的絕對內存地址。 如果標識符表示的是函數(shù)名或子程序名，則目標地址是該函數(shù)或子程序代碼的開始地址。如果是數(shù)組名，則應為數(shù)組模板的起始地址。 符號表管理技術類型：不同數(shù)據(jù)類型的變量占據(jù)不同大小的內存空間，另外類型檢查是語義分析的一項重要工作，所以符號表中要保存每個標識符的數(shù)據(jù)類型，以便分配內存和進行類型檢查。 維數(shù)及參數(shù)個數(shù)：這兩個屬性對類型檢查都是重要的。在數(shù)組引用時，其維數(shù)應當與數(shù)組聲明中所定義的維數(shù)一致，類型檢查階段必須對這種一致

8、性進行檢查，另外，維數(shù)也用于數(shù)組元素地址的計算。 過程調用時，實參個數(shù)也必須與形參個數(shù)一致。實際上，在符號表組織中，把參數(shù)的個數(shù)看成它的維數(shù)是很方便的，因此可以將兩個屬性合并成一個，另外這種方法也是協(xié)調的，因為對這兩種屬性所做的類型檢查是類似的。 符號表管理技術 原則上，一個編譯程序使用一張符號表就夠了，但在源程序中，由于不同種類的符號起著不同的作用，相應于各類符號所需記錄的屬性往往不同，因此，多數(shù)編譯程序都是根據(jù)符號的不同種類，分別建立不同的符號表，如常數(shù)表、變量名表、數(shù)組信息表、過程信息表、保留字表、特殊符號表、標準函數(shù)名表等等，這樣處理起來更方便一些。 從編譯系統(tǒng)建造符號表的過程來劃分，

9、符號表可分為靜態(tài)表和動態(tài)表兩大類：一是靜態(tài)表，即在編譯前就已經(jīng)構造好了的符號表，如保留字表、標準函數(shù)名表等。二是動態(tài)表，即在編譯過程中根據(jù)需要構造的符號表，如變量表、數(shù)組信息表、過程信息表等等。 符號表上的操作 在符號表上最常執(zhí)行的操作是插入和查找。 對于變量都必須顯式說明的語言：插入操作發(fā)生在變量聲明時，即處理一個變量聲明語句的時候。在進行插入操作前，首先要查符號表，以確定符號表中無該變量記錄，即變量不是重復聲明。 查找符號表操作發(fā)生的次數(shù)很多。除了插入前要先查符號表外，每次變量引用時都要查找符號表。如果查到，那么查找出的信息將用于語義檢查和代碼生成，同時可根據(jù)變量的上下文對未聲明(或預先聲

10、明的)變量的有關屬性進行推測，發(fā)出錯誤或警告信息、或相應的改正信息；如果沒有查到，說明存在變量沒有聲明就引用的錯誤，應報告相應的錯誤信息。 非塊程序結構語言的符號表結構 所謂非塊程序結構語言，是指用它編寫的每一個可獨立編譯的程序是一個不包含子塊的單一模塊程序，該模塊中聲明的所有變量是屬于整個模塊的。非塊程序結構語言的符號表有幾種組織方式，其中比較簡單的是無序表和有序表。 1、無序表 無序符號表也稱為線性表。構造一個符號表最簡單的方法是變量的屬性項按變量被聲明的先后順序填入表中。無序表插入和查找操作比較簡單，但查找效率低。但如果符號表較小，采用無序表則非常合適。無序表的優(yōu)點是結構簡單、節(jié)省空間，

11、添加及查找操作簡單、易于實現(xiàn)。 2、有序表 在編譯過程中，由于查找符號表的次數(shù)遠大于插入符號表的次數(shù)，所以如何提高符號表的查找效率直接影響編譯的效率。 有序符號表的表項是根據(jù)變量名按字母順序存放的。因此，每次插入符號表前，首先要進行查表工作，以確定要插入的符號在符號表中的位置，然后將符號插入。這樣難免會造成原有一些符號的移動，所以，這種符號表結構在插入符號時開銷較大。對于有序表，最常用的查找技術是折半查找法。非塊程序結構語言的符號表結構 塊程序結構語言的符號表組織 塊程序結構語言的概念 所謂塊程序結構語言是指程序模塊可包含嵌套的子模塊，每一子模塊可以有一組自己的局部變量。 按塊程序結構語言的規(guī)

12、定：變量的作用域是定義它的塊程序；同一塊內的變量不能重名，但不同塊以及嵌套塊之間的變量可以重名，因而某變量的聲明可與嵌套塊的內層變量同名，使用時局部變量優(yōu)先。 下面為一段C程序，右邊給出當編譯程序編譯到此處時的有效變量。 real x,y; char name; name,y,xint fun1(int ind) ind,fun1,name, y,x int x; x,ind, fun1,name, y,x x=m2(ind+1); fun1,name, y,xint fun2(int j) j,fun2, fun1,name, y,x int f10; bool test1; test1,f

13、, j,fun2, fun1,name, y,x j,fun2, fun1,name, y,x fun2, fun1,name, y,xmain() main, fun2, fun1,name, y,x char name; name, main, fun2, fun1,name, y,x x=2;y=5; printf(%dn,fun1(x/y);當編譯完第2行時，符號表中應含有變量name,y,x的記錄。編譯到第4行時，符號表中應含有變量x,ind, fun1,name, y,x的記錄，此時，符號表同時含有兩個變量x的記錄，而在函數(shù)fun1內有效的變量是局部變量x，即第4行聲明的變量。而編

14、譯到第6行時，符號表中有變量fun1,name, y,x的記錄，x,ind失效。編譯到第10行時，有效變量為test1,f, j,fun2, fun1,name, y,x。而編譯到第11行時，符號表中有變量j,fun2, fun1,name, y,x的記錄，test1,f失效。編譯到第15行時，符號表中應含有變量name, main, fun2, fun1,name, y,x的記錄，此時，在主函數(shù)main內使用的變量x和y都是全局變量。 棧式符號表 對于塊程序結構語言，其最簡單的符號表結構為棧式符號表，它包括一個符號表棧及一個塊索引棧。 符號表棧記錄變量的屬性，塊索引棧指出每個塊的符號表的開始

15、位置。棧式符號表操作過程十分簡單，當遇到變量聲明時，將包含變量的屬性壓入堆棧；當遇到塊程序開始時，將當前的符號表棧頂位置壓入塊索引棧，從而開始一個新塊的變量處理；當?shù)竭_塊程序結尾時，則根據(jù)塊索引棧指出的本塊的開始為位置，將該塊程序中聲明的所有變量記錄彈出堆棧，從而使局部聲明的變量在塊外不再存在。 棧式符號表 棧式符號表的插入操作: 首先，剛開始編譯時，設符號表棧頂指針TOP為0，當?shù)谝粋€標識符出現(xiàn)時，將該標識符的屬性入棧，同時將該標識符的地址0壓入塊索引棧，然后棧頂指針TOP為1。 后面再遇到標識符時，如果新的標識符與棧頂?shù)臉俗R符在同一塊中，則只需將新記錄壓入符號表棧頂單元，然后，棧頂指針TO

16、P加1(圖a)。 如果新的標識符與棧頂?shù)臉俗R符不在同一塊中，表示剛才處理的程序塊嵌套著一個程序塊，而現(xiàn)在進入了這個嵌套的程序塊中，則要進行定位操作，即將棧頂指針TOP入塊索引棧，再將該標識符屬性壓入符號棧，然后棧頂指針TOP加1(圖b、c)。 當編譯遇到程序塊的結尾時要進行重定位操作，即將塊索引棧的棧頂單元出棧并將內容賦給棧頂指針TOP。注意：棧頂指針TOP始終指向符號表棧頂?shù)谝粋€空閑的存儲單元。 棧式符號表 塊結構語言程序中允許存在重名變量的聲明，但重名變量不能出現(xiàn)在同一塊中，因此所有標識符插入前要檢查當前處理的塊中是否有同名變量。其方法是：從棧頂單元(TOP-1)開始到塊索引棧的棧頂單元所

17、指的單元，逐一檢查，如果有與要插入的變量同名，則表示源程序中存在變量重復聲明的錯誤；如果沒有，才可將該標識符的屬性入棧。 查表操作要對符號棧進行從頂(TOP-1)到底進行線性搜索，這樣確保找到的變量滿足局部變量優(yōu)先于全局變量的規(guī)則。由于棧式符號表中記錄是無序的，因而查詢效率比較差。 棧式符號表例 ，有一段C程序如下，畫出編譯到a、b、c、d處的棧式符號表。real x,y;char name;aint fun1(int ind) int x; b x=m2(ind+1);int fun2(int j) int f10; bool test1; c main() char name; dx=2;

18、y=5; printf(%dn,fun1(x/y);nameyx0TOPxindfun1nameyx40TOP棧式符號表解：a、b、c、d處的棧式符號表棧式符號表見圖a、b、c、d。 test1f數(shù)組jfun2fun1nameyx 650TOPnamemainfun2fun1nameyx 60TOPxindfun1nameyx40TOPnameyx0TOP (a) (b) (c) (d) 圖 棧式符號表 棧式符號表解：a、b、c、d處的棧式符號表棧式符號表見圖a、b、c、d。 test1f數(shù)組jfun2fun1nameyx 650TOPnamemainfun2fun1nameyx 60TOPxindfun1nameyx40TOPnameyx0TOP (a) (b) (c) (d) 圖 棧式符號表 real x,