编译原理与技术讲义 第6章 符号表的组织和管理

1、编译原理与技术第6章符号表的组织和管理 青岛大学信息工程学院主要内容符号表的作用 符号表的主要属性及其作用 符号表的组织结构 名字的作用范围编译原理与技术26.1 符号表的作用 登记符号属性值在源程序的各个分析阶段，编译程序根据标识符的声明信息收集它属性的有关值，并把它们存放在符合表中。每种语言规则定义了不同的符号属性；即使是同一个语言，不同的编译程序也可能会定义并且收集不同的属性信息。现代编程语言中一般包括常数声明、变量声明、类型声明和过程/函数声明等四类声明。对于每类声明，编译程序要收集、存储和应用的属性完全不同。 编译原理与技术36.1 符号表的作用例6.1 C语言的变量声明short

2、int a;float b = 0.0;把标识符a声明为短整数型，把b声明为浮点类型，而且初始化为0。那么，编译程序对每个变量要记录它的类型，以便执行类型检查和分配存储，比如短整型变量i占2个字节；要记录它在存储器中的位置（相对位移或绝对地址），以便目标程序运行时访问；若像b有初始值，则还需要记录这个初始值。 编译原理与技术46.1 符号表的作用例6.2 下面是计算阶乘n!的C语言的函数声明：int factory ( int n) int t;if (n = = 0) | | n = = 1) t = 1;else t = n factory (n1); return t;对于函数facto

3、ry要记录的属性包括：函数的名称，各种变量如参数、返回值、局部变量及其类型，同时还要记录函数的调用信息，以便在函数体执行完毕以后返回到调用点，特别是对这种允许递归调用的函数，要为每次调用保留上面提到的所有信息。 编译原理与技术56.1 符号表的作用查找符号的属性 符号表存放了源程序中的各种类型的信息，比如数值、变量类型、参数传递的地址等，在分析和翻译源程序的过程中会被不断地查询。例如，对于上述的变量声明，如果源程序有代码a + b时，就需要查找、计算表达式中运算数的类型和值，以便计算出表达式。又如，在源程序中如果出现了函数调用factory (6)，编译程序就需要查找到factory的声明，找

4、到实参6的地址并传给形参n，执行函数factory的体，并返回值，等。编译原理与技术66.1 符号表的作用检查符号的合法性 例如，对于上述声明，代码 a = a + b，C语言的编译将检查变量a和b的类型，把表达式a + b的结果转换成短整型，仅取整数部分进行赋值。在其它强类型语言，如Pascal和Ada，表达式运算数的类型必须一致，不能进行隐式类型转换，对于这样的表达式a + b，编译程序在语义分析的过程中将发现并报告类型错误的信息。又如，面向对象语言的继承性和多态性允许同一个消息在不同的环境中调用不同的方法（函数），即调用同名但在不同的类中实现的方法。这就需要编译或者运行时在方法的符号表中

5、查询在参数、返回数以及方法方面名字一致的实现。编译原理与技术76.1 符号表的作用作为目标代码生成阶段地址分配的依据 标识符由它定义的存储类型或它在程序中的位置来确定。首先是要确定变量存储的区域。例如，在Java语言中，整数的类型（以及所占用的字节）有byte（1个字节）、short（2个字节）、int（4个字节）以及long（8个字节），而float类型占4个字节，double类型占8个字节。又如，对寄存器变量，编译将尽可能地把它们保留在机器的寄存器当中，以提高运行速度；而对在一个文件中定义的外部变量，它们要在不同的源程序文件之间访问，需要编译程序把它们放在所有源程序文件都可以方便寻找到的存

6、储器的位置。其次，要根据标识符出现的顺序，决定标识符在某个存储区域中的具体位置，而有关区域的标志及其相对位置都是作为该标识符的语义信息存放在它的符号表中的。编译原理与技术86.2 符号表的主要属性及其作用不同的符号类别包含了不同的属性，由于它们的信息不同，也就导致了符号表的组织有较大的差别。例如，数量类型的变量名字和过程名字：对于一个变量名要记录其类型（如整型、实型、布尔型等）、占用的存储字节以及相对与某个基准位置的相对位置；对一个过程名要记录的属性包括参数的个数及其类型，该过程是否有返回值，过程中的变量声明，甚至过程声明（如果像Pascal语言允许嵌套过程声明）等信息。 编译原理与技术96.

