07第7章-符号表管理技术

第7章符号表管理技术2019/9/201内容提要符号表的作用符号表的建立与访问符号表的内容与组织符号表上的操作非块程序结构语言的符号表结构块程序结构语言的符号表结构2019/9/202符号表是编译程序中的一个重要数据结构，用来保存各类标识符的属性信息；编译的各个阶段都可能用到与符号相关的各种信息，这些信息用一些表格进行记录、存储和管理，如常量表、数组信息表等等，这些表统称为符号表；编译的分析阶段收集和更新符号表信息，综合阶段从符号表获取信息。7.1符号表的作用2019/9/203符号表的作用∶(1)登记符号属性值在源程序的各个分析阶段，编译程序根据标识符的声明信息收集其有关的属性值并存放在符号表中。每种语言规则定义了不同的符号属性；即使是同一个语言，不同的编译程序也可能会定义并且收集不同的属性信息。现代编程语言中一般包括常数声明、变量声明、类型声明和过程/函数声明等四类声明。对于每类声明，编译程序要收集、存储和应用的属性完全不同。2019/9/204例：C语言的变量声明shortinta;floatb=0.0;编译程序对每个变量要记录其类型，以便执行类型检查和存储分配；比如短整型变量a占2个字节，要记录它在存储器中的位置（相对位移或绝对地址）；若像b有初始值，则还需要记录该初始值。2019/9/205(2)查找符号属性符号表存放源程序中的各种类型的信息，比如数值、变量类型、参数传递的地址等，在分析和翻译源程序的过程中会被不断地查询。例：对声明语句：shortinta=9;shortintb=10;如果源程序有代码a+b时，需要查找、计算表达式中运算数的类型和值，以便计算出表达式。2019/9/206(3)检查符号的合法性A、检查类型是否一致例：对声明语句：shortinta;floatb=0.0;有代码a=b+b，C语言的编译将检查变量a和b的类型，把表达式b+b的结果转换成短整型，仅取整数部分进行赋值。强类型语言(如Pascal和Ada)的表达式运算数的类型必须一致2019/9/207B、检查变量重复定义例：C语言程序中出现…inti[3][5];//定义整型数组i…floati[4][2];//定义实型数组i,重定义冲突…inti[3][5];//定义整型数组i,重定义冲突…编译程序首先在符号表中记录了标识符i的属性是3×5个整型元素的数组，而后在分析第二、第三这两个定义说明时，编译程序可通过符号表检查出标识符i的重定义冲突错误。不论在后二句中i的其它属性与前一句是否完全相同，只要标识符名重定义，就将产生标识符重定义的语义错误。2019/9/208(4)作为目标代码生成阶段地址分配的依据由标识符定义的存储类型或它在程序中的位置来确定。首先确定变量存储的区域。例如，在Java语言中，整数类型有byte（1个字节）、short（2个字节）、int（4个字节）以及long（8个字节），而float类型占4个字节，double类型占8个字节。其次根据标识符的出现顺序，决定标识符在某个存储区域中的具体位置，而有关区域的标志及其相对位置都作为该标识符的语义信息存放在其符号表中。2019/9/209创建时间：词法分析时和语义分析时1、词法分析时创建：当词法分析程序识别出一个标识符时，以该标识符名查找符号表；若表中无此标识符的登记项，将此标识符填入符号表；与标识符相关的其它信息，可视工作方便分别语义分析及中间代码生成等阶段陆续填入。语义分析程序进行语义正确性分析，遇到声明语句填入有关标识符的属性。在符号表中记录的标识符属性信息会在代码生成阶段用于产生目标代码的指令序列。7.2符号表的建立与访问2019/9/20102、语义分析时创建：词法分析只输出标识符符号，而标识符名字作为标识符符号的属性输出，在语义分析阶段根据标识符的属性创建符号表记录，并同时填入其它的属性信息。小结：如果在词法分析阶段创建符号表，只能在符号表中将标识符的名字填入符号表，而其他属性则要在语义分析和代码生成阶段填入。如果在语义分析阶段创建符号表，那么与符号表打交道就仅局限于语义分析和代码生成。2019/9/2011符号表的访问效率是制定符号表管理方案时重点考虑的因素，一个高效的管理方案应该使符号表具有快速查找、快速删除、易于使用、易于维护等特点。符号表的内容和组织方式影响其访问效率符号表具体包含哪些内容，属性的种类，一定程度上取决于程序设计语言的性质。符号表的组织方式要根据内存和存取速度的限制做相应的调整。7.3符号表的组织和内容2019/9/2012符号表的内容：符号表是由一些表项组成的二维表格每个表项可分为两部分：名字域：存放符号名字；属性域：记录与该名字相对应的各种属性2019/9/20132019/9/2014名字目标地址类型维数声明行引用行指针Computer02129,4,57X1410312,140FORM83246符号表示例①变量名②目标地址③类型④维数或过程的参数数目⑤变量声明的源程序行号⑥变量引用的源程序行号⑦以字母顺序列表的链域名字：符号表中设置一个符号名域，存放该标识符，该域通常作为符号表的关键字。名字在符号表创建时填入，需要解决标识符长度可变问题，根据标识符定长与否，采用两种存储方法：①定长存贮方法：规定标识符名字域宽度，标识符按左对齐方式存放。特点：简单、存取速度快；缺点：空间利用率低，标识符长度不能超过名字域宽度。②集中存贮方法：开辟一个存放所有标识符的缓冲区，而在标识符名字域中只存放标识符在缓冲区中的偏移地址。特点：存贮效率高，标识符无长度限制；缺点：存取效率低。根据保存标识符长度方法不同有三种方案：2019/9/20152019/9/2016314名字属性符号表表项1符号表表项2......abcimain...符号表表项3(a)标识符长度放在符号表中2019/9/2017名字属性符号表表项1符号表表项2......3bcimain...符号表表项3a14(b)标识符长度放在字符串中2019/9/2018名字属性符号表表项1符号表表项2......ac\0\0ain\0...符号表表项3bim(c)用’\0’表示标识符的结束目标地址：当声明一个变量时为该变量分配内存地址，并将其分配的地址填入符号表中。当该变量在程序的其它地方被引用时，可以从符号表中查询该地址，并填入存取该变量值的目标代码中。内存分配可采用静态分配和动态分配。如果标识符是函数名，则地址是该函数开始地址；如果是数组名，则应为数组模板的起始地址。2019/9/2019类型：函数和变量标识符都具有数据类型属性。函数标识符的数据类型指该函数返回值的数据类型。变量标识符的类型属性：（1）决定该变量的数据占用的存储空间大小（2）决定在该变量上可以施加的运算操作（类型检查）。2019/9/2020维数及参数个数：数组引用时，其维数应当与数组声明中所定义的维数一致；维数用于计算数组元素地址。函数调用时，实参个数必须与形参个数一致，在符号表组织中把参数个数看成维数。2019/9/2021交叉引用表：包含前面已经讨论过的许多属性，加上声明该变量或首次引用该变量的语句行号以及所有引用该变量的语句行号。链域：便于产生按字母顺序排序的变量交叉引用表。如果编译程序不产生交叉引用表，则符号表中的链域以及语句的行号属性都可从表中删去。2019/9/2022符号表的组织方式有三种：①属性相同的符号组织在一起：空间效率高，但表多，难管理②所有符号组织在一张表中：只有一张表，管理集中统一，但管理复杂，空间开销大③根据属性相似程度分类组织成若干张表，每张表中记录的符号都有比较多的相同属性从编译系统构造符号表的过程来划分，符号表可分为静态表和动态表：静态表：在编译前经构造好的符号表，如保留字表、标准函数名表等。动态表：在编译过程中根据需要构造的符号表，如变量表、数组信息表、过程信息表等2019/9/20237.4符号表上的操作在整个编译期间，对于符号表的操作大致可归纳为五类：•对给定名字，查询名字是否已在表中；•往表中填入一个新的名字；•对给定名字，访问其某些信息；•对给定名字，填写或更新其某些信息；•删除一个或一组无用的项。上述五个方面只是一些基本的共同操作。符号表上的操作主要有插入和查找，根据声明方式不同而不同。2019/9/20241、强类型语言:所有变量都必须显式说明。(1)遇到变量声明时，先查找符号表以确定是否重复声明，若是则产生错误信息，否则插入符号表。有序表：先找位置再插入无序表：添加表尾(2)遇到变量引用时，查找符号表，若查到则将查到的信息用于语义检查和代码生成，否则报告错误（变量未声明）2019/9/20252、弱类型语言:允许对变量做隐式说明。每遇到变量出现时需要插入和查询；任一变量引用都处理成首次引用，先查符号表，如查到则直接获取变量的全部属性，否则进行插入操作，而且需要从上下文中推测出隐式变量的全部属性。例：程序中首次出现a=5和x=3.14时，可根据常量5和3.14确定为a为整型变量、x为实型变量。2019/9/2026非块程序结构语言：指用该语言编写的每一个可独立编译的程序是一个不包含子块的单一模块程序，该模块中声明的所有变量是属于整个模块的。非块程序结构语言的符号表组织方式主要采用①无序表②有序表③散列表。7.4非块程序结构语言的符号表结构2019/9/2027①无序表：规定符号表中表项按符号被扫描到的先后顺序填入。例：程序中符号的出现情况如下：……………a……//a第一次出现…b……//b第一次出现……a…//a第二次出现…d……//d第一次出现……c…//c第一次出现…b……//b第二次出现……其中h为表头，p为表尾优点：结构简单、节省空间，插入、查找操作简单、易于实现。缺点：查找效率低。对于含有N项的符号表，查找某个符号，平均要做N/2次比较。2019/9/2028②有序表：对每一个符号排序组织的符号表，在符号表中的表项按其符号的字符代码串（可以看成一个整数值）值的大小从大到小（或从小到大）排列的。编译扫描次序是a，b，d，c。由于c代码小于d代码，因此c应在d表项之前。排序表的表项建立及符号查找，通常采用二分法。例：程序中符号的出现情况如下：……………a……//a第一次出现…b……//b第一次出现……a…//a第二次出现…d……//d第一次出现……c…//c第一次出现…b……//b第二次出现……其中h为表头，p为表尾2019/9/2029名字类型维数mint0mainkeyword0nint5namechar0xreal0例：给出编译下面程序的有序符号表。main(){intm,n[5];realx;charname;}2019/9/2030③散列符号表：散列符号表不仅可以提高查找操作的效率，同时也可以提高插入操作的效率，所以在许多实际编译器的符号表实现中均采用了散列技术散列符号表又称哈希(hash)符号表，其关键在于哈希函数，将程序中出现的符号通过哈希函数进行映射，得到的函数值作为该符号在表中的位置。2019/9/2031散列函数(哈希函数)具有如下性质：1）函数值只依赖于对应的符号。2）函数的计算简单且高效。3）函数值能比较均匀地分布在一定范围内。散列函数：除法散列函数、乘法散列函数、多项式除法散列函数、平方取中散列函数等等。冲突处理办法：顺序法、倍数法和链表法。2019/9/2032例：用“质数除余法”构造散列符号表。1）根据各符号名中的字符确定正整数h2）将整数h除以符号表长度N，然后取其余数，该余数作为符号的散列位置。如果N是质数，散列的效果较好，即冲突较少。3）冲突处理：链接法。现有5个符号C1、C2、C3、C4、C5，分别转换成正整数为87、55、319、273和214，符号表长度是5，利用质数除余法得到的散列地址为：2、0、4、3、4符号正整数H/5C1872C2550C33194C42733C52144位置名字域属性域0C212C13C44C3