編譯原理第六章

第6章語義分析（SemanticAnalysis)

和符號表Semantic：oforrelatingtomeaning,especiallymeaninginlanguage.1語義分析在編譯程序中的邏輯位置表處理錯誤處理目標代碼生成中間代碼優(yōu)化中間代碼生成語義分析語法分析詞法分析目標程序源程序26.1 語義分析概述6.2 符號表的數(shù)據(jù)結(jié)構(gòu)6.3 符號表的管理6.4 程序設計語言符號表的實例

3主要內(nèi)容：語義分析的功能及重要性；標識符的內(nèi)部表示；類型的內(nèi)部表示；符號表的組織。46.1語義分析概述6.1語義分析概述

語法和語義的區(qū)別語法：描述一個合法定義的程序結(jié)構(gòu)的規(guī)則。語義：說明一個合法定義的程序的含義的規(guī)則。5PASCAL語言的條件語句：ifx>ythenz:=z+1elsez:=z-1C語言的條件語句：

if(x>y){z=z+1;}else{z=z-1;}6inti；switch（i）{case0：printf（“%s\n”，“auto”）；break；case1：printf（“%s\n”，“static”）；break；case2：printf（“%s\n”，“extern”）；break；case1：printf(“%s\n”，“register”)；break；}7intx=10;Main(){printf(“%d”,x+x);x();

f=x;}floatf(){intx=20,y;floatx;printf(“%d”,x);}符合變量聲明的語法、語義符合函數(shù)聲明的語法、語義符合函數(shù)調(diào)用的語法、不符合語義符合賦值語句的語法、不符合語義符合變量聲明的語法、語義符合變量聲明的語法、不符合語義8語義分析的必要性一個語法正確的程序不能保證它是有意義的.程序中容易出現(xiàn)各種語義錯誤：標識符未聲明操作數(shù)的類型與操作符的類型不匹配……9程序設計語言語義的分類靜態(tài)語義編譯時(compile-time)可以檢查的語義例如：標識符未聲明動態(tài)語義目標程序運行時（run-time）才能檢查的語義例如：除零溢出錯誤10如何描述程序設計語言的語義？程序設計語言的形式語義屬性文法(用于描述靜態(tài)語義)操作語義(OperationalSemantics)指稱語義(DenotationalSemantics)代數(shù)語義(AlgebraSemantics)公理語義(AxiomaticSemantics)形式語義描述技術(shù)沒有形式語法描述技術(shù)成熟碩士研究生的課程-《形式語義學》11語義分析的主要任務根據(jù)聲明部分建立符號表

符號表（symboltable）：是一種供編譯器用于保存有關(guān)源程序的各種信息的數(shù)據(jù)結(jié)構(gòu)。符號表的每個條目中包含與一個標識符相關(guān)的信息，這些信息全面地反映該名字的屬性及它們在編譯過程中的特征。 符號表的作用：存儲標識符的屬性；便于檢查語義錯誤；代碼生成階段作為地址分配的依據(jù)。12語義分析的主要任務（續(xù)1）在整個程序范圍內(nèi)檢查常見語義錯誤聲明和使用相關(guān)的錯誤類型相關(guān)的語義錯誤

13常見的語義錯誤聲明和使用相關(guān)的語義錯誤常見的語義錯誤：每個使用性標識符是否都有聲明?在同層內(nèi)有無標識符被聲明多次?標號是否有聲明?有無重復聲明和重復定位錯誤?有無非法轉(zhuǎn)入錯誤？如何檢查?每當遇到新聲明的標識符,查符號表：如果當前有效的所有標識符中有相同名字的,則是重復聲明錯誤;否則生成它的屬性信息,保存到符號表中;每當遇到標識符的使用,查符號表如果沒有找到,說明該標識符沒有聲明;如果找到,則可獲取該標識符的屬性,進行進一步分析;14類型相關(guān)的語義錯誤各種條件表達式的類型是不是boolean型?運算符的分量的類型是否相容?賦值語句的左右部的類型是否相容?形參和實參的類型是否相容?下標表達式的類型是否為所允許的類型?常見的語義錯誤（續(xù)1）15函數(shù)說明中的函數(shù)類型和返回值的類型是否一致?V[E]中的V是不是變量,而且是不是數(shù)組類型？V.id中的V是不是變量,而且是不是結(jié)構(gòu)體類型?id是不是該記錄類型中的成員?V↑(*V)中的V是不是指針或文件變量？y+f(....)中的f是不是函數(shù)名?形參個數(shù)和實參個數(shù)是否一致?p(....)語句中的p是不是過程名?形參個數(shù)和實參個數(shù)是否一致?子界類型中的下界和上界類型是否相容?下界是否小于等于上界？常見的語義錯誤（續(xù)2）16語義分析的實現(xiàn)方式一：不作為獨立的一遍類型語義錯誤檢查：可以安排在中間代碼生成時進行一般的語義檢查：與語法分析相結(jié)合17方式二

