符號表的作用ppt課件Chapt8符合表

1、國防科技大學(xué)計算機(jī)系602教研室第八章 符號表符號表符號表的作用符號表的作用: : 一致性檢查和作用域分析一致性檢查和作用域分析; ; 輔助代碼生成輔助代碼生成. .國防科技大學(xué)計算機(jī)系602教研室8.1 8.1 符號表的組織與作用符號表的每一項符號表的每一項( (入口入口) )包含兩大欄包含兩大欄: : 名字欄，也稱主欄，關(guān)鍵字欄名字欄，也稱主欄，關(guān)鍵字欄 信息欄，記錄相應(yīng)的不同屬性，分為若干子欄信息欄，記錄相應(yīng)的不同屬性，分為若干子欄. .對符號表的操作對符號表的操作: : 填入名稱填入名稱 查找名字查找名字 訪問信息訪問信息 填寫修改信息填寫修改信息 刪除刪除國防科技大學(xué)計算機(jī)系602教

2、研室對符號表進(jìn)行操作的時機(jī)：對符號表進(jìn)行操作的時機(jī)： 定義性出現(xiàn)定義性出現(xiàn) 使用性出現(xiàn)使用性出現(xiàn)按名字的不同種屬建立多張符號表，如常數(shù)表、變量名表、過按名字的不同種屬建立多張符號表，如常數(shù)表、變量名表、過程名表、程名表、符號的組織方式符號的組織方式: :1. 1. 安排各項各欄的存儲單元為固定長度安排各項各欄的存儲單元為固定長度2. 2. 用間接方式安排各欄存儲單元用間接方式安排各欄存儲單元國防科技大學(xué)計算機(jī)系602教研室符號表的存放次序符號表的存放次序: :1. 1. 把每一項置于連續(xù)把每一項置于連續(xù)k存儲單元中，構(gòu)成一存儲單元中，構(gòu)成一張張k*n的表的表2. 把整個符號表分成把整個符號表分

3、成m個子表，如個子表，如t1,t2,tm，每個子表含有，每個子表含有n項項.國防科技大學(xué)計算機(jī)系602教研室例: : pascalpascal程序段：procedure incwap(mprocedure incwap(m，n:integer);n:integer);label start;label start;varvar k:integer; k:integer;beginbeginstart:start: k:=m+1; k:=m+1; m:=n+4; m:=n+4; n:=k; n:=k;end.end.國防科技大學(xué)計算機(jī)系602教研室procedure incwap(mproced

4、ure incwap(m，n:integer);n:integer);label start;label start;varvar k:integer; k:integer;beginbeginstart:start: k:=m+1; k:=m+1; m:=n+4; m:=n+4; n:=k; n:=k;end.end.表 0.1 符號名表 sntnameinformationm形式參數(shù)，整型，值參數(shù)n形式參數(shù)，整型，值參數(shù)k整型，變量國防科技大學(xué)計算機(jī)系602教研室表 0.2 常數(shù)表 ct值(value)(1)1(2)4procedure incwap(mprocedure incwap(m

5、，n:integer);n:integer);label start;label start;varvar k:integer; k:integer;beginbeginstart:start: k:=m+1; k:=m+1; m:=n+4; m:=n+4; n:=k; n:=k;end.end.國防科技大學(xué)計算機(jī)系602教研室表 0.3 入口名表 entnameinformation(1)incwap 二目子程序,入口四元式:1procedure incwap(mprocedure incwap(m，n:integer);n:integer);label start;label start;

6、varvar k:integer; k:integer;beginbeginstart:start: k:=m+1; k:=m+1; m:=n+4; m:=n+4; n:=k; n:=k;end.end.國防科技大學(xué)計算機(jī)系602教研室 表 0.4 標(biāo)號表 ltname information(1)start 四元式:(4)procedure incwap(mprocedure incwap(m，n:integer);n:integer);label start;label start;varvar k:integer; k:integer;beginbeginstart:start: k:=

