编译原理compiler7_符号表.ppt

《编译原理compiler7_符号表.ppt》由会员分享，可在线阅读，更多相关《编译原理compiler7_符号表.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第七七章章:符号符号表管理技术表管理技术7.1 1 概述概述7.2 符号表的组织与内容符号表的组织与内容7.3 非分程序结构语言的符号表组织非分程序结构语言的符号表组织7.4 分程序结构语言的符号表组织分程序结构语言的符号表组织7.1 7.1 概述概述(1)什么什么是符号表是符号表?在编译过程中，编译程序用于记录源程序在编译过程中，编译程序用于记录源程序中各种名字的特性信息，中各种名字的特性信息，所以也称为所以也称为名字特名字特性表性表。名字名字：程序名、过程名、函数名、用户定程序名、过程名、函数名、用户定义类型、变量名、符号名字。义类型、变量名、符号名字。特性信息特性信息：名字种类、类型、

2、维数、参数：名字种类、类型、维数、参数个数及目标地址（存储单元地址）等。个数及目标地址（存储单元地址）等。(2)建表和查表的必要性建表和查表的必要性 (符号表在编译过程中的作用符号表在编译过程中的作用)源程序中变量要先声明，然后才能引用。源程序中变量要先声明，然后才能引用。用户通过用户通过用户通过用户通过声明语句声明语句声明语句声明语句，声明各种，声明各种，声明各种，声明各种名字名字名字名字，以及给出它们，以及给出它们，以及给出它们，以及给出它们的类型维数等的类型维数等的类型维数等的类型维数等信息信息信息信息，编译程序在出来这些声明语句时，编译程序在出来这些声明语句时，编译程序在出来这些声明语

3、句时，编译程序在出来这些声明语句时，因将声明中的名字以及信息因将声明中的名字以及信息因将声明中的名字以及信息因将声明中的名字以及信息登录登录登录登录到符号表中，同时编译到符号表中，同时编译到符号表中，同时编译到符号表中，同时编译还要给变量分配存储单元，而还要给变量分配存储单元，而还要给变量分配存储单元，而还要给变量分配存储单元，而存储单元地址存储单元地址存储单元地址存储单元地址也必须登录也必须登录也必须登录也必须登录在符号表中。在符号表中。在符号表中。在符号表中。当编译程序编译到当编译程序编译到当编译程序编译到当编译程序编译到引用引用引用引用所声明的变量时所声明的变量时所声明的变量时所声明的变

4、量时（赋值或引赋值或引赋值或引赋值或引用其值）要进行语法语义正确性检查用其值）要进行语法语义正确性检查用其值）要进行语法语义正确性检查用其值）要进行语法语义正确性检查 类型是否符合要求类型是否符合要求类型是否符合要求类型是否符合要求和生成相应的目标程序，这就需要和生成相应的目标程序，这就需要和生成相应的目标程序，这就需要和生成相应的目标程序，这就需要查查符号表来取得相关符号表来取得相关符号表来取得相关符号表来取得相关信息信息信息信息。1.1.1.1.语法分析和语义分析语法分析和语义分析语法分析和语义分析语法分析和语义分析 说明语句赋值语句的语法规则说明语句赋值语句的语法规则说明语句赋值语句的语

5、法规则说明语句赋值语句的语法规则 上下文有关分析；是否声明；上下文有关分析；是否声明；上下文有关分析；是否声明；上下文有关分析；是否声明；类型一致性检查类型一致性检查类型一致性检查类型一致性检查2.2.生成目标代码生成目标代码生成目标代码生成目标代码LOAD a LOAD a 的地址的地址的地址的地址ADD b ADD b 的地址的地址的地址的地址STO x STO x 的地址的地址的地址的地址例例例例:int int x,a,b;x,a,b;L:x:=a+b;L:x:=a+b;建表建表建表建表分配存贮分配存贮分配存贮分配存贮符号表符号表符号表符号表数据区数据区数据区数据区X X 简单变量简单

