第六章符号表组织课件

内容提要内容提要:第第 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 符号表的地位和功能符号表的地位和功能 符号表是符号表是标识符标识符的的动态语义词典动态语义词典，属于，属于编译中语义分析的知识库；主要内容：编译中语义分析的知识库；主要内容：名字名字 标识符源码，用作查询关键字；标识符源码，用作查询关键字；类型类型-该标识符的数据类型及其相关信息；该标识符的数据类型及其相关信息；种类种类-该标识符在源程序中的语义角色；该标识符在源程序中的语义角色；地址地址 -与值单元相关的一些信息；与值单元相关的一些信息；定义和重定义检查；定义和重定义检查；类型匹配校验；类型匹配校验；数据的越界和溢出检查；数据的越界和溢出检查；值单元存储分配信息；值单元存储分配信息；函数、过程的参数传递与校验；函数、过程的参数传递与校验；符号表符号表的功能的功能标识符标识符四种语四种语义信息义信息6.2 6.2 符号表的组织与管理符号表的组织与管理6.2.1 6.2.1 符号表的工作原理符号表的工作原理 遇遇 定义性标识符定义性标识符(在说明中在说明中)-)-把语义信把语义信息息填填入表中，并修改其入表中，并修改其TOKENTOKEN的指针，使其指向相的指针，使其指向相应的表项：应的表项：（i,)i,)该该标识符标识符符号表项符号表项 遇遇 应用性标识符应用性标识符(在语句中在语句中)-)-查查符号表符号表的相应项，查到后修改其的相应项，查到后修改其TOKENTOKEN的指针，使其指向的指针，使其指向相应的表项：相应的表项：6.2.2 6.2.2 符号表的查询、访问方式符号表的查询、访问方式线性表、顺序表、索引表和散列表，皆可以采用。线性表、顺序表、索引表和散列表，皆可以采用。（i,)i,)该该标识符标识符符号表项符号表项6.2.3 6.2.3 符号表的维护、管理方式符号表的维护、管理方式 一个源文件有若干个函数组成，通常，一个源文件有若干个函数组成，通常，每个函数对每个函数对应一个符号表应一个符号表，此外，还是有一个，此外，还是有一个公用符号表公用符号表；符号表如何管理？往往取决于所属语言的程序结符号表如何管理？往往取决于所属语言的程序结构，就构，就 C C语言来说，可以在内存设置一定长度的语言来说，可以在内存设置一定长度的符号符号表区表区，并建立适当的，并建立适当的索引机制索引机制，访问相应的符号表：，访问相应的符号表：公用公用符号表符号表FUNCTION 2 符号表符号表 FUNCTION 1 符号表符号表现行现行函数符号表函数符号表全局全局 符号表区符号表区局部局部 符号表区符号表区 索引索引机制机制FUNCTION exp(x:REAL;VAR y:INTEGER):REAL;FUNCTION exp(x:REAL;VAR y:INTEGER):REAL;CONST pai=3.14;CONST pai=3.14;TYPE arr=ARRAY1.5,1.10 OF INTEGER;TYPE arr=ARRAY1.5,1.10 OF INTEGER;VAR a:arr;b,a:real;VAR a:arr;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 重定义、重定义、z z 无定义以及下表变量无定义以及下表变量a2,5a2,5的值地址在何处？的值地址在何处？符号表的体系结构设计符号表的体系结构设计 由于标识符的种类不同，导致语义属性也不尽相同；怎由于标识符的种类不同，导致语义属性也不尽相同；怎样组织符号表？下面提供一个符号表的样组织符号表？下面提供一个符号表的体系结构体系结构：SYNBL SYNBL（符号表）（符号表）NAME TYPE CAT ADDRNAME TYPE CAT ADDR PFINFL(PFINFL(函数表函数表)CONSL(CONSL(常量表常量表)AINFL(AINFL(数组表数组表)RINFL(RINFL(结构表结构表)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(常量常量)，t(t(类型类型)，d(d(域名域名)，v,vn,vf(v,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(布尔型布尔型)，a a(数组型数组型)，d d(结构型结构型)，TPOINT(TPOINT(指针指针)根据数据类型不同，指向不同的根据数据类型不同，指向不同的信息表项：信息表项：基本数据类型基本数据类型(i i,r r,c c,b b)nul()nul(空指针空指针)；数组类型数组类型(a a)指向数组表；指向数组表；结构类型结构类型(d d)指向结构表指向结构表;6.3.3 6.3.3 数组表数组表(AINFL)(AINFL)结构：结构：每维占表中一个纪录每维占表中一个纪录 LOW(LOW(数组的下界数组的下界)-)-（C C语言自动设为：语言自动设为：0 0）;UP(UP(数组的上界数组的上界)CTP(CTP(成分类型指针成分类型指针)指针，指向该维数组成分类指针，指向该维数组成分类型型(在类型表中的信息在类型表中的信息););CLEN(CLEN(成分类型的长度成分类型的长度)成分类型的数据所占成分类型的数据所占值单值单元的个数元的个数；这里假定：这里假定：值单元个数值单元个数依依字长字长为单位计算。为单位计算。6.3.4 6.3.4 结构表结构表(RINFL)(RINFL)结构：结构：ID(ID(结构的域名结构的域名)OFF(OFF(区距区距)是是ididk k的值单元首址相对于所在记录值的值单元首址相对于所在记录值区区头位置；区区头位置；约定：约定：offoff1 1=0=0，off off2 2=off=off1 1+LEN(tp+LEN(tp1 1),),off offn n=off=offn-1n-1+LEN(tpLEN(tpn-1n-1)。id idn-1n-1的长度的长度 TP(TP(域成分类型指针域成分类型指针)指针，指向指针，指向ididk k域成分类型域成分类型(在类型表中的信息在类型表中的信息););每个域占表中一个纪录每个域占表中一个纪录6.3.5 6.3.5 函数表函数表(PFINFL)(PFINFL)结构：结构：LEVEL(LEVEL(层次号层次号)该过函静态层次嵌套号该过函静态层次嵌套号,OFF(OFF(区距区距)该过函自身数据区起始单元相对该该过函自身数据区起始单元相对该过函值区区头位置过函值区区头位置 ；FN(FN(参数个数参数个数)该过函的形式参数的个数；该过函的形式参数的个数；PARAM(PARAM(参数表参数表)指针，指向形参表；指针，指向形参表；ENTRY(ENTRY(入口地址入口地址)该函数目标程序首地址该函数目标程序首地址(运运行时填写行时填写)；-过程过程或或函数函数语义信息语义信息6.3.6 6.3.6 其他表其他表()()常量表常量表(CONSL)-(CONSL)-存放相应常量的初值；存放相应常量的初值；长度表长度表(LENL)(LENL)存放相应数据类型所占值单元存放相应数据类型所占值单元个数；个数；活动纪录表活动纪录表(VALL)(VALL)一个函数一个函数(或过程或过程)虚拟虚拟的值单元存储分配表；此分配表在运行调用时才可的值单元存储分配表；此分配表在运行调用时才可用，故称用，故称活动纪录活动纪录。结构：结构：结构：结构：结构结构：6.4 6.4 符号表的构造过程示例符号表的构造过程示例：ENTENT 2 2?v3 v3 vn vnitpitp y y v2 v2 vf vfrtprtp 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 vf vfrtprtp x x f frtprtpexpexpSYNBLSYNBLPFINFLPFINFLVALLVALLCONSLCONSLLENLLENLAINFLAINFLTYPELTYPEL设：整型占设：整型占1个存储单元，个存储单元，【例【例6.26.2】有类型说明】有类型说明:TYPE arr=ARRAY 1.10 OF ARRAY 1.5 OF INTEGER;TYPE arr=ARRAY 1.10 OF ARRAY 1.5 OF INTEGER;试填写符号表。试填写符号表。SYNBLSYNBLTYPELTYPELAINFLAINFLarra110a15itp设：实型占设：实型占8 8个存储单元，整型占个存储单元，整型占4 4个单元，布尔型和字符型占个单元，布尔型和字符型占1 1个单元。个单元。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;RINFLRINFLu0itpuitpd4v4avd10r14x0rtprtprrtpdxdd8y8yrtp81630【例【例6.46.4】试填写符号表。试填写符号表。SYNBLSYNBLTYPELTYPELvf?rtp设：实型占设：实型占8 8个存储单元，整型占个存储单元，整型占4 4个单元，布尔型和字符型占个单元，布尔型和字符型占1 1个单元。个单元。?PROCEDURE P1(VAR x:REAL;y:INTEGER);BEG