第9章 符号表

9.1 类型的语义表示 单词是最小的语义单位。 标识符的处理主要包括语义代码化、作用域处理、符号表构造、单元分配等工作。

一、符号表的作用 表 格 管 理 词法分析 语法分析 中间代码生成 中间代码优化 目标代码生成 目标程序 源程序 错 误 处 理

在整个编译阶段都离不开符号表。 二、符号表的内容 Pascal0有以下几种类型： 整 型：integer 实 型：real 布尔型：boolean 数组型：ARRAY[N1…N2]OF T 记录型：RECORD id1：T1；…；idn;Tn END

类型表TYPEL结构形如： TYPEL[tp]： TCLASS TPOINT 种类部分 指针

TCLASS部分结构如下： TCLASS: i r b a d 实型 整型 布尔型 记录型 数组型

数组信息表 AINFL的结构形如: AINFL[ap]: LOW UP CTP CLEN 下界 上界 指针 类型的长度

记录信息表 RINFL的表项结构形如： RINFL[rp]: IDE OFF FTP 域名部分 区距部分 FTP是域类型部分

一个记录类型要占几个RINFL表项，不同记录类型所占表项个数不一，而在表项中没有链接部分，因此在不同记录的RINFL表之间可放置一条空项，以表示记录类型的RINFL表中的结束。

TYPEL表 综上所述，我们有: integer: i nil real: r nil boolean: b nil AINFL a array: RINFL record: d

rp：    设一记录类型的RINFL表为 : id1 Off1 tp1 id2 Off2 tp2 idn Offn tpn    idn Offn tpn 假定integer,real,boolean为标准类型，其地址部分分别为itp,rtp,btp。 Leng(itp)=Leng(rtp)=Leng(btp)=1

例1：设有数组类型ARRAY[1…10] OF ARRAY [1…5] OF integer 则其内部表示如下图所示。 AINFL TYPEL tp: a TCLASS TPOINT LOW UP CTP CLEN 1 10 5 a 1 5 itp 1

例2：记录类型RECORD u：integer； a：ARRAY[1…10] OF boolean； r：RECORD x,y：real END END 则表示如下图所示。 d rtp: TCLASS TPOINT u 0 itp a 1 atp r 11 rtp’ AINFL表 TCLASS TPOINT atp: a 1 10 btp 1

d rtp: TCLASS TPOINT x 0 rtp y 1 rtp

9.2 标识符的语义表示 程序中标识符的出现分为定义性的和使用性的。 标识符的定义部分确定标识符的语义，它主要包括种类、类型、地址等等内容。 标识符语义的内部表示称为机内符(机器内部符号)或语义字。

在我们的PASCAL0语言中，标识符的种类有： 常量种类 类型种类 实在变量 变量种类 赋值形参变量 引用形参变量 实在变量 过函种类 赋值形参变量

标识符语义字的一种结构： ITYPE ICLASS IADDR 地址部分 种类部分 类型部分

ICLASS的具体结构如下： ICLASS: c t v p d f r 常量 类型 形参 变量 过函 引用型形参 域名种类

从实际实现的角度来说，ICLASS的上述结构是很不经济的，因为如果用编码方法，三个二进位就够了。但上述结构直观、便于描述，因此还是采用这种结构。 IADDR部分的具体意义依赖于ICLASS内容。 1. 若ICLASS.c=1，则IADDR是CONSL表地址。

2.若ICLASS.t=1，则IADDR是类型长度 3.若ICLASS.v=1.则IADDR是形如： 的抽象地址，其中LEVEL 是层数，OFF是区距部分。 LEVEL OFF 4.若ICLASS.d=1 ，则是域类型长度 5.若ICLASS.p=1，则IADDR是过函信息表PFINFL的地址，该表的表项结构如下：

LEVEL OFF NOFF MOFF FN ENTRY PARAMS 参数个数 参数 层数 区距 子程序入口地址 DISSPLAY表的区距 处理完临时变量时的第一个可用OFF值

标识符的语义字内容如下图所示 ITYPE ICLASS ADDR tp ’c’ CONSL 常量： 类型： tp ’t’ leng 变量： tp ’v’ l off 域名： tp ’d’ leng PFINFL 过函： tp ’p’

例子：设有PASCAL过程说明段: PROCEDURE p(VAR x:real; y:boolean); CONST pai=3.14; TYPE arr=ARRAY[1…10] OF integer; VAR m:integer; a:arr； FUNCTION f(Z:real;FUNCTION G(U,W: real):real;K:integer):integer; BEGIN………………END

各标识符的语义字分别如下图所示 TYPE CLASS ADDR p： x： y： pai: arr: m: p pfinfp1 2…4 rtp v f r x： 2…5 btp v f y： <3.14> rtp c pai: 10 ainfp t arr: 2…offm itp v m:

