编译原理符表课件

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