编译原理第六章

第6章语义分析（SemanticAnalysis)

和符号表Semantic：oforrelatingtomeaning,especiallymeaninginlanguage.1语义分析在编译程序中的逻辑位置表处理错误处理目标代码生成中间代码优化中间代码生成语义分析语法分析词法分析目标程序源程序26.1 语义分析概述6.2 符号表的数据结构6.3 符号表的管理6.4 程序设计语言符号表的实例

3主要内容：语义分析的功能及重要性；标识符的内部表示；类型的内部表示；符号表的组织。46.1语义分析概述6.1语义分析概述

语法和语义的区别语法：描述一个合法定义的程序结构的规则。语义：说明一个合法定义的程序的含义的规则。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);}符合变量声明的语法、语义符合函数声明的语法、语义符合函数调用的语法、不符合语义符合赋值语句的语法、不符合语义符合变量声明的语法、语义符合变量声明的语法、不符合语义8语义分析的必要性一个语法正确的程序不能保证它是有意义的.程序中容易出现各种语义错误：标识符未声明操作数的类型与操作符的类型不匹配……9程序设计语言语义的分类静态语义编译时(compile-time)可以检查的语义例如：标识符未声明动态语义目标程序运行时（run-time）才能检查的语义例如：除零溢出错误10如何描述程序设计语言的语义？程序设计语言的形式语义属性文法(用于描述静态语义)操作语义(OperationalSemantics)指称语义(DenotationalSemantics)代数语义(AlgebraSemantics)公理语义(AxiomaticSemantics)形式语义描述技术没有形式语法描述技术成熟硕士研究生的课程-《形式语义学》11语义分析的主要任务根据声明部分建立符号表

符号表（symboltable）：是一种供编译器用于保存有关源程序的各种信息的数据结构。符号表的每个条目中包含与一个标识符相关的信息，这些信息全面地反映该名字的属性及它们在编译过程中的特征。 符号表的作用：存储标识符的属性；便于检查语义错误；代码生成阶段作为地址分配的依据。12语义分析的主要任务（续1）在整个程序范围内检查常见语义错误声明和使用相关的错误类型相关的语义错误

13常见的语义错误声明和使用相关的语义错误常见的语义错误：每个使用性标识符是否都有声明?在同层内有无标识符被声明多次?标号是否有声明?有无重复声明和重复定位错误?有无非法转入错误？如何检查?每当遇到新声明的标识符,查符号表：如果当前有效的所有标识符中有相同名字的,则是重复声明错误;否则生成它的属性信息,保存到符号表中;每当遇到标识符的使用,查符号表如果没有找到,说明该标识符没有声明;如果找到,则可获取该标识符的属性,进行进一步分析;14类型相关的语义错误各种条件表达式的类型是不是boolean型?运算符的分量的类型是否相容?赋值语句的左右部的类型是否相容?形参和实参的类型是否相容?下标表达式的类型是否为所允许的类型?常见的语义错误（续1）15函数说明中的函数类型和返回值的类型是否一致?V[E]中的V是不是变量,而且是不是数组类型？V.id中的V是不是变量,而且是不是结构体类型?id是不是该记录类型中的成员?V↑(*V)中的V是不是指针或文件变量？y+f(....)中的f是不是函数名?形参个数和实参个数是否一致?p(....)语句中的p是不是过程名?形参个数和实参个数是否一致?子界类型中的下界和上界类型是否相容?下界是否小于等于上界？常见的语义错误（续2）16语义分析的实现方式一：不作为独立的一遍类型语义错误检查：可以安排在中间代码生成时进行一般的语义检查：与语法分析相结合17方式二

独立一遍的语义分析的功能图示语义分析语法分析树TokenList语义定义自然语言描述的规定符号表判定18类C语言的抽象语法树程序Root节点Node1节点Node2……节点Noden节点Node常量声明类型声明变量声明函数声明FunNode1语句语句1920标识符的属性

6.2符号表的数据结构名字类型存取方式存储类别作用域和可视性21名字

在程序语言中，标识符可以作为变量的名字、函数的名字或过程的名字，是变量、函数或过程的唯一标志，因此在符号表中标识符的名字一般不允许重名。若程序中出现重名标识符：

1.将根据语言的定义，按照该标识符在程序中的作用域和可视性规则进行相应的处理。

2.在一些允许操作重载（OperatorOverload）的语言中，函数名、过程名是可以重名的，对于这类标识符要通过它们的参数个数和类型、函数返回值类型来区别，以达到它们在符号表中的唯一性。