7、m+1; k:=m+1; m:=n+4; m:=n+4; n:=k; n:=k;end.end.國防科技大學(xué)計算機(jī)系602教研室表 0.1 符號名表 sntnameinformationm形式參數(shù)，整型，值參數(shù)n形式參數(shù)，整型，值參數(shù)k整型，變量表 0.2 常數(shù)表 ct值(value)(1)1(2)4表 0.3 入口名表 entnameinformation(1)incwap 二目子程序,入口四元式:1 表 0.4 標(biāo)號表 ltname information(1)start 四元式:(4)國防科技大學(xué)計算機(jī)系602教研室 表 0.5 四元式表 qtopropn1opn2result(1)li

8、nk(2)parincwap1m(3)parincwap2n(4)+m1k(5)+n4m(6):=kn(7) returnprocedure incwap(mprocedure incwap(m，n:integer);n:integer);label start;label start;varvar k:integer; k:integer;beginbeginstart:start: k:=m+1; k:=m+1; m:=n+4; m:=n+4; n:=k; n:=k;end.end.國防科技大學(xué)計算機(jī)系602教研室8 8. .2 2 整理和查找1. 線性查找線性查找按關(guān)鍵字出現(xiàn)的順序填寫各

9、項。按關(guān)鍵字出現(xiàn)的順序填寫各項。填表快，查找慢。填表快，查找慢。結(jié)構(gòu)簡單，節(jié)省空間，效率低，查找時間結(jié)構(gòu)簡單，節(jié)省空間，效率低，查找時間復(fù)雜度復(fù)雜度：o(n)(n)。改進(jìn)：改進(jìn)：自適應(yīng)線性表自適應(yīng)線性表國防科技大學(xué)計算機(jī)系602教研室2. 二分查找二分查找表格中的項按名字的表格中的項按名字的“大小大小”順序整理排列。順序整理排列。填表慢填表慢, ,查找快。查找時間查找快。查找時間復(fù)雜度復(fù)雜度: :o(log2n)改進(jìn)：組織成二叉樹。改進(jìn)：組織成二叉樹。3. 3. 雜湊查找雜湊查找( (hashhash技術(shù)技術(shù)) )雜湊函數(shù)雜湊函數(shù)h(sym)：0n-1 n：符號表的項數(shù)。符號表的項數(shù)。要求：要

10、求：1. 計算簡單高效計算簡單高效 2. 函數(shù)值分布均勻函數(shù)值分布均勻填表快，查找快填表快，查找快國防科技大學(xué)計算機(jī)系602教研室8 8. .4 4 符號表的內(nèi)容n符號表的信息欄中登記了每個名字的有關(guān)符號表的信息欄中登記了每個名字的有關(guān)性質(zhì)性質(zhì) 類型：整、實或布爾等類型：整、實或布爾等種屬：簡單變量、數(shù)組、過程等種屬：簡單變量、數(shù)組、過程等大小：長度，即所需的存儲單元字?jǐn)?shù)大?。洪L度，即所需的存儲單元字?jǐn)?shù)相對數(shù)：指分配給該名字的存儲單元相對數(shù)：指分配給該名字的存儲單元的相對地址的相對地址國防科技大學(xué)計算機(jī)系602教研室pl 語言編譯程序的符號表1. 表格的定義表格的定義n名字表名字表(namet

11、ab)n程序體表程序體表(btab)n層次顯示表層次顯示表(display)n數(shù)組信息表數(shù)組信息表(atab)n中間代碼表中間代碼表(code)國防科技大學(xué)計算機(jī)系602教研室1) 名字表名字表(nametab) 名字表名字表nametab：登記程序中出現(xiàn)的各種名字及其屬性登記程序中出現(xiàn)的各種名字及其屬性name kind lev typ normal ref adr/val/size link01tx名字標(biāo)識符名字標(biāo)識符名字種類，可以是常量名字種類，可以是常量(constant)、變量、變量(variable)、類、類型型(type)、過程、過程(procedure)名字所在的程序體的靜態(tài)層

