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

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

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

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

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

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

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

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

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

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

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

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

12、定：變量的作用域是定義它的塊程序；同一塊內(nèi)的變量不能重名，但不同塊以及嵌套塊之間的變量可以重名，因而某變量的聲明可與嵌套塊的內(nèi)層變量同名，使用時(shí)局部變量?jī)?yōu)先。 下面為一段C程序，右邊給出當(dāng)編譯程序編譯到此處時(shí)的有效變量。 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行時(shí)，符號(hào)表中應(yīng)含有變量name,y,x的記錄。編譯到第4行時(shí)，符號(hào)表中應(yīng)含有變量x,ind, fun1,name, y,x的記錄，此時(shí)，符號(hào)表同時(shí)含有兩個(gè)變量x的記錄，而在函數(shù)fun1內(nèi)有效的變量是局部變量x，即第4行聲明的變量。而編

14、譯到第6行時(shí)，符號(hào)表中有變量fun1,name, y,x的記錄，x,ind失效。編譯到第10行時(shí)，有效變量為test1,f, j,fun2, fun1,name, y,x。而編譯到第11行時(shí)，符號(hào)表中有變量j,fun2, fun1,name, y,x的記錄，test1,f失效。編譯到第15行時(shí)，符號(hào)表中應(yīng)含有變量name, main, fun2, fun1,name, y,x的記錄，此時(shí)，在主函數(shù)main內(nèi)使用的變量x和y都是全局變量。 棧式符號(hào)表 對(duì)于塊程序結(jié)構(gòu)語(yǔ)言，其最簡(jiǎn)單的符號(hào)表結(jié)構(gòu)為棧式符號(hào)表，它包括一個(gè)符號(hào)表?xiàng)＜耙粋€(gè)塊索引棧。 符號(hào)表?xiàng)Ｓ涗涀兞康膶傩?，塊索引棧指出每個(gè)塊的符號(hào)表的開始

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

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

17、指的單元，逐一檢查，如果有與要插入的變量同名，則表示源程序中存在變量重復(fù)聲明的錯(cuò)誤；如果沒有，才可將該標(biāo)識(shí)符的屬性入棧。 查表操作要對(duì)符號(hào)棧進(jìn)行從頂(TOP-1)到底進(jìn)行線性搜索，這樣確保找到的變量滿足局部變量?jī)?yōu)先于全局變量的規(guī)則。由于棧式符號(hào)表中記錄是無序的，因而查詢效率比較差。 棧式符號(hào)表例 ，有一段C程序如下，畫出編譯到a、b、c、d處的棧式符號(hào)表。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棧式符號(hào)表解：a、b、c、d處的棧式符號(hào)表?xiàng)Ｊ椒?hào)表見圖a、b、c、d。 test1f數(shù)組jfun2fun1nameyx 650TOPnamemainfun2fun1nameyx 60TOPxindfun1nameyx40TOPnameyx0TOP (a) (b) (c) (d) 圖 棧式符號(hào)表 棧式符號(hào)表解：a、b、c、d處的棧式符號(hào)表?xiàng)Ｊ椒?hào)表見圖a、b、c、d。 test1f數(shù)組jfun2fun1nameyx 650TOPnamemainfun2fun1nameyx 60TOPxindfun1nameyx40TOPnameyx0TOP (a) (b) (c) (d) 圖 棧式符號(hào)表 real x,