語義分析抽象地址符號表

第四章：語義分析

抽象地址

符號表1.抽象地址1.1地址分配1.2抽象地址結(jié)構(gòu)1.3層數(shù)定義1.4過程活動記錄1.5分配原則1.1地址分配原則靜態(tài)分配在編譯時間即為所有數(shù)據(jù)對象分配固定的地址單元，且這些地址在運(yùn)行時間始終保持不變。是一種直觀的方法，但不適用于動態(tài)申請空間。動態(tài)分配程序中變量分配的地址不是具體的地址，而是一個抽象地址，當(dāng)程序運(yùn)行時根據(jù)抽象地址分配具體的物理地址。1.2抽象地址的結(jié)構(gòu)抽象地址的形式是一個二元組，由層數(shù)和偏移組成。層數(shù)主要是針對嵌套式語言，表示的是某個函數(shù)所處的嵌套定義層數(shù)。偏移是針對過程活動記錄的一個相對偏移量層數(shù)偏移1.3層數(shù)的定義嵌套式語言中：主程序設(shè)為0層主程序直接定義的函數(shù)和過程定義為1層若某函數(shù)為L層，則該函數(shù)直接定義的函數(shù)為L+1層并列式語言中:全局變量定義為0層，函數(shù)中的變量定義為1層1.4過程活動記錄臨時變量區(qū)局部變量區(qū)形參區(qū)管理信息每次函數(shù)被調(diào)用時都會給函數(shù)分配一片空間，用以存儲如圖信息，我們把這片存儲空間稱作過程活動記錄偏移是針對過程活動記錄的，通過起始位置+偏移量就可以找到對應(yīng)的物理位置。過程活動記錄中存儲的順序?qū)嶋H上是處理的先后順序。1.5空間分配原則臨時變量一律一個單元局部變量按類型大小分形參地址引用型形參：分一個單元值引用型形參：按類型大小分過/函形參：分兩個單元（入口地址，display表信息）2.1符號表結(jié)構(gòu)和總體組織符號表存儲的是標(biāo)識符的語義信息，包含兩部分：標(biāo)識符的名字；語義字(種類、類型、抽象地址...)不同類別的標(biāo)識符所包含的信息是不同的。符號表的總體組織既可以采用多表結(jié)構(gòu)，也可以采用單表結(jié)構(gòu),也可以二者折中。究竟采用哪種結(jié)構(gòu)并沒有統(tǒng)一的規(guī)定，編譯程序可根據(jù)實際處理語言的需要進(jìn)行選擇。2.2Newtoken與符號表的關(guān)系聲明性出現(xiàn)：<標(biāo)識符，a>創(chuàng)建標(biāo)識符a所對應(yīng)的符號表，將token轉(zhuǎn)化為<標(biāo)識符，指針（符號表中創(chuàng)建的項）>使用性出現(xiàn)：<標(biāo)識符，a>到符號表中查找a，找到則將token轉(zhuǎn)化為<標(biāo)識符，指針（符號表中查找到的項）>2.3符號表查表技術(shù)

順序查表法折半查表法（二分法）散列查表法（哈希表）2.4標(biāo)識符的作用域

標(biāo)識符的作用域：是指某標(biāo)識符可以有效使用的范圍，標(biāo)識符的作用域是一個程序段，稱之為程序的局部化區(qū)，通常是一個子程序或者分程序，局部化區(qū)是允許含有聲明的最小程序單位。voidfunction【(){...}】structuredata【{}】{【】}2.5局部化區(qū)的語義錯誤檢查變量的重復(fù)聲明在一個程序的局部化區(qū)里，同一個標(biāo)識符不能被聲明兩次。標(biāo)識符的使用有無聲明強(qiáng)類型語言規(guī)定標(biāo)識符必須先聲明后使用，弱類型語言無要求。2.6標(biāo)識符處理原則這兩個問題清楚之后，我們來看一下標(biāo)識符的處理原則，既要保存有用的信息，又要杜絕語義錯誤。每進(jìn)入一個局部化區(qū)，記錄本層符號表的首地址遇到聲明性標(biāo)識符時，構(gòu)造其語義字，查本層的符號表，檢查是否有重名，有則出錯，否則就把其語義字填到符號表里。遇到使用性出現(xiàn)，查符號表，如果查到則讀取其語義字，否則出現(xiàn)語義錯誤。退出一個局部化區(qū)，'作廢'本層的符號表。2.7Pascal語言的符號表的管理Pascal語言的最大特點就是允許嵌套的過程聲明。規(guī)定Pascal主程序的層數(shù)為0，在主程序中聲明的標(biāo)識符(包括過/函標(biāo)識符)的層數(shù)為1，在第i層過/函中聲明的標(biāo)識符(包括形參和局部標(biāo)識符)的層數(shù)為i+1(i≥1)。用一個Scope棧來實現(xiàn)標(biāo)識符的嵌套作用域。Scope棧的每項指向當(dāng)前仍有效的某層符號表的首項，具體說Scope(0)指向0層符號表的首項，Scope(i)指向i層符號表的首項。

