第六章符号表组织

1、内容提要内容提要: :第第 6 6 章章 符号表组织符号表组织 - - 语义分析之一语义分析之一6.1 6.1 符号表的地位和作用符号表的地位和作用6.2 6.2 符号表的组织与管理符号表的组织与管理6.3 6.3 符号表的结构设计符号表的结构设计6.4 6.4 符号表的构造过程示例符号表的构造过程示例 6.5 6.5 运行时刻存储分配运行时刻存储分配6.1 6.1 符号表的地位和功能符号表的地位和功能 符号表是符号表是标识符标识符的的动态语义词典动态语义词典，属于，属于编译中语义分析的知识库；主要内容：编译中语义分析的知识库；主要内容： 名字名字 标识符源码，用作查询关键字；标识符源码，用作

2、查询关键字； 类型类型 - - 该标识符的数据类型及其相关信息；该标识符的数据类型及其相关信息； 种类种类 - - 该标识符在源程序中的语义角色；该标识符在源程序中的语义角色； 地址地址 - - 与值单元相关的一些信息；与值单元相关的一些信息； 定义和重定义检查；定义和重定义检查； 类型匹配校验；类型匹配校验； 数据的越界和溢出检查；数据的越界和溢出检查； 值单元存储分配信息；值单元存储分配信息； 函数、过程的参数传递与校验；函数、过程的参数传递与校验； 符号表符号表的功能的功能标识符标识符四种语四种语义信息义信息6.2 6.2 符号表的组织与管理符号表的组织与管理6.2.1 6.2.1 符号

3、表的工作原理符号表的工作原理 遇遇 定义性标识符定义性标识符( (在说明中在说明中)- )- 把语义信把语义信息息填填入表中，并修改其入表中，并修改其TOKENTOKEN的指针，使其指向相的指针，使其指向相应的表项：应的表项：（i , )i , )该该标识符标识符符号表项符号表项 遇遇 应用性标识符应用性标识符( (在语句中在语句中)- )- 查查符号表符号表的相应项，查到后修改其的相应项，查到后修改其TOKENTOKEN的指针，使其指向的指针，使其指向相应的表项：相应的表项：6.2.2 6.2.2 符号表的查询、访问方式符号表的查询、访问方式线性表、顺序表、索引表和散列表，皆可以采用。线性表

4、、顺序表、索引表和散列表，皆可以采用。（i , )i , )该该标识符标识符符号表项符号表项6.2.3 6.2.3 符号表的维护、管理方式符号表的维护、管理方式 一个源文件有若干个函数组成，通常，一个源文件有若干个函数组成，通常，每个函数对每个函数对应一个符号表应一个符号表，此外，还是有一个，此外，还是有一个公用符号表公用符号表； 符号表如何管理？往往取决于所属语言的程序结符号表如何管理？往往取决于所属语言的程序结构，就构，就 C C语言来说，可以在内存设置一定长度的语言来说，可以在内存设置一定长度的符号符号表区表区，并建立适当的，并建立适当的索引机制索引机制，访问相应的符号表：，访问相应的符

5、号表：公用公用符号表符号表FUNCTION 2 符号表符号表 FUNCTION 1 符号表符号表现行现行函数符号表函数符号表全局全局 符号表区符号表区局部局部 符号表区符号表区 索引索引机制机制FUNCTION exp(x:REAL;VAR y:INTEGER):REAL;FUNCTION exp(x:REAL;VAR y:INTEGER):REAL; CONST CONST paipai=3.14;=3.14; TYPE TYPE arrarr=ARRAY1.5,1.10 OF INTEGER;=ARRAY1.5,1.10 OF INTEGER; VAR VAR a:arra:arr; b,