獨立一遍的語義分析的功能圖示語義分析語法分析樹TokenList語義定義自然語言描述的規(guī)定符號表判定18類C語言的抽象語法樹程序Root節(jié)點Node1節(jié)點Node2……節(jié)點Noden節(jié)點Node常量聲明類型聲明變量聲明函數(shù)聲明FunNode1語句語句1920標識符的屬性

6.2符號表的數(shù)據(jù)結(jié)構(gòu)名字類型存取方式存儲類別作用域和可視性21名字

在程序語言中，標識符可以作為變量的名字、函數(shù)的名字或過程的名字，是變量、函數(shù)或過程的唯一標志，因此在符號表中標識符的名字一般不允許重名。若程序中出現(xiàn)重名標識符：

1.將根據(jù)語言的定義，按照該標識符在程序中的作用域和可視性規(guī)則進行相應的處理。

2.在一些允許操作重載（OperatorOverload）的語言中，函數(shù)名、過程名是可以重名的，對于這類標識符要通過它們的參數(shù)個數(shù)和類型、函數(shù)返回值類型來區(qū)別，以達到它們在符號表中的唯一性。

標識符的屬性22標識符的屬性

（續(xù)1）類型除過程標識符之外，其他標識符都具有類型屬性，函數(shù)的數(shù)據(jù)類型指的是函數(shù)返回值的數(shù)據(jù)類型?；绢愋陀姓?、實型、字符型以及布爾型等。在基本類型的基礎上，還可以定義數(shù)組、結(jié)構(gòu)體、聯(lián)合、枚舉、子界、集合、指針等結(jié)構(gòu)類型。標識符的類型是在程序中該標識符的定義部分得到的。變量標識符的類型屬性決定了變量所占存儲空間的大小以及能夠施于變量上的操作等。23標識符的屬性（續(xù)2）存取方式

因為變量標識符代表的是一個內(nèi)存單元或一段連續(xù)的內(nèi)存單元，根據(jù)這些內(nèi)存單元中存放信息的類別又可以把變量分為間接存取變量和直接存取變量。如果變量標識符p所代表的內(nèi)存單元中存放的是另一個變量q對應的內(nèi)存地址，則稱變量p為間接存取變量；如果變量標識符p所代表的內(nèi)存單元中存放的是一個值，則稱變量p為直接存取變量。24標識符的屬性（續(xù)3）存儲類別存儲類別是指數(shù)據(jù)的存儲方式，存儲方式可分為兩大類：靜態(tài)存儲方式和動態(tài)存儲方式。靜態(tài)存儲方式是指在程序運行前即為數(shù)據(jù)分配好存儲空間(在靜態(tài)區(qū))，在程序運行期間，數(shù)據(jù)的存儲空間仍保持不變；動態(tài)存儲方式則是在程序運行期間根據(jù)函數(shù)調(diào)用(函數(shù)被激活)和分程序語句的開始執(zhí)行(分程序語句被激活)的需要進行動態(tài)存儲分配。標識符的存儲類別屬性是編譯過程語義處理、檢查和存儲分配的重要依據(jù)。編譯程序一般根據(jù)變量聲明時的存儲類別關(guān)鍵字以及它們聲明出現(xiàn)的位置和次序來確定每一個變量應分配的存儲區(qū)及在該區(qū)中的具體位置。程序區(qū)靜態(tài)存儲區(qū)動態(tài)存儲區(qū)25作用域和可視性標識符在程序中起作用的范圍，稱為它的作用域。一般地，定義該標識符的位置及存儲類關(guān)鍵字決定了它的作用域。如：C語言中，