6、变量简单变量简单变量 整型整型整型整型A A 简单变量简单变量简单变量简单变量 整型整型整型整型B B 简单变量简单变量简单变量简单变量 整型整型整型整型L L 标号标号标号标号(3)有关符号表的操作：填表和查有关符号表的操作：填表和查表表填表填表:当分析到程序中的当分析到程序中的当分析到程序中的当分析到程序中的说明说明说明说明或或或或定义定义定义定义语句时应将说明语句时应将说明语句时应将说明语句时应将说明或定义的名字以及与之有关的信息填入符号表中或定义的名字以及与之有关的信息填入符号表中或定义的名字以及与之有关的信息填入符号表中或定义的名字以及与之有关的信息填入符号表中 例：例：例：例：Pr

7、ocedure P()Procedure P()Procedure P()Procedure P()查表查表:(1)(1)填表前查表检查在程序的同一作用域内填表前查表检查在程序的同一作用域内填表前查表检查在程序的同一作用域内填表前查表检查在程序的同一作用域内名字名字名字名字是否是否是否是否重复定义重复定义重复定义重复定义(2)(2)检查名字的检查名字的检查名字的检查名字的种类种类种类种类是否与说明一致是否与说明一致是否与说明一致是否与说明一致(3)(3)(3)(3)对于强类型语言要检查表达式中各变量的对于强类型语言要检查表达式中各变量的对于强类型语言要检查表达式中各变量的对于强类型语言要检查表

8、达式中各变量的类型类型类型类型是是是是否一致否一致否一致否一致(4)(4)生成目标指令时要取得所需要的地址生成目标指令时要取得所需要的地址生成目标指令时要取得所需要的地址生成目标指令时要取得所需要的地址 7.2 符号表的组织与内容符号表的组织与内容(1)(1)符号表的结构与内容符号表的结构与内容符号表的基本结构如下符号表的基本结构如下 名字名字 特性特性(信息信息)“名字名字”域域:存放名字。一般为标识符的符存放名字。一般为标识符的符号串，也可为指向标识符字符串串指针号串，也可为指向标识符字符串串指针“特性特性特性特性”域：域：域：域：可包括多个子域，分别表示标识符的有可包括多个子域，分别表示

9、标识符的有可包括多个子域，分别表示标识符的有可包括多个子域，分别表示标识符的有关信息。如：关信息。如：关信息。如：关信息。如：名字（标识符）的种类：名字（标识符）的种类：名字（标识符）的种类：名字（标识符）的种类：变量、函数、过程、数组、变量、函数、过程、数组、变量、函数、过程、数组、变量、函数、过程、数组、标号、参数等标号、参数等标号、参数等标号、参数等类型：类型：类型：类型：如整型、浮点型、字符型、指针等如整型、浮点型、字符型、指针等如整型、浮点型、字符型、指针等如整型、浮点型、字符型、指针等性质：性质：性质：性质：变量形参、值形参等变量形参、值形参等变量形参、值形参等变量形参、值形参等名

10、字：名字：名字：名字：常量名常量名常量名常量名地址：地址：地址：地址：变量所分配单元的首址或地址位移变量所分配单元的首址或地址位移变量所分配单元的首址或地址位移变量所分配单元的首址或地址位移大小：大小：大小：大小：所占的字节数所占的字节数所占的字节数所占的字节数名字名字名字名字 特性特性特性特性(信息信息信息信息)作用域的嵌套层次作用域的嵌套层次 对于数组：对于数组：维数、上下界值、计算下标量地址维数、上下界值、计算下标量地址所用的信息以及数组元素类型等所用的信息以及数组元素类型等对于记录（结构、联合）：对于记录（结构、联合）：域的个数、每个域名、域的个数、每个域名、地址位移、类型等地址位移、

11、类型等对于过程或函数：对于过程或函数：形参个数、所在层次、函数返形参个数、所在层次、函数返回值类型、局部变量所占空间大小等回值类型、局部变量所占空间大小等对于指针：对于指针：所指对象类型等所指对象类型等(2)组织方式组织方式1.1.统一符号表统一符号表:无论什么名字都填入统一格式无论什么名字都填入统一格式的符号表中的符号表中符号表表项应按信息量最大的名字设计符号表表项应按信息量最大的名字设计 填表填表查表比较方便查表比较方便 结构简单结构简单 但是但是浪费浪费大量空间大量空间2.对于不同种类的名字分别建立各种符号表对于不同种类的名字分别建立各种符号表节节省省空间空间 但是填表和查表不方便但是填

