語(yǔ)義分析抽象地址符號(hào)表

第四章：語(yǔ)義分析

抽象地址

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

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

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

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

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

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

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

ijkQabRab

#

#Sce

#Scope棧符號(hào)表PROGRAMexample;2.8C語(yǔ)言的符號(hào)表的管理C語(yǔ)言不允許函數(shù)的嵌套聲明。一個(gè)C程序是由若干個(gè)函數(shù)并列組成的（其中一定要有main函數(shù)），這些函數(shù)的地位都是相同的。從main函數(shù)調(diào)用開始執(zhí)行，在后面聲明的函數(shù)可以調(diào)用在它之前聲明的函數(shù)。C語(yǔ)言的每個(gè)標(biāo)識(shí)符的層次只有兩個(gè)，即0層和1層。全局標(biāo)識(shí)符和所有的函數(shù)標(biāo)識(shí)符的層數(shù)是0，函數(shù)的形式參數(shù)和局部標(biāo)識(shí)符的層數(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）簡(jiǎn)單的C語(yǔ)言符號(hào)表_駐留法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語(yǔ)言全局符號(hào)_駐留法

(假定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語(yǔ)言全局符號(hào)_刪除法a=3,b=2a=1,b=4a=1,b=1………1a…….1b…….2b………3a…….4b2.9嵌套式語(yǔ)言并列式語(yǔ)