符號表組織匯編課件

內(nèi)容提要:符號表的地位和作用符號表的組織與管理符號表的結(jié)構(gòu)設(shè)計符號表的構(gòu)造過程示例運行時刻存儲分配第

6

章 符號表組織----

語義分析之一16.1

符號表的地位和功能符號表是標識符的動態(tài)語義詞典，屬于編譯中語義分析的知識庫；主要內(nèi)容：⑴名字—標識符源碼，用作查詢關(guān)鍵字；⑵類型--該標識符的數(shù)據(jù)類型及其相關(guān)信息；⑶種類--該標識符在源程序中的語義角色；⑷地址--與值單元相關(guān)的一些信息；①

定義和重定義檢查；②

類型匹配校驗；③

數(shù)據(jù)的越界和溢出檢查；④

值單元存儲分配信息；⑤

函數(shù)、過程的參數(shù)傳遞與校驗；…符號表的功能標識符四種語義信息26.2

符號表的組織與管理符號表的工作原理⑴遇定義性標識符(在說明中)---把語義信息填入表中，并修改其TOKEN的指針，使其指向相應(yīng)的表項：（i

,

) 該標識符符號表項⑵遇應(yīng)用性標識符(在語句中)---查符號表的相應(yīng)項，查到后修改其TOKEN的指針，使其指向相應(yīng)的表項：（i

,

) 該標識符符號表項符號表的查詢、訪問方式線性表、順序表、索引表和散列表，皆可以采用。36.2.3

符號表的維護、管理方式※一個源文件有若干個函數(shù)組成，通常，每個函數(shù)對應(yīng)一個符號表，此外，還是有一個公用符號表；※符號表如何管理？往往取決于所屬語言的程序結(jié)構(gòu)，就C語言來說，可以在內(nèi)存設(shè)置一定長度的符號表區(qū)，并建立適當?shù)乃饕龣C制，訪問相應(yīng)的符號表：公用符號表現(xiàn)行函數(shù)符號表…FUNCTION

2

符號表FUNCTION

1

符號表全局

符號表區(qū)局部

符號表區(qū)…索引機制46.3

符號表的結(jié)構(gòu)設(shè)計【例6.1】有下列函數(shù)過程：FUNCTION

exp(x:REAL;VAR

y:INTEGER):REAL;CONST

pai=3.14;TYPE

arr=ARRAY[1..5,1..10]

OF

INTEGER;VAR

a:arr;

b,a:real;BEGIN

…

;

a[2,5]:=100;

b:=z+6;…

END;⑴

需要進符號表的標識符：exp(函數(shù),附帶信息:類型、參數(shù)情況和入口地址

p…ai),(常量),arr(類型),a(下標變量)，b(簡單變量)，⑵…怎樣檢查出：a

重定義、z

無定義以及下表變量a[2,5]的值地址在何處？…5※

符號表的體系結(jié)構(gòu)設(shè)計PFINFL(函數(shù)表)CONSL(常量表)AINFL(數(shù)組表)RINFL(結(jié)構(gòu)表)VALL(活動紀錄)LENL(長度表)TYPEL（類型表）TVAL

TPOINT·…由于標識符的種類不同，導(dǎo)致語義屬性也不盡相同；怎樣組織符號表？下面提供一個符號表的體系結(jié)構(gòu)：名字類型種類地址SYNBL（符號表）token

NAME

TYPE

CAT

ADDRi

·

…66.3.1 符號表總表(SYNBL)NAMETYPCATADDR※

結(jié)構(gòu)：NEME(名字)— 標識符源碼(或內(nèi)部碼)TYP(類型)

– 指針，指向類型表相應(yīng)項；CAT(種類)

– 種類編碼：f(函數(shù))，c(常量)，t(類型)，d(域名)，

v,vn,vf(變量，換名形參，賦值形參)；ADDR(地址)

