第七章符號表

第七章:符號表管理技術(shù)7.1概述7.2符號表的組織與內(nèi)容7.3非分程序結(jié)構(gòu)語言的符號表組織7.4分程序結(jié)構(gòu)語言的符號表組織7.1概述(1)什么是符號表?在編譯過程中，編譯程序用于記錄源程序中各種名字的特性信息，

所以也稱為名字特性表。名字：

程序名、過程名、函數(shù)名、用戶定義類型、變量名、符號名字。特性信息：名字種類、類型、維數(shù)、參數(shù)個數(shù)及目標(biāo)地址（存儲單元地址）等。(2)建表和查表的必要性

(符號表在編譯過程中的作用)

源程序中變量要先聲明，然后才能引用。用戶通過聲明語句，聲明各種名字，以及給出它們的類型維數(shù)等信息，編譯程序在出來這些聲明語句時，因?qū)⒙暶髦械拿忠约靶畔⒌卿浀椒柋碇?，同時編譯還要給變量分配存儲單元，而存儲單元地址也必須登錄在符號表中。當(dāng)編譯程序編譯到引用所聲明的變量時（賦值或引用其值）要進(jìn)行語法語義正確性檢查

類型是否符合要求和生成相應(yīng)的目標(biāo)程序，這就需要查符號表來取得相關(guān)信息。1.語法分析和語義分析

說明語句賦值語句的語法規(guī)則

上下文有關(guān)分析；是否聲明；

類型一致性檢查2.生成目標(biāo)代碼LOADa的地址ADDb的地址STOx的地址

例:intx,a,b;

…

…

L:x:=a+b;

…

建表分配存貯符號表數(shù)據(jù)區(qū)X簡單變量整型A簡單變量整型B簡單變量整型L標(biāo)號(3)有關(guān)符號表的操作：填表和查表填表:當(dāng)分析到程序中的說明或定義語句時應(yīng)將說明或定義的名字以及與之有關(guān)的信息填入符號表中例：ProcedureP()查表:(1)填表前查表檢查在程序的同一作用域內(nèi)名字是否重復(fù)定義(2)檢查名字的種類是否與說明一致(3)對于強(qiáng)類型語言要檢查表達(dá)式中各變量的類型是否一致(4)生成目標(biāo)指令時要取得所需要的地址7.2符號表的組織與內(nèi)容(1)符號表的結(jié)構(gòu)與內(nèi)容符號表的基本結(jié)構(gòu)如下

名字特性(信息)

“名字”域:存放名字。一般為標(biāo)識符的符號串，也可為指向標(biāo)識符字符串串指針“特性”域：可包括多個子域，分別表示標(biāo)識符的有關(guān)信息。如：名字（標(biāo)識符）的種類：變量、函數(shù)、過程、數(shù)組、標(biāo)號、參數(shù)等類型：如整型、浮點(diǎn)型、字符型、指針等性質(zhì)：變量形參、值形參等名字：常量名地址：變量所分配單元的首址或地址位移大?。核嫉淖止?jié)數(shù)名字特性(信息)作用域的嵌套層次

對于數(shù)組：維數(shù)、上下界值、計(jì)算下標(biāo)量地址所用的信息以及數(shù)組元素類型等對于記錄（結(jié)構(gòu)、聯(lián)合）：域的個數(shù)、每個域名、地址位移、類型等對于過程或函數(shù)：形參個數(shù)、所在層次、函數(shù)返回值類型、局部變量所占空間大小等對于指針：所指對象類型等(2)組織方式1.統(tǒng)一符號表:無論什么名字都填入統(tǒng)一格式的符號表中符號表表項(xiàng)應(yīng)按信息量最大的名字設(shè)計(jì)

填表查表比較方便

結(jié)構(gòu)簡單

但是浪費(fèi)大量空間2.對于不同種類的名字分別建立各種符號表節(jié)省空間

但是填表和查表不方便3.折中辦法:大部分共同信息組成統(tǒng)一格式的符號表。特殊信息另設(shè)附表,兩者用指針連接.例：

begin

arrayB[1..100]

…

endB數(shù)組實(shí)型維數(shù)上下界首地址補(bǔ)充指針連接7.3非分程序結(jié)構(gòu)語言的符號表組織(1)分程序的結(jié)構(gòu)語言:每個可獨(dú)立進(jìn)行編譯的程序單元是一個不包含有子模塊的單一模塊.如Fortran語言Fortran程序構(gòu)造主程序子程序及函數(shù)主程序和子程序中可定義common語句(2)標(biāo)識符的作用域及基本處理辦法1.作用域:全局:

子程序名,函數(shù)名和公共區(qū)名局部:程序單元中定義的變量2.符號表的組織3.基本處理辦法<1>子程序函數(shù)名和公共區(qū)變量填入全局符號表全局符號表局部符號表<2>在聲明部分讀到標(biāo)識符,造局部符號表查本程序單元局部符號表,有無同名<3>在語句部分讀到標(biāo)識符

