編譯原理課件：Chapter-6 符號表管理技術(shù)

1、1第六章 符號表管理技術(shù)概述符號表的組織與內(nèi)容非分程序結(jié)構(gòu)語言的符號表組織 分程序結(jié)構(gòu)語言的符號表組織 26.1 概述(1)什么是符號表？ 在編譯過程中，編譯程序用來記錄源程序中各種名字的特性信息，所以也稱為名字特性表。名字: 程序名、過程名、函數(shù)名、用戶定義類型名、變量名、常量名、枚舉值名、標(biāo)號名等。特性信息: 上述名字的種類、類型、維數(shù)、參數(shù)個(gè)數(shù)及目標(biāo)地址（存儲單元地址）等。 3(2)建表和查表的必要性(符號表在編譯過程中的作用)源程序中變量要先聲明，然后才能引用。用戶通過聲明語句，聲明各種名字，并給出它們的類型維數(shù)等信息。編譯程序在遇到這些聲明語句時(shí)，應(yīng)該將聲明中的名字以及信息登錄到符號

2、表中，同時(shí)編譯程序還要給變量分配存儲單元。存儲單元地址也必須登錄在符號表中。當(dāng)編譯程序編譯到引用所聲明的變量時(shí)（賦值或引用其值），要進(jìn)行語法語義正確性檢查（類型是否符合要求等）和生成相應(yīng)的目標(biāo)程序，這就需要查符號表以取得相關(guān)信息。4例：int x, a, b;.L: x := a + b;.建表，分配存貯L 標(biāo)號b 簡單變量 整型a 簡單變量 整型x 簡單變量 整型符號表數(shù)據(jù)區(qū)1. 語法分析和語義分析 說明語句、賦值語句的語法規(guī)則； 上下文有關(guān)分析：是否聲明； 類型一致性檢查。 2. 生成目標(biāo)代碼 LOAD a的地址 ADD b的地址 STO x的地址5(3)有關(guān)符號表的操作：填表和查表填表：

3、當(dāng)分析到程序中的說明或定義語句時(shí)，應(yīng)將說明或 定義的名字，以及與之有關(guān)的信息填入符號表中。 例：Procedure P( )查表：(1) 填表前查表，檢查在程序的同一作用域內(nèi)名字 是否重復(fù)定義； (2) 檢查名字的種類是否與說明一致； (3) 對于強(qiáng)類型語言，要檢查表達(dá)式中各變量的類型 是否一致； (4) 生成目標(biāo)指令時(shí)，要取得所需要的地址。 66.2 符號表的組織與內(nèi)容(1)符號表的結(jié)構(gòu)與內(nèi)容符號表的基本結(jié)構(gòu)如下:名字特性（信息）“名字”域：存放名字。一般為標(biāo)識符的符號串，也可為指向標(biāo)識符字符串的指針。7“特性”域：可包括多個(gè)子域，分別表示標(biāo)識符的有關(guān)信息。如：名字（標(biāo)識符）的種類：簡單變量

4、、函數(shù)、過程、 數(shù)組、標(biāo)號、參數(shù)等類型：如整型、浮點(diǎn)型、字符型、指針等性質(zhì)：變量形參、值形參等 值：常量名所代表的數(shù)值地址：變量所分配單元的首址或地址位移大小：所占的字節(jié)數(shù)作用域的嵌套層次:名字特性（信息）8對于數(shù)組：維數(shù)、上下界值、計(jì)算下標(biāo)量地址所用的信息 （數(shù)組信息向量）以及數(shù)組元素類型等。對于記錄（結(jié)構(gòu)、聯(lián)合）：域的個(gè)數(shù)，每個(gè)域名、地址位移、類型等。對于過程或函數(shù)：形參個(gè)數(shù)、所在層次、函數(shù)返回值類型、 局部變量所占空間大小等。對于指針：所指對象類型等。9(2)符號表的組織方式 1.統(tǒng)一符號表不論什么名字都填入統(tǒng)一格式的符號表中2.對于不同種類的名字分別建立各種符號表 符號表表項(xiàng)應(yīng)按信息量

5、最大的名字設(shè)計(jì)。填表、查表比較方便，結(jié)構(gòu)簡單，但是浪費(fèi)大量空間。 節(jié)省空間，但是填表和查表不方便。 符號名表（用來登記源程序中的常量名、變量名、數(shù)組名和過程名等，并記錄其屬性、引用等） 常數(shù)表（分類型登記各種常量值） 標(biāo)號表（登記標(biāo)號的定義與應(yīng)用） 分程序入口表（登記過程的層號、分程序符號表的入口等） 中間代碼表10例: begin real A; array B1:100; : : endAB簡變 實(shí)型地址 實(shí)型 數(shù)組維數(shù)上下界首地址指針連接補(bǔ)充3.折中辦法大部分共同信息組成統(tǒng)一格式的符號表。特殊信息另設(shè)附表，兩者用指針連接。116.3 非分程序結(jié)構(gòu)語言的符號表組織(1)非分程序的結(jié)構(gòu)語言：