7、2 符号表的主要属性及其作用符号名符号种属符号类型存储类别作用域存储分配信息其它属性符号名 符号名可以是变量名、函数名（操作名）、类型名、类对象名等每个符号名通常由若干个（非空）的字符组成的字符串来表达，在语言中它们通常是一个变量、函数或对象的位移标志，因此在符号表中的符号名作为表项的唯一区别一般是不允许重名的。符号名与它在符号表中的位置建立起一一对应的关系，这使得我们可以用一个符号在表中的位置来代替该符号名、访问其信息。通常把一个标识符在符号表中的位置值称为该标识符的内部代码。在经过分析处理的源程序中，标识符不再是一个字符串而是一个表示内部码的整数值，这不但便于识别，而且也可以压缩存储和表达

8、的长度。 编译原理与技术106.2 符号表的主要属性及其作用 符号名语言中的符号名通常用标识符来表示。根据语言的定义，程序中出现的重名标识符定义将按照该标识符在程序中的作用域和可视规则进行相应的处理。而在程序的运行过程中，符号表中的符号名始终是唯一的标志。在一些允许操作重载、类继承的语言中，函数名、操作名允许重名，对于重载操作的标识符，它们可以通过参数的个数与类型以及返回值的类型来区别；而对于操作的继承，编译器可以构造继承图，同时保存类结构，这样就可以为每个操作和属性找到唯一的定义。例如，对应不同的参数类型，可以定义几个求和重载函数：int sum ( int a, int b) double

9、 sum ( double a, double b)float sum（float a, float b, float c）当某个函数中调用到重载函数时，编译器根据实参的类型和个数去调用相应的函数。编译原理与技术116.2 符号表的主要属性及其作用符号种属 由于语言中符号所拥有的属性可能不同，其组织就可以采用不同的数据结构，可以用符号的种属来区别每个符号的基本划分。根据不同的语言，符号的种属可以包括：简单变量、结构型变量、数组、过程、类型、类等。可以依据符号种属的划分来组织符号表，一种方式是为每个种属的标识符建立一张表，这样，可以对符号表类似地安排组织结构、进行同样的操作；另外一种方式把所有种

10、属的标识符统一安排在一张表中，根据符号的种属进行条件判断，对不同种属的特殊型执行不同的存储安排和操作。符号名符号种属符号类型存储类别作用域存储分配信息其它属性编译原理与技术126.2 符号表的主要属性及其作用符号类型 现代程序语言中的一个重要构造就是数据类型（类型），它是变量标识符的重要属性，函数的数据类型指的是该函数返回值的数据类型。现代语言通常都有如下的基本类型：整型、实型、字符型、布尔型、逻辑型等；符号的类型属性从源程序中该符号的定义中得到变量符号的数据类型属性不但决定了该变量的数据在存储器中的存储格式，也规定了可以对该变量施加的操作运算。符号名符号种属符号类型存储类别作用域存储分配信息

11、其它属性编译原理与技术136.2 符号表的主要属性及其作用符号类型 目前的大多数语言都在基本类型的基础上定义复合数据类型，如数组、集合和记录。许多语言还允许程序员自己定义数据类型。这些复合类型的基本元素可以是基本类型，也可以是复合类型。作为存储变量地址的指针类型所指向的变量可以是基本的数据类型，也可以是其它任何一种复合数据类型。符号名符号种属符号类型存储类别作用域存储分配信息其它属性每一个变量的类型是符号表中标识符属性的重要信息。 编译原理与技术146.2 符号表的主要属性及其作用存储类别 大多数程序语言对变量的存储类别采用两种方式。一种是用关键字指定，例如，在FORTRAN语言中用COMMO