Pascal語言的符號表的實例(刪除法)procedureP1()vari,j,k:integer;{t1}procedureQ2()vara,b:real;procedureR3(){t2}vara,b:boolean;{t3}beginR的過程體（a,b,i)endbeginQ的過程體（a,b,i)end;procedureS2()var

c,e:char;{t4}beginS的過程體（a,b,i,Q)end;{t5}beginP的過程體（a,b,i,P,Q,S)20.end;21begin..P();..end.PijkQabRabSceScope棧PROGRAMexample;符號表

關(guān)于Pascal語言的符號表的實例(跳轉(zhuǎn)法)procedureP()vari,j,k:integer;{t1}procedureQ()vara,b:real;procedureR(){t2}vara,b:boolean;{t3}beginR的過程體（a,b,i)end;beginQ的過程體（a,b,i)end;procedureS()var

c,e:char;{t4}beginS的過程體（a,b,i)end;{t5}beginP的過程體(a,b,i)endbegin.....end.P….

ijkQabRab

#

#Sce

#Scope棧符號表PROGRAMexample;2.8C語言的符號表的管理C語言不允許函數(shù)的嵌套聲明。一個C程序是由若干個函數(shù)并列組成的（其中一定要有main函數(shù)），這些函數(shù)的地位都是相同的。從main函數(shù)調(diào)用開始執(zhí)行，在后面聲明的函數(shù)可以調(diào)用在它之前聲明的函數(shù)。C語言的每個標(biāo)識符的層次只有兩個，即0層和1層。全局標(biāo)識符和所有的函數(shù)標(biāo)識符的層數(shù)是0，函數(shù)的形式參數(shù)和局部標(biāo)識符的層數(shù)是1。xvarKindintPtrdir00swaproutKindNULLactual0sizefalseavarKindatptrindir1offobvarKindbtptrindir1offo+1tmpvarKindintPtrdir1offo+2#mainroutKindNULLactual0nullsizeFalse##yvarKindintPtrdir01intx,y;voidswap(int*a,int*b){inttmp;tmp=*a;*a=*b;*b=tmp;}voidmain(){x=10;y=20;swap(&x,&y);}（1）簡單的C語言符號表_駐留法atptr→

btptr→1pointerTyintPtrbtptr→1pointerTyintPtr1.main()2.{13. inta；4. floatb，d；5.{26intc；7.floata；8.{39. intd;10. floatc;11.{412. floatd;13.……14.a=b+c+d;15.}4

16.}317.{518.chard;19.}520.}221.}1mainroutKindNULLactual0NULLfalseavarKindintPtrdir10bvarKindrealPtrdir11dvarKindrealPtrdir13avarKindrealPtrdir16dvarKindintPtrdir18cvarKindrealPtrdir19dvarKindrealPtrdir111cvarKindintPtrdir15##dvarKindcharPtrdir113（8）##（2）帶有分程序的C語言全局符號_駐留法

(假定off（偏移）為0)#voidmain(){}inta=1;B1intb=1;{}printf(“a=%d,b=%d\n”,a,b);intb=2;B2{}{}inta=3;B3printf(“a=%d,b=%d\n”,a,b);intb=4;B4printf(“a=%d,b=%d\n”,a,b);（3）帶有分程序的C語言全局符號_刪除法a=3,b=2a=1,b=4a=1,b=1………1a…….1b…….2b………3a…….4b2.9嵌套式語言并列式語