北航编译原理课件符号表管理技术.ppt

北京航空航天大学计算机学院北京航空航天大学计算机学院1第五章 符号表管理技术概述符号表的组织与内容非分程序结构语言的符号表组织 分程序结构语言的符号表组织 北京航空航天大学计算机学院北京航空航天大学计算机学院25.1 概述(1)什么是符号表?在编译过程中,编译程序用来记录源程序中各种 名字的特性信息,所以也称为名字特性表。名 字:程序名、过程名、函数名、用户定义类型名、变量名、常量名、枚举值名、标号名等。特性信息:上述名字的种类、类型、维数、参数个数、数值及目标地址（存储单元地址）等。北京航空航天大学计算机学院北京航空航天大学计算机学院3(2)建表和查表的必要性(符号表在编译过程中的作用)源程序中变量要先声明，然后才能引用。用户通过声明语句，声明各种名字，并给出它们的类型、维数等信息，编译程序在处理这些声明语句时，应该将声 明中的名字及其信息登录到符号表中，同时编译程序还要 给变量分配存储单元，而存储单元地址也必须登录在符号 表中。当编译程序编译到引用所声明的变量时(赋值或引用其值)，要进行语法语义正确性检查(类型是否符合要求)和生成相 应的目标程序，这就需要查符号表以取得相关信息。北京航空航天大学计算机学院北京航空航天大学计算机学院4例：int x,a,b;.L:x:=a+b;.建表，分配存贮符号表符号表数据区数据区1.语法分析和语义分析 说明语句、赋值语句的语法规则 上下文有关分析：是否声明 类型一致性检查 2.生成目标代码 LOAD a的地址 ADD b的地址 STO x的地址x 简单变量 整型a 简单变量 整型b 简单变量 整型L 标号北京航空航天大学计算机学院北京航空航天大学计算机学院5(3)有关符号表的操作：填表和查表填表：当分析到程序中的说明或定义语句时，应将说明或 定义的名字，以及与之有关的信息填入符号表中。例：Procedure P()查表：(1)填表前查表，检查在程序的同一作用域内名字 是否重复定义；(2)检查名字的种类是否与说明一致；(3)对于强类型语言，要检查表达式中各变量的类型 是否一致；(4)生成目标指令时，要取得所需要的地址。.北京航空航天大学计算机学院北京航空航天大学计算机学院65.2 符号表的组织与内容(1)符号表的结构与内容符号表的基本结构符号表的基本结构:名字名字特性特性(信息信息)“名字”域:存放名字，一般为标识符的符号串,也可 为指向标识符字符串的指针。北京航空航天大学计算机学院北京航空航天大学计算机学院7“特性”域:可包括多个子域,分别表示标识符的有 关信息，如:名字(标识符)的种类:简单变量、函数、过程、数组、标号、参数等类型：如整型、浮点型、字符型、指针等性质：变量形参、值形参等值：常量名所代表的数值地址：变量所分配单元的首址或地址位移大小：所占的字节数作用域的嵌套层次:名字特性(信息)北京航空航天大学计算机学院北京航空航天大学计算机学院8对于数组:维数、上下界值、计算下标变量地址所用的 信息（数组信息向量）以及数组元素类型等。对于记录（结构、联合）：域的个数，每个域的域名、地址位移、类型等。对于过程或函数：形参个数、所在层次、函数返回值类型、局部变量所占空间大小等。对于指针：所指对象类型等。北京航空航天大学计算机学院北京航空航天大学计算机学院9(2)符号表的组织方式 1.统一符号表:不论什么名字都填入统一格式的符号表中2.对于不同种类的名字分别建立各种符号表 符号表表项应按信息量最大的名字设计,填表、查表比较方便,结构简单,但是浪费大量空间。3.折中办法:大部分共同信息组成统一格式的符号表，特殊信息另设附表,两者用指针连接。节省空间,但是填表和查表不方便。北京航空航天大学计算机学院北京航空航天大学计算机学院10例:begin A:real;B:array 1:100 of real;:endAB简变简变 实型实型 地址地址 实型实型 数组数组维数维数上下界上下界首地址首地址补充补充指针连接指针连接北京航空航天大学计算机学院北京航空航天大学计算机学院115.3 非分程序结构语言的符号表组织(1)非分程序结构语言:每个可独立进行编译的程序单 元是一个不包含有子模块的单 一模块，如FORTRAN语言。FORTRAN程序构造主程序主程序子程序子程序或函数或函数 主程序和子程序中可定义common语句北京航空航天大学计算机学院北京航空航天大学计算机学院12(2)标识符的作用域及基本处理办法 1.作用域:全局:子程序名,函数名和公共区名。局部:程序单元中定义的变量。2.符号表的组织:全局符号表全局符号表局部符号表局部符号表3.基本处理办法:子程序、函数名和公共区名填入全局 符号表。北京航空航天大学计算机学院北京航空航天大学计算机学院13 在子程序（函数）声明部分读到标识符，造局部符号表。查本程序单元局部符号表，有无同名？有,重复声明,报错无,造表 在语句部分读到标识符,查表:查本程序单元局部符号表，有无同名？有,即已声明无,查全局变量表有,全局量无,无定义 标识符北京航空航天大学计算机学院北京航空航天大学计算机学院144.程序单元结束:释放该程序单元的局部符号表。5.程序编译完成:释放全部符号表。(3)符号表的组织方式 1.无序符号表:按扫描顺序建表,查表要逐项查找查表操作的平均长度为查表操作的平均长度为n+1 2北京航空航天大学计算机学院北京航空航天大学计算机学院152.有序符号表：符号表按变量名进行字典式排序线性查表:n+1 2折半查表:1-Log2n3.散列符号表(Hash表)：符号表地址=Hash(标识符)解决：冲突北京航空航天大学计算机学院北京航空航天大学计算机学院165.4 分程序结构语言的符号表组织(1)分程序结构语言:模块内可嵌入子模块(2)标识符的作用域和基本处理方法：作用域：标识符局部于所定义的模块(最小模块)模块中所定义的标识符作用域是定义该标识模块中所定义的标识符作用域是定义该标识符的子程序符的子程序1北京航空航天大学计算机学院北京航空航天大学计算机学院17real A;A为内分程序局部变量为内分程序局部变量12real A;A为可作用于内分程序的全局变量为可作用于内分程序的全局变量121real A;2real A;2都是局部变量1real A;2real A;B:=A;北京航空航天大学计算机学院北京航空航天大学计算机学院18过程或函数说明中定义的标识符(包括形参)其作用域为本过程体。2例begin procedure P(i,j);begin :L:end goto L;P(3,5);end;12北京航空航天大学计算机学院北京航空航天大学计算机学院19循环语句中定义的标识符,其作用域为该循环语句。3for do begin :L:endGoto L;:北京航空航天大学计算机学院北京航空航天大学计算机学院20基本处理办法:建查符号表均要遵循标识符的作用域规定进行。建表：不能重复,不能遗漏查表：按标识符作用域 real x,A,B;integer x,y;real x;A:=x +2.0;:B:=x +2.0 定义重复错误查表，是本层的x必须填表查表，是本层的x(外层的x)北京航空航天大学计算机学院北京航空航天大学计算机学院21处理方法:a.在程序声明部分读到标识符时(声明性出现),建表:查本层符号表,有无同名？有,重复声明,报错无,填入符号表b.在语句中读到标识符(引用性出现),查表:查本层符号表,有无同名？有,即已声明,取该名字信息(局部量)无,是否是最外层?是,未声明标识 符,报错否,转到直接 外层(n-1)北京航空航天大学计算机学院北京航空航天大学计算机学院22c.标准标识符的处理 主要是语言定义的一些标准过程和函数的名字,它们是标识符的子集。如 sin con abs.特点：1)用户不必声明,就可全程使用 2)设计编译程序时，标准名字及其数目已知处理方法：1)单独建表：使用不便，费时。2)预先将标准名填入名字表中最外层北京航空航天大学计算机学院北京航空航天大学计算机学院23例:Pascal程序的分程序结构示例如下:program main();var x,y:real;i,k:integer;name:array 116 of char;:procedure M1(ind:integer);var x:integer procedure P2(j:real);:procedure P3;var f:array 15 of integer test1:boolean;begin :end;P3:0123P2mainM1P3q201223北京航空航天大学计算机学院北京航空航天大学计算机学院24 begin :end;P2 procedure q2;var r1,r2:real;begin :P2(r1+r2);:end;q2 begin :P2(x/y);:end;M1 begin :M1(i+k);:end main0 1 22program main();var x,y:real;i,k:integer;name:array 116 of char;:procedure M1(ind:integer);var x:integer procedure P2(j:real);:procedure P3;var f:array 15 of integer test1:boolean;begin :end;P3 begin :end;P2 procedure q2;var r1,r2:real;begin :p2(r1+r2);:end;q2 begin :P2(x/y);:end;M1 begin :M1(i+k);:end main 012320 12北京航空航天大学计算机学院北京航空航天大学计算机学院25栈式符号表结构main符号表M1符号表P2符号表P3符号表main符号表M1符号表q2main符号表M1符号表main符号表主程序符号表mainM1符号表P2符号表栈顶释放符号表M1符号表P2符号表main符号表北京航空航天大学计算机学院北京航空航天大学计算机学院26other infmainM1P2P312345678910111213namekindtypelevxyiknameM1indxP2jP3ftest1varvarvarvarvarvarvarvarprocprocprocparapararealrealrealintintintintarrayarrayboolean0000001112233符号表0123171012分程序索引表北京航空航天大学计算机学院北京航空航天大学计算机学院27编译q2说明部分后:78910 11 12 13indparaint1111122intrealrealrealvarprocprocvarvarparaxP2q2r2r1q2M1北京航空航天大学计算机学院北京航空航天大学计算机学院28编译完q2过程体:7891011indparaintxP2q2varprocparaprocintreal 当过程和函数体编译完成后，应将与之相应的 参数名和局部变量名以及后者的特性信息从符号表中删去。要求：给出一段程序，会画出其栈式符号表