動態(tài)存儲：

自動變量（本函數(shù)內(nèi)有效）

寄存器變量（本函數(shù)內(nèi)有效）

形式參數(shù)（本函數(shù)內(nèi)有效）

靜態(tài)存儲：

靜態(tài)局部變量（函數(shù)內(nèi)有效）

靜態(tài)外部變量（本文件內(nèi)有效）

外部變量（其他文件可引用）26通常一個變量的作用域就是該變量可以出現(xiàn)的場合，也就是說在某個變量作用域范圍內(nèi)該變量是可以引用的，這就是變量可視性的作用域規(guī)則。有兩種情況也將影響變量的可視性。271、函數(shù)的形式參數(shù)和函數(shù)外部定義的變量重名：函數(shù)的形式參數(shù)在函數(shù)內(nèi)可見。inta；//外部定義的整型變量a

intfunc(a,b)

{

floata；//函數(shù)內(nèi)部定義的局部變量a,屏閉了外部定義的變量b;

…

…a…//引用floata.

…

}程序區(qū)靜態(tài)存儲區(qū)inta；動態(tài)存儲區(qū)floata；

intb;28為了在函數(shù)中也能看inta，C的新版本中增加了文法記號“::”，如：inta；//外部定義的整型變量a

intfunc(a,b)

{

floata；//函數(shù)內(nèi)部定義的局部變量a,屏閉了外部定義的變量b;

…

…a…//引用floata.

…

…::a…//引用inta.

}程序區(qū)靜態(tài)存儲區(qū)inta；動態(tài)存儲區(qū)floata；

intb;292、分程序結(jié)構(gòu)：C語言中分程序語句的語法是:

{聲明語句}分程序的一個特點是它的嵌套結(jié)構(gòu)。分程序結(jié)構(gòu)的聲明作用域由下面的最近嵌套規(guī)則給出：（1）分程序B中聲明的作用域包括B。 （2）如果名字x沒有在B中聲明，那么B中x的出現(xiàn)是在外圍分程序B的x聲明的作用域中，且滿足：（a）B有x的聲明；（b）B比其它任何含x聲明的分程序更接近被嵌套的B。30…

｛inta；

//第一層頭,定義的局部整型變量a

…

｛chara；

//第二層頭,定義的局部字符型變量a

…

｛

//第三層頭

…

｛floata；

//第四層頭,定義的局部實型變量a

...a...

｝//第四層尾

…a…//引用第二層定義的局部字符型變量a

｝

//第三層尾

…

｝

//第二層尾

....

｝

//第一層尾

程序區(qū)靜態(tài)存儲區(qū)動態(tài)存儲區(qū)：

inta；chara；flaota；31

值的內(nèi)部表示

類型的內(nèi)部表示

標識符的內(nèi)部表示三種內(nèi)部表示32

值的內(nèi)部表示

非結(jié)構(gòu)類型值的內(nèi)部表示：實型：指針：

有序類型：整數(shù)形式

33有序類型的常量表示：

整型常量：ord(N)=N

布爾常量：ord(false)=0,ord(true)=1

字符常量：ord(C)=ASCⅡ(C)

枚舉常量：設有枚舉類型(D,A,B),則有

ord(D)=0,ord(A)=1,ord(B)=2

子界常量：設有子界類型C1..C2,則值空間為[ord(C1)...ord(C2)]34typedeffloatAT[10][100];類型表達式：如：AT=ARRAY[1..10]OFARRAY[1..100]OFREAL;RT= RECORDx:real;a:AT; CASEu:booleanOF false:(k:integer); true:(y:real;b:boolean) END類型的內(nèi)部表示：表示類型表達式所包含的各種信息的數(shù)據(jù)結(jié)構(gòu)。類型的內(nèi)部表示structRT{floatx;ATa;intu;union{intk;struct{floaty;intb;}rt2:};};35類型的種類屬性：標準、子界、枚舉、數(shù)組、記錄、集合、文件、指針類型等等。

TypeKind=(intTy，boolTy，charTy，realTy，

enumTy，subTy，arrayTy， structTy，setTy，fileTy，pointerTy)類型size屬性：表示此種類型數(shù)據(jù)應該分配的內(nèi)存空間的小。其它屬性依類型的不同而不同。

