语义分析在编译程序中的作用.ppt

语义分析在编译程序中的作用,词法分析,语法分析,语义分析,中间代码优化,中间代码生成,目标代码生成,分析,合成,第六章 语义分析,6.1 语义分析概述 6.2 符号表 6.3 类型的语义分析 6.4 声明的语义分析 6.5 程序体的语义分析 6.6 属性文法和动作文法,6.1 语义分析概述,语法(Syntax)和语义(Semantics)的区别 语义分析的必要性 程序设计语言语义的分类 如何描述程序设计语言的语义？ 语义分析的主要任务,语法和语义的区别,语法： 是描述一个合法定义的程序结构的规则 例如： id( ) 语义： 说明一个合法定义的程序的含义,int x; float f(); x(); x = f();,符合变量声明的语法、语义,符合函数声明的语法、语义,符合函数调用的语法、不符合语义,符合赋值语句的语法、不符合语义,语义分析的必要性,一个语法正确的程序不能保证它是有意义的！ 程序中容易出现各种语义错误： 标识符未声明 操作数的类型与操作符的类型不匹配 ,程序设计语言语义的分类,静态语义 编译时(compile-time)可以检查的语义 例如：标识符未声明 动态语义 目标程序运行时（run-time）才能检查的语义 例如：除零溢出错误,如何描述程序设计语言的语义？,程序设计语言的形式语义 属性文法 (用于描述静态语义) 操作语义(Operational Semantics) 指称语义(Denotational Semantics) 代数语义(Algebra Semantics) 公理语义(Axiomatic Semantics) 形式语义技术没有形式语法成熟 硕士研究生的课程-形式语义学,语义分析的主要任务,根据声明部分建立符号表 存储标识符的属性，以便检查语义错误和为代码生成提供信息; 在整个程序范围内检查语义错误 声明和使用相关的错误 类型相关的语义错误 一般地，语义分析是伴随着语法分析完成的;,常见的语义错误,声明和使用相关的语义错误 标识符没有声明; 重复声明; 如何检查? 每当遇到新声明的标识符,查符号表 如果当前有效的所有标识符中有相同名字的,则是重复声明错误; 否则生成它的属性信息,保存到符号表中; 每当遇到标识符的使用,查符号表 如果没有找到,说明该标识符没有声明; 否则, 得到该标识符的属性,进行进一步分析;,常见的语义错误,类型相关的语义错误 各种条件表达式的类型不是布尔类型; 运算符的分量类型不相容; 赋值语句左右类型不相容; 形实参类型不相容; 函数调用参数个数不同; f()中f不是函数标识符; 下标表达式(数组)不是合法类型; 函数说明和函数返回类型不相容; ,第六章 语义分析,6.1 语义分析概述 6.2 符号表 6.3 类型的语义分析 6.4 声明的语义分析 6.5 程序体的语义分析 6.6 属性文法和动作文法,6.2 符号表,什么是符号表(Symbol Table)? 符号表可看作是从标识符名字到它的属性的映射; 用于存储程序中声明的标识符及其属性;,6.2 符号表,为什么在语义分析时需要符号表(Symbol Table)? 从标识符的Token定义，我们仅仅知道了标识符的名字，对于其它属性，例如类型，种类等没有记录 对于标识符的更多信息需要进行语义分析，从而检查语义错误;,6.2 符号表,为表示标识符的属性，我们需要建立 标识符的内部表示 类型的内部表示 值的内部表示 符号表的组织 标识符的作用域 局部化的符号表 全局化的符号表 符号表的接口函数,知识关系图,语义分析,需要标识符的更多信息,符号表,标识符的属性,标识符的内部表示,类型的内部表示,值的内部表示,标识符的内部表示,标识符的不同种类 常量标识符 类型标识符 变量标识符 函数标识符 过程标识符 域名标识符,typedef enum constKind, typeKind, varKind, procKind, funcKind, fieldKind idKid;,标识符的内部表示,不同种类标识符的属性 常量: (类型，值) 类型: (类型) 变量: (类型, 层数，偏移) 函数: (返回类型, 形参定义, 代码地址, 空间大小, .) 过程: (形参定义, 代码地址, 空间大小, .) 域名: (类型, 偏移, 所在结构类型),常量标识符的属性,TypePtr 指向常量类型内部表示的指针; Kind 标识符的种类，所有常量的 kind = constKind; Value 常量的值;,类型标识符的属性,TypePtr 指向类型内部表示的指针; Kind 标识符的种类，所有类型标识符的 kind = typeKind;,变量标识符的属性,TypePtr 指向变量类型的内部表示; Kind 标识符的种类, 所有变量标识符的Kind = varKind; Access: (dir, indir); Level: 层数 Offset:偏移量,域名标识符的属性,TypePtr 指向域名类型的内部表示; Kind 标识符的种类, 所有域名标识符的Kind =fieldKind; Offset: 该域名针对所在结构类型的偏移量; Ptr: 指向所在结构体的下一个域;,(实在过程或者函数的属性),TypePtr: 指向函数返回值类型的内部表示，过程情形为空; Kind: 标识符的种类，此处为 routKind; Class: actual指代实在的(有自己的函数体)函数或过程; Level: 标识符被定义的层数; Param: 指向形式参数列表的指针; Code: 指向函数或过程对应的目标代码的起始地址; Size: 目标代码的大小; Forward: 该函数为向前声明时取值 = true;,形参过程或者函数的属性,TypePtr:同形式函数/过程; Kind: 同形式函数/过程, = routKind; Class: = formal; Level:同形式函数/过程; Param:同形式函数/过程; Offset: 在形参列表中的偏移;,层数(level) 某些程序语言，过程/函数的定义可以嵌套 通常规定主程序的层数为0; 偏移量(offset) 执行过程/函数的调用时, 需要为其中的变量分配空间; 偏移量指的是变量针对其所在过程/函数的空间的首地址的偏移量;,变量的层数和偏移 (包括形式参数),Program A Var x, y: integer; Begin End.,Procedure P() Var k:array19 of real; m: integer; Begin End;,Procedure 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; real x;,void q(int i) real 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) 结构体(Structure、record) 联合类型(Union、变体记录) 枚举类型 指针类型,基本类型的内部表示,intPtr,intSize,intTy,Size Kind,boolPtr,boolSize,boolTy,realPtr,realSize,realTy,charPtr,charSize,charTy,数组类型的内部表示,size = sizeof(ElemTy) (Up-Low+1) ElemTy: 指向数组成分类型的指针;,array 29 of integer; (8, arrayTy, 2, 9, intPtr),int 7; (7, arrayTy, 0, 6, intPtr),结构体类型的内部表示,Body: 指向结构体中域定义链表 Size: 所有域的类型的size的总和;,Body,FieldType,Offset,Next,FieldName,typedef struct int i; char name10; real x; example;,联合类型的内部表示,Body: 指向联合体中域定义链表 Size: 所有域的类型的size中最大值;,Body,FieldType,Next,FieldName,typedef union int i; char name10; real x; test;,指针类型的内部表示,BaseType: 指向指针的基类型; Size:指针的空间大小(通常为一个单元);,枚举类型的内部表示,EList: 枚举常量链表; Size:枚举类型值的空间大小(通常为一个单元);,值的内部表示,可表示的值 Integer Real False, true(通常对应0和1) char: ASCII码值 枚举类型: 对应整数 结构值 数组 结构 联合 指针,知识关系图,语义分析,需要标识符的更多信息,符号表,标识符的属性,标识符的内部表示,类型的内部表示,值的内部表示,符号表的组织,标识符的作用域 符号表的局部化 符号表的全局化 接口函数,标识符的作用域,作用域(scope) 程序中的每个标识符都有自己的作用域; 标识符的作用域是标识符可见(visible)或有效的(effective)一个程序片段,称为程序的局部化单位; 通常一个程序局部化单位是一个子程序(函数)或者分程序; 一个标识符的作用域从声明该标识符的位置开始到其所在的局部化单位的结束(其中要去掉其内部声明的同名标识符的作用域); 特别地, 域名的作用域是包含该域名的结构或者联合体;,标识符的作用域,int i , j ; void test(int j) real x ; int x ; . void main() char i ; int i ; ,“test”和 “main” 的作用域是什么?,符号表的处理,int i , j ; void test ( int j ) real x ; j int x ; . void main() char i ; int i ; ,j: (intPtr, varKind, 0, 1, dir),i: (intPtr, varKind, 0, 0, dir),test: (voidPtr, routKind, 0, ),j: (intPtr, varKind, 1, 0, dir),x: (realPtr, varKind, 1, 1, dir),x: (intPtr, varKind, 1, ?, dir),main: (voidPtr, routKind, 0, ),i: (charPtr, varKind, 1, 0, dir),i: (intPtr, varKind, 1, 1, dir),语义分析时对符号表的管理,标识符声明 查找符号表检查标识符是否已经被声明过; 如果是，则重复声明错； 如果不是，则建立标识符的内部表示，将其放入符号表; 标识符使用 查找符号表检查标识符是否有声明； 如果是，则取出标识符的属性进行语义分析； 如果不是，则未声明错； 退出局部化单位,“删除” 该局部化单位里声明的所有标识符;,符号表的组织,第一，易于查找 顺序查找 折半查找 散列表(hash table) 第二，反映标识符的作用域，保证每次标识符的有效属性都能被找到; 局部化: 每个局部化单位的符号表作为一个独立的表处理, 即把每个局部化单位的符号表作为建表和查表单位; 全局化:把整个程序的符号表统一处理;,局部化符号表,Scope栈保存当前所有局部化单位符号表的首地址; 局部化实现原理: 进入局部化单位,建立一个新的空符号表,并将地址压入Scope栈; 遇到定义性标识符(声明), 查当前符号表判定是否有重复定义,如果没有则将其属性登记到当前符号表中; 遇到使用性标识符,查符号表(从当前符号表查,如果没有,再依次查scope栈中下一个符号表,如果都没有,没有声明错;否则,找到对应的属性); 结束一个局部化单位时,删除当前符号表, 弹出scope栈顶元素; 每个局部化单位的符号表可以是 线性表; 二叉树; 散列表,局部化符号表,int i , j ; void test ( int j ) real x ; j int x ; . void main() char i ; int i ; ,Scope栈,0,全局化符号表,全局化实现原理 整个程序用一个符号表, 该符号表的组织可以是 线性表; 二叉树; 散列表 每个局部化单位对应一个唯一的局部化编号num; 符号表的表项为(num, id, attributes); 初始化: CurrentNum = 0; 进入局部化单位, CurrentNum+; 遇到定义性标识符(声明),检查所有对应CurrentNum的表项,判定是否有重复定义,如果没有则将其属性及其CurrentNum登记到符号表中; 遇到使用性标识符,查符号表,如果都没有,没有声明错;否则,找到对应的属性; 结束一个局部化单位时,删除所有CurrentNum对应的表项, CurrentNum -;,全局化符号表,如何查找标识符X的属性？ 依赖于符号表的组织方式 主要思想 (1)Num = CurrentNum; (2) 在符号表