编译原理第九章-符号表

第9章符号表数计学院

宋彩芳第一页，共六十二页。9

符号表符号表的作用和地位符号的主要属性及作用符号表的组织符号表的管理第二页，共六十二页。符号表的作用和地位符号表用来存放语言程序中出现的有关标识符的属性信息，这些信息集中反映了标识符的语义特征属性；在词法分析及语法分析过程中不断积累和更新表中的信息。在词法分析到代码生成的各个阶段，按各自需要从表中获取不同的属性信息。第三页，共六十二页。符号表的作用和地位符号表的功能有：收集符号属性；int

i[3][5];上下文语义的合法性检查的依据；extern

float

i;

//类型不一致float

i[4][2];

//重定义作为目标代码生成阶段地址分配的依据；extern

公共区extern

static文件静态区static

函数静态区auto

动态区第四页，共六十二页。9

符号表符号表的作用和地位符号的主要属性及作用符号表的组织符号表的管理第五页，共六十二页。符号的主要属性及作用语言符号可分为：关键字（保留字）符号操作符符号标识符符号语言中标识符可以是变量名、函数名、过程名；过程没有返回值,如同C的void函数则有,如同C的带返回值函数第六页，共六十二页。标识符符号的属性(信息）几种通常都是需要的。符号名符号的类型符号的存储类别符号的作用域及可视性符号变量的存储分配信息符号的其它属性数组内情向量记录结构型的成员信息函数及过程的形参第七页，共六十二页。标识符符号的属性(信息）一、符号名符号名与它在符号表中的位置一一对应；标识符的内部代码也即标识符在符号表中的位置（通常是一个整数）可以替换符号名；符号表运行过程中，表中的标识符名始终是唯一标志；特殊情形：重名标识符定义：根据标识符在程序中的作用域和可视性规则进行处理。表中标识符名始终唯一；操作重载：通过它们的参数个数和类型，以及函数返回值类型来区别。以达到标识符的唯一；第八页，共六十二页。标识符符号的属性(信息）三、符号的存储类别由关键字指定；用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（符号代码值）=

mod（Vhash，N）改进：Lhash………..…a…………..b..…..a…..……..d..…c…….……b….第三十三页，共六十二页。符号表项的排列散列组织需事项注意：散列冲突，解决方法是多次散列方法；散列函数的选择：静态符号表动态符号表

对符号代码的位操作作为杂凑函数，如符号代码的字段叠加或加权叠加以及符号代码的对折或多对折等位操作；第三十四页，共六十二页。符号表的组织符号表的总体组织符号表项的排列关键字域的组织其他域的组织第三十五页，共六十二页。关键字域的组织有关符号的基础知识保留字操作符标识符外部名（前6个字符可以惟一地区分）内部名（前31个字符可以惟一地区分）可见，标识符的内部规则是符号表关键字组织的基础和依据；第三十六页，共六十二页。关键字域的组织等长关键字域（段）符号表设置关键字段为标识符的最大长度；第三十七页，共六十二页。关键字域的组织不等长关键字段符号表采用关键字池的索引结构。第三十八页，共六十二页。符号表的组织符号表的总体组织符号表项的排列关键字域的组织其他域的组织第三十九页，共六十二页。其他域的组织等长属性值域组织符号表中符号的属性值具有相同类型且等长；不等长属性域组织符号表中符号的属性值具有相同类型但长度不同；下推链域的组织第四十页，共六十二页。等长属性值域组织可以取相应的数据类型表达属性值符号布尔性质的属性域defined

1(true)表示已定义defined

0(false)表示未定义表示符号的基本数据类型Data-type3个bit位（整型值）Char0

0

0

(0)short0

0

1

(1)int0

1

0

(2)long0

1

1

(3)unsigned1

0

0

(4)float1

0

1

(5)double1

1

0

(6)第四十一页，共六十二页。等长属性值域组织可以取相应的数据类型表达属性值符号变量：存储类别——数据类型一样的构造方式存储位移——整型量表示相对位移量第四十二页，共六十二页。等长属性值域组织可以取相应的数据类型表达属性值结构struct

tag1

{memb1memb2struct

tag2

{memb3

memb4memb5}

memb6memb7}

stv;第四十四页，共六十二页。不等长属性值域组织另设空间存放属性值数组的内情向量array1(subscrip1,subscrip2)array2(subscrip3,subscrip4,subscrip5,subscrip6)第四十五页，共六十二页。不等长属性值域组织另设空间存放属性值C语言中数组特别的含义int

abc[3][4][2];第四十六页，共六十二页。不等长属性值域组织复合属性域的组织存在若干个可用位表示的信息该符号变量是否初始化该符号是否是结构成员该符号是否是标号该符号是否是保留字第四十八页，共六十二页。下推链域的组织实现同名标识符的语义功能第四十九页，共六十二页。9

符号表符号表的作用和地位符号的主要属性及作用符号表的组织符号表的管理第五十页，共六十二页。符号表的管理符号表的作用反映了符号表的行为：符号表的初始化符号的登录符号的查找符号表中分程序结构层次的管理第五十一页，共六十二页。符号表的初始化符号表的表长是渐增变化的情况线性组织和二分法组织符号表的表长是确定的情况散列组织的符号表第五十二页，共六十二页。符号的登录不同组织方式导致不同的登录方式线性方法：图9.21二分方法：图9.22散列表：通过杂凑算法决定登录表项的位置；登入的内容：名字登入名字属性：取决于编译程序获得某个符号时编译所处的程序扫描点的状态；第五十三页，共六十二页。符号的登录符号a的属性…func(x,y){

…struct

tag

{int

a[n][m];}

t;…}类型属性存储类别属性作用域属性存储分配属性数组内情向量属性第五十四页，共六十二页。符号的查找目的：建立和确认该符号的属性；步骤：先在保留字表和运算符表中查找；再在标识符表中查找；查找算法与该符号表的组织方式密切相关；线性表：顺序查找

二分表：折半查找

杂凑表：杂凑算法查找第五十五页，共六十二页。符号表中分程序结构层次管理｛float

a;int

a;

float

b,d;{int

c;{int

d;

float

c;{float

d;a=b+c+d;}

}

}

}第五十六页，共六十二页。符号表中分程序结构层次管理分表结构对每个分程序建立一个独立的分表结构的符号表动态建立和动态消亡｛float

a;int

a;

float

b,d;{int

c;{intd;

float

c;{float

d;a=b+c+d;}

}

}

}第五十七页，共六十二页。符号表中分程序结构层次管理单表结构把分程序符号组织在一张总表结构的符号表中。特定要求：为了标志符号所属的分程序层次，在符号表中可设立一个属性域用