符号表的组织与管理

1第六章符号表§6.1符号表的作用§6.2符号表的组织§6.3符号表的建立和查找2【学习目标】符号表作为编译系统的重要设施，贯穿于文法分析、检查和语义处理的编译全过程。本章目的使学生深刻全面地了解符号表的地位和作用；掌握符号表的组织和管理方法；以及编译过程中符号表的操作活动过程。3【学习指南】在编译程序中符号表用来存放源程序中出现的有关名字的属性信息，这些信息集中反映了名字的语义特征属性。符号表在编译全过程的地位和作用非常重要，是进行上下文合法性检查和语义处理及代码生成的依据。符号表总体结构的设计和实现是与源语言的复杂性（包括词法结构、语法结构的复杂性）有关，还与对于编译系统在时间效率和空间效率方面的要求有关。4【难重点】符号表总体组织的选择原则。变量的类型和存储类别等属性的重要性。采用单表结构时,如何解决分程序构造中同名名字声明的可视性规则。采用分表结构适合哪种语言的编译系统。5§6.1符号表的作用在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息，这些信息集中反映了标识符的语义特征属性。1.在词法分析及语法在分析过程中不断积累和更新表中的信息；2.在词法分析到代码生成的各阶段，按各自的需要从表中获取不同的属性信息。3.不论编译策略是否分趟，符号表的作用和地位是完全一致的。6根据编译程序工作阶段的不同划分，名字表中的各种信息将在编译程序工作过程中的适当时候填入。对于在词法分析阶段就建立符号表的编译程序，当扫描源程序识别出一个单词(名字)时，就以此名字查找符号表；若表中无此名的登记项，就将此名字填入符号表中；至于与此名相关的其它信息，可视工作方便分别在语法分析、语义分析及中间代码生成等阶段陆续填入。在语义分析时，符号表中的信息可以用于语义检查；在代码优化时，编译程序则利用符号表提供的信息选出恰当的代码进行优化；而目标代码生成时，编译程序将依据符号表中的符号名来分配目标地址。7几乎在编译程序工作的全过程中，都需要对符号表进行频繁地访问(查表或填表)，其耗费的时间在整个编译过程中占有很大的比例。因此，合理地组织符号表并相应选择好的查、填表方法是提高编译程序工作效率的有效办法。8符号表的作用1.收集符号属性2.上下文语义的合法性检查的依据3.作为目标代码生成阶段地址分配的依据9作用一：收集符号属性编译程序扫描说明部分收集有关标识符的属性，并在符号表中建立符号的相应属性信息。例如，编译程序分析到下述两个说明语句intx,y[5];floatw;则在符号表中收集到关于符号x的属性是一个整型变量，y是一个具有10个元素的整型数组，关于符号w的属性是浮点型简单变量。10作用二：上下文语义的合法性检查的依据同一个标识符可能在程序的不同地方出现，而有关该符号的属性是在这些不同情况下收集的。特别是在多趟编译及程序分段编译（在PASCAL及C中以文件为单位）的情况下，更需检查标识符属性在上下文中的一致性和合法性。通过符号表中属性记录可进行相应上下文的语义检查。11例如，在一个C语言程序中出现intA[2][3];//定义整型数组AfloatA[4][5];//定义实型数组A,重定义冲突intA[2][3];//定义整型数组A,重定义冲突编译过程首先在符号表中记录了标识符A的属性是2×3个整型元素的数组；而后在分析第二、第三这两个定义说明时编译系统可通过符号表检查出标识符A的二次重定义冲突错误。本例还可以看到不论在后二句中A的其它属性与前一句是否完全相同，只要标识符名重定义，就将产生重定义冲突的语义错误。12作用三：目标代码生成阶段地址分配的依据每个符号变量在目标代码生成时需要确定其在存储分配的位置（主要是相对位置）。语言程序中的符号变量由它被定义的存储类别（如在C、FORTRAN语言中）或被定义的位置（如分程序结构的位置）来确定。首先要确定其被分配的区域。例如，在C语言中首先要确定该符号变量是分配在公共区（extern）、文件静态区（externstatic）、函数静态区（函数中static）、还是函数运行时的动态区（auto）等。其次是根据变量出现的次序，决定该变量在某个区中所处的具体位置，这通常使用在该区域中相对区头的相对位置确定。而有关区域的标志及相对位置都是作为该变量的语义信息被收集在该变量的符号表属性中。13符号的主要属性及作用1.符号名变量名、函数名、过程名等，重载信息2.符号类型int、float等，函数的类型看返回值3.符号的存储类型Common、Static、Auto、Regist4.符号的作用域及可视性Public、Private等5.符号变量的存储分配信息静态存储区、动态存储区6.符号的其他属性数组内情向量、结构成员信息、函数及过程的形参141、符号名语言中的一个标识符可以是一个变量的名字、一个函数的名字或一个过程的名字。每个标识符通常由若干个字符（非空格字符）组成的字符串来表达。符号表中设置一个符号名域，存放该标识符，该域通常就是符号表的关键字域。15通常在语言程序中标识符字符串是一个变量、函数或过程的唯一标志，因此在符号表中符号名作为表项之间的唯一区别一般不允许重名。从而该符号名与它在符号表中的位置建立起一一对应之关系，使得我们可以用一个符号在表中的位置（通常是一个整数）来替换该符号名。通常把一个标识符在符号表中的位置的整数值称之谓该标识符的内部代码。在经过分析处理的语言程序中标识符不再是一个字符串而是一个整数值，这不但便于识别比较而且缩短了表达的长度。16根据语言的定义，程序中出现的重名标识符定义将按照该标识符在程序中的作用域和可视性规则进行相应的处理。而在符号表运行过程中，表中的标识符名始终是唯一的标志。在一些允许操作重载(operatoroverload)的语言中，函数名、过程名是可以重名的，对于这类重载的标识符要通过它们的参数个数和类型以及函数返回值类型来区别，以达到它们在符号表中的唯一性。172、符号的类型标识符中除过程标识符之外函数和变量标识符都具有数据类型（datatype）属性。对于函数的数据类型指的是该函数值的数据类型。基本数据类型有整型、实型、字符型、逻辑型（布尔型）及位组型等，符号的类型属性是在语言程序中该符号的定义中得到。变量符号的类型属性决定了该变量的数据在存储空间的存储格式，还决定了在该变量上可以施加的运算操作。18随着程序设计语言的发展，语言中变量的类型也得到了扩充，目前大多数语言已定义了在基本数据类型基础上扩充的复合数据类型。复合数据类型有数组类型、记录结构类型等，它们都是由基本数据类型组合而成的。数组或记录结构中的每个基本元素可以是基本数据类型，也可以是其它任何一种组合式数据类型，构成嵌套式数据类型定义。作为存储变量地址的指针类型所指向的变量同样可以是基本数据类型，也可以是其它任何一种组合式数据类型。定义一个变量的基本数据类型或它的组合类型都是符号表中表示标识符属性的重要信息。符号表中设置一个符号类型域，存放该符号的类型。对复合数据类型，通常还需要设置该类型的扩展成分，以存放复合类型的完整的类型属性。193、符号的存储类别大多数语言对变量的存储类别定义采用二种方式。一种是用关键字指定。例如在C语言中用static定义是属于文件的静态存储变量或属于函数内部的静态存储变量，用register定义使用寄存器存储的变量。一种方式是根据定义变量说明在程序中的位置来决定。例如在C语言中，在函数体外缺省存储类关键字所定义的变量是外部变量，即程序的公共存储变量，而在函数体内缺省存储类关键字所定义的变量是内部变量，即属于该函数所独有的私有存储变量（通常是动态分配的存储变量）。20符号表中设置一个符号存储类别域，存放该符号的存储类别。区别符号存储类型的属性是编译过程语义处理、检查和存储分配的重要依据。符号的存储类别还决定了符号变量的作用域、可视性和它的生命周期等问题。214、符号的作用域及可视性一个符号变量在程序中起作用的范围，称谓它的作用域。一般来说，定义该符号的位置及存储类关键字决定了该符号的作用域。C语言中一个外部变量的作用域是整个程序，因此一个外部变量符号的定义在整个程序中只能出现一次，同名变量的说明可以出现多次那是为了使用和编译的方便。在函数外说明的定义的静态变量的作用域是定义该静态变量的文件，而在函数内部定义的静态变量其作用域仅仅是该变量定义所在的函数或过程中。与局部量不同的是，这些内部静态量在其作用域之外，仍然保持存在。一般来说一个变量的作用域就是该变量可以出现的场合，也就是说在某个变量作用域范围内该变量是可引用的，这就是变量可视性的作用域规则。22其它两种情况影响到一个变量的可视性⑴函数的形式参数：inta；//外部定义的整型变量aintfunc(floata,intb)//函数内部定义的局部整型变量a,//屏蔽了外部定义的整型变量a{……a…//引用的是函数内部定义(此处是形参)的局部整型变量a…::a…//引用inta…}23⑵分程序（或复合语句）结构：…{inta；//第一层头,定义的局部整型变量a…{chara；//第二层头,定义的局部字符型变量a…{//第三层头…{floata；//第四层头,定义的局部实型变量a…}//第四层尾…a…//引用第二层定义的局部字符型变量a}//第三层尾}//第二层尾}//第一层尾第三层所引用的a，不是第四层的floata；不是第一层inta；而是第二层chara；也就可以说从第三层向外，看到的第一个定义a的变量定义即chara。24怎么确立符号的作用域和可视性？为确立符号的作用域和可视性。符号表属性中除了需要符号的存储类别之外还需要表示该符号在程序结构上被定义的层次。符号表中设置一个表达符号所在层次的属性域，存放该符号的定义层次。无论是作为函数形参的定义也好或作为分程序中的局部定义也好，都可统一地用定义层次来区分。一般来说，若把外部变量视为0层的话，则函数内部作为第1层，依次向内嵌套定义的分程序分别为2，3，…层。在C语言程序中函数之间是并列定义的，因此每个函数内部都定义为第一层，而函数内的分程序也可以是并列定义的，对于并列定义的分程序当然具有相同的层次号。255、符号变量的存储分配信息根据符号变量的存储类别定义及它们出现的位置和次序来确定每一个变量应分配的存储区及在该区中的具体位置，用相对区头的位移量表示。通常有两类存储区，即静态存储区和动态存储区；①静态存储区该存储区单元经定义分配后成为静态单元，即在整个语言程序运行过程中是不可改变的。②动态存储区根据变量的局部定义和分程序结构，编译程序设置动态存储区来适应这些局部变量的生存和消亡。局部即在该定义范围之外此变量已经没存在的必要。动态变量的生存期是定义该变量的局部范围。266、符号的其它属性①数组内情向量编译程序处理数组说明的主要工作是，把描述数组属性信息的内情向量登录到符号表中。内情向量包括数组类型，维数，各维的上、下界及数组首地址，这些属性信息是确定存储分配时数组所占空间的大小和数组元素位置的依据。②记录结构型的成员信息一个记录结构型的变量，在存储分配时所占空间大小要由它的全体组成成员来确定，另外对于记录结构型变量还需要有它所属成员排列次序的属性信息。这二种信息用来确定结构型变量存储分配时所占空间的尺寸及确定该结构成员的位置。③函数及过程的形参函数和过程的形参作为该函数或过程的局部变量，但它又是该函数或过程对外的接口。每个函数或过程的形参个数、形参的排列次序及每个形参的类型，都体现了调用该函数或过程时的属性，它们都应该反映在符号表的函数或过程标识符的项中。有关函数及过程的形参属性信息用来作调用过程的匹配处理和语义检查。27对于编译程序所用的符号表来说，它所涉及的基本操作大致可以归纳为1.往表中填入一个新标识符；2.对给定的标识符：①查找它是否已在表中。②访问它的有关信息；③往表中填入或更新它在表中的某些信息；3.从表中删去一个或一组无用的项。28§6.2符号表的组织语言中不同种类的符号，它们的属性信息种类不完全相同，而不同的程度也是不一样的，如语