第六章符号表组织bfqw

《第六章符号表组织bfqw》由会员分享，可在线阅读，更多相关《第六章符号表组织bfqw（28页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,*,,,内容提要:,第 6 章 符号表组织,---- 语义分析之一,6.1 符号表的地位和作用,6.2 符号表的组织与管理,6.3 符号表的结构设计,6.4 符号表的构造过程示例,6.5 运行时刻存储分配,,,,6.1 符号表的地位和功能,符号表是,标识符,的,动态语义词典,，属于编译中语义分析的知识库；主要内容：,⑴,名字,— 标识符源码，用作查询关键字；,⑵,类型,-- 该标识符的数据类型及其相关信息；,⑶,种类,-- 该标识符在源程序中的语义角色；,⑷,地址,-- 与值单元相关的一些信

2、息；,,① 定义和重定义检查；,② 类型匹配校验；,③ 数据的越界和溢出检查；,④ 值单元存储分配信息；,⑤ 函数、过程的参数传递与校验；…,符号表的功能,标识符,四种语义信息,,,,6.2 符号表的组织与管理,6.2.1 符号表的工作原理,⑴ 遇,定义性标识符,(在说明中)--- 把语义信息,填,入表中，并修改其TOKEN的指针，使其指向相应的表项：,,（i , ),该,标识符,符号表项,⑵ 遇,应用性标识符,(在语句中)---,查,符号表的相应项，查到后修改其TOKEN的指针，使其指向相应的表项：,6.2.2 符号表的查询、访问方式,,,线性表、顺序表、索引表和散列表，皆可以采用。,

3、,（i , ),该,标识符,符号表项,,,,,,6.2.3 符号表的维护、管理方式,,※一个源文件有若干个函数组成，通常，,每个函数对应一个符号表,，此外，还是有一个,公用符号表,；,※符号表如何管理？往往取决于所属语言的程序结构，就 C语言来说，可以在内存设置一定长度的,符号表区,，并建立适当的,索引机制,，访问相应的符号表：,公用,符号表,FUNCTION 2,符号表,FUNCTION 1,符号表,…,现行,函数符号表,,,全局 符号表区,局部 符号表区,,,…,索引机制,,,,FUNCTION exp(x:REAL;VAR y:INTEGER):REAL;,CONST pa

4、i=3.14;,TYPE arr=ARRAY[1..5,1..10] OF INTEGER;,VAR a:arr; b,a:real;,BEGIN … ; a[2,5]:=100; b:=z+6;… END;,6.3 符号表的结构设计,【例6.1】有下列函数过程：,⑴ 需要进符号表的标识符：,exp(,函数,附带信息:类型、参数情况和入口地址…),,pai,(常量),,arr,(类型),,a(,下标变量)，,b,(简单变量)，…,⑵ 怎样检查出：,a,重定义、,z,无定义以及下表变量,a[2,5],的值地址在何处？…,,,※ 符号表的体系结构设计,由于标识符的种类不同，导致语义属性也不尽

5、相同；怎样组织符号表？下面提供一个符号表的,体系结构,：,,SYNBL（符号表）,,NAME TYPE CAT ADDR,,…,PFINFL(函数表),CONSL(常量表),AINFL(数组表),RINFL(结构表),,VALL(活动纪录),,LENL(长度表),,TYPEL（类型表）,,TVAL TPOINT,·,…,名字 类型 种类 地址,token,i ·,,,6.3.1 符号表总表(SYNBL),※ 结构：,NEME(名字)— 标识符源码(或内部码),TYP(类型) – 指针，指向类型表相应项；,CAT(种类) – 种类编码：,f/P(函数)，c(常量)，t(类型)，d(域名

6、)，,v,vn,vf(变量，换名形参，赋值形参)；,ADDR(地址) – 指针，根据标识符的,种类,不同，分别指向：PFINFL,CONSL,LENL,VALL,…,,,,6.3.2 类型表(TAPEL),※ 结构：,TVAL(类码)– 类型代码：,,i,(整型)，,r,(实型)，,c,(字符型)，,b,(布尔型)，,,a,(数组型)，,d,(结构型)，…,TPOINT(指针) – 根据数据类型不同，指向不同的信息表项：,① 基本数据类型(,i,,,r,,,c,,,b,)– nul(空指针)；,② 数组类型(,a,) – 指向数组表；,③ 结构类型(,d,) – 指向结构表;…,,,6.3.