– 指針，根據(jù)標識符的種類不同，分別指向：PFINFL,CONSL,LENL,VALL,…76.3.2 類型表(TAPEL)※

結(jié)構(gòu)：TVALTPOINTTVAL(類碼)– 類型代碼：i(整型)，r(實型)，c(字符型)，b(布爾型)，

a(數(shù)組型)，d(結(jié)構(gòu)型)，…TPOINT(指針)

– 根據(jù)數(shù)據(jù)類型不同，指向不同的信息表項：① 基本數(shù)據(jù)類型(i,r,c,b)–

nul(空指針)；② 數(shù)組類型(a)

– 指向數(shù)組表；③ 結(jié)構(gòu)類型(d)

– 指向結(jié)構(gòu)表;…86.3.3 數(shù)組表(AINFL)※

結(jié)構(gòu)：LOWUPCTPCLEN每維占表中一個紀錄LOW(數(shù)組的下界)--（C語言自動設(shè)為：0）;UP(數(shù)組的上界)—CTP(成分類型指針)

– 指針，指向該維數(shù)組成分類型(在類型表中的信息);CLEN(成分類型的長度)– 成分類型的數(shù)據(jù)所占值單元的個數(shù)；※ 這里假定：值單元個數(shù)依字長為單位計算。96.3.4 結(jié)構(gòu)表(RINFL)※

結(jié)構(gòu)：每個域占表中一個紀錄ID(結(jié)構(gòu)的域名)—OFF(區(qū)距)—是idk的值單元首址相對于所在記錄值區(qū)區(qū)頭位置；約定：off1=0，off2=

off1+LEN(tp1),

……offn= offn-1+LEN(tpn-1)。idn-1的長度TP(域成分類型指針)

– 指針，指向idk域成分類型(在類型表中的信息);IDOFFTP106.3.5 函數(shù)表(PFINFL)----

過程或函數(shù)語義信息※

結(jié)構(gòu)：LEVELOFFFNENTRYPARAM…LEVEL(層次號)

–該過函靜態(tài)層次嵌套號,OFF(區(qū)距)

–該過函自身數(shù)據(jù)區(qū)起始單元相對該過函值區(qū)區(qū)頭位置

；FN(參數(shù)個數(shù))

– 該過函的形式參數(shù)的個數(shù)；PARAM(參數(shù)表)

– 指針，指向形參表；ENTRY(入口地址)

– 該函數(shù)目標程序首地址(運行時填寫)；116.3.6

其他表(…)個數(shù)；⑴ 常量表(CONSL)-- 存放相應(yīng)常量的初值；※

結(jié)構(gòu)：⑵ 長度表(LENL)

– 存放相應(yīng)數(shù)據(jù)類型所占值單元※

結(jié)構(gòu)：⑶ 活動紀錄表(VALL)

– 一個函數(shù)(或過程)虛擬的值單元存儲分配表；此分配表在運行調(diào)用時才可用，故稱活動紀錄?！?/p>

結(jié)構(gòu)：…126.4

符號表的構(gòu)造過程示例：ENT…2?xrtpvfv2yitpvnv3臨時變量值區(qū)b值數(shù)組a值區(qū)鏈接表y值x值exp值管理區(qū)3.1450aac,i,r,bv310

v2v1v5v4exp

rtp

fx

rtp

vf

v2y

itp

vn

v3SYNBL

PFINFLVALLCONSLLENLAINFL1

51

10

itp

1pai

rtp

carr

tv

v4rtp

v

v5TYPEL13【例6.2】有類型說明:TYPE

arr

=

ARRAY

[1..10]

OF

ARRAY

[1..5]

OF

INTEGER;試填寫符號表。SYNBLTYPELircbAINFLarra110a15itp設(shè)：實型占8個存儲單元，整型占4個單元，布爾型和字符型占1個單元14。420tLENL200【例6.3】有類型說明:試填寫符號表。

SYNBLAINFLd設(shè)：實型占8個存儲單元，整型占4個單元，布爾型和字符型占1個單元。110btp1rec

