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