a： f： Z： G： K： 2…offa ainfp v pfinfp2 itp p 3…4 f v rtp pfinfp3 f rtp 3…7 f v itp K： 实在过函标识符的OFF值为3，第一个形参的OFF值为4，ainfp表示AINFL表的一表项地址如下图：

AINFL[ainfp]= 1 itp 10 Pinfp1 如所示: 其他的情况类似 PFINFL PARINFL PARAMS ENTRY FN MOFF NOFF OFF LEVEL 2 6 3 1 SEMAN(y) SEMAN(x) 其他的情况类似

9.3 符号表的组织 一、符号表的结构 符号表记为SYMBL，它是标识符的语义表，在语义学中，把这种表称为环境。SYMBL表项的结构如下： SYMBL[i]: IDENT SEMAN 标识符部分 语义字部分

二、定义性标识符 1.CONST Pi=3.14 2.TYPE A… 3.VAR A,B,C 4.PROCEDURE X( A,B ) 5.FUNCINON X( A,B ):Tname 6.RECORD X:T;…;X END

三、标识符的作用域与处理 程序段：PROGRAM…………………END 过程段：PROCEDURE………………END 函数段： FUNCTION………………END 记录类型： RECORD………………END 具体实现方法可分为两种: 真删除法 加标记法

9.4 抽象地址的处理 存储分配分为静态分配与动态分配。 在编译时分配的称静态分配。 在目标程序运行时分配的称动态分配。 编译程序只能确定某种结构的形式地址，称之为抽象地址。

抽象地址通常采用如下结构： level off 层数部分 区距部分 0层 1层 2层 q p 主

每当一个过程说明的子程序被调用时，就要给其中的变量分配一串存贮单元，称这一串单元为该过程的一个活动区。 从第3号单元开始分配给过函名、形参等。

活动区的分配情况如下图所示： 临时变量 局部变量 DISPLAY表 l＋1 形式参数2 形式参数1 过函名 5 4 3 管理信息 0-2

抽象地址的变化规律可图示如下： 实在声明: (l,off) (l,off) (l,off) (l,off+size(T)) (l,off) (l,off) <标号声明部分> <常量声明部分> <类型声明部分> var id:T <过程声明部分> <函数声明部分>

形参入口: (l,off) (l +1,4) proc p( func p( proc P( func F(

形参声明: (l,off) (l ,off+Size(T)) (l,off) (l ,off+1) (l,off) (l ,off+2) Id:T Var id:T func F(…):T proc P(…): 形参出口: (l,off) (l,off+l+1) <形参结束”)”>

其中小写字母的标识符表示实在标识符，大写字母的标识符则表示形参标识符。Size(T)表示类型T的长度。 在形参出口,off+l+1中的l+1表示DISPLAY表的位置。

例：在下面程序中，每个对偶(l,i)表示此刻的LEVEL和OFF值。 (l,10)LABEL 100,200; (l,10)CONST pai=3.14; (l,10)TYPE arr=ARRAY[1…10]OF integer; (l,10)VAR x:integer; (l,11) a:ARRAY[1…5] OF integer; (l,16) FUNCTION f( (l+1,4)VAR x:real; (l+1,5) a:arr; (传值)

):real; BEGIN………………END； (l+1,15)VAR c:arr; (传地址) (l+1,16)PROCEDURE G( ); (l+1,18)FUNCTION F( ):real (l+1,20) ):real; (l+1,20+l+2) (形参结束 off+(l+1)+1 ) BEGIN………………END； (l,16)

9.5 标识符的处理算法 最后得到下列一些表的内容： 例子：设有非形参过程首部(层数为l)。 PROCEDURE P(X,Y:integer; VAR Z: real; PROCEDURE G(U:real；J:integer); FUNCTION F( VAR W:real; FUNCTION H(M:integer):real): bool) 最后得到下列一些表的内容：

Scope[s]: P SEMAN(P) SEMAN(F) SEMAN(G) SEMAN(Z) SEMAN(Y) SEMAN(X) X 5 3 1 PFINFL 表 P SEMAN(P) SEMAN(F) SEMAN(G) SEMAN(Z) SEMAN(Y) SEMAN(X) PFINFL 表 X SEMAN(X) Y SEMAN(Y) Z SEMAN(Z) G SEMAN(G) F SEMAN(F) PFINFL 表 PFINFL 表 9 2 7 2

SEMAN(w) SEMAN(U) SEMAN(H) SEMAN(J) SEMAN(M) PFINFL 表 PFINFL 表 5 1 PFINFL 表 SEMAN(M)