tLENLTYPE

rec

=RECORDu:INTEGER;v:

ARRAY

[1..10]

OF

BOOLEAN;r:

RECORD

x,

y

:

REAL

ENDEND;TYPELi,r,c,bRINFLu0itpuitpdv4advdr14x0rtprtprrtpdxddy8yrtp30410168815【例6.4】有過程說明:設(shè)P1所在層BELGEIVNEL=…1，…即E所N定D;義的層LEVEL=2,

試填寫符號表。SYNBLTYPELvf設(shè)：實型占8個存儲單元，整型占4個單元，布爾型和字符型占1個單元16。PROCEDURE P1(VAR

x:

REAL;

y:INTEGER);……ircbPFINFLP1rtppyrtp12P12?2

Entryxvn?xrtpvn?yrtpvf??注：？——該標識符的值單元首址，為相對地址（LEVEL,

offset）LEVEL——該標識符所在層次號，

offset——區(qū)距，存儲分配時可定。6.5

運行時刻存儲分配※解決的問題：標識符變量的地址分配與對它們的訪問。6.5.1

標識符值單元分配值單元分配分兩類：1.靜態(tài)分配在編譯階段即可完成真實的地址分配。在編譯時對所有數(shù)據(jù)對象分配固定的存儲單元，且在運行是始終保持不變。2.動態(tài)分配指在運行時刻進行的值單元分配，在編譯時只能進行相對地址分配?！Ｊ絼討B(tài)分配；·堆式動態(tài)分配。注：值單元分配是以過程函數(shù)為單位的。176.5.2

活動記錄可以在編譯時確定的。1.三個概念過程：一個可執(zhí)行模塊，過程或函數(shù)，通常完成特定的功能。活動：過函的一次執(zhí)行。每執(zhí)行一次過程體，則產(chǎn)生該過函的一個活動?；顒佑涗洠阂粋€有結(jié)構(gòu)的連續(xù)存儲塊。用來存儲過函一次執(zhí)行中所需要的信息?；顒佑涗泝H是一種存儲映像，編譯程序所進行的運行時刻存儲分配是在符號表中進行的。如果不支持可變數(shù)據(jù)結(jié)構(gòu)，活動記錄的體積是18臨時單元內(nèi)情向量局部變量形式單元靜態(tài)鏈動態(tài)鏈返回地址6.5.2 活動記錄（續(xù)）2.活動記錄的結(jié)構(gòu)（1）連接數(shù)據(jù)區(qū)VALLTOPSP連接數(shù)據(jù)局部數(shù)據(jù)·返回地址：·動態(tài)鏈：指向調(diào)用該過程的主調(diào)程序的活動記錄的指針；·靜態(tài)鏈：指向靜態(tài)直接外層活動記錄的指針。（2）形式單元用來存放實參的值或地址。（3）局部數(shù)據(jù)區(qū)用來存放局部變量、內(nèi)情向量、臨時單元。（4）棧指針SP

—指向現(xiàn)行過程活動記錄的起點，即第一個單元；TOP

—指向（已占用）棧頂單元，即活動記錄的最后一個單元。19臨時單元內(nèi)情向量局部變量形式單元參數(shù)個數(shù)返回地址Old

SPR的活動記錄Q的活動記錄Main的活動記錄全局數(shù)據(jù)區(qū)6.5.3

簡單的棧式存儲分配·以C語言為例:沒有分程序結(jié)構(gòu)，過程定義不允許嵌套，但允許過程的遞歸調(diào)用。1．C語言程序的存儲組織【例6.5】

C語言過程調(diào)用關(guān)系：Main(

)

Q(

)

R(

)則，活動記錄棧狀態(tài)為：TOPSP2．C的活動記錄其中：Old

SP值，即前一活動記錄的地址；SPTOP206.5.3 簡單的棧式存儲分配（續(xù)）3．C語言的過程調(diào)用與返回（1）過程調(diào)用①