12、N来定义公共存储区域，允许不同程序段都可以访问这些数据；又如，C和C+语言规定static定义的变量属于文件的静态存储变量或属于函数内部的静态存储变量，这些变量在编译时分配存储空间，如果定义时没有初值，编译器还需要将它们初始化为0。另一种方式是根据定义变量的声明在程序中的位置来决定。例如，C+规定在一个文件中定义的变量缺省为外部的，即程序的公共存储变量；而在函数体内缺省存储类别关键字所定义的变量是内部变量，是属于该函数体所独有的私有存储变量，因而是动态地分配存储空间。区别符号存储类型地属性是编译过程中语义处理、检查和存储分配的重要依据。符号的存储类别同时还决定了符号变量的作用域、可见性和它的生

13、命周期等性质 。符号名符号种属符号类型存储类别作用域存储分配信息其它属性编译原理与技术156.2 符号表的主要属性及其作用作用域 一个标识符在程序中起作用的范围称为其作用域。一般来说，定义一个符号的位置及存储类型就决定了该符号的作用域，就是它可以出现的场合，可以在程序中作为参数、表达式的运算数等被引用。C语言中外部变量的作用域是整个程序，一个外部符号的定义在整个策划能够许中只能出现一次，为了方便使用和编译，同名标识符的其它说明可以多次出现。FORTRAN语言中的COMMON变量的作用域则不是整个程序，而只能在定义这个COMMON块的函数或过程中引用。面向对象语言，如C+，的每个类都引入了一个独

14、立的类域。 符号名符号种属符号类型存储类别作用域存储分配信息其它属性编译原理与技术166.2 符号表的主要属性及其作用作用域与可见性 标识符的可见性从另外一个角度说明其有效性，它与作用域有一定一致性。标识符的作用域包含可见范围，但是，可见范围不会超过作用域。可见性在理解同名是不是合法的作用域嵌套时十分直观。对于外层块域内层块定义的同名标识符，在外层作用域中，内层所定义的标识符时不可见的，即外层所引用的是外层所定义的标识符；同样，在内层作用域中，外层的标识符将被内层的同名标识符所屏蔽，变得不可见，即外层中同名标识符的可见范围是作用域中挖去内层块的范围，在内存块形成了作用域洞 。符号名符号种属符号

15、类型存储类别作用域存储分配信息其它属性编译原理与技术176.2 符号表的主要属性及其作用例6.3 图6.1（b）显示了下列程序段中变量的作用域与可见性，其中int m的作用域在括号中不可见，即这个程序块在int m的作用域中挖了一个洞。 int m = 1;float n; float m = 3.14; n = 5.5; m+;int m和float n的作用域int m和n可见float m不可见float m的作用域float m和n可见int m不可见符号名符号种属符号类型存储类别作用域存储分配信息其它属性编译原理与技术18存储分配信息 编译程序需要根据符号的存储类别定义以及它们在程序

16、中出现的位置和顺序来确定每一个符号应该分配的存储区域及其具体位置。通常情况下，编译为每个符号分配一个相对于某个基址的相对位移，而不是绝对的内存地址。编译程序中有关源程序的存储组织和分配的问题将在第7章中详细讨论。符号名符号种属符号类型存储类别作用域存储分配信息其它属性6.2 符号表的主要属性及其作用编译原理与技术196.2 符号表的主要属性及其作用其它属性 数组内情向量 需要把描述数组属性的信息如数组类型、维数、每个维的上下界、数组元素的首地址等登录在符号表中，以便确定数组在存储器占用的空间和数组元素的确定，并且完成数组的翻译。记录结构型的成员信息 一个记录结构型的变量包含若干成员，每个成员的

17、数据类型可以彼此不同，因此，一个记录结构型变量在存储分配时所占空间的大小由其成员来确定，而且，对每个成员的访问还需要它所属成员排列次序的属性信息。函数或过程的形参 函数或过程的形参作为其局部变量，同时又是对外部调用的接口。每个函数或过程形参的个数、类型、排列顺序都体现了调用函数或过程时的属性，它们都应该反映在符号表中，以便在过程调用的时候进行参数传递，并且执行语义检查（如处理函数名的重载）。在面相对象语言中，还必须把一个类或其超类所定义同名方法存放在一个方法表中，指向每个方法的实现操作，以便实现面相对象的继承性质。 符号名符号种属符号类型存储类别作用域存储分配信息其它属性编译原理与技术206.