标识符的属性22标识符的属性

（续1）类型除过程标识符之外，其他标识符都具有类型属性，函数的数据类型指的是函数返回值的数据类型。基本类型有整型、实型、字符型以及布尔型等。在基本类型的基础上，还可以定义数组、结构体、联合、枚举、子界、集合、指针等结构类型。标识符的类型是在程序中该标识符的定义部分得到的。变量标识符的类型属性决定了变量所占存储空间的大小以及能够施于变量上的操作等。23标识符的属性（续2）存取方式

因为变量标识符代表的是一个内存单元或一段连续的内存单元，根据这些内存单元中存放信息的类别又可以把变量分为间接存取变量和直接存取变量。如果变量标识符p所代表的内存单元中存放的是另一个变量q对应的内存地址，则称变量p为间接存取变量；如果变量标识符p所代表的内存单元中存放的是一个值，则称变量p为直接存取变量。24标识符的属性（续3）存储类别存储类别是指数据的存储方式，存储方式可分为两大类：静态存储方式和动态存储方式。静态存储方式是指在程序运行前即为数据分配好存储空间(在静态区)，在程序运行期间，数据的存储空间仍保持不变；动态存储方式则是在程序运行期间根据函数调用(函数被激活)和分程序语句的开始执行(分程序语句被激活)的需要进行动态存储分配。标识符的存储类别属性是编译过程语义处理、检查和存储分配的重要依据。编译程序一般根据变量声明时的存储类别关键字以及它们声明出现的位置和次序来确定每一个变量应分配的存储区及在该区中的具体位置。程序区静态存储区动态存储区25作用域和可视性标识符在程序中起作用的范围，称为它的作用域。一般地，定义该标识符的位置及存储类关键字决定了它的作用域。如：C语言中，

动态存储：

自动变量（本函数内有效）

寄存器变量（本函数内有效）

形式参数（本函数内有效）

静态存储：

静态局部变量（函数内有效）

静态外部变量（本文件内有效）

外部变量（其他文件可引用）26通常一个变量的作用域就是该变量可以出现的场合，也就是说在某个变量作用域范围内该变量是可以引用的，这就是变量可视性的作用域规则。有两种情况也将影响变量的可视性。271、函数的形式参数和函数外部定义的变量重名：函数的形式参数在函数内可见。inta；//外部定义的整型变量a

intfunc(a,b)

{

floata；//函数内部定义的局部变量a,屏闭了外部定义的变量b;

…

…a…//引用floata.

…

}程序区静态存储区inta；动态存储区floata；

intb;28为了在函数中也能看inta，C的新版本中增加了文法记号“::”，如：inta；//外部定义的整型变量a

intfunc(a,b)

{

floata；//函数内部定义的局部变量a,屏闭了外部定义的变量b;

…

…a…//引用floata.

…

…::a…//引用inta.

}程序区静态存储区inta；动态存储区floata；

intb;292、分程序结构：C语言中分程序语句的语法是:

{声明语句}分程序的一个特点是它的嵌套结构。分程序结构的声明作用域由下面的最近嵌套规则给出：（1）分程序B中声明的作用域包括B。 （2）如果名字x没有在B中声明，那么B中x的出现是在外围分程序B的x声明的作用域中，且满足：（a）B有x的声明；（b）B比其它任何含x声明的分程序更接近被嵌套的B。30…

｛inta；

//第一层头,定义的局部整型变量a

…

｛chara；

//第二层头,定义的局部字符型变量a

…

｛

//第三层头

…

｛floata；

//第四层头,定义的局部实型变量a

...a...

｝//第四层尾

…a…//引用第二层定义的局部字符型变量a

｝

//第三层尾

…

｝

//第二层尾

....

｝

//第一层尾

程序区静态存储区动态存储区：

inta；chara；flaota；31

值的内部表示

类型的内部表示

标识符的内部表示三种内部表示32

值的内部表示

非结构类型值的内部表示：实型：指针：

有序类型：整数形式

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类型的内部表示：表示类型表达式所包含的各种信息的数据结构。类型的内部表示structRT{floatx;ATa;intu;union{intk;struct{floaty;intb;}rt2:};};35类型的种类属性：标准、子界、枚举、数组、记录、集合、文件、指针类型等等。

TypeKind=(intTy，boolTy，charTy，realTy，

enumTy，subTy，arrayTy， structTy，setTy，fileTy，pointerTy)类型size属性：表示此种类型数据应该分配的内存空间的小。其它属性依类型的不同而不同。