查表查本程序單元局部符號表有無同名有,重復(fù)聲明,報(bào)錯無,造表有,即已聲明無,查全局變量表有

全局量無

無定義標(biāo)識符(3)符號表的組織方式4.程序單元結(jié)束:釋放該程序單元的局部符號表5.程序編譯完成:釋放全部符號表1.無序符號表:按掃描順序建表,查表要逐項(xiàng)查找

查表操作的平均長度為:n+1/22.有序符號表符號表按變量名進(jìn)行字典式排序線性查表:n+1/2折半查表:log2n-1

3.散列符號表(Hash)表:符號表地址=Hash(標(biāo)識符)解決:沖突7.4分程序結(jié)構(gòu)語言的符號表組織(1)分程序的結(jié)構(gòu)語言:塊內(nèi)可嵌入子模塊(2)標(biāo)識符的作用域和基本處理方法作用域:標(biāo)識符局部于所定義的模塊(最小模塊)①模塊中所定義的標(biāo)識符作用域是定義該標(biāo)識符的子程序A為內(nèi)分程序局部變量

A為內(nèi)分程序全局變量都是局部變量RealA;RealA;RealA;RealA;RealA;RealA;B:=A;begin……procedureP(i,j);begin…Lend…gotoL;P(3,5);…End;②過程或函數(shù)說明中定義的標(biāo)識符（包括形參）

其作用域?yàn)楸具^程體例:③循環(huán)語句中定義的標(biāo)識符，其作用域?yàn)樵撗h(huán)語句for…dobegin…Lend…gotoL;…不能從循環(huán)體外轉(zhuǎn)到循環(huán)體內(nèi)循環(huán)語句應(yīng)看作一層建查符號表均要遵循標(biāo)識符作用域規(guī)定進(jìn)行建表不能重復(fù)

不能遺漏查表按標(biāo)識符作用域基本處理辦法：Realx,A,BIntegerx,y;procedurep()beginrealx;A:=x+2.0;…endB:=x+2.0定義重復(fù)錯誤必須填表查表是本層的查表是本層的(最外層的)處理方法假設(shè)標(biāo)識符是先聲明后引用(標(biāo)號例外,要特殊處理)a.在程序聲明部分讀到標(biāo)識符時

聲明性出現(xiàn)

建表查本層符號表

有無重名b.在語句中讀到標(biāo)識符(引用性出現(xiàn))查表查本層符號表

有無重名有

重復(fù)聲明

報(bào)錯無

填入符號表有

即已聲明

已取該名字信息

局部量無

是否是最外層?是

未聲明標(biāo)識符

報(bào)錯否

轉(zhuǎn)到直接外層c.標(biāo)準(zhǔn)標(biāo)識符的處理主要是語言定義的一些標(biāo)準(zhǔn)過程和函數(shù)的名字,它們是標(biāo)識符的子集。如sincosabs…

(注意

它們不是語言的保留字)特點(diǎn):

1)用戶不必聲明

就可全程使用2)設(shè)計(jì)編譯程序時標(biāo)準(zhǔn)名字及其數(shù)目已知處理方法:

1)單獨(dú)建表,使用不便,出錯2)預(yù)先將標(biāo)準(zhǔn)命填入名字表中,

因?yàn)樗鼈兪侨塘?所以應(yīng)填入最外層第八章符號表編譯過程中編譯程序需要不斷匯集和反復(fù)查證出現(xiàn)在源程序中各種名字的屬性和特征等有關(guān)信息。這些信息通常記錄在一張或幾張符號表中。符號表的每一項(xiàng)包括兩部分：一部分是名字（標(biāo)識符）；另一部分是此名字的有關(guān)信息。每個名字的有關(guān)信息是指種屬（如簡單變量、數(shù)組、過程等）、類型（如整、實(shí)、布爾等）。這些信息將用于語義檢查、產(chǎn)生中間代碼以及最終生成目標(biāo)代碼等不同階段。幾乎在編譯程序工作的全過程中，都需要對符號表進(jìn)行頻繁訪問，可以認(rèn)為查表或填表等操作，在編譯程序的編譯過程中是很大的一筆開銷。因此，合理地組織符號表，并相應(yīng)地選擇好查表和填表的方法，是提高編譯序工作效率的重要一環(huán)。例題與習(xí)題解答[例8。1]在編譯過程中，嵌套調(diào)用的過程間尋址問題如何解決？下面是一個示意性元程序，請給出編譯期間棧式符號表的變化情況。PROGRAMmaina=10;b,c:integer;d,e:real;PROCEDUREp(x:real);f:real;PROCEDUREq(y:real);g=5;n:boolean;BEGIN…IFe<0THENp(f);…..END;{q}BEGIN….Q(e);…END;{p}PROCEDUREt;j:real;BEGIN…p(e);…END;{t}BEGIN…WHILEc>0DO…;p(d);…END.{main}解：在編