編譯原理第九章-符號表

第9章符號表數(shù)計學(xué)院

宋彩芳第一頁，共六十二頁。9

符號表符號表的作用和地位符號的主要屬性及作用符號表的組織符號表的管理第二頁，共六十二頁。符號表的作用和地位符號表用來存放語言程序中出現(xiàn)的有關(guān)標識符的屬性信息，這些信息集中反映了標識符的語義特征屬性；在詞法分析及語法分析過程中不斷積累和更新表中的信息。在詞法分析到代碼生成的各個階段，按各自需要從表中獲取不同的屬性信息。第三頁，共六十二頁。符號表的作用和地位符號表的功能有：收集符號屬性；int

i[3][5];上下文語義的合法性檢查的依據(jù)；extern

float

i;

//類型不一致float

i[4][2];

//重定義作為目標代碼生成階段地址分配的依據(jù)；extern

公共區(qū)extern

static文件靜態(tài)區(qū)static

函數(shù)靜態(tài)區(qū)auto

動態(tài)區(qū)第四頁，共六十二頁。9

符號表符號表的作用和地位符號的主要屬性及作用符號表的組織符號表的管理第五頁，共六十二頁。符號的主要屬性及作用語言符號可分為：關(guān)鍵字（保留字）符號操作符符號標識符符號語言中標識符可以是變量名、函數(shù)名、過程名；過程沒有返回值,如同C的void函數(shù)則有,如同C的帶返回值函數(shù)第六頁，共六十二頁。標識符符號的屬性(信息）幾種通常都是需要的。符號名符號的類型符號的存儲類別符號的作用域及可視性符號變量的存儲分配信息符號的其它屬性數(shù)組內(nèi)情向量記錄結(jié)構(gòu)型的成員信息函數(shù)及過程的形參第七頁，共六十二頁。標識符符號的屬性(信息）一、符號名符號名與它在符號表中的位置一一對應(yīng)；標識符的內(nèi)部代碼也即標識符在符號表中的位置（通常是一個整數(shù)）可以替換符號名；符號表運行過程中，表中的標識符名始終是唯一標志；特殊情形：重名標識符定義：根據(jù)標識符在程序中的作用域和可視性規(guī)則進行處理。表中標識符名始終唯一；操作重載：通過它們的參數(shù)個數(shù)和類型，以及函數(shù)返回值類型來區(qū)別。以達到標識符的唯一；第八頁，共六十二頁。標識符符號的屬性(信息）三、符號的存儲類別由關(guān)鍵字指定；用static定義屬于文件的靜態(tài)存儲變量或?qū)儆诤瘮?shù)內(nèi)部的靜態(tài)存變量用regist定義使用寄存器存儲的變量；由變量在程序中位置決定；函數(shù)外是程序的公共存儲變量函數(shù)內(nèi)是內(nèi)部變量；存儲類別作用：編譯過程語義處理、檢查和存儲分配的重要依據(jù)；決定了符號變量的作用域、可視性和它的生命周期；第十頁，共六十二頁。標識符符號的屬性(信息）四、符號的作用域及可視性：作用域：符號變量在程序中起作用的范圍；如C語言中聲明為extern的外部變量，其作用域是整個程序；在函數(shù)外聲明的靜態(tài)變量的作用域是定義該靜態(tài)變變量的文件；函數(shù)內(nèi)聲明的靜態(tài)變量作用域是定義該變量的函數(shù)；第十一頁，共六十二頁。標識符符號的屬性(信息）影響變量可視性的情況：函數(shù)的形式參數(shù)；int

a;int

fun(float

a,

float

b){……a……}//引用float

a改變可見性——作用域操作符::int

a;int

fun(float

a,

float

b){……a……//引用float

a……

::a

……

//引用int

a

}第十二頁，共六十二頁。標識符符號的屬性(信息）影響變量可視性的情況：復(fù)合語句分程序結(jié)構(gòu)；{

int

a;…{

char

a;…{

…{

float

a;…}…a…

//引用char

a｝｝｝第十三頁，共六十二頁。標識符符號的屬性(信息）為確立符號的作用域和可視性，符號表屬性除了需要符號的存儲類別之外還需要表示該符號在程序結(jié)構(gòu)上被定義的層次；第十四頁，共六十二頁。標識符符號的屬性(信息）五、符號變量的存儲分配信息：根據(jù)符號變量的存儲類別定義及它們出現(xiàn)的位置和次序來確定每個變量應(yīng)分配的存儲區(qū)及在該區(qū)的具體位置；存儲區(qū)靜態(tài)存儲區(qū)：生命周期是程序運行的全過程；公共靜態(tài)區(qū)：如extern定義的外部變量；局部靜態(tài)區(qū)：如static定義的靜態(tài)變量；·

函數(shù)外表示文件可視性，函數(shù)內(nèi)表示所在函數(shù)可視；動態(tài)存儲區(qū)：生命周期是定義該變量的局部范圍；第十五頁，共六十二頁。標識符符號的屬性(信息）具體位置：按該變量在存儲區(qū)類分別依出現(xiàn)先后的次序排列下相對該存儲區(qū)表頭的相對位移量來表示的；…Int

a;….float

b;…Struct

cc{int

d;float

e;}

c;…第十六頁，共六十二頁。標識符符號的屬性(信息）符號的其他屬性：數(shù)組內(nèi)情向量數(shù)組類型、維數(shù)、各維上下界、數(shù)組首地址；記錄結(jié)構(gòu)型的成員信息全體成員確定其存儲分配；成員排列次序的屬性信息；函數(shù)及過程的形參形參個數(shù)、形參的排列次序及每個形參的類型；第十七頁，共六十二頁。9

符號表符號表的作用和地位符號的主要屬性及作用符號表的組織符號表的管理第十八頁，共六十二頁。符號表的組織符號表的總體組織不同種類符號，其屬性信息種類不完全相同；不同程度但有有所不同；符號表項的排列關(guān)鍵字域的組織其他域的組織第十九頁，共六十二頁。符號表的組織第二十頁，共六十二頁。符號表的組織第一種：按屬性種類完全相同的那些符號組織在一起；第二十一頁，共六十二頁。符號表的組織第一種：按屬性種類完全相同的那些符號組織在一起；優(yōu)點：每個符號表存放符號的屬性個數(shù)和結(jié)構(gòu)完全相同；表項等長，且表項每個屬性欄都有效；對單個符號表來說，管理方便一直，空間效率高；缺點：同時管理多個符號表，增加了總體管理的工作量和復(fù)雜度；第二十二頁，共六十二頁。符號表的總體組織把所有語言中的符號都組織在一張符號表中；第二十三頁，共六十二頁。符號表的總體組織把所有語言中的符號都組織在一張符號表中；優(yōu)點：總體管理非常集中單一，且不同種類符號的共同屬性可以一致地管理和處理；缺點：增加了符號表管理的復(fù)雜度；增加無用的屬性空間，從而增加了空間開銷；第二十四頁，共六十二頁。符號表的總體組織根據(jù)符號屬性相似程度分類組織若干張表；第二十五頁，共六十二頁。符號表的總體組織根據(jù)符號屬性相似程度分類組織若干張表；折中的組織方式在管理復(fù)雜性及時空效率方面都取得折中的效果。對復(fù)雜性和效率的取舍可由設(shè)計者根據(jù)自己的經(jīng)驗和要求及目標系統(tǒng)的客觀環(huán)境和需求進行選擇和調(diào)整；第二十六頁，共六十二頁。屬性3欄與屬性4欄冗余，可將其合并；增加了符號表管理和運行的復(fù)雜性，但減少了空間開銷；符號表的總體組織第二十七頁，共六十二頁。符號表的總體組織總結(jié)：為便于符號表的組織管理，每張符號表的表長通常為定長是合理的；每張符號表可以看作是一個多元組，每個元組由若干屬性組成，元組之間有相同的成員個數(shù)和一致的排列；元組之間的區(qū)分由表項中“符號”一欄區(qū)分；第二十八頁，共六十二頁。符號表的組織符號表的總體組織符號表項的排列關(guān)鍵字域的組織其他域的組織第二十九頁，共六十二頁。符號表項的排列符號表作為一個多元組，表中元組的排列組織是構(gòu)造符號表的重要成分。在編譯程序的整個工作過程中，符號表被頻繁地用來建立表項，查找表項，填充和引用表項的屬性。在編譯程序中，符號表項的組織傳統(tǒng)上采用三種構(gòu)造方法。即線性法，二分法及散列法。第三十頁，共六十二頁。符號表項的排列管理簡單但運行效率低；線性組織符號表中表項按它的符號被掃描的先后順序登錄；………..…a…………..b..…..a…..……..d..…c…….……b….第三十一頁，共六十二頁。符號表項的排列排列組織及二分法符號表中表項按其符號的字符代碼串的值的大小排列；………..…a…………..b..…..a…..……..d..…c…….……b….排序表的空間組織和存儲開銷與線性表相同，但運行效率高于線性表，算法復(fù)雜性也高于線性表；第三十二頁，共六十二頁。符號表項的排列散列組織對符號進行某種函數(shù)操作（雜湊函數(shù)）所得的函數(shù)值確定它在符號表的位置；Vhash=fhash（符號代碼值）=

mod（Vhash，N）改進：Lhash………..…a…………..b..…..a…..……..d..…c…….……b….第三十三頁，共六十二頁。符號表項的排列散列組織需事項注意：散列沖突，解決方法是多次散列方法；散列函數(shù)的選擇：靜態(tài)符號表動態(tài)符號表

對符號代碼的位操作作為雜湊函數(shù)，如符號代碼的字段疊加或加權(quán)疊加以及符號代碼的對折或多對折等位操作；第三十四頁，共六十二頁。符號表的組織符號表的總體組織符號表項的排列關(guān)鍵字域的組織其他域的組織第三十五頁，共六十二頁。關(guān)鍵字域的組織有關(guān)符號的基礎(chǔ)知識保留字操作符標識符外部名（前6個字符可以惟一地區(qū)分）內(nèi)部名（前31個字符可以惟一地區(qū)分）可見，標識符的內(nèi)部規(guī)則是符號表關(guān)鍵字組織的基礎(chǔ)和依據(jù)；第三十六頁，共六十二頁。關(guān)鍵字域的組織等長關(guān)鍵字域（段）符號表設(shè)置關(guān)鍵字段為標識符的最大長度；第三十七頁，共六十二頁。關(guān)鍵字域的組織不等長關(guān)鍵字段符號表采用關(guān)鍵字池的索引結(jié)構(gòu)。第三十八頁，共六十二頁。符號表的組織符號表的總體組織符號表項的排列關(guān)鍵字域的組織其他域的組織第三十九頁，共六十二頁。其他域的組織等長屬性值域組織符號表中符號的屬性值具有相同類型且等長；不等長屬性域組織符號表中符號的屬性值具有相同類型但長度不同；下推鏈域的組織第四十頁，共六十二頁。等長屬性值域組織可以取相應(yīng)的數(shù)據(jù)類型表達屬性值符號布爾性質(zhì)的屬性域defined

1(true)表示已定義defined

0(false)表示未定義表示符號的基本數(shù)據(jù)類型Data-type3個bit位（整型值）Char0

0

0

(0)short0

0

1

(1)int0

1

0

(2)long0

1

1

(3)unsigned1

0

0

(4)float1

0

1

(5)double1

1

0

(6)第四十一頁，共六十二頁。等長屬性值域組織可以取相應(yīng)的數(shù)據(jù)類型表達屬性值符號變量：存儲類別——數(shù)據(jù)類型一樣的構(gòu)造方式存儲位移——整型量表示相對位移量第四十二頁，共六十二頁。等長屬性值域組織可以取相應(yīng)的數(shù)據(jù)類型表達屬性值結(jié)構(gòu)struct

tag1

{memb1memb2struct

tag2

{memb3

memb4memb5}

memb6memb7}

stv;第四十四頁，共六十二頁。不等長屬性值域組織另設(shè)空間存放屬性值數(shù)組的內(nèi)情向量array1(subscrip1,subscrip2)array2(subscrip3,subscrip4,subscrip5,subscrip6)第四十五頁，共六十二頁。不等長屬性值域組織另設(shè)空間存放屬性值C語言中數(shù)組特別的含義int

abc[3][4][2];第四十六頁，共六十二頁。不等長屬性值域組織復(fù)合屬性域的組織存在若干個可用位表示的信息該符號變量是否初始化該符號是否是結(jié)構(gòu)成員該符號是否是標號該符號是否是保留字第四十八頁，共六十二頁。下推鏈域的組織實現(xiàn)同名標識符的語義功能第四十九頁，共六十二頁。9

符號表符號表的作用和地位符號的主要屬性及作用符號表的組織符號表的管理第五十頁，共六十二頁。符號表的管理符號表的作用反映了符號表的行為：符號表的初始化符號的登錄符號的查找符號表中分程序結(jié)構(gòu)層次的管理第五十一頁，共六十二頁。符號表的初始化符號表的表長是漸增變化的情況線性組織和二分法組織符號表的表長是確定的情況散列組織的符號表第五十二頁，共六十二頁。符號的登錄不同組織方式導(dǎo)致不同的登錄方式線性方法：圖9.21二分方法：圖9.22散列表：通過雜湊算法決定登錄表項的位置；登入的內(nèi)容：名字登入名字屬性：取決于編譯程序獲得某個符號時編譯所處的程序掃描點的狀態(tài)；第五十三頁，共六十二頁。符號的登錄符號a的屬性…func(x,y){

…struct

tag

{int

a[n][m];}

t;…}類型屬性存儲類別屬性作用域?qū)傩源鎯Ψ峙鋵傩詳?shù)組內(nèi)情向量屬性第五十四頁，共六十二頁。符號的查找目的：建立和確認該符號的屬性；步驟：先在保留字表和運算符表中查找；再在標識符表中查找；查找算法與該符號表的組織方式密切相關(guān)；線性表：順序查找

二分表：折半查找

雜湊表：雜湊算法查找第五十五頁，共六十二頁。符號表中分程序結(jié)構(gòu)層次管理｛float

a;int

a;

float

b,d;{int

c;{int

d;

float

c;{float

d;a=b+c+d;}

}

}

}第五十六頁，共六十二頁。符號表中分程序結(jié)構(gòu)層次管理分表結(jié)構(gòu)對每個分程序建立一個獨立的分表結(jié)構(gòu)的符號表動態(tài)建立和動態(tài)消亡｛float

a;int

a;

float

b,d;{int

c;{intd;

float

c;{float

d;a=b+c+d;}

}

}

}第五十七頁，共六十二頁。符號表中分程序結(jié)構(gòu)層次管理單表結(jié)構(gòu)把分程序符號組織在一張總表結(jié)構(gòu)的符號表中。特定要求：為了標志符號所屬的分程序?qū)哟?，在符號表中可設(shè)立一個屬性域用