8符号表

9.1符号表的作用和地位编译程序在执行的过程中，为了完成源程序到目标代码的翻译，需要不断收集、记录和使用源程序中一些语法符号的类型、特征和属性等相关信息。通常这些信息利用一些表格来保存，如常数表、变量名表、数组名表、过程或子程序名表以及标号表等。习惯上，将这些表格统称为符号表。源程序词法分析程序语法分析程序语义分析程序中间代码生成程序代码优化程序目标代码生成程序目标程序出错处理程序表格管理程序9.1符号表的作用和地位符号表的每一登记项包括名字标识符以及与该名字相关联的一些信息。这些信息全面反映了各个符号的属性及它们在编译过程中的特征。在编译程序工作的全部过程中，都需要频繁对符号表进行访问。有时填写信息，有时是查找信息。无论是查找，还是填写符号表，在编译过程中都是一笔很大的开销。但仍然要利用它，因为，它的功能体现如下：1.收集符号属性：在分析语言程序中标识说明部分时，编译程序根据说明信息收集有关标识符的属性，并在符号表中建立符号的相应属性信息。2.上下文语义的合法性检查的依据：同一个符号，可能在不同的地方出现，有的是定义；有的是引用。需要检查上下文之间的一致性和合法性。9.1符号表的作用和地位9.1符号表的作用和地位3.作为目标代码生成阶段地址分配的依据：除了在分析过程中临时变量需要存贮单元外，每个符号变量在生成目标代码时需要安排存贮位置。这需要解决两个问题：存在哪个存贮区；在存贮区中存在哪个位置。这两个信息都要存贮在符号表中。符号表在编译过程中担任很重要的角色，然而，又有很大开销。因此，合理组织符号表，正确利用符号表，是提高编译程序工作效率的重要一环。9.2符号表的主要属性及作用语言符号可以分为关键字（保留字）符号、操作符符号和标识符符号。它们之间的主要属性有较大差别。需要建立不同的符号表。以标识符为例，通常具有下列几种属性：1.符号名：a.在程序设计语言中，一个标识符可以是一个变量名、一个函数名或一个过程的名字；b.每个标识符通常由若干个字符组成的字符串来表达。a.因为标识符是变量、函数或过程的唯一标识，因此标识符的重命名问题需要注意。b.符号名与它在符号表中的位置一一对应，而该位置通常用一个整数来表示，这个整数就是该符号的内部代码，在分析过程中符号串就变成了一个数值，识别与处理就方便了。9.2符号表的主要属性及作用2.符号的类型：a.除了过程标识符之外函数和变量标识符都具有数据类型属性，其中，对于函数的数据类型指的是函数值的数据类型；b.基本数据类型有整数、实数、字符、逻辑及位组型等；c.符号的类型属性是在语言程序中定义的；d.变量符号的类型属性决定了该变量的数据存贮格式和可以施加的运算操作；a.不同类型的变量类型在运算过程中可能发生变化；b.符号类型调整的原则是把其中一个存贮尺寸较小或结构简单的变量转换成另一个符号类型；c.在基本数据类型基础上可以扩充复合数据类型。如数组类型、记录结构类型等；d.符号的类型是符号表存贮的符号的重要属性。9.2符号表的主要属性及作用3.符号的存贮类别：a.大多数语言对变量的存贮类别定义采用二种方式；①一种是用关键字指定。如：COMMON、Static等；②另一种是根据定义变量说明在程序中的位置来决定。如私有变量、全局变量等；b.区别符号存贮类型的属性是编译过程语义处理、检查和存贮分配的重要依据。4.符号的作用域及可视性：a.一个符号变量在程序中起作用的范围，称为它的作用域；b.一般来说，定义该符号的位置及存贮类关键字决定了该符号的作用域；c.一个变量的作用域就是该变量可以出现的场合，也就是说在某个变量作用域范围内该变量是可以引用的，这就是变量可视性的作用域规则；9.2符号表的主要属性及作用a.变量的可视性还体现在函数的形式参数及分程序结构情形中；①函数的形式参数：通常函数的形式参数是作为函数的内部变量处理的。函数体外定义的变量在函数体内是看不见的。这时可以重名。②分程序结构：即结构化的程序设计。程序可以分为若干程序模块，程序模块中又可以嵌套其他程序模块。为确定符号的作用域和可视性，符号表属性中除了需要符号的存贮类别之外还需要表示该符号在程序结构上被定义的层次。b.无论是函数形式参数，还是分程序结构中的局部定义都可以统一地用定义层次来区分。一般外部为0层，函数内部为1层，依次向内嵌套定义的分程序为2、3等层。5.符号变量的存贮分配信息：a.根据符号变量的存贮类别定义及它们出现的位置和次序来确定每一个变量应分配的存贮区及在该区中的具体位置；b.在编译程序中，变量符号有两个存贮区域：静态存贮区和动态存贮区；①静态存贮区：该存贮区单元经定义分配后成为静态单元，在整个语言程序运行过程中是不可改变的。静态单元分配的符号变量的生命周期是整个语言程序运行的周期；根据变量存贮类别及作用域规则，静态存贮区又可以分为：公共静态区和局部静态区。9.2符号表的主要属性及作用①动态存贮区：根据变量的局部定义和分程序结构，编译程序设置动态存贮区来适应这些局部变量的生存和消亡。局部动态变量的生存周期是定义该变量的局部范围，即在该范围之外此变量已经没有存在的必要。及时撤消时，这些单元可以收回，从而提高运行的空间效率。a.符号变量在存贮区中存放具体位置是根据扫描源程序变量出现的次序以及它们之间的相对位置决定。6.符号的其他属性：a.数组内情向量：在程序设计语言中，数组是重要的数据类型。数组内情向量是描述数组属性的信息，包括：数组类型、维数、各维的上下界、数组的首地址，这些信息登录在符号表中，是数组存贮分配时确定所占空间大小和数组元素位置的依据；b.记录结构的成员信息：一个记录结构的变量，是由若干成员组成的，因此记录结构变量在存贮分配时所占据空间大小和位置要由它的全体成员的属性以及这些成员排列次序来确定；c.函数及过程的形参：函数或过程的形式参数是函数或过程的变量，有是对外的窗口，它们的属性和排列次序都要反映在符号表中。。9.2符号表的主要属性及作用9.3符号表的组织从词法分析、语法分析、语义分析到代码生成的整个过程中，符号表是连贯上下文进行语义检查、语义处理、生成代码和存贮分配的主要依据，因此，符号表的组织直接关系到这些语义功能的实现和语义处理的时空效率。1.符号表的总体组织在程序设计语言中，有不同的种类的符号，它们的属性信息各不相同，有的差异很大，有的比较接近。要将这样属性信息各不相同的符号放入符号表中，需要很好的组织，通常有三种方法：①a).按照属性完全相同的符号组织在一起；b).这样就需要建立多个符号表；c).好处是空间效率高，对每个符号表来说管理一致方便；d).缺点，表多，总体管理复杂，混乱。②a).把程序设计语言中所有的符号集中在一张表中；b).好处，集中管理方便，处理和管理比较一致；c).缺点，空间效率低，符号个性化处理不方便。③将第一、第二中折中，将属性接近的符号放在一个符号表中，各个表通过关键字索引。9.3符号表的组织2.符号表项的排列符号表作为一个多元组，表中元组之间的排列组织是构造符号表的重要成分；在整个编译过程中，符号表被频繁的用来建立、查找、填写和引用，因此，表项的排列和组织对系统运行效率影响很大。符号表项的排列通常有三种方式：①线性组织：按符号被扫描的先后顺序建立在符号表中。②排序组织及二分法：按照符号的代码值（ASCII）从小到大排列。③散列组织：a).表项位置由对表项符号值进行“杂凑”函数计算得到函数值来确定；b).所得到的函数值与该表项在表中的位置的对应关系是通过函数值求整及相对于表长“求余”得到；c).有时会出现，不同符号散列到表中同一个位置上，造成“散列冲突”；d).解决冲突的方法是不断散列，直到确定或报错。静态符号表：多为关键字符号表动态符号表：多为一般变量符号表。9.3符号表的组织3.关键字域的组织关键字域就是指符号表的关键字。符号表的关键字域就是符号本身。它可以是语言的保留字、操作符、标识符（包括变量、函数名、记录结构等）。不同的程序设计语言，关键字域的规定不同，如：最大字符个数，保留字冲突限制等。编译程序中标识符的内部规则是符号表关键字组织的基础和依据。语言中标识符不会很长，并且也不会等长，就会造成空间的浪费。既要保证关键字的等长，又要减少甚至消除冗余，采用关键字池的索引结构是可取的。关键字池组织的符号表假设有一组标识符anexemplarofkey-wrdsfield关键字段属性信息0……3……12……15……25…………anexemplarofkey-wordsfield关键字池p池的空区9.3符号表的组织4.其他域的组织符号表属性域的组织，根据属性性质分成两类：属性相同且等长；属性相同但不等长。1.属性相同且等长：可以取相应的数据类型表达属性值。例如：符号是否被定义属性、符号的数据类型属性、符号之间关系属性等。2.属性相同但不等长：对于不等长的属性域，一般不把属性值存放在符号表项的某个域中，而另设一个相关空间存放属性值。类似于关键字池。数组内情向量属性域中存放一个指针（指针是等长的），指向不等长的数组内情向量空间。数组内情向量属性域组织符号内情向量指针array1array2subscrip1subscrip20subscrip3subscrip4Subscrip5subscrip60array1的内情向量array2的内情向量设有两个数组：Array1（subscrip1，subscrip2）Array2（subscrip3，subscrip4，subscrip5，subscrip6）9.3符号表的组织5.下推链域的组织在分层的程序设计中，允许同名标识符具有的生命周期发生重叠。这些同名的标识符在程序的某一处只能看到其中的某一个，其他的几个仍然存在。下推组织要求在进入一个内层结构并发生重名标识符定义时，需要把当前符号表中外层的该符号表项下推到下推链中而在符号表被下推的表项处建立内层的同名标识符的表项。为了实现同名标识符的语义功能，符号表中需要设立下推链域的组织方式。9.4符号表的管理符号表的管理主要体现在：初始化、登录、查找和符号表层次管理。除初始化外，其他都是动态进行1.符号表的初始化符号表的状态反映了该时刻被编译的语言程序正被编译的位置的状态。也就是在该时刻语言程序中可视标识符的状态。符号表的初始化就是在对语言程序开始编译的时刻，定义建立符号表的初始状态。符号表的表长是渐增变化的情况（线性组织和排序组织）符号表的表长是确定的情况（散列组织）9.4符号表的管理2.符号的登录当编译程序从语言中获得一个标识符并确定该符号在符号表中不存在，就要将此符号登录在符号表。首先，确定符号在符号表中的位置。①线性排列登录②排序组织方式的登录③散列组织的登录其次，登录符号名称及属性，有些属性可以直接登录；有些属性可以在以后的语法分析过程中逐步登录。9.4符号表的管理3.符号的查找在编译过程中，在源程序中获取一个符号，则在保留字和运算符表或符号表中查找。查找的目的是建立或确认符号的语义属性。符号的查找算法与符号表的组织方法密切相关。顺序查找、折半查找、杂凑查找等方法。9.4符号表的管理4.符号表中分程序结构层次的管理分表管理：每个分程序建立一个独立的符号表①每当编译程序扫描到一个分程序结构开始时，为该分程序建立一张符号表。②在该分程序中定义的标识符，都被登录在该符号表中。③当编译程序扫描到一个分程序的结束时，编译程序释放为该分程序建立的符号表。④登录是在该分程序的符号表中登录，查找可以向外层查找，若查不到则出错。单表查找：各个分程序符号组织在一张符号表中。①为了标志一个符号所属的分程序层次，在符号表中设立一个属性域用来登记符号所在分程序的层次②在编译进入一个分程序时，表示分程序层次的状态量要增加一层，表示相应的层次属性③退出分程序是要做相应的处理，不仅要降低一层分层状态量，还要清除该分程序中登录的符号项④不同分程序层次中的符号项要用下推域动态管理。