6、每個(gè)可獨(dú)立進(jìn)行編譯的程序單元是一個(gè)不包含有子模塊的單一模塊。如FORTRAN語言。FORTRAN程序構(gòu)造主程序子程序及函數(shù)主程序和子程序中可定義common語句：FORTRAN程序中各程序單位之間的數(shù)據(jù)交換可以通過虛實(shí)結(jié)合來實(shí)現(xiàn)，也可以通過建立公用區(qū)的方式來完成。公用區(qū)有兩種，一種是無名公用區(qū)，任何一個(gè)程序中只可能有一個(gè)無名公用區(qū)；一種是有名公用區(qū)，一個(gè)程序中可以根據(jù)需要由程序員開辟任意多個(gè)有名公用區(qū)。無名和有名公用區(qū)都通過COMMON語句來進(jìn)行建立。 12(2)標(biāo)識符的作用域及基本處理辦法 1. 作用域全局：子程序名、函數(shù)名和公共區(qū)名。局部：程序單元中定義的變量。2. 符號表的組織: 全局符

7、號表局部符號表13 在子程序(函數(shù))聲明部分讀到標(biāo)識符時(shí)，構(gòu)造局部符號表。查本程序單元局部符號表，有無同名有：重復(fù)聲明，報(bào)錯(cuò)無：填表 在語句部分讀到標(biāo)識符，查表。查本程序單元局部符號表，有無同名有：已聲明過無：查全局變量表有：全局量無：無定義標(biāo)識符3. 基本處理辦法: 子程序、函數(shù)名和公共區(qū)變量填入全局符號表。 14查表操作的平均長度為 （n + 1）2。4. 程序單元結(jié)束：釋放該程序單元的局部符號表。5. 程序執(zhí)行完成：釋放全部符號表。(3)符號表的組織方式 1. 無序符號表按掃描順序建表，查表要逐項(xiàng)查找。15線性查表: （n + 1） / 2折半查表:12-Log n2. 有序符號表：符號

8、表按變量名進(jìn)行字典式排序。3. 散列符號表（Hash表）： 符號表地址 = Hash（標(biāo)識符） 解決：沖突166.4 分程序結(jié)構(gòu)語言的符號表組織 分程序的結(jié)構(gòu)語言：模塊內(nèi)可嵌入子模塊。(2) 標(biāo)識符的作用域和基本處理方法作用域：標(biāo)識符局部于所定義的模塊（最小模塊） 模塊中所定義標(biāo)識符的作用域是定義該標(biāo)識符的子程序。17real A;A為內(nèi)分程序局部變量12real A;A為內(nèi)分程序全局變量121real A;2real A;2都是局部變量1real A;2real A;B:=A;18begin procedure P (i, j); begin : L end goto L; P(3, 5);

9、end ; 過程或函數(shù)說明中定義的標(biāo)識符（包括形參）其作用域?yàn)楸具^程體。例1219 循環(huán)語句中定義的標(biāo)識符，其作用域?yàn)樵撗h(huán)語句。for do begin : L endgoto L; :不能從循環(huán)體外轉(zhuǎn)到循環(huán)體內(nèi)。循環(huán)語句應(yīng)看作一層！20基本處理辦法：建查符號表均要遵循標(biāo)識符作用域規(guī)定進(jìn)行。建表：不能重復(fù)，不能遺漏。查表：按標(biāo)識符作用域查找。begin real x, A, B; integer x, y; begin real x; A:= x + 2.0; : end : B:= x + 2.0end定義重復(fù)錯(cuò)誤查表, 是內(nèi)層的x必須填表查表，是外層的x21處理方法:假設(shè)標(biāo)識符是先聲明后

10、引用（標(biāo)號例外，要特殊處理）。a. 在程序聲明部分讀到標(biāo)識符時(shí)（聲明性出現(xiàn)） 建表: 查本層符號表，有無同名有：重復(fù)聲明，報(bào)錯(cuò)無：填入符號表b. 在語句中讀到標(biāo)識符（引用性出現(xiàn)），查表:查本層符號表，有無同名有：即已聲明。則取該名字信息（局部量）。無，是否是最外層？是：未聲明標(biāo)識符。報(bào)錯(cuò)(n - 1)否：轉(zhuǎn)到直接外層22c. 標(biāo)準(zhǔn)標(biāo)識符的處理 主要是語言定義的一些標(biāo)準(zhǔn)過程和函數(shù)的名字。它們是標(biāo)識符的子集。如 sin con abs.（注意它們不是語言的保留字）特點(diǎn)：1) 用戶不必聲明就可全程使用。 2) 設(shè)計(jì)編譯程序時(shí)，標(biāo)準(zhǔn)名字及其數(shù)目已知。處理方法：1) 單獨(dú)建表：使用不便，費(fèi)時(shí)。 2) 預(yù)