7、3 数组表(AINFL),,※ 结构：,,,每维占表中一个纪录,LOW(数组的下界)--（C语言自动设为：0）;,UP(数组的上界)—,CTP(成分类型指针) – 指针，指向该维数组成分类型(在类型表中的信息);,CLEN(成分类型的长度)– 成分类型的数据所占,值单元的个数,；,※ 这里假定：,值单元个数,依,字长,为单位计算。,,,6.3.4 结构表(RINFL),,※ 结构：,,,,ID(结构的域名)—,OFF(区距)—是id,k,的值单元首址相对于所在记录值区区头位置；,约定：off,1,=0，,off,2,= off,1,+LEN(tp,1,), ……,off,n,= off,n

8、-1,+,LEN(tp,n-1,),。,id,n-1,的长度,TP(域成分类型指针) – 指针，指向id,k,域成分类型(在类型表中的信息);,每个域占表中一个纪录,,,6.3.5 函数表(PFINFL),※ 结构：,LEVEL(层次号) –该过函静态层次嵌套号,,OFF(区距) –该过函自身数据区起始单元相对该过函值区区头位置 ；,FN(参数个数) – 该过函的形式参数的个数；,PARAM(参数表) – 指针，指向形参表；,ENTRY(入口地址) – 该函数目标程序首地址(运行时填写)；,----,,过程,或,函数,语义信息,,,,,,6.3.6 其他表(…),,⑴ 常量表(CONSL

9、)-- 存放相应常量的初值；,⑵ 长度表(LENL) – 存放相应数据类型所占值单元个数；,⑶ 活动纪录表(VALL) – 一个函数(或过程)虚拟的值单元存储分配表；此分配表在运行调用时才可用，故称,活动纪录,。,※ 结构：,,※ 结构：,,※,结构,：,…,,,,,,,,,,,,6.4,符号表的构造过程示例,：,,,ENT,,…,2,,?,v3,vn,itp,y,v2,vf,rtp,x,临时变量值区,b值,y值,数组a值区,管理区,exp值,x值,链接表,3.14,50,1,itp,10,1,10,,5,1,,,a,a,c,i,r,b,v1,v2,v3,v4,v5,,t,,arr,v4,v,

10、,a,,c,rtp,pai,v5,v,rtp,b,v3,vn,itp,y,v2,vf,rtp,x,,f,rtp,exp,SYNBL,PFINFL,VALL,CONSL,LENL,,AINFL,TYPEL,设：整型占1个存储单元，,,,,【例6.2】有类型说明:,,TYPE arr = ARRAY [1..10] OF ARRAY [1..5] OF INTEGER;,,试填写符号表。,,SYNBL,TYPEL,AINFL,arr,a,1,10,a,1,5,i,tp,设：实型占8个存储单元，整型占4个单元，布尔型和字符型占1个单元。,,4,20,t,LENL,200,,,,【例6.3】有类型说明

11、:,试填写符号表。,,SYNBL,TYPEL,AINFL,rec,d,1,10,d,b,tp,设：实型占8个存储单元，整型占4个单元，布尔型和字符型占1个单元。,,1,t,LENL,TYPE rec = RECORD,u: INTEGER;,v: ARRAY [1..10] OF BOOLEAN;,r: RECORD x, y : REAL END,END;,RINFL,u,0,i,tp,u,i,tp,d,4,v,4,a,v,d,10,r,14,x,0,r,tp,r,tp,r,r,tp,d,x,d,d,8,y,8,y,r,tp,8,16,30,,,,,【例6.4】,试填写符号表。,,SYNBL