enumTypeKind{intTy，boolTy，charTy，realTy，enumTy，subTy，arrayTy,structTy，setTy，fileTy，pointerTy};36內(nèi)部表示與類型表

標準類型：

SizeKind1intTy1boolTy1charTy2realTyintPtrboolPtrcharPtrrealPtrSizeKindIntSizeintTyBoolSizeboolTyCharSizecharTyRealSizerealTyintPtrboolPtrcharPtrrealPtr37子界類型：例：T=1..10;TypeIR’(Size:1,Kind:subTyHostType:intPtr,low:1,up:10)

SizeKindHostTypeLowUpSubSizeSubTySizeKindHostTypeLowUp1subTyIntPtr11038ElemTypeSizeKindArraySizeArrayTyLowUp其中各個域的含義如下：Size表示數(shù)組類型所占空間的大小，是數(shù)組所有成分數(shù)據(jù)占用空間的和，需要通過計算得到，Size=(Up-Low+1)*sizeof(ElemType),其中sizeof是一個輔助函數(shù)，用于計算每種類型的size；Kind=arrayTy,表示是數(shù)組類型；Low表示數(shù)組下標的下界，在C語言中Low=0；Up表示數(shù)組下標的上界；ElemType

表示數(shù)組成分類型的內(nèi)部表示指針。

