编译原理第06.ppt

第6章 符号表的组织和查找 为了检查语义的正确性和生成代码，需要知道源程序中使用的各种标始符的属性，这些属性常常由编译程序集中起来并存放在一个标始符表或符号表中。 组织、构造和各种查找符号表。 符号表的作用和地位 收集符号属性 上下文语义的合法性检查的依据 作为目标代码生成阶段地址分配的依据 符号的主要属性及作用 符号名 变量名、函数名、过程名等，重载信息 符号类型 int、float等，函数的类型看返回值 符号的存储类型 Common、Static、Auto、Regist 符号的作用域及可视性 Public、Private等 符号变量的存储分配信息 静态存储区、动态存储区 符号的其他属性 数组内情向量、结构成员信息、函数及过程的形参 符号表的组织 符号表的总体组织 符号表项的排列 关键字域的组织 其他域的组织 下推链域的组织 符号表的总体组织 1 把属性完全相同的符号组织在一起 优点：表项等长、单个表容易管理 缺点：表较多、总体管理较复杂 2 把所有符号放在一张表中 优点：相同属性处理一致、总体管理简单 缺点：表项不等长、表项复杂、空间浪费 3 根据属性相似程度进行分类组织成若干张表 关键字域的组织 表示符的内部规则（长度）是符号表关键字组织的依据 如：C语言内部变量长度最大为31个字符可设置关键字段最大长度为32个字符（包含结束符号）或：考虑空间的节约（字符不等长），将名称字符串放在“关键字池”中，关键字段变为整数（指针） 实现方式 符号表中的数据 变量 类型、种类、精度、数组的维数以及信息向量表、形参以及类型、结构分量的连接方式、标号类别等 过程 是否为函数，函数类型，是否为形参，是否为外部过程，递归过程等 符号表的一般组织形式 符号表的生存期 当编译程序开始工作时，符号表或者为空或者已经存放了保留字或标准函数等标项。在编译过程中，每遇到标识符时，就要填写符号表，若是新的标识符，就向符号表填入一个新的表项；否则，根据情况向符号表中已有表项增填信息（如分配的存储地址）或查获信息（如语义检查）。符号表中的信息有些用在语法阶段的查错，有些用于语义检查，有些用作代码生成，因此，整个编译阶段都会用到符号表，有些信息可能还会传到程序的运行阶段（如数组地址计算的相关信息等）。 符号表的构造和查找 线性组织 根据扫描到的符号先后顺序建立 优点：管理简单；缺点：运行效率低 适合于较少符号的组织 线性构造 线性查找 LINEARSEARCH { for i=n to 1 do if T[i]=x return (“x的信息”); return (“表中不存在x表项”); } 排序组织及二分法 将符号按名称排序（词典排序） 优点：查找迅速；缺点：算法复杂 如：有哪些信誉好的足球投注网站到新符号后，将其插入到表中，必须采用链表组织 折半法 BINARSEARCH { i=1;j=n; for k=(i+j)/2 while i=j do if T[k]=x return (“x的信息”) else if T[k]x i=k+1 else j=k-1; return(“表中不存在x表项”); } 适合比较固定的表（很少填入新项的表） 散列组织 用hash函数将符号名映射成整数 优点：运行效率高、算法复杂度比排序组织低 缺点：对变量表难以找到高效的hash函数 散列组织 散列组织（杂凑技术），基本思想是设计一个杂凑函数h(x)，x是任意标识符，它把x映射到表区中的某一个地址，并要求当x?y时, h(x)=h(y)的可能性尽量地小，即单元冲突的可能性尽量地小，从而使要填入的标识符比较均匀地散列到整个表区中。 hash函数h(x) 剩法公式：h(x)=[C*((?*x) mod 1)]*2 除法公式：h(x)=(x mod k)*2 折叠函数 线性探查法(1) HASHBUILD { if g=2048 return(error: 标识符表溢出); “计算h(x)?h”; while@(h)?0 do if @(h)=x return(error:重名); else {h=h+2; if h=4096 h=0;} @(h)=x; g=g+1; return; } 线性探查法(2) HASHSEARCH { f=0; “计算h(x)?h”; while f2048 do {if @h(x)=x return(“找到x的信息”); if