12、次。規(guī)名字所在的程序體的靜態(tài)層次。規(guī)定主程序的層次為定主程序的層次為1，主程序中定，主程序中定義的層次為義的層次為2，依次類推，依次類推名字的類型，類型有整型名字的類型，類型有整型(ints)、字符型、字符型(chars)、布爾型、布爾型(bool)、數(shù)組、數(shù)組(arrays)，對，對于無類型的名字填入于無類型的名字填入notype一個布爾量，用于標(biāo)明名字是否為變量形參一個布爾量，用于標(biāo)明名字是否為變量形參名，當(dāng)名字是否為變量形參名時填入名，當(dāng)名字是否為變量形參名時填入false，其他情況填入其他情況填入true或不填或不填當(dāng)名字為數(shù)組類型或數(shù)組變量名時，當(dāng)名字為數(shù)組類型或數(shù)組變量名時，ref

13、指向該數(shù)組在數(shù)指向該數(shù)組在數(shù)組信息表中的位置；當(dāng)名字為過程名時，組信息表中的位置；當(dāng)名字為過程名時，ref指向該過程指向該過程在程序體表在程序體表(btab)中的位置；其他情況中的位置；其他情況ref為為0adr, 當(dāng)名字為變量名時當(dāng)名字為變量名時(包括形參，存入該變量包括形參，存入該變量(或形參或形參)在相應(yīng)活動記錄在相應(yīng)活動記錄中分類的存貯單元的相對地址；對于過程名，填入他們相應(yīng)代碼的入口地中分類的存貯單元的相對地址；對于過程名，填入他們相應(yīng)代碼的入口地址址val, 當(dāng)名字為變量名時，填入他們的相應(yīng)值當(dāng)名字為變量名時，填入他們的相應(yīng)值size, 當(dāng)名字為類型名時，填入該類型數(shù)據(jù)所需存貯單元

14、的數(shù)目當(dāng)名字為類型名時，填入該類型數(shù)據(jù)所需存貯單元的數(shù)目指向同一程序體中定義的上一個名字指向同一程序體中定義的上一個名字在在nametab中的位置，每個程序體在中的位置，每個程序體在nametab中登記的第一個名字的中登記的第一個名字的link為為0國防科技大學(xué)計算機(jī)系602教研室(2) 程序體表程序體表btab和層次顯示表和層次顯示表display程序體表程序體表btab：記錄個程序體的總信息，用記錄個程序體的總信息，用于對源程序中定義的名字的作用域進(jìn)行分析于對源程序中定義的名字的作用域進(jìn)行分析；對名字表進(jìn)行管理；對名字表進(jìn)行管理lastpar lastpsizevsize01bx指向本程序

15、體中最后一個形式參在指向本程序體中最后一個形式參在nametab中的位置中的位置指向本程序體中最后一個名字在指向本程序體中最后一個名字在nametab中的位置中的位置本程序體所有形參所需體積、包本程序體所有形參所需體積、包括連接數(shù)據(jù)所占空間括連接數(shù)據(jù)所占空間本程序體所有局部數(shù)據(jù)所本程序體所有局部數(shù)據(jù)所需空間大小需空間大小國防科技大學(xué)計算機(jī)系602教研室層次顯示表層次顯示表display：描述正在處理的各嵌描述正在處理的各嵌套層，對程序體表進(jìn)行管理套層，對程序體表進(jìn)行管理01levellastpar lastpsizevsize01bxbtab國防科技大學(xué)計算機(jī)系602教研室(3)數(shù)組信息表數(shù)組

16、信息表atabinxtypeltypelreflowhighelsizesize12ax數(shù)組的下標(biāo)類型數(shù)組的下標(biāo)類型數(shù)組元素類型數(shù)組元素類型當(dāng)元素為數(shù)組時，它指向當(dāng)元素為數(shù)組時，它指向該元素數(shù)組信息在該元素數(shù)組信息在atab表表中的位置，其他情況為中的位置，其他情況為0數(shù)組下限數(shù)組下限數(shù)組上限數(shù)組上限數(shù)組元素的體積數(shù)組元素的體積數(shù)組本身的體積數(shù)組本身的體積國防科技大學(xué)計算機(jī)系602教研室type a=array1.10, 1.10 of integer;name kindtypref katype arraysntxnametabinxtyp eltypelreflow high elsize

17、 size nintsarraysm11010100 mintsints0110110axatab國防科技大學(xué)計算機(jī)系602教研室(4) 中間代碼表中間代碼表codecode：用于存放編譯程序所產(chǎn)生的每條中間用于存放編譯程序所產(chǎn)生的每條中間代碼。代碼。國防科技大學(xué)計算機(jī)系602教研室8 8. .3 3 名字的作用范圍在許多程序語言中在許多程序語言中, ,名字都有一個確定的作用范圍名字都有一個確定的作用范圍. .兩種程序體結(jié)構(gòu)兩種程序體結(jié)構(gòu): : 并列結(jié)構(gòu)，如并列結(jié)構(gòu)，如fortranfortran 嵌套結(jié)構(gòu)，如嵌套結(jié)構(gòu)，如pascalpascal，adaada國防科技大學(xué)計算機(jī)系602教研室p

18、rogram main integer x，ycommon /c/a，b endsubroutine sub1 real x，zcommon /c/a1，b1 end國防科技大學(xué)計算機(jī)系602教研室program p; var a,b : integer; procedure p1(i1, j1:integer); var c,d : integer end; procedure p2(i2, j2:integer); var a,c : integer; procedure p21; var b1,b2 : boolean; end; end; end.國防科技大學(xué)計算機(jī)系602教研室1.

19、fortranfortran的符號表組織的符號表組織 一個一個fortranfortran程序由一個主程序段和若干程序由一個主程序段和若干個輔程序段組成個輔程序段組成. 把局部名和全局名分別存在不同的地方把局部名和全局名分別存在不同的地方.2. 嵌套結(jié)構(gòu)語言的符號表組織嵌套結(jié)構(gòu)語言的符號表組織 如如pascalpascal、algolalgol、adaada作用域遵循作用域遵循 最近最近嵌套原則嵌套原則 .國防科技大學(xué)計算機(jī)系602教研室pascal pascal程序本身可以看成是一個操作系程序本身可以看成是一個操作系統(tǒng)所調(diào)用的過程，過程可以嵌套和遞歸。統(tǒng)所調(diào)用的過程，過程可以嵌套和遞歸。 一

20、個一個pascal過程：過程：過程頭；過程頭；說明段（由一系列的說明語句組成）；說明段（由一系列的說明語句組成）；begin執(zhí)行體（由一系列的執(zhí)行語句組成）；執(zhí)行體（由一系列的執(zhí)行語句組成）；end國防科技大學(xué)計算機(jī)系602教研室作用域作用域：一個名字能被使用的區(qū)域范圍：一個名字能被使用的區(qū)域范圍稱作這個名字的作用域。稱作這個名字的作用域。允許同一個標(biāo)識符在不同的過程中代表允許同一個標(biāo)識符在不同的過程中代表不同的名字。不同的名字。名字作用域規(guī)則名字作用域規(guī)則- 最近嵌套原則最近嵌套原則 一個在子程序一個在子程序b1中說明的名字中說明的名字x只在只在b1中中有效（局部于有效（局部于b1）；）；

21、如果如果b2是是b1的一個內(nèi)層子程序且的一個內(nèi)層子程序且b2中對中對標(biāo)識符標(biāo)識符x沒有新的說明，則原來的名字沒有新的說明，則原來的名字x在在b2中仍然有效。如果中仍然有效。如果b2對對x重新作了說明重新作了說明，那么，那么，b2對對x的任何引用都是指重新說的任何引用都是指重新說明過的這個明過的這個x。國防科技大學(xué)計算機(jī)系602教研室program main var a, b : real; procedure p1 var b:boolean; begin end procedure p2 var a:integer; begin endbegin enda(real)b(real)b(boo

22、l)a(integr)國防科技大學(xué)計算機(jī)系602教研室兩種做法兩種做法: :引入引入 過程編號過程編號 屬性屬性。查找時，先查找本查找時，先查找本過程編號的名字，查不到則查找外層過程過程編號的名字，查不到則查找外層過程編號的名字，編號的名字，等等，等等. .按按 棧棧 式思想組織符號表。查找時，從后式思想組織符號表。查找時，從后往前查找，碰到的第一個名字就是所需查往前查找，碰到的第一個名字就是所需查找的名字找的名字. .國防科技大學(xué)計算機(jī)系602教研室pl語言的中間代碼指令格式：指令格式： opcod l a opcod：操作碼：操作碼 l：第一操作數(shù)，程序體層數(shù)：第一操作數(shù)，程序體層數(shù) a：

23、第一操作數(shù)，相對地址：第一操作數(shù)，相對地址編譯是如何確定變量的層數(shù)編譯是如何確定變量的層數(shù)(地址地址)？運行是如何根據(jù)指令中變量的層數(shù)和相對地址確定變量的存儲運行是如何根據(jù)指令中變量的層數(shù)和相對地址確定變量的存儲單元？單元？國防科技大學(xué)計算機(jī)系602教研室program p; var a,b : integer; procedure p1(i1, j1:integer); var c,d : integer end; procedure p2(i2, j2:integer); var a,c : integer; procedure p21; var b1,b2 : boolean; end;

24、 end; end.國防科技大學(xué)計算機(jī)系602教研室 n n a a m m e e t t a a b b b b t t a a b b d d i i s s p p l l a a y y0 00 01 11 12 23 3l l e e v ve e l l 3 34 40 00 07 70 01 11 1 5 51 1 2 22 21 1 4 41 1 7 73 32 2 0 00 04 42 2 2 20 01 1c c h h a ar r0 02 2i i n n t te e g ge e r r1 13 3b b o o o ol l e ea a n n2 24 4f

25、f a a l ls s e e3 35 5t t r r u ue e4 46 6r r e e a ad d5 57 7w w r r i it t e e6 68 8a a0 09 9b b8 81 1 0 0p p 1 19 91 1 1 1i i 1 10 01 1 2 2j j 1 11 1 1 11 1 3 3c c1 1 2 21 1 4 4d d1 1 3 31 1 5 5p p 2 21 1 0 01 1 6 6i i 2 20 01 1 7 7j j 2 21 1 6 61 1 8 8a a1 1 7 71 1 9 9c c1 1 8 82 2 0 0p p 2 2 1

26、11 1 9 92 2 1 1b b 1 10 02 2 2 2b b 2 22 2 1 1program p; var a,b : integer; procedure p1(i1, j1:integer); var c,d : integer end; procedure p2(i2, j2:integer); var a,c : integer; procedure p21; var b1,b2 : boolean; end; end; end.國防科技大學(xué)計算機(jī)系602教研室 n n a a m m e e t t a a b b b b t t a a b b d d i i s s p p l l a a y y0 00 01 11 12 23 3l l e e v ve e l l 3 34 40 00 07 70 01 11 1 5 51 1 2 22 21 1 4 41 1 7 73 32 2 0 00 04 42 2 2 20 01 1c c h h a ar r0 02 2i i n n t te e g ge e r r1 13 3b b o o o ol l e ea a n n2 24 4f f a a l ls s e e3 35 5t t r r u ue e4 46 6r r e e a ad d5 57 7w w r r i it t e e6