18、3 符号表的组织结构符号表的整体组织结构符号名栏目也叫主栏，其内容是源程序中出现的标识符，它是区分每个表项的关键码。对于保留字、类型、函数，它们的名字（标识符）就是符号表的关键码；对于语言中的保留字，它们本身就是表项中的关键码；对于语言中操作符，如乘幂“*”、赋值号“:=、+=”或者FORTRAN中的拼写操作“.GT.”，其字符或字符串就作为该操作符表项的关键码。 符号名信息栏属性值1属性值2属性值m表项1（入口1）表项2（入口2）表项n（入口n）编译原理与技术216.3 符号表的组织结构编译程序对符号表的总体组织可以有3种形式假设有下列三种类型的符号及其属性： 第一类符号符号种属名字类型值地

19、址 第二类符号 符号种属名字字节数第三类符号符号种属名字值嵌套数地址编译原理与技术226.3 符号表的组织结构第一种（如图6.3所示）：根据符号类型进行分类，把属性完全相同的那些符号安排在一张表中这样就构造出许多不同的符号表，每个表的信息栏目中属性个数和结构完全一样，而且每个表项的属性栏目都是等长、有效。这种单个符号表的管理和操作都比较方便，空间使用效率也高。缺点是一个编译程序要同时管理若干个不同类型的符号表，符号表分得太散，对不同类型符号表中的共同属性必须设置重复的管理机制，增加了符号表管理的工作量和复杂度。 符号表1符号种属名字类型值地址符号表2符号种属名字字节数符号表3符号种属名字值嵌套

20、数地址编译原理与技术236.3 符号表的组织结构第二种（如图6.4所示）：把语言中的所有符号都组织在一张符号表中。优点是总体管理符号表集中、单一，不同类型符号中的相同属性得到了一致的管理和处理。为了完整地存放所有属性就导致每个表项所包含的属性个数不一样，出现不等长的表项，这就极大地提高了符号表管理和处理的复杂性。为了保持表项等长，把所有符号的全部属性都作为符号表中信息栏目的属性，这样的组织有助于减低符号表的管理和处理的复杂性。但是对于不同类型的符号，可能增加了无用的属性空间，从而降低编译程序的空间使用效率。例如，对于第二类符号，单一组织的符号表中就超过一般的属性不需要，极大地浪费存储空间。 符

21、号种属名字类型值字节数地址1地址2编译原理与技术246.3 符号表的组织结构第三种是前两种的折衷形式。根据属性的相似程度把符号表分成若干类型，每个类型组织成一张表，每张表中记录的符号都有很多相同的属性。这种组织方式在管理的复杂程度和空间的使用效率方面都取得了上述两种组织的这种效果。而且，可以根据目标系统的体系结构和编译程序设计者的经验，对符号表的分类进行选择和调整。例如，可以将上面的类型一和类型三的符号合成一张表，类型二构成一个单独的符号表。第一类和第三类共同的符号表第二类符号的符号表符号种属名字类型值嵌套数地址符号种属名字字节数编译原理与技术256.3 符号表的组织结构关键码域的组织符号表的

22、关键码域就是符号本身，它可以是语言的保留字、操作符，也可以是标识符，如变量名、常数名、函数名、类型名、类名等程序结构。语言文法的词法对各种符号都有严格的定义。保留字和操作符的名字一般是只有唯一的拼写方法，而且不能用当作其它用途的用户定义的标识符。标识符通常是以字母开头的、长度确定或不限长度的字母和数字组成的字符串。如果语言对标识符的长度有限制，可以让符号表中关键码域有标识符允许的最大长度以容纳语言的整个标识符单词。 但是，如果语言对标识符的长度不加限制，或者为了避免最大标识符长度过大而浪费存储空间，通常的做法是另外设立一个存放标识符单词的字符数组，在符号表的名字栏目中仅给出标识符单词在这个数组

23、中的首地址和符号长度的二元组。这样，符号表的关键码域可以有一致的大小，而且，同时也可以节省存储空间。 编译原理与技术266.3 符号表的组织结构例6.4 假定有标识符student、name、birthday、code、p，它们依次存放在上述的标识符单词数组中，其间没有间隔标志，这样的符号表结构如图6.6所示 。tudentnamebirthdaycodeps符号名信息.编译原理与技术276.3 符号表的组织结构不等长域的组织 上述对标识符不限长度的处理是组织符号名的一种间接方式，这种方式可以推广到属性域不相等的情形。我们可以把一些共同属性直接记录在符号表的信息栏，把某些特殊的属性记录在其它地

