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

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

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

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

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

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

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

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

8、表按變量名進行字典式排序。3. 散列符號表（Hash表）： 符號表地址 = Hash（標識符） 解決：沖突166.4 分程序結構語言的符號表組織 分程序的結構語言：模塊內(nèi)可嵌入子模塊。(2) 標識符的作用域和基本處理方法作用域：標識符局部于所定義的模塊（最小模塊） 模塊中所定義標識符的作用域是定義該標識符的子程序。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ù)說明中定義的標識符（包括形參）其作用域為本過程體。例1219 循環(huán)語句中定義的標識符，其作用域為該循環(huán)語句。for do begin : L endgoto L; :不能從循環(huán)體外轉到循環(huán)體內(nèi)。循環(huán)語句應看作一層！20基本處理辦法：建查符號表均要遵循標識符作用域規(guī)定進行。建表：不能重復，不能遺漏。查表：按標識符作用域查找。begin real x, A, B; integer x, y; begin real x; A:= x + 2.0; : end : B:= x + 2.0end定義重復錯誤查表, 是內(nèi)層的x必須填表查表，是外層的x21處理方法:假設標識符是先聲明后

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

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

12、例：設有如下分程序：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;嵌套結構為： A, B, C, D1層 L1, E, F2 L2, L3, G, H3 A426分程序表和符號表：OUTERNECOUNTPOINTER104213314431L1, E, FAL2, L3, G, HA, B, C, D分程序索引

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

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棧式符號表結構main符號表m1符號表p2符號表p3符號表main符號表m1符號表q2符號表main符號表m1符號表main符號表釋放符號表m1符號表p2符號表main符號表main符號表m1符號表主程序main符號表棧頂main符號表m1符號表p2符號表main符號表m1符號表p2mainm1p3q20122332p2mainm1p3q2012233int1編譯P3說明部分后的符號棧狀態(tài)：78910111213indpara11223intrealarrayboolvarprocprocvarvarparaxp2p3test1fp3m1p2m1主分程序索引表012345xvar0000varvarvarvarinameint06procykrealrealarraym1mainintj