第6章-白底黑字概要课件.ppt
第6章 符号表的组织与管理,编译过程中，始终涉及到对一些语法符号的处理，需要用到这些语法符号的相关属性。为了在需要的时候能找到这些语法成分及其相关属性，必须使用一些表格保存这些语法成分及其相关属性，这些表格就是符号表。,第6章 符号表的组织与管理,符号表是编译程序中主要的数据结构之一。,本章主要介绍,符号表的作用,符号表的组织,符号表的建立和查找,6.1 符号表的作用与生成期,符号表的作用,将标识符的名字及属性登录在符号 表中,符号表用来存放程序语言中出现的有关标识符的属性和特征。,符号表在整个编译期间的作用归纳为以下几个方面：,在分析说明语句时，编译程序根据说明语句信息将标识符的相应属性 如标识符的类型：实型，整型，布尔型等；标识符的种属：数组名，变量名，过程名，函数名等;标识符的作用域：全局变量或局部变量等信息登录到符号表中。,6.1 符号表的作用与生成期,通过符号表中记录的属性可进行上述语义检查。,如对运算对象和运算符进行类型检查,对变量进行先定义后使用检查等。,辅助上下文语义的正确性检查,6.1 符号表的作用与生成期,在目标代码生成阶段，符号表是数据存储分配的依据。要形成能运行的目标代码，需要对程序中引用的标识符分配存储单元，而存储单元的分配与标识符属性相关，与属性相关的信息可通过查符号表获取。,6.1 符号表的作用与生成期,辅助目标代码生成,符号表的生成期,符号表的建立可以开始于词法分析阶段，也可以放到语法、语义阶段，但符号表的使用有时会延续到目标代码的运行阶段（如数组下标地址计算的需要等）。,6.1 符号表的作用与生成期,6.2 符号表的内容,符号表中一般要保存以下信息：,1.标识符的名字,2.标识符有关的信息：,(1)类型信息,包括种类（常量、变量、数组、标号或函数等）与属性（整型、实型、字符型、布尔型等）,数组,包括维数、界差、上下界、计算下标地址时涉及的常量等，放在数组信息向量表（内情向量表）中。,6.2 符号表的内容,函数或过程,包括参数的个数、类型、次序、是否允许递归等。,一般是该量在数据区所占单元的绝对地址或相对地址。,(2)地址码,常量或简单变量,6.2 符号表的内容,数组,是该数组在数据区中的首地址。,函数或过程,6.2 符号表的内容,是该函数或过程的分程序入口地址。,(3)层次信息,对于分程序嵌套或过程嵌套结构型程序设计语言，还应包括每个标识符所属分程序（过程）的层次。,(4)行号信息,有些程序设计语言需要保存标识符在源程序中的行号，包括说明行和引用行。,6.3 符号表的组织,一个编译程序，从词法分析、语法分析、语义分析到代码生成的整个过程中，符号表是连贯上下文进行语义检查、语义处理、生成代码和存储分配的主要依据，因此符号表的组织直接关系到这些语义功能的实现和语义处理的时空效率。,符号表的表格形式,6.3 符号表的组织,名字栏存放标识符的名字，信息栏存放名字相关属性。,符号表的总体组织,6.3 符号表的组织,1.编译程序按名字的不同属性构造出多个符号表。如常量表、变量名表等。,2.编译程序把语言中的所有名字组织在一张符号表中。,符号表结构相同，表项等长。不便管理。,符号表便于管理，但表结构复杂且表项不等长。,6.3 符号表的组织,3.折衷方式即按名字属性相似程度分类构造出多个符号表。,符号表管理复杂性折衷。,名字和标识符的区别,在程序设计语言中，凡以字母开头的字母数字序列都是标识符。当给予某个标识符以确切的含义后，这个标识符就叫做一个名字。,6.3 符号表的组织,也就是说标识符是一个没有意义的字符序列，而名字有确切的意义。在程序语言中标识符可以是一个变量的名字或一个函数的名字。,例如 area,作为标识符，它没有任何意思，但作为名字，可以表示变量名或函数名等。,6.3 符号表的组织,一个名字代表一个存储单元，该存储单元的内容为该名字的值，同时名字还有属性（即类型和作用域等）,符号表的数据结构可以是线性符号表、也可以是树结构、散列表或桶等。,6.4 符号表的构造和查找,在整个编译期间，对于符号表的操作一般可归纳为下列五类：,(1)对给定名字，查询此名是否已在表中。,(3)对给定名字，访问它的某些信息。,(2)往表中填入一个新的名字。,6.4 符号表的构造和查找,(4)对给定名字，往表中填写或更新它的某些信息。,(5)删除一个或一组无用的表项。,在整个编译过程中，符号表的查填频率是非常高的，所以研究符号表的构造和查找方法是很重要的。,6.4 符号表的构造和查找,1.符号表的构造方法,线性法、二分法及散列法。,线性法：是按名字出现的先后顺序填写各表项。,二分法：造表时是将名字拦按名字的大小顺序排列。,散列法：构造一个散列函数将所得的函数值求整或求余得到表项在表中位置。,6.4 符号表的构造和查找,2.符号表的查找算法,符号表的查找算法与该符号表的构造方法密切相关即有顺序查找、折半查找和杂凑查找算法。,本章小结,1.符号表的作用,符号表用来存放程序语言中出现的有关标识符的属性和特征。,(1)将标识符的名字及属性登录在符号表中,(2)辅助上下文语义的正确性检查,(3)辅助目标代码生成,本章小结,2.标识符和名字的区别,在程序设计语言中，凡以字母开头的字母数字序列都是标识符。当给予某个标识符以确切的含义后，这个标识符就叫做一个名字。,本章小结,也就是说标识符是一个没有意义的字符序列，而名字有确切的意义。在程序语言中标识符可以是一个变量的名字或一个函数的名字。,例如 area,作为标识符，它没有任何意思，但作为名字，可以表示变量名或函数名等。,本章小结,3.符号表的查找,符号表查找算法与该符号表的构造方法密切相关即有顺序查找、折半查找和杂凑查找算法。,
