编译原理第九章-符号表.ppt

第9章 符号表,数计学院宋彩芳,9 符号表,符号表的作用和地位符号的主要属性及作用符号表的组织符号表的管理,符号表的作用和地位,符号表用来存放语言程序中出现的有关标识符的属性信息，这些信息集中反映了标识符的语义特征属性；在词法分析及语法分析过程中不断积累和更新表中的信息。在词法分析到代码生成的各个阶段，按各自需要从表中获取不同的属性信息。,符号表的作用和地位,符号表的功能有：收集符号属性；int i35;上下文语义的合法性检查的依据；extern float i;/类型不一致float i42;/重定义作为目标代码生成阶段地址分配的依据；extern 公共区extern static 文件静态区static 函数静态区auto 动态区,9 符号表,符号表的作用和地位符号的主要属性及作用符号表的组织符号表的管理,符号的主要属性及作用,语言符号可分为：关键字（保留字）符号操作符符号标识符符号语言中标识符可以是变量名、函数名、过程名；过程没有返回值,如同C的void 函数则有,如同C的带返回值函数,标识符符号的属性(信息）,几种通常都是需要的。1 符号名 2 符号的类型 3 符号的存储类别 4 符号的作用域及可视性 5 符号变量的存储分配信息 6 符号的其它属性 数组内情向量 记录结构型的成员信息 函数及过程的形参,标识符符号的属性(信息）,一、符号名符号名与它在符号表中的位置一一对应；标识符的内部代码也即标识符在符号表中的位置（通常是一个整数）可以替换符号名；符号表运行过程中，表中的标识符名始终是唯一标志；特殊情形：重名标识符定义：根据标识符在程序中的作用域和可视性规则进行处理。表中标识符名始终唯一；操作重载：通过它们的参数个数和类型，以及函数返回值类型来区别。以达到标识符的唯一；,标识符符号的属性(信息）,二、符号的类型除过程标识符之外的函数和变量标识符都具有数据类型；函数的数据类型指该函数值的数据类型；变量符号的类型属性决定了其存储方式和可施加的运算操作；数据类型：基本数据类型：整型、实型、字符型、逻辑型（布尔型）、位组型（字节型）；复合数据类型：数组、记录结构；,标识符符号的属性(信息）,三、符号的存储类别由关键字指定；用static定义属于文件的静态存储变量或属于函数内部的静态存储变量用regist定义使用寄存器存储的变量；由变量在程序中位置决定；函数外是程序的公共存储变量函数内是内部变量；存储类别作用：编译过程语义处理、检查和存储分配的重要依据；决定了符号变量的作用域、可视性和它的生命周期；,标识符符号的属性(信息）,四、符号的作用域及可视性：作用域：符号变量在程序中起作用的范围；如C语言中声明为extern的外部变量，其作用域是整个程序；在函数外声明的静态变量的作用域是定义该静态变变量的文件；函数内声明的静态变量作用域是定义该变量的函数；,标识符符号的属性(信息）,影响变量可视性的情况：函数的形式参数；int a;int fun(float a,float b)a/引用float a改变可见性作用域操作符:int a;int fun(float a,float b)a/引用float a:a/引用int a,标识符符号的属性(信息）,影响变量可视性的情况：复合语句分程序结构；int a;char a;float a;a/引用char a,标识符符号的属性(信息）,为确立符号的作用域和可视性，符号表属性除了需要符号的存储类别之外还需要表示该符号在程序结构上被定义的层次；,标识符符号的属性(信息）,五、符号变量的存储分配信息：根据符号变量的存储类别定义及它们出现的位置和次序来确定每个变量应分配的存储区及在该区的具体位置；存储区静态存储区：生命周期是程序运行的全过程；公共静态区：如extern定义的外部变量；局部静态区：如static定义的静态变量；函数外表示文件可视性，函数内表示所在函数可视；动态存储区：生命周期是定义该变量的局部范围；,标识符符号的属性(信息）,具体位置：按该变量在存储区类分别依出现先后的次序排列下相对该存储区表头的相对位移量来表示的；Int a;.float b;Struct cc int d;float e;c;,标识符符号的属性(信息）,符号的其他属性：数组内情向量数组类型、维数、各维上下界、数组首地址；记录结构型的成员信息全体成员确定其存储分配；成员排列次序的属性信息；函数及过程的形参形参个数、形参的排列次序及每个形参的类型；,9 符号表,符号表的作用和地位符号的主要属性及作用符号表的组织符号表的管理,符号表的组织,符号表的总体组织不同种类符号，其属性信息种类不完全相同；不同程度但有有所不同；符号表项的排列关键字域的组织其他域的组织,符号表的组织,符号表的组织,第一种：按属性种类完全相同的那些符号组织在一起；,符号表的组织,第一种：按属性种类完全相同的那些符号组织在一起；优点：每个符号表存放符号的属性个数和结构完全相同；表项等长，且表项每个属性栏都有效；对单个符号表来说，管理方便一直，空间效率高；缺点：同时管理多个符号表，增加了总体管理的工作量和复杂度；,符号表的总体组织,把所有语言中的符号都组织在一张符号表中；,符号表的总体组织,把所有语言中的符号都组织在一张符号表中；优点：总体管理非常集中单一，且不同种类符号的共同属性可以一致地管理和处理；缺点：增加了符号表管理的复杂度；增加无用的属性空间，从而增加了空间开销；,符号表的总体组织,根据符号属性相似程度分类组织若干张表；,符号表的总体组织,根据符号属性相似程度分类组织若干张表；折中的组织方式在管理复杂性及时空效率方面都取得折中的效果。对复杂性和效率的取舍可由设计者根据自己的经验和要求及目标系统的客观环境和需求进行选择和调整；,属性3栏与属性4栏冗余，可将其合并；增加了符号表管理和运行的复杂性，但减少了空间开销；,符号表的总体组织,符号表的总体组织,总结：为便于符号表的组织管理，每张符号表的表长通常为定长是合理的；每张符号表可以看作是一个多元组，每个元组由若干属性组成，元组之间有相同的成员个数和一致的排列；元组之间的区分由表项中“符号”一栏区分；,符号表的组织,符号表的总体组织符号表项的排列关键字域的组织其他域的组织,符号表项的排列,符号表作为一个多元组，表中元组的排列组织是构造符号表的重要成分。在编译程序的整个工作过程中，符号表被频繁地用来建立表项，查找表项，填充和引用表项的属性。在编译程序中，符号表项的组织传统上采用三种构造方法。即线性法，二分法及散列法。,符号表项的排列,线性组织符号表中表项按它的符号被扫描的先后顺序登录；管理简单但运行效率低；,.a.b.a.d.c.b.,符号表项的排列,排列组织及二分法符号表中表项按其符号的字符代码串的值的大小排列；排序表的空间组织和存储开销与线性表相同，但运行效率高于线性表，算法复杂性也高于线性表；,.a.b.a.d.c.b.,符号表项的排列,散列组织对符号进行某种函数操作（杂凑函数）所得的函数值确定它在符号表的位置；Vhash=fhash（符号代码值）改进：Lhash=mod（Vhash，N）,.a.b.a.d.c.b.,符号表项的排列,散列组织需事项注意：散列冲突，解决方法是多次散列方法；散列函数的选择：静态符号表动态符号表对符号代码的位操作作为杂凑函数，如符号代码的字段叠加或加权叠加以及符号代码的对折或多对折等位操作；,符号表的组织,符号表的总体组织符号表项的排列关键字域的组织其他域的组织,关键字域的组织,有关符号的基础知识保留字操作符标识符外部名（前6个字符可以惟一地区分）内部名（前31个字符可以惟一地区分）可见，标识符的内部规则是符号表关键字组织的基础和依据；,关键字域的组织,等长关键字域（段）符号表 设置关键字段为标识符的最大长度；,关键字域的组织,不等长关键字段符号表采用关键字池的索引结构。,符号表的组织,符号表的总体组织符号表项的排列关键字域的组织其他域的组织,其他域的组织,等长属性值域组织符号表中符号的属性值具有相同类型且等长；不等长属性域组织符号表中符号的属性值具有相同类型但长度不同；下推链域的组织,等长属性值域组织,可以取相应的数据类型表达属性值符号布尔性质的属性域defined 1(true)表示已定义defined 0(false)表示未定义表示符号的基本数据类型Data-type 3个bit位（整型值）Char 0 0 0(0)short 0 0 1(1)int 0 1 0(2)long 0 1 1(3)unsigned 1 0 0(4)float 1 0 1(5)double 1 1 0(6),等长属性值域组织,可以取相应的数据类型表达属性值符号变量：存储类别数据类型一样的构造方式存储位移整型量表示相对位移量,等长属性值域组织,可以取相应的数据类型表达属性值符号之间关系的属性可用指针或指针链来构造；如：函数和形参关系func1(para1,para2,para3)func2(),等长属性值域组织,可以取相应的数据类型表达属性值结构struct tag1 memb1 memb2 struct tag2 memb3 memb4 memb5 memb6 memb7 stv;,不等长属性值域组织,另设空间存放属性值数组的内情向量array1(subscrip1,subscrip2)array2(subscrip3,subscrip4,subscrip5,subscrip6),不等长属性值域组织,另设空间存放属性值C语言中数组特别的含义int abc342;,不等长属性值域组织,另设空间存放属性值结构struct tag1 memb1 memb2 struct tag2 memb3 memb4 memb5 memb6 memb7 stv;,不等长属性值域组织,复合属性域的组织存在若干个可用位表示的信息该符号变量是否初始化该符号是否是结构成员该符号是否是标号该符号是否是保留字,下推链域的组织,实现同名标识符的语义功能,9 符号表,符号表的作用和地位符号的主要属性及作用符号表的组织符号表的管理,符号表的管理,符号表的作用反映了符号表的行为：符号表的初始化符号的登录符号的查找符号表中分程序结构层次的管理,符号表的初始化,符号表的表长是渐增变化的情况线性组织和二分法组织符号表的表长是确定的情况散列组织的符号表,符号的登录,不同组织方式导致不同的登录方式线性方法：图9.21二分方法：图9.22散列表：通过杂凑算法决定登录表项的位置；登入的内容：名字登入名字属性：取决于编译程序获得某个符号时编译所处的程序扫描点的状态；,符号的登录,符号a的属性func(x,y)struct tag int anm;t;,类型属性存储类别属性作用域属性存储分配属性数组内情向量属性,符号的查找,目的：建立和确认该符号的属性；步骤：先在保留字表和运算符表中查找；再在标识符表中查找；查找算法与该符号表的组织方式密切相关；线性表：顺序查找二分表：折半查找杂凑表：杂凑算法查找,符号表中分程序结构层次管理,int a;float b,d;int c;float a;int d;float c;float d;a=b+c+d;,符号表中分程序结构层次管理,分表结构对每个分程序建立一个独立的分表结构的符号表动态建立和动态消亡,int a;float b,d;int c;float a;int d;float c;float d;a=b+c+d;,符号表中分程序结构层次管理,单表结构把分程序符号组织在一张总表结构的符号表中。特定要求：为了标志符号所属的分程序层次，在符号表中可设立一个属性域用来登录符号所在分程序的层次；在编译程序扫描进入一个分程序时，表示分程序层次的状态量要增加一层，使进入分程序后定义的标识符登录符号表时，有相应的层次量作为层次属性登录；对于具有分程序结构的源程序，在不同分程序中允许定义重名标识符，单表结构可以用下推链来组织；,单表结构,int a;float b,d;int c;float a;int d;float c;float d;a=b+c+d;,单表结构,int a;float b,d;int c;float a;int d;float c;float d;a=b+c+d;,单表结构,int a;float b,d;int c;float a;int d;float c;float d;a=b+c+d;,单表结构,int a;float b,d;int c;float a;int d;float c;float d;a=b+c+d;,下推链结构不但符号作用域规则，也实现了可视性规则；,