符号表Z 标识符的作用：声明部分：定义了各种对象及对应的属性和使用规则。程序体：对所定义的对象进行各种操作。$ididnameIdname AttributeIRZ 必要性Token：新表符号表（种类、类型等信息）：Z 有关符号表的操作：添加、作用域删除、查询Z 处理符号表的模块：定义符号表数据结构 定义符号表上的操作符号表符号表的作用：为语义检查和代码生成提供标识符的语义信息。标识符的处理思想： 遇到定义性标识符时，在符号表中填写被定义标识符的符号项； 当遇到使用性标识符时，用该标识符查符号表求得其属性。标识符的特点标识符的作用域：标识符有效的最大程序段 嵌套作用域规则：当存在标识符的嵌套声明 时，最近定义的属性为标识符的当前属性 局部化单位：允许有声明的程序段P:Var x ,y,zVar x,m,nx:=1;m:=x+1;y:=x+1;x:=0; Q :符号表的种类：全局符号表、局部符号表符号表的操作特点： 在声明部分，定义标识符，要加入符号表 在表达式或语句中，使用标识符，应查表查其属性。 每个标识符在其作用域结束后，要删掉该属性表项 体现嵌套作用规则和局部化 符号表处理技术基本表组织结构： 线性表结构：顺序查表法 二叉树结构：平分查表法 Hash表结构：散列查表法符号表的局部化处理 思想：确定在某个程序点处有效的所有标识符属性表项。即每个局部化单位能确定其符号表。 方法：二叉式局部符号表 散列式全局符号表 嵌套式局部符号表 二叉式局部符号表组织结构：每个局部化单位构造一个符号表，每个符号表采用二叉树结构。 具体实现：用栈(Scope)来保存活跃的局部化单位的符号表地址n进入局部化区：创建一个新的空符号表，其地址压入scope栈n遇定义性标识符：其属性加入当前栈顶符号表n遇使用性标识符：从栈顶符号表依次往下查找n退出局部化区：删掉栈顶符号表 二叉式局部符号表例子1BEGIN A :int；2BEGIN A :real;3BEGIN A: bool; A := false END ;A := 0.55 ;END ;A := 100END散列式全局符号表 组织结构：整个程序用一个符号表，采用外拉链散列表 具体实现：符号表的局部化：嵌套作用域规则：设置计数器标记局部化单位：n:=0 n 进入局部化单位：n:=n+1; n 定义性标识符：hash(Key)= pos;放入最前面位置 n 使用性标识符：hash(Key)=pos;第一个遇到的 n 退出局部化单位：删除局部化单位编号为n的标识符;n:= n-1;散列式全局符号表例1BEGIN A :int；2BEGIN A :real;3BEGIN A: bool; A := false END ;A := 0.55 ;END ;A := 100END嵌套式局部符号表 组织结构： 整个程序一个表，采用线性组织方式，用栈记录 每个局部化单位符号表的头地址。 具体实现：n 进入局部化单位：登记符号表头地址；level:=level+1;Scopelevel:=top;n 定义性标识符：登记标识符属性到符号表中；n 使用性标识符：从本层依次往下查；n 退出局部化单位：关闭本层符号表；top:=top+1;SymbTabletop:=(0,Scopelevel-1);level:= level-1;嵌套式局部符号表例Proc P( )VAR i, j, k: int；Proc Q( )VAR x, y : real;BEGIN ENDProc S( )VAR c, e : char;BEGIN ENDBEGIN END