6、a:real; b,a:real; BEGIN ; a2,5:=100; b:=z+6; END; BEGIN ; a2,5:=100; b:=z+6; END;6.3 6.3 符号表的结构设计符号表的结构设计【例【例6.16.1】有下列函数过程：】有下列函数过程： 需要进符号表的标识符：需要进符号表的标识符： exp(exp(函数函数, ,附带信息附带信息: :类型、参数情况和入口地址类型、参数情况和入口地址),),paipai( (常量常量),),arrarr( (类型类型),),a(a(下标变量下标变量) )，b b( (简单变量简单变量) )， 怎样检查出：怎样检查出：a a 重定义、

7、重定义、z z 无定义以及下表变量无定义以及下表变量a2,5a2,5的值地址在何处？的值地址在何处？ 符号表的体系结构设计符号表的体系结构设计 由于标识符的种类不同，导致语义属性也不尽相同；怎由于标识符的种类不同，导致语义属性也不尽相同；怎样组织符号表？下面提供一个符号表的样组织符号表？下面提供一个符号表的体系结构体系结构： SYNBLSYNBL（符号表）符号表） NAME TYPE CAT ADDRNAME TYPE CAT ADDR PFINFL(PFINFL(函数表函数表) )CONSL(CONSL(常量表常量表) ) AINFL(AINFL(数组表数组表) )RINFL(RINFL(结

8、构表结构表) )VALL(VALL(活动纪录活动纪录) )LENL(LENL(长度表长度表) )TYPELTYPEL（类型表）类型表） TVAL TPOINTTVAL TPOINT名字名字 类型类型 种类种类 地址地址 tokentoken i i 6.3.1 6.3.1 符号表总表符号表总表(SYNBL)(SYNBL) 结构：结构：NEME(NEME(名字名字) ) 标识符源码标识符源码( (或内部码或内部码) )TYP(TYP(类型类型) ) 指针，指向类型表相应项；指针，指向类型表相应项；CAT(CAT(种类种类) ) 种类编码：种类编码： f/P(f/P(函数函数) )，c(c(常量常

9、量) )，t(t(类型类型) )，d(d(域名域名) )， v,vn,vfv,vn,vf( (变量，换名形参，赋值形参变量，换名形参，赋值形参) )；ADDR(ADDR(地址地址) ) 指针，根据标识符的指针，根据标识符的种类种类不同，分不同，分别指向：别指向：PFINFL,CONSL,LENL,VALL,PFINFL,CONSL,LENL,VALL,6.3.2 6.3.2 类型表类型表(TAPEL)(TAPEL) 结构：结构：TVAL(TVAL(类码类码) ) 类型代码：类型代码： i i( (整型整型) )，r r( (实型实型) )，c c( (字符型字符型) )，b b( (布尔型布尔

10、型) )， a a( (数组型数组型) )，d d( (结构型结构型) )，TPOINT(TPOINT(指针指针) ) 根据数据类型不同，指向不同的根据数据类型不同，指向不同的信息表项：信息表项： 基本数据类型基本数据类型( (i i, ,r r, ,c c, ,b b) ) nulnul( (空指针空指针) )； 数组类型数组类型( (a a) ) 指向数组表；指向数组表； 结构类型结构类型( (d d) ) 指向结构表指向结构表; ; 6.3.3 6.3.3 数组表数组表(AINFL)(AINFL) 结构：结构：每维占表中一个纪录每维占表中一个纪录 LOW(LOW(数组的下界数组的下界)-

11、)-（C C语言自动设为：语言自动设为：0 0）; ; UP( UP(数组的上界数组的上界) CTP( CTP(成分类型指针成分类型指针) ) 指针，指向该维数组成分类指针，指向该维数组成分类型型( (在类型表中的信息在类型表中的信息);); CLEN( CLEN(成分类型的长度成分类型的长度) ) 成分类型的数据所占成分类型的数据所占值单值单元的个数元的个数； 这里假定：这里假定：值单元个数值单元个数依依字长字长为单位计算。为单位计算。6.3.4 6.3.4 结构表结构表(RINFL)(RINFL) 结构：结构： ID(ID(结构的域名结构的域名) OFF( OFF(区距区距)是是ididk

12、 k的值单元首址相对于所在记录值的值单元首址相对于所在记录值区区头位置；区区头位置；约定：约定：offoff1 1=0=0， offoff2 2= off= off1 1+LEN(tp+LEN(tp1 1), ), offoffn n= off= offn-1n-1+ +LEN(tpLEN(tpn-1n-1) )。 ididn-1n-1的长度的长度 TP(TP(域成分类型指针域成分类型指针) ) 指针，指向指针，指向ididk k域域成分类型成分类型( (在类型表中的信息在类型表中的信息););每个域占表中一个纪录每个域占表中一个纪录6.3.5 6.3.5 函数表函数表(PFINFL)(PFI

13、NFL) 结构：结构： LEVEL(LEVEL(层次号层次号) ) 该过函静态层次嵌套号该过函静态层次嵌套号, , OFF( OFF(区距区距) ) 该过函自身数据区起始单元相对该该过函自身数据区起始单元相对该过函值区区头位置过函值区区头位置 ； FN(FN(参数个数参数个数) ) 该过函的形式参数的个数；该过函的形式参数的个数； PARAM(PARAM(参数表参数表) ) 指针，指向形参表；指针，指向形参表； ENTRY(ENTRY(入口地址入口地址) ) 该函数目标程序首地址该函数目标程序首地址( (运运行时填写行时填写) )； - 过程过程或或函数函数语义信息语义信息6.3.6 6.3.

14、6 其他表其他表()() 常量表常量表(CONSL)- (CONSL)- 存放相应常量的初值；存放相应常量的初值； 长度表长度表(LENL) (LENL) 存放相应数据类型所占值单元存放相应数据类型所占值单元个数；个数； 活动纪录表活动纪录表(VALL) (VALL) 一个函数一个函数( (或过程或过程) )虚拟虚拟的值单元存储分配表；此分配表在运行调用时才可的值单元存储分配表；此分配表在运行调用时才可用，故称用，故称活动纪录活动纪录。 结构：结构： 结构：结构： 结构结构： 6.4 6.4 符号表的构造过程示例符号表的构造过程示例： ENTENT 2 2 ? ? v3 v3 vnvnitpi

15、tp y y v2 v2 vfvfrtprtp x x临时变量值区临时变量值区 b值 y值 数组a值区 管理区 exp值 x值 链接表3.143.14 50 50 1 1itpitp10101 110105 51 1 a a a ac,i,r,bc,i,r,bv1v1v2v2v3v3v4v4v5v5 t t arrarr v4 v4 v v a a c crtprtppaipai v5 v5 v vrtprtp b b v3 v3vnvnitpitp y y v2 v2 vfvfrtprtp x x f frtprtpexpexpSYNBLSYNBLPFINFLPFINFLVALLVALLCO

16、NSLCONSLLENLLENLAINFLAINFLTYPELTYPEL设：整型占设：整型占1个存储单元，个存储单元，【例例6.26.2】有类型说明有类型说明: : TYPE TYPE arrarr = ARRAY 1.10 OF ARRAY 1.5 OF INTEGER; = ARRAY 1.10 OF ARRAY 1.5 OF INTEGER; 试填写符号表。试填写符号表。 SYNBLSYNBLTYPELTYPELAINFLAINFLarra110a15itp设：实型占设：实型占8 8个存储单元，整型占个存储单元，整型占4 4个单元，布尔型和字符型占个单元，布尔型和字符型占1 1个单元。个

17、单元。 420tLENLLENL200【例例6.36.3】有类型说明有类型说明: :试填写符号表。试填写符号表。 SYNBLSYNBLTYPELTYPELAINFLAINFLrecd110dbtp设：实型占设：实型占8 8个存储单元，整型占个存储单元，整型占4 4个单元，布尔型和字符型占个单元，布尔型和字符型占1 1个单元。个单元。 1 tLENLLENLTYPE rec = RECORD u: INTEGER; v: ARRAY 1.10 OF BOOLEAN; r: RECORD x, y : REAL END END; RINFLRINFLu0itpuitpd4v4avd10r14x0r

18、tprtprrtpdxdd8y8yrtp81630【例【例6.46.4】试填写符号表。试填写符号表。 SYNBLSYNBLTYPELTYPELvf?rtp设：实型占设：实型占8 8个存储单元，整型占个存储单元，整型占4 4个单元，布尔型和字符型占个单元，布尔型和字符型占1 1个单元。个单元。 ? PROCEDURE P1(VAR x: REAL; y: INTEGER); BEGIN END; PFINFLPFINFLrtpP1rtppxvny2yrtp有过程说明有过程说明: :设设P1P1所在层所在层LEVEL=1LEVEL=1，即所定义的层即所定义的层LEVEL=2,LEVEL=2,1P1

19、22?Entryxvn? vf? 注注： ？ 该标识符的值单元首址，该标识符的值单元首址， 为相对地址（为相对地址（LEVEL, offsetLEVEL, offset） LEVEL LEVEL 该标识符该标识符所在层次号，所在层次号， offset offset 区距，区距，存储分配时可定存储分配时可定。6.5 6.5 运行时刻存储分配运行时刻存储分配解决的问题：解决的问题：标识符标识符变量的变量的地址分配地址分配与对它们的访问。与对它们的访问。 6.5.1 6.5.1 标识符值单元分配标识符值单元分配 值单元分配分两类：值单元分配分两类： 在在编译阶段编译阶段即可完成真实的地址分配。在编译

20、时即可完成真实的地址分配。在编译时对所有数据对象分配固定的存储单元，且在运行是始对所有数据对象分配固定的存储单元，且在运行是始终保持不变。终保持不变。1.1.静态分配静态分配2.2.动态分配动态分配 指在运行时刻进行的值单元分配，在编译时只能进指在运行时刻进行的值单元分配，在编译时只能进行相对地址分配。行相对地址分配。 栈式动态分配；栈式动态分配； 堆式动态分配。堆式动态分配。 值单元分配是以过程函数为单位的。值单元分配是以过程函数为单位的。 注：注：6.5.2 6.5.2 活动记录活动记录 1.三个概念三个概念过程：过程：一个可执行模块，过程或函数，通常完成特一个可执行模块，过程或函数，通常

21、完成特定的功能。定的功能。活动：活动： 过函的一次执行。每执行一次过程体，则产过函的一次执行。每执行一次过程体，则产生该过函的一个活动。生该过函的一个活动。活动记录：活动记录： 一个有一个有结构结构的连续存储块。用来存储过的连续存储块。用来存储过函一次执行中所需要的信息。函一次执行中所需要的信息。 如果不支持可变数据结构，活动记录的体积是如果不支持可变数据结构，活动记录的体积是可以在编译时确定的。可以在编译时确定的。 活动记录仅是一种活动记录仅是一种存储映像存储映像，编译程序所进行，编译程序所进行的运行时刻存储分配是在符号表中进行的。的运行时刻存储分配是在符号表中进行的。 6.5.2 6.5.

22、2 活动记录（续）活动记录（续） 2.2.活动记录的结构活动记录的结构VALLVALLTOPTOPSPSP连接数据连接数据局部数据局部数据（1 1）连接数据区）连接数据区返回地址返回地址： 动态链动态链： 指向调用该过程的主调程序的指向调用该过程的主调程序的活动记录的指针；活动记录的指针； 静态链静态链： 指向静态直接外层活动记录的指针。指向静态直接外层活动记录的指针。 （2 2）形式单元）形式单元用来存放实参的值或地址。用来存放实参的值或地址。 （3 3）局部数据区）局部数据区 用来存放局部变量、内情向量、用来存放局部变量、内情向量、临时单元。临时单元。 （4 4）栈指针）栈指针SPSP 指

23、向现行过程活动记指向现行过程活动记录的起点，即第一个单元；录的起点，即第一个单元； TOPTOP 指向（已占用）栈顶指向（已占用）栈顶单元，即活动记录的最后一单元，即活动记录的最后一个单元。个单元。 6.5.3 6.5.3 简单的栈式存储分配简单的栈式存储分配 没有分程序结构，过程定义不允许嵌套，没有分程序结构，过程定义不允许嵌套，但允许过程的递归调用。但允许过程的递归调用。 以以C C语言为例语言为例: :1 1C C语言程序的存储组织语言程序的存储组织 【例例6.56.5】 C C语言过程调用关系：语言过程调用关系：Main( )Main( ) Q( )Q( ) R( ) R( ) 则，活

24、动记录栈状态为：则，活动记录栈状态为：TOPTOPSPSP2 2C C的活动记录的活动记录 Old SPOld SP值，即前一活动记录的地址；值，即前一活动记录的地址； 其中：其中：SPSPTOPTOP6.5.4 6.5.4 嵌套过程语言的栈式存储分配嵌套过程语言的栈式存储分配 过程嵌套的一个关键问题：过程嵌套的一个关键问题：标识符的作用域问题标识符的作用域问题 。 标识符的作用范围往往与它所处的过程相关，也就标识符的作用范围往往与它所处的过程相关，也就是说，同一个标识符，在不同的程序段里，代表不同的是说，同一个标识符，在不同的程序段里，代表不同的对象，具有不同的性质，因此要分配不同的存储空间

25、。对象，具有不同的性质，因此要分配不同的存储空间。 标识符的有效范围：标识符的有效范围：（1 1）在外层未定义，而在内层定义的，服从内层定义；）在外层未定义，而在内层定义的，服从内层定义；（2 2）在外层已定义，而在内层未定义的，服从全范围；）在外层已定义，而在内层未定义的，服从全范围；（3 3）在外层已定义，而在内层也定义的，在外层服从）在外层已定义，而在内层也定义的，在外层服从外层定义，在内层服从内层定义。外层定义，在内层服从内层定义。服从最小作用域原理服从最小作用域原理；1.1.标识符的作用域标识符的作用域2.2.活动记录活动记录6.5.4 6.5.4 嵌套过程语言的栈式存储分配（续）嵌

26、套过程语言的栈式存储分配（续） 问题的提出：问题的提出： 过程过程Q Q可能会引用到它的可能会引用到它的任意外层过程任意外层过程的最新活动记的最新活动记录中的某些数据。录中的某些数据。 为了在活动记录中查找这些为了在活动记录中查找这些非局部名字所对应的存储空间，非局部名字所对应的存储空间，过程过程Q Q运行时必须设法跟踪它的运行时必须设法跟踪它的所所有外层过程有外层过程的最新活动记录的地的最新活动记录的地址。址。 解决问题的思想：解决问题的思想：解决方案：解决方案： 活动记录中增加活动记录中增加静态链静态链！使！使其其指向直接外层指向直接外层的的最新活动记录最新活动记录的首地址的首地址； SP

27、SPTOPTOP连接数据连接数据3.3.嵌套层次显示表嵌套层次显示表(display)(display)和活动记录结构和活动记录结构(1)(1)连接数据区：连接数据区：用于访问外层的变量用于访问外层的变量 Old SPOld SP返回地址返回地址全局全局DisplayDisplay地址地址参数个数参数个数 形式单元形式单元 显示区表显示区表(Display)(Display) 局部变量局部变量 内情向量内情向量 临时单元临时单元SPSPTOPTOP0 01 12 20 02 2；连接数据 全局全局displaydisplay地址地址 主调过程的显示区表首址；主调过程的显示区表首址；老老SP S

28、P 主调过程的活动记录首址；主调过程的活动记录首址；(2)(2)参数个数：参数个数：3 3；3 3(3)(3)形参值单元区：形参值单元区：4 4入口为入口为4 4；换名形参（换名形参（vnvn） 分配分配2 2个单元（地址传递）；个单元（地址传递）；赋值形参（赋值形参（vfvf） 按相应类型长度分配；按相应类型长度分配； l l为层次号，包含为层次号，包含直接外层直接外层嵌套的嵌套的l l个过个过程的活动记录的首址，再加上本过程的活程的活动记录的首址，再加上本过程的活动记录首址；动记录首址；(4)(4)显示区表显示区表(display)(display)： 占占l+1l+1个单元个单元；l+1

29、l+1类型标识符、常量标识符等不分配值单元；类型标识符、常量标识符等不分配值单元；(5)(5)局部变量区：局部变量区：入口为入口为off + l + 2off + l + 2；offoff为形参区最后一个值单元地址；为形参区最后一个值单元地址；局部变量值单元按相应类型长度分配地址；局部变量值单元按相应类型长度分配地址；编译系统定义的变量，按局部变量值单元分配原则分配地址；编译系统定义的变量，按局部变量值单元分配原则分配地址； (6)(6)临时变量区：临时变量区：4. Display4. Display表的建立表的建立 则则Q Q与与R R的的displaydisplay表的关系如下表的关系如下

30、: : 设过程调用关系为设过程调用关系为Q( )Q( ) R( )R( )，且，且R( )R( )的层次号为的层次号为l l，Old SPOld SP返回地址返回地址全局全局DisplayDisplay地址地址参数个数参数个数 形式单元形式单元 显示区表显示区表(Display)(Display) 局部变量局部变量 内情向量内情向量 临时单元临时单元SPSPTOPTOPOld SPOld SP返回地址返回地址全局全局DisplayDisplay地址地址参数个数参数个数 形式单元形式单元 显示区表显示区表(Display)(Display) 局部变量局部变量 内情向量内情向量 临时单元临时单元Q

31、 Q的活动记录的活动记录 R R的活动记录的活动记录 拷贝拷贝l个单元个单元 拷贝自身的拷贝自身的SPSPl+1l+1个单元个单元5.5.值单元的地址分配值单元的地址分配 值单元分配是依据活动记录的结构，在符号表中进行的。值单元分配是依据活动记录的结构，在符号表中进行的。 设有设有PascalPascal程序片段如下，程序片段如下，P1P1所在层所在层level=2level=2；【例例6.66.6】PROCEDURE P1( x: REAL; VAR y: BOOLEAN );PROCEDURE P1( x: REAL; VAR y: BOOLEAN ); CONST CONST paipa

32、i=3.14;=3.14; TYPE TYPE arrarr=ARRAY 1.10 OF INTEGER;=ARRAY 1.10 OF INTEGER; VAR m: INTEGER; VAR m: INTEGER; a a: : arrarr; ; l l: REAL;: REAL; FUNCTION F1( z: REAL; k: INTEGER ): REAL; FUNCTION F1( z: REAL; k: INTEGER ): REAL; BEGIN END; BEGIN END; ; ; BEGIN BEGIN ; ; END; END; 试给出符号表组织及值单元分配情况。试给出符号表组织及值单元分配情况。 设：设：(1)(1)实型占实型占8 8个存储单元，整型占个存储单元，整型占4 4个单元，布尔型和字符型占个单元，布尔型和字符型占1 1个单元。个单元。 (2)(2)换名形参换名形参vn分配分配2个单元，赋值形参个单元，赋值形参vf按相应类型长度分配；按相应类型长度分配；接上页：接上页：SYNBLSYNBLTYPELTYPELPFINFLPFINFLP1P1的的VALLVALLCONSLCONSLLENLLENLAINFLAINFL过程过程P