第六章 语义分析(1).ppt

1、语义分析在编译程序中的作用,词法分析,语法分析,语义分析,中间代码优化,中间代码生成,目标代码生成,分析,合成,第六章 语义分析,6.1 语义分析概述 6.2 符号表 6.3 类型的语义分析 6.4 声明的语义分析 6.5 程序体的语义分析 6.6 属性文法和动作文法,6.1 语义分析概述,语法(Syntax)和语义(Semantics)的区别 语义分析的必要性 程序设计语言语义的分类 如何描述程序设计语言的语义？ 语义分析的主要任务,语法和语义的区别,语法： 是描述一个合法定义的程序结构的规则 例如： id( ) 语义： 说明一个合法定义的程序的含义,int x; float* f(); x

2、(); x = f();,符合变量声明的语法、语义,符合函数声明的语法、语义,符合函数调用的语法、不符合语义,符合赋值语句的语法、不符合语义,语义分析的必要性,一个语法正确的程序不能保证它是有意义的！ 程序中容易出现各种语义错误： 标识符未声明 y = x+3; 操作数的类型与操作符的类型不匹配 y = x*3; 数组下标变量的类型出错 Ax; ,语义分析不能检查程序在计算逻辑上的错误！,程序设计语言语义的分类,静态语义(static semantics) 编译时(compile-time)可以检查的语义 例如：标识符未声明 标识符重复声明 动态语义(dynamics semantics) 目

3、标程序运行时（run-time）才能检查的语义 例如：除零溢出错误 x/(y-i); 当 y = i时 数组下标越界 int a5; a5 =0; 无效指针 int*p; p =NULL; *p = 3;,静态语义 void b() int x = 1; printf(“%dn”, a); void c() printf(“%dn”, a); void main() b(); c(); ,如何描述程序设计语言的语义？,程序设计语言的形式语义 属性文法 (用于描述静态语义) 操作语义(Operational Semantics) 指称语义(Denotational Semantics) 代数语义

4、(Algebra Semantics) 公理语义(Axiomatic Semantics) 形式语义技术没有形式语法技术成熟 硕士研究生的课程-形式语义学,语义分析的主要任务,输入：抽象语法树 或 TokenList 输出：抽象语法树+符号表 或 TokenList+符号表 数据结构：抽象语法树+符号表 算法： 基于抽象语法树的语义分析：是自左向右先根遍历抽象语法树的过程 声明节点：存储标识符的属性，检查重复声明错误 语句节点：使用标识符的属性，检查各种语义错误 基于TokenList的语义分析：是自左向右扫描Token序列的过程 扫描到标识符Token($id,idname) ($id, i

5、dentry); 语义分析可在语法分析或代码生成的同时完成。一般地，语义分析是伴随着语法分析完成的;,类Pascal语言的抽象语法树,类型声明,变量声明,过程声明,根结点,ProK,类型声明,TypeK,变量声明,VarK,程序体,StmLK,程序头,PheadK,声明,1,声明,n,声明,1,声明,n,语句,n,语句,1,过程声明,1,过程声明,n,语句,n,语句,1,形参,n,形参,1,过程体,StmLK,类C语言的抽象语法树,程序Root,节点 Node1,节点 Node2,节点 Noden,节点 Node,常量声明,类型声明,变量声明,函数声明,FunNode1,FunNode1,Fu

6、nNode1,语句,形参声明,基于Tokenlist的语义分析,int x,y; int f();,($int, -) ($id, x) ($comma, -) ($id, y) ($semi,-) ($int, -) ($id, f) ($lparen, -) ($rparen,-) ($semi,-),($int, -) ($id, xentry) ($comma, -) ($id, yentry) ($semi,-) ($int, -) ($id, fentry) ($lparen, -) ($rparen,-) ($semi,-),(x,varkind,intptr,),xentry:

7、,(y,varkind,intptr,),yentry:,(f,routkind,intptr,),fentry:,常见的语义错误,与标识符声明和使用相关的语义错误 标识符没有声明; 重复声明; 与类型相关的语义错误 各种条件表达式的类型不是布尔类型; 运算符的分量类型不相容; 其他语义错误 唯一性检查 switch语句的分支常量表达式不能有重复； 枚举类型的元素不能重复； 结构类型的域名不能重复等,如何检查各种错误？,建立符号表的时候检查,符号表建好后分析语句时候检查,第六章 语义分析,6.1 语义分析概述 6.2 符号表 6.3 类型的语义分析 6.4 声明的语义分析 6.5 程序体的语义

8、分析 6.6 属性文法和动作文法,6.2 符号表,什么是符号表(Symbol Table)? 符号表可看作是从标识符名字到它的属性的映射; 用于存储程序中声明的标识符及其属性; 在语义学中，将符号表称为“环境”,6.2 符号表,为什么在语义分析时需要符号表(Symbol Table)? 从标识符的Token定义($id, idname)，我们仅仅知道了标识符的名字，对于其它属性，例如类型，种类，存储信息等没有记录 标识符的更多信息需要通过语义分析获得，并记录到符号表中，符号表为后续的语义分析提供信息。语义分析的同时可检查语义错误;,6.2 符号表,为表示标识符的属性，我们需要建立 标识符的内部