24、方，并且在符号表的信息栏中增设一个指针，指向这个存放特殊属性值的位置。例6.5 图6.7示意了通过符号表访问内情向量的组织结构，符号表有两个数组array1和array2，它们分别有n维和1维。 符号名信息栏内情向量表类型.地址基址n上界1下界1array1数组.上界n下界narray2数组基址1上界1下界1.编译原理与技术286.3 符号表的组织结构符号表的操作对于给定符号，查询此名字是否在符号表中；对于给定符号，在符号表中访问它的属性信息；对于给定符号，在符号表中更新它的属性信息；在符号表中插入一个新的符号及其相关信息；删除一个或一组无用的表项。编译原理与技术296.3 符号表的组织结构插

25、入、查找、更新和删除的函数可以说明如下：procedure insert (token.entry: Addess; type: Typekind);把入口是entry的符号token的类型type插入符号表。类似地也可以插入其它信息，如变量的值，譬如procedure setvalue (variable.entry: Addess; value: Valuetype);对在符号表入口的变量variable设置值value。function lookup (entry: Addess): Typekind;查找符号表中入口是entry的标识符，返回它的类型。function getvalue

26、 (entry: Addess): Valuekind;得到符号表中入口是entry的标识符的数值。function delete (entry: Addess): Boolean;把入口是entry的表项从符号表中删除，如果成功则返回真值true，不成功则为假值false。编译原理与技术306.3 符号表的组织结构三种常见的符号表的结构：线性表、搜索树和散列表组织 线性表组织是按照符号被扫描到的先后顺序填写各个表项，可以用一个多维数组或多个一维数组来存放符号的信息。线性表需要两个指针来方便管理和操作：一个指针指向该符号表的开始位置，另一个指针指向符号表的下一个可用位置。线性表是最基本的数据结

27、构，可以方便、直接地实现上述的插入、查找和删除三种基本操作，而且每种的操作时间都是符号表大小的线性函数，对于有N个表项的符号表，这些操作的平均时间都是N/2左右（算法时间复杂性为(N)）。由于线性表无需附加空间，比较节省存储。如果编译器对处理时间要求不高，或者符号个数不大（如关键字），符号表就可以采用线性表结构。编译原理与技术316.3 符号表的组织结构搜索树结构搜索树可以在构造符号表的同时，按照符号名的字典顺序把表项整理排列，提高符号表查找操作的速度。这样就可以采用折半查找的方式，加快搜索的速度。对于有N个表项的符号表，每次查找最多只需要做logN次比较（因此这种查找法也叫对数查找法）。但是

28、，由于符号表在编译过程中是边填写边引用，动态地建立、更新以及删除表项，这样，每增加和删除一个表项都需要对符号表进行重新排序，这同样浪费时间。因此，搜索树结构不适合用于构造符号表，除了需要额外的空间构造搜索树以外，整体而言，它们实现这三类操作效率不是最优，而且删除操作的实现过于复杂。 编译原理与技术326.3 符号表的组织结构符号表处理的关键问题散列组织统一了查询与插入操作技术，相对来说具有较高的时空效率，为上述三种操作提供的时间基本上是常数。特别是散列表结构符合编译过程边填写边引用符号表的特性，是实现符号表的最佳数据结构，在实践中的使用最多。 线性表结构填表快，查询慢；搜索树结构查询快，填表慢

29、。如何保证查询与插入表项这两个基本操作的都能高效地完成。编译原理与技术336.3 符号表的组织结构散列方法散列方法在表项的存储位置与它的关键码之间建立一个确定的对应函数关系（哈希函数，杂凑函数，hash），使每个关键码symbol与散列结构（散列表，哈希表，杂凑表）中的唯一的存储位置相对应，即hash(symbol)。在搜索时，首先对表项的关键码用哈希函数计算出对应的表项的存储位置，在散列表中按此位置取出表项进行比较，若关键码相等，则搜索成功。在填入表项时，依同样函数计算存储位置，并按此位置存放表项。由于使用这种方法进行搜索时不必多次比较关键码，因此搜速速度比较快，可以到达逼近具有此关键码的表

