符號(hào)表組織匯編課件

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

6

章 符號(hào)表組織----

語(yǔ)義分析之一16.1

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

定義和重定義檢查；②

類型匹配校驗(yàn)；③

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

值單元存儲(chǔ)分配信息；⑤

函數(shù)、過程的參數(shù)傳遞與校驗(yàn)；…符號(hào)表的功能標(biāo)識(shí)符四種語(yǔ)義信息26.2

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

,

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

,

) 該標(biāo)識(shí)符符號(hào)表項(xiàng)符號(hào)表的查詢、訪問方式線性表、順序表、索引表和散列表，皆可以采用。36.2.3

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

2

符號(hào)表FUNCTION

1

符號(hào)表全局

符號(hào)表區(qū)局部

符號(hào)表區(qū)…索引機(jī)制46.3

符號(hào)表的結(jié)構(gòu)設(shè)計(jì)【例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;⑴

需要進(jìn)符號(hào)表的標(biāo)識(shí)符：exp(函數(shù),附帶信息:類型、參數(shù)情況和入口地址

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

重定義、z

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

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

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

NAME

TYPE

CAT

ADDRi

·

…66.3.1 符號(hào)表總表(SYNBL)NAMETYPCATADDR※

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

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

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

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

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

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

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

– 根據(jù)數(shù)據(jù)類型不同，指向不同的信息表項(xiàng)：① 基本數(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每維占表中一個(gè)紀(jì)錄LOW(數(shù)組的下界)--（C語(yǔ)言自動(dòng)設(shè)為：0）;UP(數(shù)組的上界)—CTP(成分類型指針)

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

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

off1+LEN(tp1),

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

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

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

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

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

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

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

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

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

– 該函數(shù)目標(biāo)程序首地址(運(yùn)行時(shí)填寫)；116.3.6

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

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

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

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

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

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

符號(hào)表的構(gòu)造過程示例：ENT…2?xrtpvfv2yitpvnv3臨時(shí)變量值區(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;試填寫符號(hào)表。SYNBLTYPELircbAINFLarra110a15itp設(shè)：實(shí)型占8個(gè)存儲(chǔ)單元，整型占4個(gè)單元，布爾型和字符型占1個(gè)單元14。420tLENL200【例6.3】有類型說明:試填寫符號(hào)表。

SYNBLAINFLd設(shè)：實(shí)型占8個(gè)存儲(chǔ)單元，整型占4個(gè)單元，布爾型和字符型占1個(gè)單元。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,

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

x:

REAL;

y:INTEGER);……ircbPFINFLP1rtppyrtp12P12?2

Entryxvn?xrtpvn?yrtpvf??注：？——該標(biāo)識(shí)符的值單元首址，為相對(duì)地址（LEVEL,

offset）LEVEL——該標(biāo)識(shí)符所在層次號(hào)，

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

運(yùn)行時(shí)刻存儲(chǔ)分配※解決的問題：標(biāo)識(shí)符變量的地址分配與對(duì)它們的訪問。6.5.1

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

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

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

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

SPR的活動(dòng)記錄Q的活動(dòng)記錄Main的活動(dòng)記錄全局?jǐn)?shù)據(jù)區(qū)6.5.3

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

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

)

Q(

)

R(

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

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

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

entry(t1),

_,

_)……②

對(duì)應(yīng)的目標(biāo)指令：(i+3)[TOP]

:=

entry(ti).Addr·(param,

entry(ti),_,

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

entry(P),

n,

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

:=

SP

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

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

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

SP……(param,

entry(tn),

_,

過_)程P的入口地址

(call,

entry(P),

n,

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

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

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

:=

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

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

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

_,

_,

_)②

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

:=

SP-1SP

:=

0[SP]X

:=

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

UJ

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

P的活動(dòng)記錄LTOPTOPSPSP………t1n返 地址SP……返

X地址226.5.4

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

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

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

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

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

SP4.

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

)

R(

)，且R(

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

SP返回地址全局Display地址參數(shù)個(gè)數(shù)……形式單元……顯示區(qū)表(Display)……局部變量……內(nèi)情向量……臨時(shí)單元Q的活動(dòng)記錄R的活動(dòng)記錄拷貝l個(gè)單元拷貝自身的SPl+1個(gè)單元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】 試給出程序運(yùn)行時(shí)的活動(dòng)記錄關(guān)系。09-125-84321x局部變量aDisplay表0參數(shù)個(gè)數(shù)0全局Display

0返 地址Old

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

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

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

SP

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

130292827b02719-22i

23-2637-40

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

SP

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

局部變量53525149-50R活動(dòng)記錄Q活動(dòng)記錄S活動(dòng)記錄P活動(dòng)記錄活動(dòng)記錄棧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的活動(dòng)記錄(1層)P的活動(dòng)記錄28(0層)5.值單元的地址分配·值單元分配是依據(jù)活動(dòng)記錄的結(jié)構(gòu)，在符號(hào)表中進(jìn)行的?！纠?.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;試給出符號(hào)表組織及值單元分配情況。設(shè)：(1)實(shí)型占8個(gè)存儲(chǔ)單元，整型占4個(gè)單元，布爾型和字符型占1個(gè)單元。

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

2

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