9、表示 类型的内部表示 值的内部表示 符号表的组织 标识符的作用域 局部化的符号表 全局化的符号表 符号表的接口函数,知识关系图,语义分析,需要标识符的更多信息,符号表,标识符的属性,标识符的内部表示,类型的内部表示,值的内部表示,标识符的内部表示,标识符的不同种类 常量标识符 类型标识符 变量标识符 函数/过程标识符 域名标识符,typedef enum constKind, typeKind, varKind, routKind, fieldKind idKid;,标识符的内部表示,不同种类标识符的属性 常量: (类型，值) 类型: (类型) 变量: (类型, 层数，偏移) 函数: (返回类

10、型, 形参定义, 代码地址, 空间大小, .) 过程: (形参定义, 代码地址, 空间大小, .) 域名: (类型, 偏移),常量标识符的属性,Kind 标识符的种类，所有常量的 kind = constKind; TypePtr 指向常量类型内部表示的指针; Value 常量值的内部表示; 例：#define pai 3.14 #define count 100,类型标识符的属性,Kind 标识符的种类，所有类型标识符的 kind = typeKind; TypePtr 指向类型内部表示的指针; 例：typedef int t1; typedef int t210; t1 a; /t1是类型

11、标识符，a是变量标识符 t2 b; /t2是类型标识符，b是变量标识符,变量标识符的属性,Kind 标识符的种类, 所有变量标识符的Kind = varKind; TypePtr 指向变量类型的内部表示; Access: (dir, indir); Level: 层数 Offset: 偏移量 Value: 初始化时赋给变量的值的内部表示 例：int x = 10; float y; float* z;,域名标识符的属性*,TypePtr 指向域名类型的内部表示; Kind 标识符的种类, 所有域名标识符的Kind =fieldKind; Offset: 该域名针对所在结构类型的偏移量; Ptr

12、: 指向所在结构体的下一个域;,过程或者函数的属性,Kind: 标识符的种类，此处为 routKind; TypePtr: 指向函数返回值类型的内部表示，过程情形为NULL; Class: 当前函数是实在函数时(有自己函数体)取actual; 当前函数是形参函数时( 作为其他函数的参数)取formal; Level: 函数标识符被定义的层数; Off：当前函数是形参函数时，为其分配的地址偏移； Param: 指向当前函数的形式参数列表的指针; Code: 指向函数对应的目标代码的起始地址; Size: 目标代码的大小; Forward: 该声明为函数原型时取值 true，否则取值为false;

13、 例：int f(int x, float*y, int inc() void p(int x, float*y) . ,层数(level) 某些程序语言，过程/函数的定义可以嵌套 通常规定主程序的层数为0; 偏移量(offset) 执行过程/函数的调用时, 需要为其中的变量分配空间; 偏移量指的是变量针对其所在过程/函数的空间的首地址的偏移量;,变量的层数和偏移 (包括形式参数),Program A Var x, y: integer; Begin End.,Procedure P() Var k:array1.9 of real; m: integer; Begin End;,Proced

14、ure R() Var x:real; Begin End;,Function f(i:integer) Var j:integer; Begin End;,层数为0,层数为1,层数为2,层数为1,x : (0, 0) y : (0, 1),k : (1, 0) m : (1,18),i : (2, 0) j : (2,1),x : (1, 0),变量的层数和偏移 (包括形式参数),P(0，-),f(1，-),R(0，-),typedef struct int number; char name10; example; int i; example p; float x;,void q(int

15、 i) float x, y; ,void main() int x; ,层数为0,层数为1,层数为1,i : (0, 0) p: (0, 1) x : (0, 12) q: (0,) main: (0,),i: (1, 0) x : (1, 1) y : (1,3),x: (1,0);,变量的层数和偏移 (包括形式参数),类型的内部表示,为什么需要类型的内部表示? 类型是标识符的重要属性; 类型检查是语义分析的重要部分; 类型的结构对类型检查很重要; 程序语言的类型 基本类型 Integer (int ) Real (float) Bool Char 构造类型 数组(Array) 结构体(S

16、tructure、record) 联合类型(Union、变体记录) 枚举类型(enum) 指针类型(pointer),基本类型的内部表示,intPtr,intSize,intTy,Size Kind,boolPtr,boolSize,boolTy,realPtr,realSize,realTy,charPtr,charSize,charTy,数组类型的内部表示,ElemTy: 指向数组成分类型的指针; size = sizeof(ElemTy) (Up-Low+1),例：array 2.9 of integer; (8, arrayTy, 2, 9, intPtr),int a7; (7, a

17、rrayTy, 0, 6, intPtr),结构体类型的内部表示,Size: 所有域的类型的size的总和; Body:是域名标识符的内部表示链；,Body,FieldType,Offset,Next,FieldName,例： typedef struct int i; char name10; float x; example; example wang; example factory_a100;,联合类型的内部表示,Body: 指向联合体中域定义链表 Size: 所有域的类型的size中最大值;,Body,FieldType,Next,FieldName,例： typedef union int i; char name10; float x; test; test lee; test factory_b100;,指针类型的内部表示,BaseType: 指向指针的基类型; Size:指针的空间大小(通常为1个单元); 例： int* p1; float* p2; int *p310; int (*p4)10; int* (p510); int* p6; int*(*p7