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