過程調(diào)用的四元式序列：(param,

entry(t1),

_,

_)……②

對應(yīng)的目標指令：(i+3)[TOP]

:=

entry(ti).Addr·(param,

entry(ti),_,

_)對應(yīng)的指令：//將ti地址填到活動記錄的形參區(qū)去·(call,

entry(P),

n,

_)對應(yīng)的指令：1[TOP]

:=

SP

//保護現(xiàn)行SP3[TOP]:=n

//傳遞參數(shù)個數(shù)JSP

P第n個實參地址………t1參數(shù)個數(shù)返回地址Old

SP……(param,

entry(tn),

_,

過_)程P的入口地址

(call,

entry(P),

n,

_)參數(shù)個數(shù)TOPSP主調(diào)過程活動記錄子過程

P的活動記錄形參區(qū)………t1n返回地址SP……主調(diào)過程活動21記錄子過程

P的活動記錄③ 子過程P需完成的工作：定義自己的活動記錄；SP

:=

TOP+11[SP]:=返回地址

TOP:=TOP+L//定義過程P的SP//保護返回地址//定義新TOPLSPTSOPPTOP6.5.3 簡單的棧式存儲分配（續(xù)）3．C語言的過程調(diào)用與返

（2）過程返① 過程返 的四元式：(ret,

_,

_,

_)②

對應(yīng)的目標指令：//恢復(fù)TOP//恢復(fù)SPTOP

:=

SP-1SP

:=

0[SP]X

:=

2[TOP]地址，X為某一變址器//取返

UJ

0[X]//按X中的返 地址實行變址轉(zhuǎn)移主調(diào)過程活動記錄子過程

P的活動記錄LTOPTOPSPSP………t1n返 地址SP……返

X地址226.5.4

嵌套過程語言的棧式存儲分配標識符的作用域·過程嵌套的一個關(guān)鍵問題：標識符的作用域問題。標識符的作用范圍往往與它所處的過程相關(guān)，也就是說，同一個標識符，在不同的程序段里，代表不同的對象，具有不同的性質(zhì)，因此要分配不同的存儲空間?！俗R符的有效范圍：服從最小作用域原理；在外層未定義，而在內(nèi)層定義的，服從內(nèi)層定義；在外層已定義，而在內(nèi)層未定義的，服從全范圍；在外層已定義，而在內(nèi)層也定義的，在外層服從外層定義，在內(nèi)層服從內(nèi)層定義。236.5.4 嵌套過程語言的棧式存儲分配（續(xù)）2.活動記錄·問題的提出：過程Q可能會引用到它的任意外層過程的最新活動記錄中的某些數(shù)據(jù)。·解決問題的思想：為了在活動記錄中查找這些非局部名字所對應(yīng)的存儲空間，過程Q運行時必須設(shè)法跟蹤它的所有外層過程的最新活動記錄的地址。·解決方案：活動記錄中增加靜態(tài)鏈！使其指向直接外層的最新活動記錄的首地址；臨時單元內(nèi)情向量局部變量形式單元參數(shù)個數(shù)靜態(tài)鏈返 地址Old

SPSPTOP連接數(shù)據(jù)243.嵌套層次顯示表(display)和活動記錄結(jié)構(gòu)用于訪問外層的變量Old

SP返回地址全局Display地址參數(shù)個數(shù)……形式單元……顯示區(qū)表(Display)……局部變量……內(nèi)情向量……臨時單元SPTOP(1)連接數(shù)據(jù)區(qū)：

0～2；·老SP—主調(diào)過程的活動記錄首址；·全局display地址—主調(diào)過程的顯示區(qū)表首址；012連接數(shù)據(jù)(2)參數(shù)個數(shù)：3；3形參值單元區(qū)：