12、表和查表不方便3.折中折中办办法法:大部分大部分共共同信息组成统一格式的符号表。同信息组成统一格式的符号表。特殊信息特殊信息另另设设附附表表,两者两者用指针用指针连接连接.例：例：begin begin array B1.100array B1.100endendB数组数组实实型型维数维数上下界上下界首地址首地址补充补充指针指针连接连接7.37.3非分程序结构语言的符号表组织非分程序结构语言的符号表组织(1)分程序的结构语言分程序的结构语言:每个可每个可独独立进行编立进行编译的程序单元是一个不包译的程序单元是一个不包含含有子有子模块模块的单一的单一模块模块.如如FortranFortran语言

13、语言FortranFortran程序构程序构造造主主程序程序子程序子程序及函数及函数主主程序和子程序中程序和子程序中可定义可定义commoncommon语句语句(2)标识符的作用域及基本标识符的作用域及基本处处理理办办法法1.1.作用域作用域作用域作用域:全全全全局局局局:子程序名子程序名子程序名子程序名,函数名和函数名和函数名和函数名和公共公共公共公共区名区名区名区名 局部局部局部局部:程序单元中定义的变量程序单元中定义的变量程序单元中定义的变量程序单元中定义的变量2.2.符号表的组织符号表的组织符号表的组织符号表的组织3.3.基本基本基本基本处处处处理理理理办办办办法法法法 子程序函数名和

14、子程序函数名和子程序函数名和子程序函数名和公共公共公共公共区变量填入区变量填入区变量填入区变量填入全全全全局符号表局符号表局符号表局符号表全全全全局符号表局符号表局符号表局符号表局部符号表局部符号表局部符号表局部符号表 在声明部分在声明部分读读到标识符到标识符,造造局部符号表局部符号表查本程序单元局部查本程序单元局部符号表符号表,有有无无同名同名 在语句部分在语句部分读读到标识符到标识符 查表查表查本程序单元局部查本程序单元局部符号表有符号表有无无同名同名有有有有,重复声明重复声明重复声明重复声明,报错报错报错报错无无无无,造造造造表表表表有有有有,即已即已即已即已声明声明声明声明无无无无,查

15、查查查全全全全局变量表局变量表局变量表局变量表有有有有 全全全全局量局量局量局量无无无无 无无无无定义定义定义定义标识符标识符标识符标识符 (3)符号表的组织方式符号表的组织方式4.程序单元结程序单元结束束:释释放放该该程序单元的局部符号表程序单元的局部符号表5.5.程序编译程序编译完完成成:释释放放全全部符号表部符号表1.无无序符号表序符号表:按按扫描顺扫描顺序建表序建表,查表要查表要逐逐项查项查找找 查表操作的查表操作的平均长度平均长度为为:n+1/22.有序符号表有序符号表符号表按变量名进行字符号表按变量名进行字典典式式排排序序 线线性查表性查表:n+1/2 折半折半查表查表:loglo

16、g2 2n-1n-1 3.散列散列符号表符号表(Hash)表表:符号表地址符号表地址=Hash(标识符标识符)解决解决:冲突冲突7.47.4分程序结构语言的符号表组织分程序结构语言的符号表组织(1)分程序的结构语言分程序的结构语言:块块内可嵌入子内可嵌入子模块模块(2)标识符的作用域和基本标识符的作用域和基本处处理方法理方法作用域作用域:标识符局部于所定义的标识符局部于所定义的模块模块(最小最小模块模块)模块模块中所定义的标识符作用域是定义中所定义的标识符作用域是定义该该标识标识符的子程序符的子程序 A A为内分程序为内分程序为内分程序为内分程序局部局部局部局部变量变量变量变量 A A为内分程