數(shù)組類型(方案1）：39例：C語言的數(shù)組

typedefintA[10];

typedefcharB[5][10];ElemTypeIntPtrSizeKind

ArrayTyLowUp09A和B的內(nèi)部表示分別為：ElemTypeSizeKind

ArrayTyLowUp04ElemTypeCharPtrSizeKind10ArrayTyLowUp09105040例：Pascal語言的數(shù)組type A=array[1..10]ofinteger; B=array[1..5]ofarray[1..10]ofchar;

ElemTypeIntPtrSizeKind

ArrayTyLowUp110A和B的內(nèi)部表示分別為：ElemTypeSizeKind

ArrayTyLowUp15ElemTypeCharPtrSizeKind

ArrayTyLowUp11050101041數(shù)組類型(方案2）：ElemTypeSizeKindSubSizeArrayTyIndexTy其中各個域的含義如下：Size表示數(shù)組類型所占空間的大小，是數(shù)組所有成分數(shù)據(jù)占用空間的和，需要通過計算得到，Size=(Up-Low+1)*sizeof(ElemType),其中sizeof是一個輔助函數(shù)，用于計算每種類型的size；Kind=arrayTy,表示是數(shù)組類型；IndexTy表示數(shù)組下標類型的內(nèi)部表示指針。ElemType

表示數(shù)組成分類型的內(nèi)部表示指針。

42例：C語言的數(shù)組

typedefintA[10]; A的內(nèi)部表示為：ElemTypeSizeKind10ArrayTyIndexTySizeKindHostTypeLowUp1SubTyIntPtr09IntPtr43B的內(nèi)部表示為：ElemTypeSizeKind50ArrayTyIndexTySizeKindHostTypeLowUp1SubTyIntTy15ElemTypeCharPtrSizeKind10ArrayTyIndexTySizeKindHostTypeLowUp1SubTyIntTy110例：Pascal語言的數(shù)組type B=array[1..5]ofarray[1..10]ofchar;

44FieldListKindSize結(jié)構(gòu)體與共用體類型其中各個域的含義如下：Size表示該類型數(shù)據(jù)所占空間的大小，結(jié)構(gòu)體是所有域占用空間的和，共用體類型則是所有域中占用空間的最大者的值。Kind=structTy,表示是結(jié)構(gòu)體或共用體類型；FieldList是域名表的表頭指針。45其中各個域的含義如下：Name表示標識符的名字；Type=TypePtr，TypePtr是域名標識符類型的內(nèi)部表示指針；Off表示域名標識符相對于結(jié)構(gòu)體或共用體類型分配的內(nèi)存塊起始地址的偏移量，對于聯(lián)合類型而言，所有的域名標識符的起始偏移都是相同的，所以可以省略；OffTypeName域名標識符的內(nèi)部表示如下：

結(jié)構(gòu)體與共用體類型--域名表46xV1V2VnoffVn=offVn-1+sizeof(typeof(Vn-1))………offVnoffV2=2offV1=0x+247

例：c語言的結(jié)構(gòu)體typedefstruct{intyear,month,day;}

datetype;structTy30intPtryear1intPtrmonth2intPtrday48

例：c語言的共用體typedefunion{charch;inti;

floatf;}datatype；structTy20charPtrch0intPtri0realPtrf49例：Pascal語言的記錄類型RECORD j:integer; r:RECORDj:integer;b:booleanENDENDstructTy30intPtrj1boolPtrbstructTy20intPtrj1

r50FieldListKindSize枚舉類型其中各個域的含義如下：size表示枚舉類型所占空間的大??；Kind=enumTy表示是枚舉類型；ElemList是指向枚舉常量表表頭的指針,其中枚舉常量表的內(nèi)部表示結(jié)構(gòu)如下：FieldListKindSize其中各個域的含義如下：size表示枚舉類型所占空間的大??；Kind=enumTy表示是枚舉類型；ElemList是指向枚舉常量表表頭的指針,其中枚舉常量表的內(nèi)部表示結(jié)構(gòu)如下：ValueNameName表示枚舉常量的名字Value表示枚舉常量所代表的整數(shù)值。51例：c語言的枚舉類型

enumcolor{red,yellow,blue}

enumTy10red1yellow2blue例：c語言的枚舉類型

enumcolor{red=10,yellow=red+2,blue}

enumTy110red12yellow13blue52指針類型c語言中指針類型其定義形式為：T*T稱為此指針類型的基類型。由指針類型可以定義指針變量，指針變量的定義形式為：T*p;pascal語言中指針類型其定義形式為：↑

p:T;53指針類型的內(nèi)部表示：TypeKindSize其中各個域的含義如下：size表示指針類型所占空間的大??；Kind=pointTy表示是指針類型；Type是指向指針類型的基類型的內(nèi)部表示的指針。54intPtrpointTy1例：c語言的針舉類型typedefint*T1;typedef

float*T2;realPtrpointTy155標識符的內(nèi)部表示

標識符種類：

常量名、類型名、變量名、函數(shù)名、過程名、域名。

TYPEidkind=(consKind,typeKind,varKind,procKind,funcKind,fieldKind)

內(nèi)部表示（AttributeIR）：

56常量標識符的內(nèi)部表示其中各個域的含義如下：Name是常量的名字；Kind=constKind，表明該標識符是常量標識符；Type=TypePtr,其中TypePtr是指向具體常量的類型的內(nèi)部表示的指針；Value=ValPtr，其中ValPtr是指向具體常量值的內(nèi)部表示的指針。ValueTypeKindName57常量標識符pai和count的內(nèi)部表示為：↑3.14realPtrconstKindpai例： Pascal語言的常量定義：

const pai=3.14；

count=100；

C語言的常量定義：

#definepai3.14 #definecount100↑100intPtrconstKindcount58變量標識符的內(nèi)部表示OffLevelAccessTypePtrKindValueName其中各個域的含義如下：Name是變量的名字；Kind=varKind，表明該標識符是變量標識符；Type=TypePtr,其中TypePtr是指向具體變量的類型的內(nèi)部表示的指針；59變量標識符的內(nèi)部表示（續(xù)1）：OffLevelAccessTypePtrKindValueName其中各個域的含義如下：Access=dir表示變量是直接變量，Access=indir表示變量是間接變量；Value=ValPtr,如果變量定義時說明了初值，則為初值的內(nèi)部表示的指針，否則為空。Level表示該變量聲明所在主程序/函數(shù)/過程的層數(shù)；Off表示該變量相對它所在主程序/函數(shù)/過程的內(nèi)存塊起始地址的偏移量；60offLdirintPtrvarKindnullxOff+1LdirrealPtrvarKindnullyOff+3LindirrealPtrvarKindnullz例：Pascal語言的變量聲明：

varx:integer; y:real;z:real;

變量標識符x、y和z的內(nèi)部表示為（當前層為L，可用區(qū)距為off)：61offLdirintPtrvarKind↑10xOff+1LdirrealPtrvarKindnullyOff+3LindirrealPtrvarKindnullz變量標識符x、y和z的內(nèi)部表示為（當前層為L，可用區(qū)距為off）：例：C語言的變量聲明：

intx=10; floaty;

float*z;62類型標識符的內(nèi)部表示TypePtrKindName其中各個域的含義如下：Name是類型標識符的名字；Kind=typeKind,表示標識符是類型標識符；Type=TypePtr,指向類型標識符指代的類型的內(nèi)部表示。63例：Pascal語言的類型定義：

type t1=integer; t2=array[1..10]ofinteger;intPtrtypeKindt1typeKindt2ElemTypeIntPtrSizeKind10ArrayTyLowUp110類型標識符t1和t2的內(nèi)部表示為：64例：C語言的類型定義：

typedefintt1; typedefintt2[10];intPtrtypeKindt1typeKindt2ElemTypeIntPtrSizeKind10ArrayTyLowUp09類型標識符t1和t2的內(nèi)部表示為：65過程/函數(shù)標識符的內(nèi)部表示子程序就是一段可能被重復使用多次的代碼或者是對程序某個功能的抽象。例如：在PASCAL中，子程序體現(xiàn)為過程或函數(shù)，在C中，子程序體現(xiàn)為函數(shù)。C沒有過程的概念，其中返回值為void類型的函數(shù)相當于PASCAL中的過程。函數(shù)定義一般需包含兩部分的內(nèi)容，一部分是函數(shù)頭，定義函數(shù)的名字和形式參數(shù)的名字、類型和個數(shù)，以及函數(shù)返回值的類型；另一部分是函數(shù)體，定義函數(shù)的語句序列，即函數(shù)的功能部分的具體體現(xiàn)。66過程/函數(shù)標識符的內(nèi)部表示(續(xù)1)有函數(shù)體部分的過/函稱為實在過/函，而出現(xiàn)在其他過/函定義的參數(shù)部分的過/函稱為形式過/函，因為它們只是起著說明參數(shù)的性質(zhì)的作用，并沒有實際的函數(shù)體部分，只有形實參結(jié)合時，才能獲得真正的函數(shù)體。C語言的函數(shù)定義：intf(intx,float*y,intinc(int*a))......"頭"{......f的函數(shù)體部分}67過程/函數(shù)標識符的內(nèi)部表示(續(xù)2)其中各個域的含義如下：Name是過/函標識符的名字；TypePtr表示函數(shù)返回值類型的內(nèi)部表示(過程情形是NULL)；Kind=routKind；

Class=actual表示實在過/函，Class=formal表示形式過/函；Level表示過/函的層數(shù)；NameForwardSizeCodeClassParmLevelKindTypePtroff68其中各個域的含義如下：Off只對形式過/函有效，表示形式過/函在所屬過/函內(nèi)存塊中的偏移；Param表示過/函的參數(shù)表指針，參數(shù)表的結(jié)構(gòu)同符號表的結(jié)構(gòu)相同，參數(shù)信息可以填入符號表，也可以填入單獨的參數(shù)表當中；Code只對實在過/函有效，表示過/函定義對應生成的目標代碼的起始地址，當目標代碼生成時回填得到，形式過/函的code為NULL；過程/函數(shù)標識符的內(nèi)部表示(續(xù)3)NameForwardSizeCodeClassParamLevelKindTypePtroff69其中各個域的含義如下：Size只對實在過/函有效，表示過/函的目標代碼所占內(nèi)存區(qū)的大小，也要當目標代碼生成以后回填得到；Forward屬性只對實在過/函有效，F(xiàn)orward=true表示過/函是超前聲明,Forward=false表示過/函不是超前聲明。過程/函數(shù)標識符的內(nèi)部表示(續(xù)4)NameForwardSizeCodeClassParmLevelKindTypePtroff70c7172例：Pascal語言的函標識符定義：

functionf(x：integer；vary：real；functioninc(vara：integer)：integer)：integer；"頭"begin......f的函數(shù)體部分

end；ffalseSizeCodeactualParmLroutKindintPtroff0L+1dirintPtrvarKindxoff0+1L+1indirrealPtrvarKindyincformalParmL+1routKindintPtr20L+2indirintPtrvarKindaTypePtrNameKindLeveloffParm