enumTypeKind{intTy，boolTy，charTy，realTy，enumTy，subTy，arrayTy,structTy，setTy，fileTy，pointerTy};36内部表示与类型表

标准类型：

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

SizeKindHostTypeLowUpSubSizeSubTySizeKindHostTypeLowUp1subTyIntPtr11038ElemTypeSizeKindArraySizeArrayTyLowUp其中各个域的含义如下：Size表示数组类型所占空间的大小，是数组所有成分数据占用空间的和，需要通过计算得到，Size=(Up-Low+1)*sizeof(ElemType),其中sizeof是一个辅助函数，用于计算每种类型的size；Kind=arrayTy,表示是数组类型；Low表示数组下标的下界，在C语言中Low=0；Up表示数组下标的上界；ElemType

表示数组成分类型的内部表示指针。

数组类型(方案1）：39例：C语言的数组

typedefintA[10];

typedefcharB[5][10];ElemTypeIntPtrSizeKind

ArrayTyLowUp09A和B的内部表示分别为：ElemTypeSizeKind

ArrayTyLowUp04ElemTypeCharPtrSizeKind10ArrayTyLowUp09105040例：Pascal语言的数组type A=array[1..10]ofinteger; B=array[1..5]ofarray[1..10]ofchar;

ElemTypeIntPtrSizeKind

ArrayTyLowUp110A和B的内部表示分别为：ElemTypeSizeKind

ArrayTyLowUp15ElemTypeCharPtrSizeKind

ArrayTyLowUp11050101041数组类型(方案2）：ElemTypeSizeKindSubSizeArrayTyIndexTy其中各个域的含义如下：Size表示数组类型所占空间的大小，是数组所有成分数据占用空间的和，需要通过计算得到，Size=(Up-Low+1)*sizeof(ElemType),其中sizeof是一个辅助函数，用于计算每种类型的size；Kind=arrayTy,表示是数组类型；IndexTy表示数组下标类型的内部表示指针。ElemType

表示数组成分类型的内部表示指针。

42例：C语言的数组

typedefintA[10]; A的内部表示为：ElemTypeSizeKind10ArrayTyIndexTySizeKindHostTypeLowUp1SubTyIntPtr09IntPtr43B的内部表示为：ElemTypeSizeKind50ArrayTyIndexTySizeKindHostTypeLowUp1SubTyIntTy15ElemTypeCharPtrSizeKind10ArrayTyIndexTySizeKindHostTypeLowUp1SubTyIntTy110例：Pascal语言的数组type B=array[1..5]ofarray[1..10]ofchar;

44FieldListKindSize结构体与共用体类型其中各个域的含义如下：Size表示该类型数据所占空间的大小，结构体是所有域占用空间的和，共用体类型则是所有域中占用空间的最大者的值。Kind=structTy,表示是结构体或共用体类型；FieldList是域名表的表头指针。45其中各个域的含义如下：Name表示标识符的名字；Type=TypePtr，TypePtr是域名标识符类型的内部表示指针；Off表示域名标识符相对于结构体或共用体类型分配的内存块起始地址的偏移量，对于联合类型而言，所有的域名标识符的起始偏移都是相同的，所以可以省略；OffTypeName域名标识符的内部表示如下：

结构体与共用体类型--域名表46xV1V2VnoffVn=offVn-1+sizeof(typeof(Vn-1))………offVnoffV2=2offV1=0x+247

例：c语言的结构体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是指向枚举常量表表头的指针,其中枚举常量表的内部表示结构如下：FieldListKindSize其中各个域的含义如下：size表示枚举类型所占空间的大小；Kind=enumTy表示是枚举类型；ElemList是指向枚举常量表表头的指针,其中枚举常量表的内部表示结构如下：ValueNameName表示枚举常量的名字Value表示枚举常量所代表的整数值。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指针类型的内部表示：TypeKindSize其中各个域的含义如下：size表示指针类型所占空间的大小；Kind=pointTy表示是指针类型；Type是指向指针类型的基类型的内部表示的指针。54intPtrpointTy1例：c语言的针举类型typedefint*T1;typedef

float*T2;realPtrpointTy155标识符的内部表示

标识符种类：

常量名、类型名、变量名、函数名、过程名、域名。

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

内部表示（AttributeIR）：

56常量标识符的内部表示其中各个域的含义如下：Name是常量的名字；Kind=constKind，表明该标识符是常量标识符；Type=TypePtr,其中TypePtr是指向具体常量的类型的内部表示的指针；Value=ValPtr，其中ValPtr是指向具体常量值的内部表示的指针。ValueTypeKindName57常量标识符pai和count的内部表示为：↑3.14realPtrconstKindpai例： Pascal语言的常量定义：

const pai=3.14；

count=100；

C语言的常量定义：

#definepai3.14 #definecount100↑100intPtrconstKindcount58变量标识符的内部表示OffLevelAccessTypePtrKindValueName其中各个域的含义如下：Name是变量的名字；Kind=varKind，表明该标识符是变量标识符；Type=TypePtr,其中TypePtr是指向具体变量的类型的内部表示的指针；59变量标识符的内部表示（续1）：OffLevelAccessTypePtrKindValueName其中各个域的含义如下：Access=dir表示变量是直接变量，Access=indir表示变量是间接变量；Value=ValPtr,如果变量定义时说明了初值，则为初值的内部表示的指针，否则为空。Level表示该变量声明所在主程序/函数/过程的层数；Off表示该变量相对它所在主程序/函数/过程的内存块起始地址的偏移量；60offLdirintPtrvarKindnullxOff+1LdirrealPtrvarKindnullyOff+3LindirrealPtrvarKindnullz例：Pascal语言的变量声明：

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

变量标识符x、y和z的内部表示为（当前层为L，可用区距为off)：61offLdirintPtrvarKind↑10xOff+1LdirrealPtrvarKindnullyOff+3LindirrealPtrvarKindnullz变量标识符x、y和z的内部表示为（当前层为L，可用区距为off）：例：C语言的变量声明：

intx=10; floaty;

float*z;62类型标识符的内部表示TypePtrKindName其中各个域的含义如下：Name是类型标识符的名字；Kind=typeKind,表示标识符是类型标识符；Type=TypePtr,指向类型标识符指代的类型的内部表示。63例：Pascal语言的类型定义：

type t1=integer; t2=array[1..10]ofinteger;intPtrtypeKindt1typeKindt2ElemTypeIntPtrSizeKind10ArrayTyLowUp110类型标识符t1和t2的内部表示为：64例：C语言的类型定义：

typedefintt1; typedefintt2[10];intPtrtypeKindt1typeKindt2ElemTypeIntPtrSizeKind10ArrayTyLowUp09类型标识符t1和t2的内部表示为：65过程/函数标识符的内部表示子程序就是一段可能被重复使用多次的代码或者是对程序某个功能的抽象。例如：在PASCAL中，子程序体现为过程或函数，在C中，子程序体现为函数。C没有过程的概念，其中返回值为void类型的函数相当于PASCAL中的过程。函数定义一般需包含两部分的内容，一部分是函数头，定义函数的名字和形式参数的名字、类型和个数，以及函数返回值的类型；另一部分是函数体，定义函数的语句序列，即函数的功能部分的具体体现。66过程/函数标识符的内部表示(续1)有函数体部分的过/函称为实在过/函，而出现在其他过/函定义的参数部分的过/函称为形式过/函，因为它们只是起着说明参数的性质的作用，并没有实际的函数体部分，只有形实参结合时，才能获得真正的函数体。C语言的函数定义：intf(intx,float*y,intinc(int*a))......"头"{......f的函数体部分}67过程/函数标识符的内部表示(续2)其中各个域的含义如下：Name是过/函标识符的名字；TypePtr表示函数返回值类型的内部表示(过程情形是NULL)；Kind=routKind；

Class=actual表示实在过/函，Class=formal表示形式过/函；Level表示过/函的层数；NameForwardSizeCodeClassParmLevelKindTypePtroff68其中各个域的含义如下：Off只对形式过/函有效，表示形式过/函在所属过/函内存块中的偏移；Param表示过/函的参数表指针，参数表的结构同符号表的结构相同，参数信息可以填入符号表，也可以填入单独的参数表当中；Code只对实在过/函有效，表示过/函定义对应生成的目标代码的起始地址，当目标代码生成时回填得到，形式过/函的code为NULL；过程/函数标识符的内部表示(续3)NameForwardSizeCodeClassParamLevelKindTypePtroff69其中各个域的含义如下：Size只对实在过/函有效，表示过/函的目标代码所占内存区的大小，也要当目标代码生成以后回填得到；Forward属性只对实在过/函有效，Forward=true表示过/函是超前声明,Forward=false表示过/函不是超前声明。过程/函数标识符的内部表示(续4)NameForwardSizeCodeClassParmLevelKindTypePtroff70c7172例：Pascal语言的函标识符定义：

functionf(x：integer；vary：real；functioninc(vara：integer)：integer)：integer；"头"begin......f的函数体部分

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