12、,TYPEL,v,f,?,r,tp,设：实型占8个存储单元，整型占4个单元，布尔型和字符型占1个单元。,,?,PROCEDURE P1(VAR x: REAL; y: INTEGER);,……,BEGIN …… END;,PFINFL,r,tp,P1,r,tp,p,x,v,n,y,2,y,r,tp,有过程说明:,设P1所在层LEVEL=1，即所定义的层LEVEL=2,,1,P1,2,2,?,Entry,x,v,n,?,v,f,?,注,：,,？—— 该标识符的值单元首址，,为相对地址（LEVEL, offset）,,LEVEL ——该标识符,所在层次号，,,offset ——区距，,存

13、储分配时可定,。,,,,6.5 运行时刻存储分配,※,解决的问题：,标识符,变量的,地址分配,与对它们的访问。,6.5.1,标识符值单元分配,,值单元分配分两类：,,在,编译阶段,即可完成真实的地址分配。在编译时对所有数据对象分配固定的存储单元，且在运行是始终保持不变。,1.静态分配,,2.动态分配,指在运行时刻进行的值单元分配，在编译时只能进行相对地址分配。,,·栈式动态分配；,,·堆式动态分配。,,值单元分配是以过程函数为单位的。,,注：,,,6.5.2,活动记录,,,1.三个概念,过程：,一个可执行模块，过程或函数，通常完成特定的功能。,活动：,过函的一次执行。每执行一次过程体，则产生

14、该过函的一个活动。,活动记录：,一个有,结构,的连续存储块。用来存储过函一次执行中所需要的信息。,,如果不支持可变数据结构，活动记录的体积是可以在编译时确定的。,,活动记录仅是一种,存储映像,，编译程序所进行的运行时刻存储分配是在符号表中进行的。,,,,,,6.5.2,活动记录（续）,,2.活动记录的结构,VALL,TOP,SP,,,连接数据,局部数据,（1）连接数据区,·返回地址,：,,·动态链,：,,,指向调用该过程的主调程序的活动记录的指针；,,·静态链,：,,指向静态直接外层活动记录的指针。,,（2）形式单元,,用来存放实参的值或地址。,,（3）局部数据区,,用来存放局部变量、内情向量

15、、临时单元。,（4）栈指针,,SP,— 指向现行过程活动记录的起点，即第一个单元；,,TOP,—指向（已占用）栈顶单元，即活动记录的最后一个单元。,,,,,,6.5.3,简单的栈式存储分配,,没有分程序结构，过程定义不允许嵌套，但允许过程的递归调用。,·以C语言为例:,1．C语言程序的存储组织,,【例6.5】,C语言过程调用关系：,Main( ),,Q( ),,R( ),,,则，活动记录栈状态为：,TOP,SP,,2．C的活动记录,,Old SP,值，即前一活动记录的地址；,,其中：,SP,TOP,,,6.5.4,嵌套过程语言的栈式存储分配,,·过程嵌套的一个关键问题：,标识符的作用域问题

16、,,。,,,,标识符的作用范围往往与它所处的过程相关，也就是说，同一个标识符，在不同的程序段里，代表不同的对象，具有不同的性质，因此要分配不同的存储空间。,,·标识符的有效范围：,,（1）在外层未定义，而在内层定义的，服从内层定义；,（2）在外层已定义，而在内层未定义的，服从全范围；,（3）在外层已定义，而在内层也定义的，在外层服从外层定义，在内层服从内层定义。,服从最小作用域原理,；,1.标识符的作用域,,,2.活动记录,6.5.4,嵌套过程语言的栈式存储分配（续）,,·问题的提出：,过程,Q,可能会引用到它的,任意外层过程,的最新活动记录中的某些数据。,为了在活动记录中查找这些非局部名字所

17、对应的存储空间，过程,Q,运行时必须设法跟踪它的,所有外层过程,的最新活动记录的地址。,·解决问题的思想：,·解决方案：,活动记录中增加,静态链,！使其,指向直接外层,的,最新活动记录的首地址,；,,SP,TOP,,连接数据,,,,,,,,3.嵌套层次显示表(display)和活动记录结构,(1)连接数据区：,用于访问外层的变量,,Old SP,返回地址,全局Display地址,参数个数,……,形式单元,,……,显示区表,(Display),……,局部变量,……,内情向量,……,临时单元,SP,TOP,0,1,2,0～2,；,,连接数据,,·全局display地址 — 主调过程的显示区表首址；