17、序为内分程序为内分程序为内分程序全全全全局局局局变量变量变量变量都是都是都是都是局部局部局部局部变量变量变量变量Real A;Real A;Real A;Real A;Real A;Real A;Real A;Real A;Real A;Real A;Real A;Real A;B:=A;B:=A;beginbegin procedure P(i,j);procedure P(i,j);begin begin L L end end goto goto L;L;P(3,5);P(3,5);End;End;过程或函数说明中定义的标识符（包括形参）过程或函数说明中定义的标识符（包括形参）过程或函数

18、说明中定义的标识符（包括形参）过程或函数说明中定义的标识符（包括形参）其作用域为本过程其作用域为本过程其作用域为本过程其作用域为本过程体体体体例例例例:循环循环语句中定义的标识符语句中定义的标识符，其作用域为其作用域为该该循环循环语句语句for dofor do begin begin L L end end gotogoto L;L;不能不能从从循环体外循环体外转转到到循环体循环体内内循环循环语句应语句应看看作一层作一层建查符号表建查符号表均均要要遵循遵循标识符作用域规定进行标识符作用域规定进行建表不能重复建表不能重复 不能不能遗漏遗漏查表按标识符作用域查表按标识符作用域基本基本处处理理办办

19、法：法：Real x,A,BReal x,A,BReal x,A,BReal x,A,BInteger Integer Integer Integer x x x x,y;,y;,y;,y;procedure p()procedure p()procedure p()procedure p()begin begin begin begin real real real real x x x x;A:=A:=A:=A:=x x x x+2.0;+2.0;+2.0;+2.0;end end end endB:=B:=B:=B:=x x x x+2.0+2.0+2.0+2.0定义重复定义重复错误错误

20、必须填表必须填表查表是本层的查表是本层的查表是本层的查表是本层的(最最外外层的层的)处处理方法理方法假假假假设标识符是先声明后引用设标识符是先声明后引用设标识符是先声明后引用设标识符是先声明后引用(标号例标号例标号例标号例外外外外,要特要特要特要特殊处殊处殊处殊处理理理理)a.a.在程序声明部分在程序声明部分在程序声明部分在程序声明部分读读读读到标识符时到标识符时到标识符时到标识符时 声明性出声明性出声明性出声明性出现现现现 建表建表建表建表查本层符号表查本层符号表查本层符号表查本层符号表 有有有有无无无无重名重名重名重名b.b.b.b.在语句中在语句中在语句中在语句中读读读读到标识符到标识符

21、到标识符到标识符(引用性出引用性出引用性出引用性出现现现现)查表查表查表查表查本层符号表查本层符号表查本层符号表查本层符号表 有有有有无无无无重名重名重名重名有有有有 重复声明重复声明重复声明重复声明 报错报错报错报错无无无无 填入符号表填入符号表填入符号表填入符号表有有有有 即已即已即已即已声明声明声明声明 已已已已取取取取该该该该名字名字名字名字 信息信息信息信息 局部量局部量局部量局部量无无无无 是否是最是否是最是否是最是否是最外外外外层层层层?是是是是 未未未未声明标识符声明标识符声明标识符声明标识符 报错报错报错报错否否否否 转转转转到到到到直接外直接外直接外直接外层层层层c.c.标

22、标准准标识符的标识符的处处理理 主主要是语言定义的一些标要是语言定义的一些标准准过程和函数的名过程和函数的名字字,它们是标识符的子它们是标识符的子集。集。如如sin sin cos cos absabs (注意注意 它们不是语言的它们不是语言的保留保留字字)特点特点:1)1)用户不必声明用户不必声明用户不必声明用户不必声明 就可就可就可就可全全全全程程程程使使使使用用用用 2)2)设计编译程序时标设计编译程序时标设计编译程序时标设计编译程序时标准准准准名字及其数目名字及其数目名字及其数目名字及其数目已知已知已知已知处处理方法理方法:1)1)单单单单独独独独建表建表建表建表,使使使使用不便用不便用不便用不便,出出出出错错错错 2)2)2)2)预预预预先将标先将标先将标先将标准命准命准命准命填入名字表中填入名字表中填入名字表中填入名字表中,因为它们是因为它们是因为它们是因为它们是全全全全 程量程量程量程量,所以应填入最所以应填入最所以应填入最所以应填入最外外外外层层层层