软件开发过程与项目管理综述课件.ppt
符号表管理技术,授课：胡静,2023/3/17,编译原理,2,目录,概述符号表的组织与内容非分程序结构语言的符号表组织分程序结构语言的符号表组织,2023/3/17,编译原理,3,符号表概述,符号表的作用：在编译过程中，编译程序用来记录源程序中各种名字的特性信息，所以也称为名字特性表名字：程序名、过程名、函数名、用户定义类型名、变量名、常量名、枚举值名、标号名等。特性信息：上述名字的种类、类型、维数、参数个数、数值及目标地址（存储单元地址）等。,2023/3/17,编译原理,4,建表和查表的必要性,源程序中变量要先声明，然后才能引用。用户通过声明语句，声明各种名字，并给出它们的类型、维数等信息，编译程序在处理这些声明语句时，应该将声明中的名字及其信息登录到符号表中，同时编译程序还要给变量分配存储单元，而存储单元地址也必须登录在符号表中。当编译程序编译到引用所声明的变量时(赋值或引用其值)，要进行语法语义正确性检查(类型是否符合要求)和生成相应的目标程序，这就需要查符号表以取得相关信息。,2023/3/17,编译原理,5,建表，分配存储,查表,2023/3/17,编译原理,6,符号表的操作:填表和查表,Procedure P()填表：当分析到程序中的说明或定义语句时，应将说明或定义的名字，以及与之有关的信息填入符号表中。查表:(1)填表前查表，检查在程序的同一作用域内名字是否重复定义；(2)检查名字的种类是否与说明一致;(3)对于强类型语言，要检查表达式中各变量的类型是否一致;(4)生成目标指令时，要取得所需要的地址。,2023/3/17,编译原理,7,符号表的内容,符号表的基本结构：“名字”域：存放名字，一般为标识符号串，也可以为指向标识符字符串的指针。“特性”域：可包含多个子域，表示标识符的有关信息：名字的种类:简单变量、函数、过程、数组、标号、参数等类型:如整型、浮点型、字符型、指针等性质:变量形参、值形参等值:常量名所代表的数值地址:变量所分配单元的首址或地址位移大小:所占的字节数作用域的嵌套层次:,2023/3/17,编译原理,8,符号表的内容,“特性”域：对于数组:维数、上下界值、计算下标变量地址所用的信息(数组信息向量)以及数组元素类型等。对于记录(结构、联合)：域的个数，每个域的域名、地址位移、类型等。对于过程或函数：形参个数、所在层次、函数返回值类型、局部变量所占空间大小等。对于指针：所指对象类型等。,2023/3/17,编译原理,9,符号表的组织方式,1.统一符号表：不论什么名字都填入统一格式的符号表中符号表表项应按信息量最大的名字设计，填表、查表比较方便，结构简单，但是浪费大量空间。2.对于不同种类的名字分别建立各种符号表节省空间，但是填表和查表不方便。3.折中办法：大部分共同信息组成统一格式的符号表，特殊信息另设附表，两者用指针连接。,2023/3/17,编译原理,10,2023/3/17,编译原理,11,非分程序结构语言的符号表组织,(1)非分程序结构语言:每个可独立进行编译的程序单元是一个不包含有子模块的单一模块，如FORTRAN语言。,2023/3/17,编译原理,12,非分程序结构语言的符号表组织,(2)标识符的作用域及基本处理办法:1.作用域:全局：子程序名，函数名和公共区名。局部：程序单元中定义的变量。2.符号表的组织:3.基本处理办法:子程序、函数名和公共区名填入全局符号表。在子程序(函数)声明部分读到标识符，造局部符号表。,2023/3/17,编译原理,13,非分程序结构语言的符号表组织,(2)标识符的作用域基本处理办法:3.基本处理办法:在语句部分读到标识符，查表：程序单元结束:释放该程序单元的局部符号表。程序编译完成:释放全部符号表。,2023/3/17,编译原理,14,符号表的组织方式,1.无序符号表：按扫描顺序建表，查表要逐项查找。查表操作的平均长度为(n+1)/22.有序符号表：符号表按照变量名进行字典式排序线性查表：(n+1)/2折半查表：3.散列符号表（Hash表）：符号表地址=Hash(标识符),2023/3/17,编译原理,15,数组,简单的实现方案：array每个符号一个入口查询时扫描整个数组，对每个名字都进行比较缺点：表格有确定的大小需要预先知道实体的个数,2023/3/17,编译原理,16,列表,动态的数据结构：list对表格中的一个入口，指定一个单元可以在编译过程中动态增长缺点：对大型的符号表来说，效率低下平均来说，需要扫描一般的列表,2023/3/17,编译原理,17,哈希表,高效的实现：hash table是列表的数组(buckets)使用哈希函数将符号名称映射到相应的bucket:hashfunc:string int好的哈希函数：在bucket之间平均的分配 hashfunc(“m”)=0,hashfunc(“foo”)=3,2023/3/17,编译原理,18,分程序结构语言的符号表组织,(1)分程序结构语言:模块内可嵌入子模块(2)标识符的作用域和基本处理方法作用域：标识符局部于所定义的模块(最小模块)模块中所定义的标识符作用域是定义该标识符的子程序,2023/3/17,编译原理,19,分程序结构语言的符号表组织,(2)标识符的作用域和基本处理方法作用域：标识符局部于所定义的模块(最小模块)过程或函数说明中定义的标识符(包括形参)其作用域为本过程体。,2023/3/17,编译原理,20,分程序结构语言的符号表组织,(2)标识符的作用域和基本处理方法作用域：标识符局部于所定义的模块(最小模块)循环语句中定义的标识符，其作用域为该循环语句。不能从循环体外转到循环体内。循环语句应看作一层,2023/3/17,编译原理,21,分程序结构语言的符号表组织,(2)标识符的作用域和基本处理方法基本处理办法：建查符号表均要遵循标识符的作用域规定进行。建表:不能重复，不能遗漏查表:按标识符作用域,2023/3/17,编译原理,22,分程序结构语言的符号表组织,(2)标识符的作用域和基本处理方法基本处理办法：在程序声明部分读到标识符时(声明性出现)，建表在语句中读到标识符(引用性出现)，查表,2023/3/17,编译原理,23,分程序结构语言的符号表组织,(2)标识符的作用域和基本处理方法基本处理办法：标准标识符的处理：主要是语言定义的一些标准过程和函数的名字，它们是标识符的子集。如：sin，cos，abs,2023/3/17,编译原理,24,栈式符号表结构,2023/3/17,编译原理,25,2023/3/17,编译原理,26,2023/3/17,编译原理,27,2023/3/17,编译原理,28,Example,2023/3/17,编译原理,29,Example,2023/3/17,编译原理,30,Catching Semantic Errors,2023/3/17,编译原理,31,Thanks for your time!Questions&Answers,
