1、编译原理与技术编译原理与技术第第6章章符号表的组织和管理符号表的组织和管理 编译原理与技术编译原理与技术2主要内容主要内容u符号表的作用符号表的作用 u符号表的主要属性及其作用符号表的主要属性及其作用 u符号表的组织结构符号表的组织结构 u名字的作用范围名字的作用范围编译原理与技术编译原理与技术36.1 符号表的作用符号表的作用 u登记符号属性值登记符号属性值在源程序的各个分析阶段，编译程序根据标在源程序的各个分析阶段，编译程序根据标识符的声明信息收集它属性的有关值，并把识符的声明信息收集它属性的有关值，并把它们存放在符合表中。它们存放在符合表中。每种语言规则定义了不同的符号属性；即使每种语言
2、规则定义了不同的符号属性；即使是同一个语言，不同的编译程序也可能会定是同一个语言，不同的编译程序也可能会定义并且收集不同的属性信息。义并且收集不同的属性信息。现代编程语言中一般包括常数声明、变量声现代编程语言中一般包括常数声明、变量声明、类型声明和过程明、类型声明和过程/函数声明等四类声明。函数声明等四类声明。对于每类声明，编译程序要收集、存储和应对于每类声明，编译程序要收集、存储和应用的属性完全不同。用的属性完全不同。编译原理与技术编译原理与技术46.1 符号表的作用符号表的作用例例6.1 C语言的变量声明语言的变量声明short int a;float b=0.0;把标识符把标识符a声明为
3、短整数型，把声明为短整数型，把b声明为浮点声明为浮点类型，而且初始化为类型，而且初始化为0。那么，编译程序对每。那么，编译程序对每个变量要记录它的类型，以便执行类型检查个变量要记录它的类型，以便执行类型检查和分配存储，比如短整型变量和分配存储，比如短整型变量i占占2个字节；个字节；要记录它在存储器中的位置（相对位移或绝要记录它在存储器中的位置（相对位移或绝对地址），以便目标程序运行时访问；若像对地址），以便目标程序运行时访问；若像b有初始值，则还需要记录这个初始值。有初始值，则还需要记录这个初始值。编译原理与技术编译原理与技术56.1 符号表的作用符号表的作用例例6.2 下面是计算阶乘下面是计
4、算阶乘n!的的C语言的函数声明：语言的函数声明：int factory(int n)int t;if(n=0)|n=1)t=1;else t=n factory(n1);return t;对于函数对于函数factory要记录的属性包括：函数的名称，各要记录的属性包括：函数的名称，各种变量如参数、返回值、局部变量及其类型，同时还种变量如参数、返回值、局部变量及其类型，同时还要记录函数的调用信息，以便在函数体执行完毕以后要记录函数的调用信息，以便在函数体执行完毕以后返回到调用点，特别是对这种允许递归调用的函数，返回到调用点，特别是对这种允许递归调用的函数，要为每次调用保留上面提到的所有信息。要为每
5、次调用保留上面提到的所有信息。编译原理与技术编译原理与技术66.1 符号表的作用符号表的作用u查找符号的属性查找符号的属性 符号表存放了源程序中的各种类型的信息，比如数值、符号表存放了源程序中的各种类型的信息，比如数值、变量类型、参数传递的地址等，在分析和翻译源程序变量类型、参数传递的地址等，在分析和翻译源程序的过程中会被不断地查询。的过程中会被不断地查询。例如，对于上述的变量声明，如果源程序有代码例如，对于上述的变量声明，如果源程序有代码a+b时，就需要查找、计算表达式中运算数的类型时，就需要查找、计算表达式中运算数的类型和值，以便计算出表达式。和值，以便计算出表达式。又如，在源程序中如果出
6、现了函数调用又如，在源程序中如果出现了函数调用factory(6)，编译程序就需要查找到编译程序就需要查找到factory的声明，找到实参的声明，找到实参6的的地址并传给形参地址并传给形参n，执行函数，执行函数factory的体，并返回值，的体，并返回值，等。等。编译原理与技术编译原理与技术76.1 符号表的作用符号表的作用u检查符号的合法性检查符号的合法性 1.例如，对于上述声明，代码例如，对于上述声明，代码 a=a+b，C语言的编语言的编译将检查变量译将检查变量a和和b的类型，把表达式的类型，把表达式a+b的结果转的结果转换成短整型，仅取整数部分进行赋值。换成短整型，仅取整数部分进行赋值。
7、2.在其它强类型语言，如在其它强类型语言，如Pascal和和Ada，表达式运算数，表达式运算数的类型必须一致，不能进行隐式类型转换，对于这的类型必须一致，不能进行隐式类型转换，对于这样的表达式样的表达式a+b，编译程序在语义分析的过程中将，编译程序在语义分析的过程中将发现并报告类型错误的信息。发现并报告类型错误的信息。3.又如，面向对象语言的继承性和多态性允许同一个又如，面向对象语言的继承性和多态性允许同一个消息在不同的环境中调用不同的方法（函数），即消息在不同的环境中调用不同的方法（函数），即调用同名但在不同的类中实现的方法。这就需要编调用同名但在不同的类中实现的方法。这就需要编译或者运行时
8、在方法的符号表中查询在参数、返回译或者运行时在方法的符号表中查询在参数、返回数以及方法方面名字一致的实现。数以及方法方面名字一致的实现。编译原理与技术编译原理与技术86.1 符号表的作用符号表的作用u作为目标代码生成阶段地址分配的依据作为目标代码生成阶段地址分配的依据 标识符由它定义的存储类型或它在程序中的位置来确定。标识符由它定义的存储类型或它在程序中的位置来确定。首先是要确定变量存储的区域。例如，在首先是要确定变量存储的区域。例如，在Java语言中，整数的语言中，整数的类型（以及所占用的字节）有类型（以及所占用的字节）有byte（1个字节）、个字节）、short（2个字个字节）、节）、in
9、t（4个字节）以及个字节）以及long（8个字节），而个字节），而float类型占类型占4个个字节，字节，double类型占类型占8个字节。又如，对寄存器变量，编译将尽个字节。又如，对寄存器变量，编译将尽可能地把它们保留在机器的寄存器当中，以提高运行速度；而可能地把它们保留在机器的寄存器当中，以提高运行速度；而对在一个文件中定义的外部变量，它们要在不同的源程序文件对在一个文件中定义的外部变量，它们要在不同的源程序文件之间访问，需要编译程序把它们放在所有源程序文件都可以方之间访问，需要编译程序把它们放在所有源程序文件都可以方便寻找到的存储器的位置。便寻找到的存储器的位置。其次，要根据标识符出现的
10、顺序，决定标识符在某个存储区域其次，要根据标识符出现的顺序，决定标识符在某个存储区域中的具体位置，而有关区域的标志及其相对位置都是作为该标中的具体位置，而有关区域的标志及其相对位置都是作为该标识符的语义信息存放在它的符号表中的。识符的语义信息存放在它的符号表中的。编译原理与技术编译原理与技术96.2 符号表的主要属性及其作用符号表的主要属性及其作用不同的符号类别包含了不同的属性，由于它不同的符号类别包含了不同的属性，由于它们的信息不同，也就导致了符号表的组织有们的信息不同，也就导致了符号表的组织有较大的差别。例如，数量类型的变量名字和较大的差别。例如，数量类型的变量名字和过程名字：过程名字：l
11、对于一个变量名要记录其类型（如整型、实型、对于一个变量名要记录其类型（如整型、实型、布尔型等）、占用的存储字节以及相对与某个基布尔型等）、占用的存储字节以及相对与某个基准位置的相对位置；准位置的相对位置；l对一个过程名要记录的属性包括参数的个数及其对一个过程名要记录的属性包括参数的个数及其类型，该过程是否有返回值，过程中的变量声明，类型，该过程是否有返回值，过程中的变量声明，甚至过程声明（如果像甚至过程声明（如果像Pascal语言允许嵌套过程语言允许嵌套过程声明）等信息。声明）等信息。编译原理与技术编译原理与技术106.2 符号表的主要属性及其作用符号表的主要属性及其作用符号名符号名符号种属符
12、号种属符号类型符号类型存储类别存储类别作用域作用域存储分配信息存储分配信息其它属性其它属性符号名符号名 l符号名可以是变量名、函数名（操作名）、类型名、类对象名等符号名可以是变量名、函数名（操作名）、类型名、类对象名等l每个符号名通常由若干个（非空）的字符组成的字符串来表达，在每个符号名通常由若干个（非空）的字符组成的字符串来表达，在语言中它们通常是一个变量、函数或对象的位移标志，因此在符号语言中它们通常是一个变量、函数或对象的位移标志，因此在符号表中的符号名作为表项的唯一区别一般是不允许重名的。表中的符号名作为表项的唯一区别一般是不允许重名的。l符号名与它在符号表中的位置建立起一一对应的关系
13、，这使得我们符号名与它在符号表中的位置建立起一一对应的关系，这使得我们可以用一个符号在表中的位置来代替该符号名、访问其信息。通常可以用一个符号在表中的位置来代替该符号名、访问其信息。通常把一个标识符在符号表中的位置值称为该标识符的内部代码。把一个标识符在符号表中的位置值称为该标识符的内部代码。l在经过分析处理的源程序中，标识符不再是一个字符串而是一个表在经过分析处理的源程序中，标识符不再是一个字符串而是一个表示内部码的整数值，这不但便于识别，而且也可以压缩存储和表达示内部码的整数值，这不但便于识别，而且也可以压缩存储和表达的长度。的长度。编译原理与技术编译原理与技术116.2 符号表的主要属性
14、及其作用符号表的主要属性及其作用 符号名符号名l语言中的符号名通常用标识符来表示。根据语言的定义，程序中出语言中的符号名通常用标识符来表示。根据语言的定义，程序中出现的重名标识符定义将按照该标识符在程序中的作用域和可视规则现的重名标识符定义将按照该标识符在程序中的作用域和可视规则进行相应的处理。而在程序的运行过程中，符号表中的符号名始终进行相应的处理。而在程序的运行过程中，符号表中的符号名始终是唯一的标志。是唯一的标志。l在一些允许操作重载、类继承的语言中，函数名、操作名允许重名，在一些允许操作重载、类继承的语言中，函数名、操作名允许重名，对于重载操作的标识符，它们可以通过参数的个数与类型以及
15、返回对于重载操作的标识符，它们可以通过参数的个数与类型以及返回值的类型来区别；而对于操作的继承，编译器可以构造继承图，同值的类型来区别；而对于操作的继承，编译器可以构造继承图，同时保存类结构，这样就可以为每个操作和属性找到唯一的定义。时保存类结构，这样就可以为每个操作和属性找到唯一的定义。l例如，对应不同的参数类型，可以定义几个求和重载函数：例如，对应不同的参数类型，可以定义几个求和重载函数：int sum(int a,int b)double sum(double a,double b)float sum（float a,float b,float c）l当某个函数中调用到重载函数时，编译器
16、根据实参的类型和个数去当某个函数中调用到重载函数时，编译器根据实参的类型和个数去调用相应的函数。调用相应的函数。编译原理与技术编译原理与技术126.2 符号表的主要属性及其作用符号表的主要属性及其作用符号种属符号种属 l由于语言中符号所拥有的属性可能不同，其组织就可以采用不同由于语言中符号所拥有的属性可能不同，其组织就可以采用不同的数据结构，可以用符号的种属来区别每个符号的基本划分。的数据结构，可以用符号的种属来区别每个符号的基本划分。l根据不同的语言，符号的种属可以包括：简单变量、结构型变量、根据不同的语言，符号的种属可以包括：简单变量、结构型变量、数组、过程、类型、类等。数组、过程、类型、
17、类等。l可以依据符号种属的划分来组织符号表，一种方式是为每个种属可以依据符号种属的划分来组织符号表，一种方式是为每个种属的标识符建立一张表，这样，可以对符号表类似地安排组织结构、的标识符建立一张表，这样，可以对符号表类似地安排组织结构、进行同样的操作；另外一种方式把所有种属的标识符统一安排在进行同样的操作；另外一种方式把所有种属的标识符统一安排在一张表中，根据符号的种属进行条件判断，对不同种属的特殊型一张表中，根据符号的种属进行条件判断，对不同种属的特殊型执行不同的存储安排和操作。执行不同的存储安排和操作。符号名符号名符号种属符号种属符号类型符号类型存储类别存储类别作用域作用域存储分配信息存储
18、分配信息其它属性其它属性编译原理与技术编译原理与技术136.2 符号表的主要属性及其作用符号表的主要属性及其作用符号类型符号类型 l现代程序语言中的一个重要构造就是数据类型（类型），它现代程序语言中的一个重要构造就是数据类型（类型），它是变量标识符的重要属性，函数的数据类型指的是该函数返是变量标识符的重要属性，函数的数据类型指的是该函数返回值的数据类型。回值的数据类型。l现代语言通常都有如下的基本类型：整型、实型、字符型、现代语言通常都有如下的基本类型：整型、实型、字符型、布尔型、逻辑型等；布尔型、逻辑型等；l符号的类型属性从源程序中该符号的定义中得到符号的类型属性从源程序中该符号的定义中得到
19、l变量符号的数据类型属性不但决定了该变量的数据在存储器变量符号的数据类型属性不但决定了该变量的数据在存储器中的存储格式，也规定了可以对该变量施加的操作运算。中的存储格式，也规定了可以对该变量施加的操作运算。符号名符号名符号种属符号种属符号类型符号类型存储类别存储类别作用域作用域存储分配信息存储分配信息其它属性其它属性编译原理与技术编译原理与技术146.2 符号表的主要属性及其作用符号表的主要属性及其作用符号类型符号类型 l目前的大多数语言都在基本类型的基础上定义复合数据类型，目前的大多数语言都在基本类型的基础上定义复合数据类型，如数组、集合和记录。如数组、集合和记录。l许多语言还允许程序员自己
20、定义数据类型。这些复合类型的许多语言还允许程序员自己定义数据类型。这些复合类型的基本元素可以是基本类型，也可以是复合类型。基本元素可以是基本类型，也可以是复合类型。l作为存储变量地址的指针类型所指向的变量可以是基本的数作为存储变量地址的指针类型所指向的变量可以是基本的数据类型，也可以是其它任何一种复合数据类型。据类型，也可以是其它任何一种复合数据类型。符号名符号名符号种属符号种属符号类型符号类型存储类别存储类别作用域作用域存储分配信息存储分配信息其它属性其它属性每一个变量的类型是符号表中标识符属性的重要信息。每一个变量的类型是符号表中标识符属性的重要信息。编译原理与技术编译原理与技术156.2
21、 符号表的主要属性及其作用符号表的主要属性及其作用存储类别存储类别 l大多数程序语言对变量的存储类别采用两种方式。大多数程序语言对变量的存储类别采用两种方式。l一种是用关键字指定，例如，在一种是用关键字指定，例如，在FORTRAN语言中用语言中用COMMON来来定义公共存储区域，允许不同程序段都可以访问这些数据；又如，定义公共存储区域，允许不同程序段都可以访问这些数据；又如，C和和C+语言规定语言规定static定义的变量属于文件的静态存储变量或属定义的变量属于文件的静态存储变量或属于函数内部的静态存储变量，这些变量在编译时分配存储空间，如于函数内部的静态存储变量，这些变量在编译时分配存储空间
22、，如果定义时没有初值，编译器还需要将它们初始化为果定义时没有初值，编译器还需要将它们初始化为0。l另一种方式是根据定义变量的声明在程序中的位置来决定。例如，另一种方式是根据定义变量的声明在程序中的位置来决定。例如，C+规定在一个文件中定义的变量缺省为外部的，即程序的公共存规定在一个文件中定义的变量缺省为外部的，即程序的公共存储变量；而在函数体内缺省存储类别关键字所定义的变量是内部变储变量；而在函数体内缺省存储类别关键字所定义的变量是内部变量，是属于该函数体所独有的私有存储变量，因而是动态地分配存量，是属于该函数体所独有的私有存储变量，因而是动态地分配存储空间。储空间。l区别符号存储类型地属性是
23、编译过程中语义处理、检查和存储分配区别符号存储类型地属性是编译过程中语义处理、检查和存储分配的重要依据。的重要依据。l符号的存储类别同时还决定了符号变量的作用域、可见性和它的生符号的存储类别同时还决定了符号变量的作用域、可见性和它的生命周期等性质命周期等性质。符号名符号名符号种属符号种属符号类型符号类型存储类别存储类别作用域作用域存储分配信息存储分配信息其它属性其它属性编译原理与技术编译原理与技术166.2 符号表的主要属性及其作用符号表的主要属性及其作用作用域作用域 l一个标识符在程序中起作用的范围称为其作用域一个标识符在程序中起作用的范围称为其作用域。l一般来说，定义一个符号的位置及存储类
24、型就决定了该符号一般来说，定义一个符号的位置及存储类型就决定了该符号的作用域，就是它可以出现的场合，可以在程序中作为参数、的作用域，就是它可以出现的场合，可以在程序中作为参数、表达式的运算数等被引用。表达式的运算数等被引用。lC语言中外部变量的作用域是整个程序，一个外部符号的定语言中外部变量的作用域是整个程序，一个外部符号的定义在整个策划能够许中只能出现一次，为了方便使用和编译，义在整个策划能够许中只能出现一次，为了方便使用和编译，同名标识符的其它说明可以多次出现。同名标识符的其它说明可以多次出现。lFORTRAN语言中的语言中的COMMON变量的作用域则不是整个程变量的作用域则不是整个程序，
25、而只能在定义这个序，而只能在定义这个COMMON块的函数或过程中引用。块的函数或过程中引用。l面向对象语言，如面向对象语言，如C+，的每个类都引入了一个独立的类域。，的每个类都引入了一个独立的类域。符号名符号名符号种属符号种属符号类型符号类型存储类别存储类别作用域作用域存储分配信息存储分配信息其它属性其它属性编译原理与技术编译原理与技术176.2 符号表的主要属性及其作用符号表的主要属性及其作用作用域与可见性作用域与可见性 l标识符的标识符的可见性可见性从另外一个角度说明其有效性，它与作用域从另外一个角度说明其有效性，它与作用域有一定一致性。有一定一致性。l标识符的作用域包含可见范围，但是，可
26、见范围不会超过作标识符的作用域包含可见范围，但是，可见范围不会超过作用域。用域。l可见性在理解同名是不是合法的作用域嵌套时十分直观。对可见性在理解同名是不是合法的作用域嵌套时十分直观。对于外层块域内层块定义的同名标识符，在外层作用域中，内于外层块域内层块定义的同名标识符，在外层作用域中，内层所定义的标识符时不可见的，即外层所引用的是外层所定层所定义的标识符时不可见的，即外层所引用的是外层所定义的标识符；义的标识符；l同样，在内层作用域中，外层的标识符将被内层的同名标识同样，在内层作用域中，外层的标识符将被内层的同名标识符所屏蔽，变得不可见，即外层中同名标识符的可见范围是符所屏蔽，变得不可见，即
27、外层中同名标识符的可见范围是作用域中挖去内层块的范围，在内存块形成了作用域中挖去内层块的范围，在内存块形成了作用域洞作用域洞。符号名符号名符号种属符号种属符号类型符号类型存储类别存储类别作用域作用域存储分配信息存储分配信息其它属性其它属性编译原理与技术编译原理与技术186.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的作用域的作用域in
28、t m和和n可见可见float m不可见不可见float m的作用域的作用域float m和和n可见可见int m不可见不可见符号名符号名符号种属符号种属符号类型符号类型存储类别存储类别作用域作用域存储分配信息存储分配信息其它属性其它属性编译原理与技术编译原理与技术19存储分配信息存储分配信息 l编译程序需要根据符号的存储类别定义以及它们在程序中出编译程序需要根据符号的存储类别定义以及它们在程序中出现的位置和顺序来确定每一个符号应该分配的存储区域及其现的位置和顺序来确定每一个符号应该分配的存储区域及其具体位置。具体位置。l通常情况下，编译为每个符号分配一个相对于某个基址的相通常情况下，编译为每
29、个符号分配一个相对于某个基址的相对位移，而不是绝对的内存地址。对位移，而不是绝对的内存地址。l编译程序中有关源程序的存储组织和分配的问题将在第编译程序中有关源程序的存储组织和分配的问题将在第7章章中详细讨论。中详细讨论。符号名符号名符号种属符号种属符号类型符号类型存储类别存储类别作用域作用域存储分配信息存储分配信息其它属性其它属性6.2 符号表的主要属性及其作用符号表的主要属性及其作用编译原理与技术编译原理与技术206.2 符号表的主要属性及其作用符号表的主要属性及其作用其它属性其它属性 1.数组内情向量数组内情向量 需要把描述数组属性的信息如数组类型、维数、需要把描述数组属性的信息如数组类型
30、、维数、每个维的上下界、数组元素的首地址等登录在符号表中，以便确每个维的上下界、数组元素的首地址等登录在符号表中，以便确定数组在存储器占用的空间和数组元素的确定，并且完成数组的定数组在存储器占用的空间和数组元素的确定，并且完成数组的翻译。翻译。2.记录结构型的成员信息记录结构型的成员信息 一个记录结构型的变量包含若干成员，每一个记录结构型的变量包含若干成员，每个成员的数据类型可以彼此不同，因此，一个记录结构型变量在个成员的数据类型可以彼此不同，因此，一个记录结构型变量在存储分配时所占空间的大小由其成员来确定，而且，对每个成员存储分配时所占空间的大小由其成员来确定，而且，对每个成员的访问还需要它
31、所属成员排列次序的属性信息。的访问还需要它所属成员排列次序的属性信息。3.函数或过程的形参函数或过程的形参 函数或过程的形参作为其局部变量，同时又是函数或过程的形参作为其局部变量，同时又是对外部调用的接口。每个函数或过程形参的个数、类型、排列顺对外部调用的接口。每个函数或过程形参的个数、类型、排列顺序都体现了调用函数或过程时的属性，它们都应该反映在符号表序都体现了调用函数或过程时的属性，它们都应该反映在符号表中，以便在过程调用的时候进行参数传递，并且执行语义检查中，以便在过程调用的时候进行参数传递，并且执行语义检查（如处理函数名的重载）。（如处理函数名的重载）。4.在面相对象语言中，还必须把一
32、个类或其超类所定义同名方法存在面相对象语言中，还必须把一个类或其超类所定义同名方法存放在一个方法表中，指向每个方法的实现操作，以便实现面相对放在一个方法表中，指向每个方法的实现操作，以便实现面相对象的继承性质。象的继承性质。符号名符号名符号种属符号种属符号类型符号类型存储类别存储类别作用域作用域存储分配信息存储分配信息其它属性其它属性编译原理与技术编译原理与技术216.3 符号表的组织结构符号表的组织结构符号表的整体组织结构符号表的整体组织结构1.符号名栏目也叫主栏，其内容是源程序中出现的标识符，它是区分每个表项符号名栏目也叫主栏，其内容是源程序中出现的标识符，它是区分每个表项的关键码。的关键
33、码。2.对于保留字、类型、函数，它们的名字（标识符）就是符号表的关键码；对于保留字、类型、函数，它们的名字（标识符）就是符号表的关键码；3.对于语言中的保留字，它们本身就是表项中的关键码；对于语言中的保留字，它们本身就是表项中的关键码；4.对于语言中操作符，如乘幂对于语言中操作符，如乘幂“*”、赋值号、赋值号“:=、+=”或者或者FORTRAN中的拼中的拼写操作写操作“.GT.”，其字符或字符串就作为该操作符表项的关键码。，其字符或字符串就作为该操作符表项的关键码。符号名信息栏属性值1属性值2属性值m表项1（入口1）表项2（入口2）表项n（入口n）编译原理与技术编译原理与技术226.3 符号表
34、的组织结构符号表的组织结构编译程序对符号表的总体组织可以有编译程序对符号表的总体组织可以有3种形式种形式假设有下列三种类型的符号及其属性：假设有下列三种类型的符号及其属性：第一类符号第一类符号符号种属符号种属名字名字类型类型值值地址地址 第二类符号第二类符号 符号种属符号种属名字名字字节数字节数第三类符号第三类符号符号种属符号种属名字名字值值嵌套数嵌套数地址地址编译原理与技术编译原理与技术236.3 符号表的组织结构符号表的组织结构u第一种（如图第一种（如图6.3所示）：所示）：根据符号类型进行分类，把属性完全相同的那些符号安排在一张表中根据符号类型进行分类，把属性完全相同的那些符号安排在一张
35、表中这样就构造出许多不同的符号表，每个表的信息栏目中属性个数和结构完全这样就构造出许多不同的符号表，每个表的信息栏目中属性个数和结构完全一样，而且每个表项的属性栏目都是等长、有效。这种单个符号表的管理和一样，而且每个表项的属性栏目都是等长、有效。这种单个符号表的管理和操作都比较方便，空间使用效率也高。操作都比较方便，空间使用效率也高。缺点是一个编译程序要同时管理若干个不同类型的符号表，符号表分得太散，缺点是一个编译程序要同时管理若干个不同类型的符号表，符号表分得太散，对不同类型符号表中的共同属性必须设置重复的管理机制，增加了符号表管对不同类型符号表中的共同属性必须设置重复的管理机制，增加了符号
36、表管理的工作量和复杂度。理的工作量和复杂度。符号表符号表1符号种属符号种属名字名字类型类型值值地址地址符号表符号表2符号种属符号种属名字名字字节数字节数符号表符号表3符号种属符号种属名字名字值值嵌套数嵌套数地址地址编译原理与技术编译原理与技术246.3 符号表的组织结构符号表的组织结构u第二种（如图第二种（如图6.4所示）：所示）：把语言中的所有符号都组织在一张符号表中。把语言中的所有符号都组织在一张符号表中。优点是总体管理符号表集中、单一，不同类型符号中的相同属性得优点是总体管理符号表集中、单一，不同类型符号中的相同属性得到了一致的管理和处理。到了一致的管理和处理。为了完整地存放所有属性就导
37、致每个表项所包含的属性个数不一样，为了完整地存放所有属性就导致每个表项所包含的属性个数不一样，出现不等长的表项，这就极大地提高了符号表管理和处理的复杂性。出现不等长的表项，这就极大地提高了符号表管理和处理的复杂性。为了保持表项等长，把所有符号的全部属性都作为符号表中信息栏为了保持表项等长，把所有符号的全部属性都作为符号表中信息栏目的属性，这样的组织有助于减低符号表的管理和处理的复杂性。目的属性，这样的组织有助于减低符号表的管理和处理的复杂性。但是对于不同类型的符号，可能增加了无用的属性空间，从而降低但是对于不同类型的符号，可能增加了无用的属性空间，从而降低编译程序的空间使用效率。例如，对于第二
38、类符号，单一组织的符编译程序的空间使用效率。例如，对于第二类符号，单一组织的符号表中就超过一般的属性不需要，极大地浪费存储空间。号表中就超过一般的属性不需要，极大地浪费存储空间。符号种属名字类型值字节数地址1地址2编译原理与技术编译原理与技术256.3 符号表的组织结构符号表的组织结构u第三种是前两种的折衷形式。第三种是前两种的折衷形式。根据属性的相似程度把符号表分成若干类型，每个类型组织成一张根据属性的相似程度把符号表分成若干类型，每个类型组织成一张表，每张表中记录的符号都有很多相同的属性。表，每张表中记录的符号都有很多相同的属性。这种组织方式在管理的复杂程度和空间的使用效率方面都取得了上这
39、种组织方式在管理的复杂程度和空间的使用效率方面都取得了上述两种组织的这种效果。述两种组织的这种效果。而且，可以根据目标系统的体系结构和编译程序设计者的经验，对而且，可以根据目标系统的体系结构和编译程序设计者的经验，对符号表的分类进行选择和调整。例如，可以将上面的类型一和类型符号表的分类进行选择和调整。例如，可以将上面的类型一和类型三的符号合成一张表，类型二构成一个单独的符号表。三的符号合成一张表，类型二构成一个单独的符号表。第一类和第三类共同的符号表第一类和第三类共同的符号表第二类符号的符号表第二类符号的符号表符号种属名字类型值嵌套数地址符号种属名字字节数编译原理与技术编译原理与技术266.3
40、 符号表的组织结构符号表的组织结构关键码域的组织关键码域的组织符号表的关键码域就是符号本身，它可以是语言的保留字、操作符，也可以是标识符，如变量名、常数名、函数名、类型名、类名等程序结构。语言文法的词法对各种符号都有严格的定义。语言文法的词法对各种符号都有严格的定义。保留字和操作符的名字一般是只有唯一的拼写方法，而且不能用当作其它用途的用户定义的标识符。标识符通常是以字母开头的、长度确定或不限长度的字母和数字组成的字符串。如果语言对标识符的长度有限制，可以让符号表中关键码域有标识符允许的最大长度以容纳语言的整个标识符单词。但是，如果语言对标识符的长度不加限制，或者为了避免最大标识符长度过大而浪
41、费存储空间，通常的做法是另外设立一个存放标识符单词的字符数组，在符号表的名字栏目中仅给出标识符单词在这个数组中的首地址和符号长度的二元组。这样，符号表的关键码域可以有一致的大小，而且，同时也可以节省存储空间。编译原理与技术编译原理与技术276.3 符号表的组织结构符号表的组织结构例例6.4 假定有标识符假定有标识符student、name、birthday、code、p，它们依次存放，它们依次存放在上述的标识符单词数组中，其间没有间隔标志，这样的符号表结构如图在上述的标识符单词数组中，其间没有间隔标志，这样的符号表结构如图6.6所示所示。tudentnamebirthdaycodeps符号名符
42、号名信息信息.编译原理与技术编译原理与技术286.3 符号表的组织结构符号表的组织结构u不等长域的组织不等长域的组织 上述对标识符不限长度的处理是组织符号名的一种间接方式，这种方式可以推广上述对标识符不限长度的处理是组织符号名的一种间接方式，这种方式可以推广到属性域不相等的情形。我们可以把一些共同属性直接记录在符号表的信息栏，到属性域不相等的情形。我们可以把一些共同属性直接记录在符号表的信息栏，把某些特殊的属性记录在其它地方，并且在符号表的信息栏中增设一个指针，指把某些特殊的属性记录在其它地方，并且在符号表的信息栏中增设一个指针，指向这个存放特殊属性值的位置。向这个存放特殊属性值的位置。例例6
43、.5 图图6.7示意了通过符号表访问内情向量的组织结构，符号表有两个数组示意了通过符号表访问内情向量的组织结构，符号表有两个数组array1和和array2，它们分别有，它们分别有n维和维和1维。维。符号名信息栏内情向量表类型.地址基址n上界1下界1array1数组.上界n下界narray2数组基址1上界1下界1.编译原理与技术编译原理与技术296.3 符号表的组织结构符号表的组织结构u符号表的操作符号表的操作对于给定符号，查询此名字是否在符号表中；对于给定符号，查询此名字是否在符号表中；对于给定符号，在符号表中访问它的属性信息；对于给定符号，在符号表中访问它的属性信息；对于给定符号，在符号表
44、中更新它的属性信息；对于给定符号，在符号表中更新它的属性信息；在符号表中插入一个新的符号及其相关信息；在符号表中插入一个新的符号及其相关信息；删除一个或一组无用的表项。删除一个或一组无用的表项。编译原理与技术编译原理与技术306.3 符号表的组织结构符号表的组织结构插入、查找、更新和删除的函数可以说明如下：插入、查找、更新和删除的函数可以说明如下：procedure insert(token.entry:Addess;type:Typekind);把入口是把入口是entry的符号的符号token的类型的类型type插入符号表。类似地也可插入符号表。类似地也可以插入其它信息，如变量的值，譬如以插
45、入其它信息，如变量的值，譬如procedure setvalue(variable.entry:Addess;value:Valuetype);对在符号表入口的变量对在符号表入口的变量variable设置值设置值value。function lookup(entry:Addess):Typekind;查找符号表中入口是查找符号表中入口是entry的标识符，返回它的类型。的标识符，返回它的类型。function getvalue(entry:Addess):Valuekind;得到符号表中入口是得到符号表中入口是entry的标识符的数值。的标识符的数值。function delete(entry
46、:Addess):Boolean;把入口是把入口是entry的表项从符号表中删除，如果成功则返回真值的表项从符号表中删除，如果成功则返回真值true，不成功则为假值，不成功则为假值false。编译原理与技术编译原理与技术316.3 符号表的组织结构符号表的组织结构u三种常见的符号表的结构：三种常见的符号表的结构：线性表、搜索树和散列表组织线性表、搜索树和散列表组织 线性表组织是按照符号被扫描到的先后顺序填写各个表项，可线性表组织是按照符号被扫描到的先后顺序填写各个表项，可以用一个多维数组或多个一维数组来存放符号的信息。以用一个多维数组或多个一维数组来存放符号的信息。线性表需要两个指针来方便管理
47、和操作：一个指针指向该符号线性表需要两个指针来方便管理和操作：一个指针指向该符号表的开始位置，另一个指针指向符号表的下一个可用位置。表的开始位置，另一个指针指向符号表的下一个可用位置。线性表是最基本的数据结构，可以方便、直接地实现上述的插线性表是最基本的数据结构，可以方便、直接地实现上述的插入、查找和删除三种基本操作，而且每种的操作时间都是符号入、查找和删除三种基本操作，而且每种的操作时间都是符号表大小的线性函数，对于有表大小的线性函数，对于有N个表项的符号表，个表项的符号表，这些操作的平这些操作的平均时间都是均时间都是N/2左右（算法时间复杂性为左右（算法时间复杂性为(N)）。由于线性表无需
48、附加空间，比较节省存储。如果编译器对处理由于线性表无需附加空间，比较节省存储。如果编译器对处理时间要求不高，或者符号个数不大（如关键字），符号表就可时间要求不高，或者符号个数不大（如关键字），符号表就可以采用线性表结构。以采用线性表结构。编译原理与技术编译原理与技术326.3 符号表的组织结构符号表的组织结构u搜索树结构搜索树结构搜索树可以在构造符号表的同时，按照符号名的字典顺序把表搜索树可以在构造符号表的同时，按照符号名的字典顺序把表项整理排列，提高符号表查找操作的速度。项整理排列，提高符号表查找操作的速度。这样就可以采用折半查找的方式，加快搜索的速度。这样就可以采用折半查找的方式，加快搜索
49、的速度。对于有对于有N个表项的符号表，每次查找最多只需要做个表项的符号表，每次查找最多只需要做logN次比较次比较（因此这种查找法也叫对数查找法）。（因此这种查找法也叫对数查找法）。但是，由于符号表在编译过程中是边填写边引用，动态地建立、但是，由于符号表在编译过程中是边填写边引用，动态地建立、更新以及删除表项，这样，每增加和删除一个表项都需要对符更新以及删除表项，这样，每增加和删除一个表项都需要对符号表进行重新排序，这同样浪费时间。号表进行重新排序，这同样浪费时间。因此，搜索树结构不适合用于构造符号表，除了需要额外的空因此，搜索树结构不适合用于构造符号表，除了需要额外的空间构造搜索树以外，整体
50、而言，它们实现这三类操作效率不是间构造搜索树以外，整体而言，它们实现这三类操作效率不是最优，而且删除操作的实现过于复杂。最优，而且删除操作的实现过于复杂。编译原理与技术编译原理与技术336.3 符号表的组织结构符号表的组织结构u符号表处理的关键问题符号表处理的关键问题散列组织统一了查询与插入操作技术，相对来说具有较高的时散列组织统一了查询与插入操作技术，相对来说具有较高的时空效率，为上述三种操作提供的时间基本上是常数。空效率，为上述三种操作提供的时间基本上是常数。特别是散列表结构符合编译过程边填写边引用符号表的特性，特别是散列表结构符合编译过程边填写边引用符号表的特性，是实现符号表的最佳数据结
