符号表的组织和管理.ppt

第五章:符号表的组织和管理,符号表的作用 符号表的主要属性及其作用 符号表的组织结构 名字的作用范围,5.1 符号表的作用,符号表是编译程序中的一个重要的数据结构，它象源程序的一个数据字典，存储了源程序中每个名字及其属性，使用在编译的各个阶段。 (1) 登记符号属性值 在源程序的各个分析阶段，编译程序根据标识符的声明信息收集它属性的有关值，并把它们存放在符合表中。 每种语言规则定义了不同的符号属性；即使是同一个语言，不同的编译程序也可能会定义并且收集不同的属性信息。现代编程语言中一般包括常数声明、变量声明、类型声明和过程/函数声明等四类声明。对于每类声明，编译程序要收集、存储和应用的属性完全不同。,例 C语言的变量声明 short int a; float b = 0.0; 把标识符a声明为短整数型，把b声明为浮点类型，而且初始化为0。那么，编译程序对每个变量要记录它的类型，以便执行类型检查和分配存储，比如短整型变量i占2个字节；要记录它在存储器中的位置（相对位移或绝对地址），以便目标程序运行时访问；若像b有初始值，则还需要记录这个初始值。,(2) 查找符号的属性 符号表存放了源程序中的各种类型的信息，比如数值、变量类型、参数传递的地址等，在分析和翻译源程序的过程中会被不断地查询。 例如，对于上述的变量声明，如果源程序有代码 a + b时，就需要查找、计算表达式中运算数的类型和值，以便计算出表达式。 又如，在源程序中如果出现了函数调用factory (6)，编译程序就需要查找到factory的声明，找到实参6的地址并传给形参n，执行函数factory的体，并返回值等。,(2)检查符号的合法性 例如，对于上述声明，代码 a = a + b，C语言的编译将检查变量a和b的类型，把表达式a + b的结果转换成短整型，仅取整数部分进行赋值。 在其它强类型语言，如Pascal和Ada，表达式运算数的类型必须一致，不能进行隐式类型转换，对于这样的表达式a + b，编译程序在语义分析的过程中将发现并报告类型错误的信息。 又如，面向对象语言的继承性和多态性允许同一个消息在不同的环境中调用不同的方法（函数），即调用同名但在不同的类中实现的方法。这就需要编译或者运行时在方法的符号表中查询在参数、返回数以及方法方面名字一致的实现。,(3) 作为目标代码生成阶段地址分配的依据 标识符由它定义的存储类型或它在程序中的位置来确定。 首先是要确定变量存储的区域。例如，在Java语言中，整数的类型（以及所占用的字节）有byte（1个字节）、short（2个字节）、int（4个字节）以及long（8个字节），而float类型占4个字节，double类型占8个字节。又如，对寄存器变量，编译将尽可能地把它们保留在机器的寄存器当中，以提高运行速度；而对在一个文件中定义的外部变量，它们要在不同的源程序文件之间访问，需要编译程序把它们放在所有源程序文件都可以方便寻找到的存储器的位置。 其次，要根据标识符出现的顺序，决定标识符在某个存储区域中的具体位置，而有关区域的标志及其相对位置都是作为该标识符的语义信息存放在它的符号表中的。,5.2 符号表的主要属性及其作用,不同的符号类别包含了不同的属性，由于它们的信息不同，也就导致了符号表的组织有较大的差别。例如，数量类型的变量名字和过程名字： 对于一个变量名要记录其类型（如整型、实型、布尔型等）、占用的存储字节以及相对与某个基准位置的相对位置； 对一个过程名要记录的属性包括参数的个数及其类型，该过程是否有返回值，过程中的变量声明，甚至过程声明（如果像Pascal语言允许嵌套过程声明）等信息。 不同的程序语言规定了符号的不同性质以及语法、语义和规则，几种基本的符号属性。,(1)符号名 语言中的符号名通常用标识符来表示。根据语言的定义，程序中出现的重名标识符定义将按照该标识符在程序中的作用域和可视规则进行相应的处理。而在程序的运行过程中，符号表中的符号名始终是唯一的标志。 在一些允许操作重载、类继承的语言中，函数名、操作名允许重名，对于重载操作的标识符，它们可以通过参数的个数与类型以及返回值的类型来区别；而对于操作的继承，编译器可以构造继承图，同时保存类结构，这样就可以为每个操作和属性找到唯一的定义。 例如，对应不同的参数类型，可以定义几个求和重载函数： int sum ( int a, int b) double sum ( double a, double b) float sum（float a, float b, float c） 当某个函数中调用到重载函数时，编译器根据实参的类型和个数去调用相应的函数。,(2)符号种属 由于语言中符号所拥有的属性可能不同，其组织就可以采用不同的数据结构，可以用符号的种属来区别每个符号的基本划分。 根据不同的语言，符号的种属可以包括：简单变量、结构型变量、数组、过程、类型、类等。 可以依据符号种属的划分来组织符号表，一种方式是为每个种属的标识符建立一张表，这样，可以对符号表类似地安排组织结构、进行同样的操作；另外一种方式把所有种属的标识符统一安排在一张表中，根据符号的种属进行条件判断，对不同种属的特殊型执行不同的存储安排和操作。,(3)符号类型 现代程序语言中的一个重要构造就是数据类型（类型），它是变量标识符的重要属性，函数的数据类型指的是该函数返回值的数据类型。 现代语言通常都有如下的基本类型：整型、实型、字符型、布尔型、逻辑型等； 符号的类型属性从源程序中该符号的定义中得到 变量符号的数据类型属性不但决定了该变量的数据在存储器中的存储格式，也规定了可以对该变量施加的操作运算。,每一个变量的类型是符号表中标识符属性的重要信息。,(4)存储类别 大多数程序语言对变量的存储类别采用两种方式。 一种是用关键字指定，例如，在FORTRAN语言中用COMMON来定义公共存储区域，允许不同程序段都可以访问这些数据；又如，C和C+语言规定static定义的变量属于文件的静态存储变量或属于函数内部的静态存储变量，这些变量在编译时分配存储空间，如果定义时没有初值，编译器还需要将它们初始化为0。 另一种方式是根据定义变量的声明在程序中的位置来决定。例如，C+规定在一个文件中定义的变量缺省为外部的，即程序的公共存储变量；而在函数体内缺省存储类别关键字所定义的变量是内部变量，是属于该函数体所独有的私有存储变量，因而是动态地分配存储空间。 区别符号存储类型地属性是编译过程中语义处理、检查和存储分配的重要依据。 符号的存储类别同时还决定了符号变量的作用域、可见性和它的生命周期等性质 。,(5)作用域 一个标识符在程序中起作用的范围称为其作用域。 一般来说，定义一个符号的位置及存储类型就决定了该符号的作用域，就是它可以出现的场合，可以在程序中作为参数、表达式的运算数等被引用。 C语言中外部变量的作用域是整个程序，一个外部符号的定义在整个策划能够许中只能出现一次，为了方便使用和编译，同名标识符的其它说明可以多次出现。 FORTRAN语言中的COMMON变量的作用域则不是整个程序，而只能在定义这个COMMON块的函数或过程中引用。 面向对象语言，如C+，的每个类都引入了一个独立的类域。,作用域与可见性 标识符的可见性从另外一个角度说明其有效性，它与作用域有一定一致性。 标识符的作用域包含可见范围，但是，可见范围不会超过作用域。 可见性在理解同名是不是合法的作用域嵌套时十分直观。对于外层块域内层块定义的同名标识符，在外层作用域中，内层所定义的标识符时不可见的，即外层所引用的是外层所定义的标识符； 同样，在内层作用域中，外层的标识符将被内层的同名标识符所屏蔽，变得不可见，即外层中同名标识符的可见范围是作用域中挖去内层块的范围，在内存块形成了作用域洞 。,(6 )存储分配信息 编译程序需要根据符号的存储类别定义以及它们在程序中出现的位置和顺序来确定每一个符号应该分配的存储区域及其具体位置。 通常情况下，编译为每个符号分配一个相对于某个基址的相对位移，而不是绝对的内存地址。,(7)其它属性 数组内情向量 需要把描述数组属性的信息如数组类型、维数、每个维的上下界、数组元素的首地址等登录在符号表中，以便确定数组在存储器占用的空间和数组元素的确定，并且完成数组的翻译。 记录结构型的成员信息 一个记录结构型的变量包含若干成员，每个成员的数据类型可以彼此不同，因此，一个记录结构型变量在存储分配时所占空间的大小由其成员来确定，而且，对每个成员的访问还需要它所属成员排列次序的属性信息。 函数或过程的形参 函数或过程的形参作为其局部变量，同时又是对外部调用的接口。每个函数或过程形参的个数、类型、排列顺序都体现了调用函数或过程时的属性，它们都应该反映在符号表中，以便在过程调用的时候进行参数传递，并且执行语义检查（如处理函数名的重载）。 在面相对象语言中，还必须把一个类或其超类所定义同名方法存放在一个方法表中，指向每个方法的实现操作，以便实现面相对象的继承性质。,5.3 符号表的组织结构,一个编译程序从词法分析、语法分析、语义分析到代码生成的整个过程中，都要不断地访问和管理符号表。因此，符号表的组织管理直接关系到编译程序的效率。 三种常见的符号表的结构： 线性表、搜索树和散列表组织 线性表组织是按照符号被扫描到的先后顺序填写各个表项，可以用一个多维数组或多个一维数组来存放符号的信息。 线性表需要两个指针来方便管理和操作：一个指针指向该符号表的开始位置，另一个指针指向符号表的下一个可用位置。 线性表是最基本的数据结构，可以方便、直接地实现上述的插入、查找和删除三种基本操作，而且每种的操作时间都是符号表大小的线性函数，对于有N个表项的符号表，这些操作的平均时间都是N/2左右（算法时间复杂性为(N)）。 由于线性表无需附加空间，比较节省存储。如果编译器对处理时间要求不高，或者符号个数不大（如关键字），符号表就可以采用线性表结构。,搜索树结构 搜索树可以在构造符号表的同时，按照符号名的字典顺序把表项整理排列，提高符号表查找操作的速度。 这样就可以采用折半查找的方式，加快搜索的速度。 对于有N个表项的符号表，每次查找最多只需要做logN次比较（因此这种查找法也叫对数查找法）。 但是，由于符号表在编译过程中是边填写边引用，动态地建立、更新以及删除表项，这样，每增加和删除一个表项都需要对符号表进行重新排序，这同样浪费时间。 因此，搜索树结构不适合用于构造符号表，除了需要额外的空间构造搜索树以外，整体而言，它们实现这三类操作效率不是最优，而且删除操作的实现过于复杂。,符号表处理的关键问题 散列组织统一了查询与插入操作技术，相对来说具有较高的时空效率，为上述三种操作提供的时间基本上是常数。 特别是散列表结构符合编译过程边填写边引用符号表的特性，是实现符号表的最佳数据结构，在实践中的使用最多。,线性表结构填表快，查询慢；搜索树结构查询快，填表慢。,如何保证查询与插入表项这两个基本操作的都能高效地完成。,散列方法 散列方法在表项的存储位置与它的关键码之间建立一个确定的对应函数关系（哈希函数，杂凑函数，hash），使每个关键码symbol与散列结构（散列表，哈希表，杂凑表）中的唯一的存储位置相对应，即hash(symbol)。 在搜索时，首先对表项的关键码用哈希函数计算出对应的表项的存储位置，在散列表中按此位置取出表项进行比较，若关键码相等，则搜索成功。 在填入表项时，依同样函数计算存储位置，并按此位置存放表项。由于使用这种方法进行搜索时不必多次比较关键码，因此搜速速度比较快，可以到达逼近具有此关键码的表项的实际存放地址。,对哈希函数的基本要求 计算简单、高效； 函数值能均匀地分布在1和N之间， 对不同的关键码都返回一个代表存储位置的不同值。 构造哈希函数的算法有许多，例如，若取N为素数，就可以定义哈希函数为symbol/N的余数，其中symbol是某个符号的代码。由于语言中的标识符可以相互区别，它们的代码值都是不同的。,散列冲突的解决 不同的关键码经过杂凑运算以后，有可能得到相同的杂凑值，这种现象称为散列冲突。 一种常用的方法是链地址法。 把有N个地址的散列表改为N个桶，桶号与散列地址一一对应，第i（1iN）个桶号即为第i个散列地址，每个桶则是一个线性链表（称为同义词表），链表中的表项具有相同的散列函数值。 若出现了冲突，即一个表项的散列值所对应的地址已经被占据，则需把这个表项放到该桶的链尾或链首。,5.4 名字的作用范围,名字的声明和作用域 程序语言中的声明是把信息联系到名字（标识符）的一种语法结构。 编程语言中一般包括5类声明： 常量声明、变量声明、类型声明和过程/函数声明以及类声明 常量声明把值联解到名字 。 类型声明把名字绑定到新构造的类型或者为已经存在的名字创建一个别名。 变量声明通常把名字绑定到一个类型，同时还隐式地绑定了其它属性。 一个声明起作用的程序部分称为该声明的作用域。过程中出现的名字，如果是在该过程的一个声明的作用域内，就称为局部于该过程的；否则叫做非局部的。,先声明后使用是一条在大多数程序中普遍采用的规则，它要求一个名字的声明在程序的正文中在它的引用之前。 这条规则允许编译器一边分析程序一边建立符号表： 一旦在程序代码中遇到了名字引用才执行符号表的查找操作； 如果查找失败，就出现了违反先声明后使用的规则，编译器就能发出一个适当的错误消息。 所以，