11、先將標(biāo)準(zhǔn)標(biāo)識符填入名字表中。因?yàn)樗鼈兪侨塘?，所以?yīng)填入最外層。23分程序符號表的組織方式：1、分層組織符號表的登記項(xiàng)各分程序符號表登記項(xiàng)按照語法識別順序連續(xù)排列在一起，不為其內(nèi)層分程序的符號表登記項(xiàng)所割裂。、用“分程序表”索引各分程序符號表的信息分程序表中的各登記項(xiàng)是自左至右掃描源程序的過程中，按分程序出現(xiàn)的順序依次填入的，且對每一個(gè)分程序填寫一個(gè)登記項(xiàng)。分程序表登記項(xiàng)序號隱含地表征各分程序的編號。24分程序表結(jié)構(gòu)：其中：OUTERN指明該分程序的直接外層分程序的編號ECOUNT記錄該分程序符號表登記項(xiàng)的個(gè)數(shù)POINTER指向該分程序符號表的起始位置OUTERNECOUNTPOINTER25

12、例：設(shè)有如下分程序：PROCEDURE VAR A, B, C, D: REAL; PROCEDURE LAREL L1; VAR E, F: REAL; BEGIN END; PROCEDURE LAREL L2, L3; VAR G, H: REAL; FUNCTION VAR A: INTERGER; BEGIN END; BEGIN END;嵌套結(jié)構(gòu)為： A, B, C, D1層 L1, E, F2 L2, L3, G, H3 A426分程序表和符號表：OUTERNECOUNTPOINTER104213314431L1, E, FAL2, L3, G, HA, B, C, D分程序索引

13、表各分程序符號表分程序索引表的形成順序每個(gè)模塊頭的出現(xiàn)順序分程序符號表的形成順序每個(gè)模塊(語法分析時(shí)的語法單位)識別順序27分程序符號表構(gòu)造方法：本例中，分程序符號表的形成順序?yàn)?、4、3、1，這個(gè)次序是閉分程序的次序(分程序中END出現(xiàn)的次序)。為使各分程序的符號表連續(xù)地鄰接在一起，并在掃描具有嵌套分程序結(jié)構(gòu)的源程序時(shí)，總是按先進(jìn)后出的順序來掃描其中各個(gè)分程序，可設(shè)一個(gè)臨時(shí)工作棧。每當(dāng)進(jìn)入一層分程序時(shí)，就在棧頂預(yù)造該分程序的符號表，而當(dāng)遇到該層分程序的結(jié)束符(END)時(shí)，此時(shí)該分程序的全部登記項(xiàng)已位于棧頂，再將該分程序的全部登記項(xiàng)移至正式符號表中。28例：Pascal程序的分程序結(jié)構(gòu)示例如下

14、program main (); var x, y : real; i, k: integer; name: array 116 of char; : procedure m1 (ind: integer); var x : integer procedure p2 (j : real); : procedure p3; var f : array 15 of intrger test1: boolean; begin : end; p30123p2main 0m1p329 begin : end; p2 procedure q2; var r1, r2 : real; begin : p2(

15、r1+r2); : end; q2 begin : p2(x/y); : end;m1 begin : m1(i+k); :end main0122program main (); var x, y : real; i, k: integer; name: array 116 of char; : procedure m1 (ind:integer); var x : integer procedure p2 (j : real); : procedure p3; var f : array 15 of intrger test1: boolean; begin : end; p3 begin

16、 : end;p2 procedure q2; var r1,r2 : real; begin : p2(r1+r2); : end; q2 begin : p2(x/y); : end;m1 begin : m1(i+k); : end main 0123201230p2mainm1p3q201223program main (); var x, y : real; i, k: integer; name: array 116 of char; : procedure m1 (ind:integer); var x : integer procedure p2 (j : real); : p

17、rocedure p3; var f : array 15 of intrger test1: boolean; begin : end; p3 begin : end;p2 procedure q2; var r1,r2 : real; begin : p2(r1+r2); : end; q2 begin : p2(x/y); : end;m1 begin : m1(i+k); : end main 0123231棧式符號表結(jié)構(gòu)main符號表m1符號表p2符號表p3符號表main符號表m1符號表q2符號表main符號表m1符號表main符號表釋放符號表m1符號表p2符號表main符號表main符號表m1符號表主程序main符號表?xiàng)ｍ攎ain符號表m1符號表p2符號表main符號表m1符號表p2mainm1p3q20122332p2mainm1p3q2012233int1編譯P3說明部分后的符號棧狀態(tài)：78910111213indpara11223intrealarrayboolvarprocprocvarvarparaxp2p3test1fp3m1p2m1主分程序索引表012345xvar0000varvarvarvarinameint06procykrealrealarraym1mainintj