第七章符号表

第七章:符号表管理技术7.1概述7.2符号表的组织与内容7.3非分程序结构语言的符号表组织7.4分程序结构语言的符号表组织7.1概述(1)什么是符号表?在编译过程中，编译程序用于记录源程序中各种名字的特性信息，所以也称为名字特性表。名字：程序名、过程名、函数名、用户定义类型、变量名、符号名字。特性信息：名字种类、类型、维数、参数个数及目标地址（存储单元地址）等。(2)建表和查表的必要性(符号表在编译过程中的作用)源程序中变量要先声明，然后才能引用。用户通过声明语句，声明各种名字，以及给出它们的类型维数等信息，编译程序在出来这些声明语句时，因将声明中的名字以及信息登录到符号表中，同时编译还要给变量分配存储单元，而存储单元地址也必须登录在符号表中。当编译程序编译到引用所声明的变量时（赋值或引用其值）要进行语法语义正确性检查类型是否符合要求和生成相应的目标程序，这就需要查符号表来取得相关信息。1.语法分析和语义分析说明语句赋值语句的语法规则上下文有关分析；是否声明；类型一致性检查2.生成目标代码LOADa的地址ADDb的地址STOx的地址例:intx,a,b;……L:x:=a+b;…建表分配存贮符号表数据区X简单变量整型A简单变量整型B简单变量整型L标号(3)有关符号表的操作：填表和查表填表:当分析到程序中的说明或定义语句时应将说明或定义的名字以及与之有关的信息填入符号表中例：ProcedureP()查表:(1)填表前查表检查在程序的同一作用域内名字是否重复定义(2)检查名字的种类是否与说明一致(3)对于强类型语言要检查表达式中各变量的类型是否一致(4)生成目标指令时要取得所需要的地址7.2符号表的组织与内容(1)符号表的结构与内容符号表的基本结构如下名字特性(信息)“名字”域:存放名字。一般为标识符的符号串，也可为指向标识符字符串串指针“特性”域：可包括多个子域，分别表示标识符的有关信息。如：名字（标识符）的种类：变量、函数、过程、数组、标号、参数等类型：如整型、浮点型、字符型、指针等性质：变量形参、值形参等名字：常量名地址：变量所分配单元的首址或地址位移大小：所占的字节数名字特性(信息)作用域的嵌套层次对于数组：维数、上下界值、计算下标量地址所用的信息以及数组元素类型等对于记录（结构、联合）：域的个数、每个域名、地址位移、类型等对于过程或函数：形参个数、所在层次、函数返回值类型、局部变量所占空间大小等对于指针：所指对象类型等(2)组织方式1.统一符号表:无论什么名字都填入统一格式的符号表中符号表表项应按信息量最大的名字设计填表查表比较方便结构简单但是浪费大量空间2.对于不同种类的名字分别建立各种符号表节省空间但是填表和查表不方便3.折中办法:大部分共同信息组成统一格式的符号表。特殊信息另设附表,两者用指针连接.例：beginarrayB[1..100]…endB数组实型维数上下界首地址补充指针连接7.3非分程序结构语言的符号表组织(1)分程序的结构语言:每个可独立进行编译的程序单元是一个不包含有子模块的单一模块.如Fortran语言Fortran程序构造主程序子程序及函数主程序和子程序中可定义common语句(2)标识符的作用域及基本处理办法1.作用域:全局:子程序名,函数名和公共区名局部:程序单元中定义的变量2.符号表的组织3.基本处理办法1子程序函数名和公共区变量填入全局符号表全局符号表局部符号表2在声明部分读到标识符,造局部符号表查本程序单元局部符号表,有无同名3在语句部分读到标识符查表查本程序单元局部符号表有无同名有,重复声明,报错无,造表有,即已声明无,查全局变量表有全局量无无定义标识符(3)符号表的组织方式4.程序单元结束:释放该程序单元的局部符号表5.程序编译完成:释放全部符号表1.无序符号表:按扫描顺序建表,查表要逐项查找查表操作的平均长度为:n+1/22.有序符号表符号表按变量名进行字典式排序线性查表:n+1/2折半查表:log2n-13.散列符号表(Hash)表:符号表地址=Hash(标识符)解决:冲突7.4分程序结构语言的符号表组织(1)分程序的结构语言:块内可嵌入子模块(2)标识符的作用域和基本处理方法作用域:标识符局部于所定义的模块(最小模块)①模块中所定义的标识符作用域是定义该标识符的子程序A为内分程序局部变量A为内分程序全局变量都是局部变量RealA;RealA;RealA;RealA;RealA;RealA;B:=A;begin……procedureP(i,j);begin…Lend…gotoL;P(3,5);…End;②过程或函数说明中定义的标识符（包括形参）其作用域为本过程体例:③循环语句中定义的标识符，其作用域为该循环语句for…dobegin…Lend…gotoL;…不能从循环体外转到循环体内循环语句应看作一层建查符号表均要遵循标识符作用域规定进行建表不能重复不能遗漏查表按标识符作用域基本处理办法：Realx,A,BIntegerx,y;procedurep()beginrealx;A:=x+2.0;…endB:=x+2.0定义重复错误必须填表查表是本层的查表是本层的(最外层的)处理方法假设标识符是先声明后引用(标号例外,要特殊处理)a.在程序声明部分读到标识符时声明性出现建表查本层符号表有无重名b.在语句中读到标识符(引用性出现)查表查本层符号表有无重名有重复声明报错无填入符号表有即已声明已取该名字信息局部量无是否是最外层?是未声明标识符报错否转到直接外层c.标准标识符的处理主要是语言定义的一些标准过程和函数的名字,它们是标识符的子集。如sincosabs…(注意它们不是语言的保留字)特点:1)用户不必声明就可全程使用2)设计编译程序时标准名字及其数目已知处理方法:1)单独建表,使用不便,出错2)预先将标准命填入名字表中,因为它们是全程量,所以应填入最外层第八章符号表编译过程中编译程序需要不断汇集和反复查证出现在源程序中各种名字的属性和特征等有关信息。这些信息通常记录在一张或几张符号表中。符号表的每一项包括两部分：一部分是名字（标识符）；另一部分是此名字的有关信息。每个名字的有关信息是指种属（如简单变量、数组、过程等）、类型（如整、实、布尔等）。这些信息将用于语义检查、产生中间代码以及最终生成目标代码等不同阶段。几乎在编译程序工作的全过程中，都需要对符号表进行频繁访问，可以认为查表或填表等操作，在编译程序的编译过程中是很大的一笔开销。因此，合理地组织符号表，并相应地选择好查表和填表的方法，是提高编译序工作效率的重要一环。例题与习题解答[例8。1]在编译过程中，嵌套调用的过程间寻址问题如何解决？下面是一个示意性元程序，请给出编译期间栈式符号表的变化情况。PROGRAMmaina=10;b,c:integer;d,e:real;PROCEDUREp(x:real);f:real;PROCEDUREq(y:real);g=5;n:boolean;BEGIN…IFe0THENp(f);…..END;{q}BEGIN….Q(e);…END;{p}PROCEDUREt;j:real;BEGIN…p(e);…END;{t}BEGIN…WHILEc0DO…;p(d);…END.{main}解：在编译过程中，当进入某过程体时，每引用一次标识符便需要查找栈符号表，查找范围由DISPLAY栈顶值和TOP的值控制，首先在栈符号表内的(TOP-1）至DISPLAY栈顶值这样一个范围内查找，若找到了，便可以从中取出该标识符的有关属性；若未查到，则需要继续在它的嵌套外层中查找，一直到最外层；如果引用的某标识符一直查到主程序还查不到它的说明或某些属性不相符，则说明语义不正确，处理程序将向用户报告出错信息。下面给出了元程序在编译的不同时刻栈符号表的变化：