18、,·老SP — 主调过程的活动记录首址；,(2)参数个数：,3,；,3,(3)形参值单元区：,4,入口为4,；,·换名形参（vn）—,分配2个单元（地址传递）；,·赋值形参（vf）— 按相应类型长度分配；,,l为层次号，包含,直接外层,嵌套的l个过程的活动记录的首址，再加上本过程的活动记录首址；,(4)显示区表(display)：,占l+1个单元,；,,l+1,·类型标识符、常量标识符等不分配值单元；,(5)局部变量区：,入口为off + l + 2,；,·off为形参区最后一个值单元地址；,·局部变量值单元按相应类型长度分配地址；,编译系统定义的变量，按局部变量值单元分配原则分配地址；,(6

19、)临时变量区：,,,,,4. Display表的建立,,则Q与R的display表的关系如下:,,设过程调用关系为,Q( ),,,,R( ),，且,R( ),的层次号为,l,，,Old SP,返回地址,全局Display地址,参数个数,……,形式单元,,……,显示区表,(Display),……,局部变量,……,内情向量,……,临时单元,SP,TOP,Old SP,返回地址,全局Display地址,参数个数,……,形式单元,,……,显示区表,(Display),……,局部变量,……,内情向量,……,临时单元,Q的活动记录,,R的活动记录,,,拷贝l个单元,,,,拷贝自身的SP,,l+1个单元,

20、,,5.,值单元的地址分配,,·值单元分配是依据活动记录的结构，在符号表中进行的。,,设有Pascal程序片段如下，P1所在层level=2；,【例6.6】,PROCEDURE P1( x: REAL; VAR y: BOOLEAN );,CONST pai=3.14;,TYPE arr=ARRAY [1..10] OF INTEGER;,VAR m: INTEGER;,a: arr;,l: REAL;,FUNCTION F1( z: REAL; k: INTEGER ): REAL;,BEGIN …… END;,……;,BEGIN,……;,END;,试给出符号表组织及值单元分配情况。,,,,

21、设：,(1),实型占8个存储单元，整型占4个单元，布尔型和字符型占1个单元。,,(2),换名形参vn分配2个单元，赋值形参vf按相应类型长度分配；,,,,接上页：,SYNBL,TYPEL,PFINFL,P1的VALL,CONSL,LENL,AINFL,·过程P1定义的层次为l=3,0,1,2,3,4-11,12-13,14,15,16,17,18-21,22-61,P1,p,3,3,2,Entry,,x,x,2,r,tp,v,f,(3,4),x,r,tp,v,f,(3,4),(3,12),y,y,b,tp,b,tp,v,n,v,n,y,(3,12),(4,4),pai,r,tp,c,3.14,

22、arr,a,1,10,i,tp,4,t,40,m,i,tp,v,m,(3,18),a,v,a,(3,22),l,r,tp,v,l,62-69,(3,62),F1,r,tp,f,4,3,2,Entry,z,z,k,k,r,tp,r,tp,i,tp,i,tp,v,f,v,f,v,f,v,f,(4,4),(4,12),(4,12),程序片段,,,※ 一个函数过程的符号表组织,,FUNCTION exp(x:REAL;VAR y:INTEGER):REAL;,CONST pai=3.14;,TYPE arr=ARRAY[1..5,1..10] OF INTEGER;,VAR a:arr; b:real;,BEGIN … ; a[2,5]:=100; b:=6;… END;,,,① exp , rtp , f ,,函数表,,② x , rtp , vf ,,,活动记录,,,④ pai , rtp , c ,,常数表,,,⑤ arr , atp , t ,,长度表,,③ y , itp , vn ,,,活动记录,,⑥ a , atp , v ,,,活动记录,,⑦ b , rtp , v ,,,活动记录,,,,,,,,,,,,,谢谢收看！,再见,,,