編譯原理：第9章 符號表管理技術(shù)

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

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

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

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

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

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

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

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

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

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

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

12、定：變量的作用域是定義它的塊程序；同一塊內(nèi)的變量不能重名，但不同塊以及嵌套塊之間的變量可以重名，因而某變量的聲明可與嵌套塊的內(nèi)層變量同名，使用時局部變量優(yōu)先。 下面為一段C程序，右邊給出當(dāng)編譯程序編譯到此處時的有效變量。 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);當(dāng)編譯完第2行時，符號表中應(yīng)含有變量name,y,x的記錄。編譯到第4行時，符號表中應(yīng)含有變量x,ind, fun1,name, y,x的記錄，此時，符號表同時含有兩個變量x的記錄，而在函數(shù)fun1內(nèi)有效的變量是局部變量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行時，符號表中應(yīng)含有變量name, main, fun2, fun1,name, y,x的記錄，此時，在主函數(shù)main內(nèi)使用的變量x和y都是全局變量。 棧式符號表 對于塊程序結(jié)構(gòu)語言，其最簡單的符號表結(jié)構(gòu)為棧式符號表，它包括一個符號表?xiàng)＜耙粋€塊索引棧。 符號表?xiàng)Ｓ涗涀兞康膶傩?，塊索引棧指出每個塊的符號表的開始

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

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

17、指的單元，逐一檢查，如果有與要插入的變量同名，則表示源程序中存在變量重復(fù)聲明的錯誤；如果沒有，才可將該標(biāo)識符的屬性入棧。 查表操作要對符號棧進(jìn)行從頂(TOP-1)到底進(jìn)行線性搜索，這樣確保找到的變量滿足局部變量優(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處的棧式符號表?xiàng)Ｊ椒柋硪妶Da、b、c、d。 test1f數(shù)組jfun2fun1nameyx 650TOPnamemainfun2fun1nameyx 60TOPxindfun1nameyx40TOPnameyx0TOP (a) (b) (c) (d) 圖 棧式符號表 棧式符號表解：a、b、c、d處的棧式符號表?xiàng)Ｊ椒柋硪妶Da、b、c、d。 test1f數(shù)組jfun2fun1nameyx 650TOPnamemainfun2fun1nameyx 60TOPxindfun1nameyx40TOPnameyx0TOP (a) (b) (c) (d) 圖 棧式符號表 real x,