30、项的实际存放地址。编译原理与技术346.3 符号表的组织结构对哈希函数的基本要求计算简单、高效；函数值能均匀地分布在1和N之间，对不同的关键码都返回一个代表存储位置的不同值。构造哈希函数的算法有许多，例如，若取N为素数，就可以定义哈希函数为symbol/N的余数，其中symbol是某个符号的代码。由于语言中的标识符可以相互区别，它们的代码值都是不同的。 编译原理与技术356.3 符号表的组织结构散列冲突的解决不同的关键码经过杂凑运算以后，有可能得到相同的杂凑值，这种现象称为散列冲突。一种常用的方法是链地址法。把有N个地址的散列表改为N个桶，桶号与散列地址一一对应，第i（1iN）个桶号即为第i个

31、散列地址，每个桶则是一个线性链表（称为同义词表），链表中的表项具有相同的散列函数值。若出现了冲突，即一个表项的散列值所对应的地址已经被占据，则需把这个表项放到该桶的链尾或链首。 编译原理与技术366.3 符号表的组织结构.addr.HashTable1hn名字.sym1sym2.symSymbolTablea2addra3属性1.属性j.属性m.hash()链表指针.nulla2.a3.next.如何在符号表中使用散列表技术 对于每个符号表增加一个地址链项（初始化为null）；建立一个散列表（桶），它是一个含n个符号表入口地址的一维数组，每个散列表的表项初始化为null，表示散列函数值所对应的

32、符号表的表项没有占用。对符号表的操作实际上就是通过散列函数间接地操作符号表。 编译原理与技术376.3 符号表的组织结构通过散列函数间接地操作符号表 符号表中填入一个新的sym符号（1）首先对于符号sym用散列函数hash在散列表HashTable中查找出它在符号表SymbolTable中的位置h：hash(sym)返回的值在1n之间，令指针ptr := HashTableh；否则p := hull。（2）如果ptr 为null，则把sym的信息填在SymbolTableptr所对应的一个符号表的表项中。 如果ptr不是null，则表示出现了冲突： 首先在符号表中得到下一个新的可用的项（地址用

33、next表示）， 接着在散列表中把同义词表的表头改为next， 然后填写这个新得到符号表的表项内容：把链表指针由null改成SymbolTableptr的链表指针，填写sym的其它属性值。 编译原理与技术386.4 名字的作用范围 名字的声明和作用域 程序语言中的声明是把信息联系到名字（标识符）的一种语法结构。编程语言中一般包括5类声明：常量声明、变量声明、类型声明和过程/函数声明以及类声明常量声明把值联解到名字 。类型声明把名字绑定到新构造的类型或者为已经存在的名字创建一个别名。 变量声明通常把名字绑定到一个类型，同时还隐式地绑定了其它属性。一个声明起作用的程序部分称为该声明的作用域。过程中

34、出现的名字，如果是在该过程的一个声明的作用域内，就称为局部于该过程的；否则叫做非局部的。 编译原理与技术396.4 名字的作用范围先声明后使用是一条在大多数程序中普遍采用的规则，它要求一个名字的声明在程序的正文中在它的引用之前。这条规则允许编译器一边分析程序一边建立符号表：一旦在程序代码中遇到了名字引用才执行符号表的查找操作；如果查找失败，就出现了违反先声明后使用的规则，编译器就能发出一个适当的错误消息。所以，这条规则允许一遍扫描的编译构造。编译原理与技术406.4 名字的作用范围块结构与符号表的分层次管理 块结构是现代程序语言的普通构造，它是程序中可以包含声明的任何程序构造。在Pascal语言中，主程序和过程/函数声明是块结构；C语言中，函数声明以及花括号内的复合语句表示块结构。Java语言中的包package把一组相关的类封装在一起，也构成块结构。 作用域服从最近嵌套规则（1）程序块B中声明的作用域包括b自身；（2）如果名字x没有在B中声明，那么，B中x的出现是在外围程序块B的x声明的作用域中，而且B比其它任何含x声明的程序块在程序正文中