入口為4；·換名形參（vn）—分配2個單元（地址傳遞）；·賦值形參（vf）—按相應(yīng)類型長度分配；顯示區(qū)表(display)：占l+1個單元；l為層次號，包含直接外層嵌套的l個過程的活動記錄的首址，再加上本過程的活動記錄首址；局部變量區(qū)：入口為off+l+2；·off為形參區(qū)最后一個值單元地址；4l+1·局部變量值單元按相應(yīng)類型長度分配地址；·類型標識符、常量標識符等不分配值單元；編譯系統(tǒng)定義的變量，按局部變量值單元分配原則分配地址；(6)臨時變量區(qū)：25……臨時單元……內(nèi)情向量……局部變量……顯示區(qū)表(Display)……形式單元參數(shù)個數(shù)全局Display地址返回地址Old

SP4.

Display表的建立設(shè)過程調(diào)用關(guān)系為Q(

)

R(

)，且R(

)的層次號為l，則Q與R的display表的關(guān)系如下:SPTOPOld

SP返回地址全局Display地址參數(shù)個數(shù)……形式單元……顯示區(qū)表(Display)……局部變量……內(nèi)情向量……臨時單元Q的活動記錄R的活動記錄拷貝l個單元拷貝自身的SPl+1個單元26program

P;var

a,

x:

integer;1

procedure

Q(b:

integer);var

i:

integer;2

procedure

R(u:

integer;

var

v:

integer);var

c,

d:

integer;beginif

u=1

then

u=u+1;……v:=

(a+c)+(b-d);……end

{R}begin……R(1,

x);……a,xu,vc,db,ic,iend

{Q}1

procedure

S;var

c,

i:

integer;begina:=1;Q(c);……end

{S}begina:=0;S;……end.層次：0【例6.6】設(shè)有Pascal程序片段如下：變量作用域：過程調(diào)用關(guān)系為：P

S

Q

R27【例6.6】 試給出程序運行時的活動記錄關(guān)系。09-125-84321x局部變量aDisplay表0參數(shù)個數(shù)0全局Display

0返 地址Old

SP0局部變量Display表參數(shù)個數(shù)返 地址Old

SPDisplay表形式單元返 地址Display表形式單元參數(shù)個數(shù)0全局Display

40130ci171615141318Q的活動記錄(1層)Old

SP

13全局Display17參數(shù)個數(shù)

130292827b02719-22i

23-2637-40

局部變量3635R的活動記錄(2層)Old

SP

27全局Display35返 地址43424131-342u45-4844v02741cd58-6154-57

局部變量53525149-50R活動記錄Q活動記錄S活動記錄P活動記錄活動記錄棧a-(0,5)x-(0,9)c-(1,6)i-(1,10)b-(1,4)i-(1,10)u-(2,4)v-(2,8)c-(2,15)d-(2,19)S的活動記錄(1層)P的活動記錄28(0層)5.值單元的地址分配·值單元分配是依據(jù)活動記錄的結(jié)構(gòu)，在符號表中進行的?！纠?.7】設(shè)有Pascal程序片段如下，P1所在層level=2；PROCEDURE

P1(

x:

REAL;

VAR

y:

BOOLEAN

);CONST

pai=3.14;TYPE

arr=ARRAY

[1..10]

OF

INTEGER;VAR

m:

INTEGER;a:

arr;l:

REAL;FUNCTION

F1(

z:

REAL;

k:

INTEGER

):

REAL;BEGIN

……

END;……;BEGIN……;END;試給出符號表組織及值單元分配情況。設(shè)：(1)實型占8個存儲單元，整型占4個單元，布爾型和字符型占1個單元。

(2)換名形參vn分配2個單元，賦值形參vf按相應(yīng)類型長度分配；29接上頁：SYNBLi,r,c,bTYPELP1的VALLCONSLLENLAINFL·過程P1定義的層次為l=332104-111412-1315P1p3PFINFL3

2

Entryxrtpvf(3,4btpvny()3,12)pairtpc3.14arra110itp