第5章 语义分析（Semantic Analysis)

Presentation on theme: "第5章 语义分析（Semantic Analysis)"— Presentation transcript:

1 第5章 语义分析（Semantic Analysis)
和符号表 语义分析概述 符号表的数据结构 符号表的管理 程序设计语言符号表的实例

2 语义分析在编译程序中的逻辑位置 表 处 理 源 程 序 词 法 分 析 语 法 分 析 语 义 分 析 中 间 代 码 生 成 中 间 代
优 化 目 标 代 码 生 成 目 标 程 序 错 误 处 理

3 1 语义分析概述 1.1 语法和语义的区别 语法是描述一个合法定义的程序结构的规则。
语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语。源程序的结构由上下文无关文法描述。 语义是说明一个合法定义的程序的含义的规则。 语义分析是编译过程的一个逻辑阶段。语义分析的任务是对结构上正确的源程序符号进行上下文有关性质的审查, 进行类型审查。

4 1.2 语义分析的必要性 一个语法正确的程序不能保证它是有意义的. 程序中容易出现各种语义错误： 标识符未声明
操作数的类型与操作符的类型不匹配 ……

5 符合变量声明的语法、语义 int x=10; Main( ) { printf( “%d”,x+x ); x( ); }
f = x; } float f( ) {int x=20,y; float x; printf( “%d”,x ); 符合变量声明的语法、语义 符合函数调用的语法、不符合语义 符合赋值语句的语法、不符合语义 符合函数声明的语法、语义 符合变量声明的语法、语义 符合变量声明的语法、不符合语义

6 1.3 程序设计语言语义的分类 静态语义 动态语义 在编译阶段(compile-time)可以检查的语义 例如：标识符未声明
目标程序运行时（run-time）才能检查的语义 例如：除零、溢出错误

7 1.4 语义分析的主要任务 在变量、常量、类型、函数等标识符的定义和使用间建立联系 - 建立符号表保存标识符相关信息
　 - 建立符号表保存标识符相关信息 在整个程序范围内检查静态语义错误 声明和使用相关的错误 类型相关的语义错误 执行真正的翻译:生成更简单的中间表示形式或生成目标代码。

8 1.5 语义错误检查 类型检查 一般性的语义检查 1、各种条件表达式的类型是不是boolean型? 2、运算符的分量的类型是否相容?
3、赋值语句的左右部的类型是否相容? 4、形参和实参的类型是否相容? 5、下标表达式的类型是否为所允许的类型? 6、函数说明中的函数类型和返回值的类型是否一致? 一般性的语义检查 1、每个使用性标识符是否都有声明?在同层内有无标识符被声明多次? 2、标识符是否正确使用？ V[E]中的V是不是变量,而且是数组类型？ V.id中的V是不是变量,而且是记录类型? id是不是该记录类型中的域名? y+f(…)中的f是不是函数名?形参个数和实参个数是否一致? p(…)语句中的p是不是过程名?形参个数和实参个数是否一致? V↑中的V是不是指针或文件变量？ 子界类型中的下界和上界类型是否相容?下界是否小于等于上界？

9 1.6 语义分析的实现 语义检查要与语法分析相结合 语法分析树 语义分析 符号表 TokenList 语义定义 判定

10 C 语言语义分析过程 void main( ) { int x; float y=10; x=y+5*y; } 符号表 符号名 种类 类型
存储位置 …… main funKind void x varKind int Off y float Off+sizeof(int) … …….

11 2 符号表的数据结构 符号表（symbol table）：是一种供编译器用于保存有关源程序的各种信息的数据结构。符号表的每个条目中包含与一个标识符相关的信息，这些信息全面地反映该名字的属性及它们在编译过程中的特征。 符号表的作用： 收集存储标识符的属性； 上下文语义的合法性检查的依据； 代码生成阶段作为地址分配的依据。

12 2.1 标识符的语义检查 标识符的声明性出现：int x; 标识符的使用性出现： x=10;
通过遍历语法树检查：创建标识符a所对应的符号表，将a在符号表中的地址指针存入树中标识符节点； 通过扫描TokenList：创建标识符a所对应的符号表，将原token <标识符，a>转化为 <标识符，符号表a项指针> 标识符的使用性出现： x=10; 通过遍历语法树检查：到符号表中查找a，找到则将a在符号表中的地址指针存入树中标识符节点； 通过扫描TokenList：到符号表中查找a，找到则将token <标识符，a>转化为<标识符，符号表a项指针>

13 2.2 符号的内部表示 1. 值的内部表示 2. 类型的内部表示 3. 标识符的内部表示

14 1.值的内部表示 基本类型：整型，实型 有序类型：布尔，字符，枚举，数组下标 布尔常量：ord(false)=0, ord(true)= 1
字符常量：ord(C) = ASCⅡ(C) 枚举常量：设有枚举类型(D,A,B),则有ord(D)=0,ord(A)=1,ord(B)=2

15 2.类型的内部表示 类型语义信息的作用 类型的语义检查 分配空间的大小
标识符的语义信息我们都表示出来了，也就是种类信息、类型信息、其他信息，种类信息按照前面的介绍来看我们已经可以把它充分的表现出来了但是对于我们来说，类型却没有准确的语义表示。下面我们就来看一下类型的语义信息如何表示出来。 可能大一的时候大家就觉得为什么我们要给出变量的声明，又要给出他的类型，这种声明到底有啥意义，现在学编译，我们就可以知道这些声明是为了我们编译的工作提供一些信息。类型信息有什么作用呢？他的作用主要有两类： 1、做类型的检查，前面我们也说了很多的问题，xxx等等~ 原因是不同类型的数在计算机中的表示形式是不同的 2、我们要根据类型的大小为每一个变量分配存储空间的，一个简单变量和一个数组他们占用的存储空间的大小是不同的，我们根据什么给他们分配存储空间呢？~就是根据类型的大小，在真正执行的时候为他们进行存储空间的分配。这就是类型的作用。

16 2.类型的内部表示 … Kind Size 类型的种类Kind属性： 标准、子界、枚举、数组、记录、 集合、文件、指针类型等等。
Kind = ( intTy，boolTy，charTy，realTy， enumTy，subTy，arrayTy， structTy，setTy，fileTy，pointerTy) 类型存储占用空间大小size属性：为方便起见，规定RealSize取2外,IntSize、BoolSize、CharSize取1。 其它属性依类型的不同而不同。

17 (1)标准类型： Size Kind IntSize intTy BoolSize boolTy CharSize charTy
RealSize realTy intPtr boolPtr charPtr realPtr Size Kind 1 intTy boolTy charTy 2 realTy intPtr boolPtr charPtr realPtr

18 (2)数组类型 其中各个域的含义如下： --Size Size = (Up-Low+1)*sizeof(ElemType) ElemType
TypePtr ArraySize Size Kind ArrayTy Low Up 其中各个域的含义如下： --Size Size = (Up-Low+1)*sizeof(ElemType) -- Kind = arrayTy, 表示是数组类型； -- Low表示数组下标的下界，在C语言中Low = 0； -- Up表示数组下标的上界； -- ElemType 表示数组成分类型的内部表示指针。

19 例：C语言的数组 typedef int A[10]; typedef char B [5] [10]; A和B的内部表示分别为：
ElemType IntPtr Size Kind ArrayTy Low Up 9 10 ElemType Size Kind ArrayTy Low Up 4 50 ElemType CharPtr Size Kind 10 ArrayTy Low Up 9

20 (3)结构体与共用体类型 其中各个域的含义如下： Size:结构体是所有域占用空间的和，共用体类型则是所有域中占用空间的最大者的值。
FieldList Kind Size 其中各个域的含义如下： Size:结构体是所有域占用空间的和，共用体类型则是所有域中占用空间的最大者的值。 Kind = structTy表示是结构体或共用体类型 FieldList 是域名表的表头指针。

21 TypePtr是域名标识符类型的内部表示指针；
域名Field标识符的内部表示如下： Name Typeptr Off link 其中各个域的含义如下： Name表示标识符的名字； TypePtr是域名标识符类型的内部表示指针； Off表示域名标识符相对于结构体或共用体类型分配的内存块起始地址的偏移量，对于联合类型而言，所有的域名标识符的起始偏移都是相同的，所以可以省略； link:下一个域名标识符的内部表示的指针。

22 typedef struct DateType {int year, month, day;} datetype;
例： typedef struct DateType {int year, month, day;} datetype; Size Kind FieldList structTy 3 Name Type Off intPtr year 1 intPtr month 域名表其它表示 2 intPtr day intPtr year 1 month 2 day null

23 structTy intPtr j 1 IntPtr ArrayTy 9
例： typedef struct { int j; int r[10]; } A; Size Kind FieldList structTy 11 Name Type Off intPtr j 1 r ElemType IntPtr Size Kind ArrayTy Low Up 9 10

24 typedef union {char ch; int i; float f;} datatype；
structTy 2 charPtr ch intPtr i realPtr f

25 (4)枚举类型 其中各个域的含义如下： size表示枚举类型所占空间的大小； Kind = enumTy；
FieldList Kind Size ElemList Kind Size 其中各个域的含义如下： size表示枚举类型所占空间的大小； Kind = enumTy； ElemList是指向枚举常量表表头的指针. 枚举常量表内部表示： Value Name Name表示枚举常量的名字； Value表示枚举常量所代表的整数值。

26 例：c语言的枚举类型 enum color {red, yellow, blue} enumTy 1 red 例：c语言的枚举类型 enum color {red=10, yellow=red+2, blue} 1 yellow 2 blue enumTy 1 10 red 12 yellow 13 blue

27 (5)指针类型 c语言中指针类型其定义形式为：T * T称为此指针类型的基类型。 指针类型的内部表示： 其中各个域的含义如下：
Type Kind Size 其中各个域的含义如下： size表示指针类型所占空间的大小； Kind = pointTy表示是指针类型； Type是指向指针类型的基类型的内部表示的指针。

28 typedef int* T1; typedef float* T2; intPtr pointTy 1 realPtr pointTy 1
例：c语言的针举类型 typedef int* T1; typedef float* T2; intPtr pointTy 1 realPtr pointTy 1

29 类型内部表示 … Kind Size (1)标准类型： int,real,bool,char Kind Size TypePtr
ArraySize ArrayTy Low Up ElemType (2)数组类型 (3)结构体与共用体类型 FieldList structTy Size off typePtr Name link (4)枚举类型 Value Name enumList enumTy Size (5)指针类型 TypePtr pointTy Size

30 3. 标识符的内部表示 其它属性依种类的不同而不同。 标识符名字Name 种类Kind 常量名、类型名、变量名、函数名、过程名。
Kind = ( consKind, typeKind, varKind, procKind, funcKind) 所属类型Typeptr:指向该标识符所属类型内部表示指针。 其它属性依种类的不同而不同。 Name Kind Typeptr …

31 （1）常量标识符的内部表示 其中各个域的含义如下： Name是常量的名字； Kind = constKind，表明该标识符是常量标识符；
Value TypePtr Kind Name 其中各个域的含义如下： Name是常量的名字； Kind = constKind，表明该标识符是常量标识符； Type = TypePtr, 其中TypePtr是指向具体常量的类型的内部表示的指针； Value = ValPtr，其中ValPtr是指向具体常量值的内部表示的指针。

32 常量标识符pai 和count的内部表示为：
#define pai 3.14 const int count=100 常量标识符pai 和count的内部表示为： ↑<3.14> realPtr constKind pai ↑<100> intPtr constKind count

33 (2)变量标识符的内部表示 其中各个域的含义如下： Name是变量的名字； Kind = varKind，表明该标识符是变量标识符；
Off Level Access TypePtr Kind Value Name 其中各个域的含义如下： Name是变量的名字； Kind = varKind，表明该标识符是变量标识符； Type = TypePtr, 其中TypePtr是指向具体变量的类型的内部表示的指针；

34 Access = dir表示变量是直接变量，Access = indir表示变量是间接变量；
Off Level Access TypePtr Kind Value Name 其中各个域的含义如下： Access = dir表示变量是直接变量，Access = indir表示变量是间接变量； Level表示该变量声明所在主程序/函数/过程的层数； Off表示该变量相对它所在主程序/函数/过程的内存块起始地址的偏移量； Value = ValPtr, 如果变量定义时说明了初值，则为初值的内部表示的指针，否则为空。

35 变量标识符x、y和z的内部表示为（当前层为L，当前偏移量为off ）：
例： C语言的变量声明： int x=10; float y; float* z; 变量标识符x、y和z的内部表示为（当前层为L，当前偏移量为off ）： off L dir intPtr varKind ↑<10> x Off+1 L dir realPtr varKind null y Off+3 L indir varKind null z realPtr pointTy 1

36 (3) 类型标识符的内部表示 其中各个域的含义如下： Name是类型标识符的名字；
TypePtr Kind Name 其中各个域的含义如下： Name是类型标识符的名字； Kind = typeKind, 表示标识符是类型标识符； Type = TypePtr, 指向类型标识符指代的类型的内部表示。

37 类型标识符t1和t2的内部表示为： 例： C语言的类型定义： typedef int t1; typedef int t2 [10];
Size Kind 1 intTy intPtr typeKind t1 typeKind t2 ElemType intPtr Size Kind 10 ArrayTy Low Up 9

38 (4) 过程/函数标识符的内部表示 函数定义一般需包含两部分的内容，
--函数头:定义函数的名字和形式参数的名字、类型和个数，以及函数返回值的类型； --函数体:定义函数的语句序列，即函数的功能部分的具体体现。 int f ( int x, float* y) "头" { f的函数体部分 }

39 有函数体部分的过/函称为实在过/函，而出现在其他过/函定义的参数部分的过/函称为形式过/函，因为它们只是起着说明参数的性质的作用，并没有实际的函数体部分，只有形实参结合时，才能获得真正的函数体。
C语言的函数定义： int f ( int x, float* y, int inc(int *a)) "头" { f的函数体部分 }

40 过程/函数标识符的内部表示 其中各个域的含义如下： Name是过/函标识符的名字；
Forward Size Code Class Param Level Kind TypePtr off 其中各个域的含义如下： Name是过/函标识符的名字； TypePtr表示函数返回值类型的内部表示(过程情形是NULL) Kind = routKind； Level表示过/函的层数； Off只对形式过/函有效，表示形式过/函在所属过/函内存块中的偏移。形式过/函在内存中占2个字节空间，用于存入口地址；

41 过程/函数标识符的内部表示(续3) 其中各个域的含义如下：
Name Forward Size Code Class Param Level Kind TypePtr off 其中各个域的含义如下： Param表示过/函的参数表指针，参数表的结构同符号表的结构相同，参数信息可以填入符号表，也可以填入单独的参数表当中； Class= actual表示实在过/函，Class = formal表示形式过/函； Code只对实在过/函有效，表示过/函定义对应生成的目标代码的起始地址，当目标代码生成时回填得到，形式过/函的code为NULL；

42 过程/函数标识符的内部表示(续4) 其中各个域的含义如下：
Name Forward Size Code Class Parm Level Kind TypePtr off 其中各个域的含义如下： Size只对实在过/函有效，表示过/函所占内存区的大小，也要当目标代码生成以后回填得到； Forward 属性只对实在过/函有效，Forward= true表示过/函是超前声明, Forward = false表示过/函不是超前声明。

43 dir intPtr varKind x indir varKind y dir intPtr varKind a
例：C语言的函数定义： int f(int x,float* y, int inc(int a)) "头" { ......f的函数体部分 } Name TypePtr Kind Level off Parm Class Code Size Forward f false XXX actual L routKind intPtr off0 L+1 dir intPtr varKind x off0+1 L+1 indir varKind y realPtr pointTy 1 inc formal L+1 routKind intPtr off0 +2 dir intPtr varKind a

44 标示符内部表示 (1)常量标识符的内部表示 (2)变量标识符的内部表示： (3)类型标识符的内部表示 (4)过程/函数标识符的内部表示
Name Kind Typeptr … (1)常量标识符的内部表示 Value Typeptr constKind Name (2)变量标识符的内部表示： Off Level Access TypePtr varKind Value Name (3)类型标识符的内部表示 TypePtr typeKind Name (4)过程/函数标识符的内部表示 Name Forward Size Code Class Param Level TypePtr routKind off