符号表 NEW解析课件.ppt

《符号表 NEW解析课件.ppt》由会员分享，可在线阅读，更多相关《符号表 NEW解析课件.ppt（73页珍藏版）》请在三一办公上搜索。

1、主要内容,符号表的介绍说明语句的翻译数组元素的引用,符号表,符号表是连接声明与引用的桥梁。一个名字在声明时，相关信息被填写进符号表，而在引用时，根据符号表中的信息生成相应的可执行语句。如何有效记录各类符号的信息，以便于在编译的各个阶段对符号表进行快速、有效的查找、插入、修改、删除等操作，是符号表设计的基本目标之一。,符号表的管理贯穿整个编译过程，既涉及到前端，也涉及后端，尤其与后端的存储空间分配有密切联系。符号表的内容一般仅在编译时使用，如果名字的具体信息需要在运行时确定或使用，则符号表的部分内容还要保留并运行，例如动态数组和跟踪调试信息等。合理组织符号表的内容，以适应不同阶段的需要，也是符号

2、表设计需要考虑的问题之一。,符号表的作用,符号表用来存放程序设计语言中出现的有关标识符的属性和特征。符号表在整个编译期间的作用可归纳为以下几个方面：1、将标识符的名字及属性登陆到符号表中 在分析说明语句的时候，编译程序根据说明语句信息将标识符的相应属性，例如标识符的类型：实型、整型，布尔型等；标识符的种属：数组名，变量名，过程名，函数名等登录到符号表中。,2、辅助上下文语义的正确性检查 例如对运算对象和运算符进行类型检查，对变量进行先定义后使用检查等。通过符号表中的属性记录可进行上述语义检查。,作用域,public class Foo private int value=39;public i

3、nt test()int b=3;return value+b;public void setValue(int c)value=c;int d=c;c=c+d;value=c;public class Bar private int value=42;public void setValue(int c)value=c;,scope of value,scope of b,scope of c,scope of c,scope of value,scope of d,符号表,(Foo),(Test),(setValue),(setValue-block),符号表lookup,(Foo),(T

4、est),(setValue),(setValue-block),public void setValue(int c)value=c;int d=c;c=c+d;value=c;,Lookup(value),Symbol Table Lookup,(Foo),(Test),(setValue),(setValue-block),public void setValue(int c)value=c;int d=c;c=c+d;myValue=c;,Lookup(myValue),Error!,符号表操作,插入插入新的符号插入到当前作用域中查询lookup 在符号表中找到一个符号可能引起到父表中

5、查找当符号没有找到的时候报错符号表类似一个仓库,class,之一：可通过遍历AST构建符号表,MethodDecl,MethodDecl,ClassDecl,root,name=foo,name=setValue,name=test,(some details omitted),globals,foo,test,setValue,foo,test,method,setValue,method,b,var,c,var,block1,d,var,3、辅助目标代码生成 在目标代码生成阶段，符号表是数据存储分配的依据。要形成能运行的目标代码，需要对程序中应用的标识符分配存储单元，而存储单元的分配与标识

6、符属性相关，与属性相关的信息可通过查符号表获取。,符号表的生存期,符号表的建立可以开始于词法分析阶段，也可以放到语法、语义阶段，但符号表的使用有时会延续到目标代码的运行阶段。如数组下标地址计算的需要等。在词法分析的时候，仅把标识符的名字属性放到符号表中。其他属性都为空。,符号表中的内容,保存的信息：标识符的名字和与标识符有关的信息1、类型信息包括种类与属性种类：常量、变量、数组、标号或函数等属性：整型、实型、字符型、布尔型等。,数组（如果是数组的话）包括维数，界差，上下界，计算下标地址时涉及的常量等。这些信息放在数组信息向量表（内情向量表）中。函数或过程 包括参数的个数、类型、次序，是否允许递

7、归等。,2 地址码 常量或简单变量 一般是该量在数据区中所占单元的绝对地址或相对地址数组，是该数组在数据区中的首地址函数或过程 是该函数或过程的分程序入口地址 放在符号表中,3 层次信息 对于分程序嵌套或过程嵌套结构型程序设计语言，还应该包括每个标识符所属分程序（过程）的层次4 行号信息 有些程序设计语言需要保存标识符在源程序中的行号，包括说明行和引用行。,一个编译程序，从词法，语法，语义分析到代码生成的整个过程中，符号表是连冠上下文进行语义检查、语义处理、生成代码和存储分配的主要依据，因此符号表的组织直接关系到这些语义功能的实现和语义处理的时空效率。,符号表的总体组织：,1、编译程序按名字的

8、不同属性构造出多个符号表，如常量表、变量名表等。符号表结构相同，表项等长，不便管理。2、编译程序把语言中的所有名字组织在一张符号表中。符号表便于管理，但表结构复杂且表项不等长。3、折衷方式，即按名字属性相似程度分类构造出多个符号表。符号表管理复杂性折衷。,符号表的建立 线性法、二分法以及散列法。线性法是按名字出现的先后顺序建立符号表。二分法是建表时将名字栏按名字的大小顺序排列 散列法建表时是构造一个散列函数将所得的函数值求整或求余得到表项在表中的位置。,符号表的查找 符号表查找算法与该符号表的构造方法密切相关，即有顺序查找、折半查找和杂凑查找法。,说明语句的翻译,说明语句的作用是为可执行语句提

9、供信息，以便于其执行。对声明语句的处理，主要是将所需要的信息正确的填写进合理组织的符号表中。变量的类型定义与声明决定变量存储空间的是变量的数据类型。声明一个变量，实质上是声明此变量属于什么类型。编译器根据类型确定变量的存储空间。,说明语句说明语句的翻译：对每个局部名字，在符号表中建立相应的表项，填写有关的信息如类型、嵌套深度、相对地址等。相对地址：相对静态数据区基址或活动记录中局部数据区基址的一个偏移值。,说明部分的翻译,对于说明部分的翻译，需要考虑的问题包括：标识符的类型纪录。标识符对应的数据对象的地址分配。标识符的作用域问题。,过程中的说明语句 一个过程中的所有说明语句作为一个类集来处理。

10、用一个全程变量Offset来记录下一个数据在活动记录中的位置。P M D M offset：0/intializationD D；D D id：T enter（id.name，T.type，offset）；offset:offset+T.width T integerT.type:integer；T.width:4 T realT.type:real；T.width:8 T arraynum of T1 T.typearray（num.val，T1.type）；T.widthnum.val*T1.width T T1 T.type:pointer（T1.type）；T.width：=4 图 计

11、算说明语句中名字的类型和相对地址,P M D M offset：0/intializationD D；D D id：T enter（id.name，T.type，offset）；offset:offset+T.width T integerT.type:integer；T.width:4 T realT.type:real；T.width:8 T arraynum of T1 T.typearray（num.val，T1.type）；T.widthnum.val*T1.width T T1 T.type:pointer（T1.type）；T.width：=4,a:array 10 of int

12、eger;x:integer;,保留作用域信息(嵌套过程的声明)问题的提出 一般的语言中，标识符的作用在程序正文中有一个确定的范围。因此，同一个标识符在不同的程序正文中可能标识不同的对象，具有不同的性质，要求分配不同的存储空间。于是提出下面的问题：如何组织符号表，使得同一个标识符在不同的作用域中得到正确的引用而不产生混乱。编译程序分析说明语句时建立符号表，编译执行语句时查找符号表。Lookup(id)返回正确的 id.entry。,程序结构一组嵌套过程，为每个过程说明的局部名字建立一个符号表，所有正在翻译过程的符号表组成整个源程序的符号表。翻译语句部分时查找符号表，查找过程的符号表的路线相当于

13、当前被翻译过程的静态链。翻译时，实际上，为每一个过程维持一个符号表。这种符号表可用链表实现。当碰到过程说明Dproc id；D1；S时，就创建一张新的符号表，并且把在D1中的所有说明项都填入此符号表内。新表有一个指针指向刚好包围该嵌入过程的外围过程的符号表，由id表示的过程名字作为该外围过程的局部名字。,处理嵌套过程中的说明语句 PMD addwidth(top(tblptr)，top(offset)；pop(tblptr)；pop(offset)M t=mktable（nil）；push（t，tblptr）；push（0，offset）DD1；D2 Dproc id；ND1；S ttop（t

14、blptr)；addwidth（t，top(offset)）；pop（tblptr）；pop（offset）；enterproc（top（tblptr），id.name，t）D id：T enter（top（tblptr），id.name，T.type，top(offset)）；top(offset）：=top(offset)T.width N tmktable（top（tblptr）；push(t，tblptr）；push（0，offset),（1）过程说明D-proc id;D1;S 引进一个新的过程，其过程名id局部于这个新过程的外围过程，因此这个id应该出现在外围过程的符号表中。（2）

15、在遇到过程说明D-proc id;D1;S 时应该暂停它的外围过程说明语句的处理；为新过程创建一个符号表。将D1中所说明的名字在这张新的符号表中登记，他们都是局部于这个新过程的。（3）外围过程中说明的名字全局于新过程，因此新过程的符号表中有一指针指向外围过程的符号表。,program sort var a,x procedure readarry var i begin end/readarry procedure exchange begin x=a end/exchange procedure quiksort var k,v function partition var i,j begi

16、n a.;.v exchange(i,j)end partition begin.end/sort,nil headeraxreadarryexchangequicksort,headeri,readarry,header,partition,headerkvpartition,headerij,exchange,quicksort,exchange,readarry,sort,嵌套过程的符号表,这个过程sort中说明了过程readarray,exchange,quicksort,因此在sort符号表中登记了这三个过程名，相应的指针指向新创建的符号表，而新建的符号表表头项中均有指针指向外围过程

17、sort符号表。在quicksort中又说明了partition过程名及指向相应符号表的指针，而partition符号表中则有指向外围过程quicksort符号表的指针。,（1）为了处理嵌套过程的说明语句，上述翻译方案中使用了tblptr栈和offset栈。处于栈顶的是指向当前正在处理的这一层过程的符号表的指针top(tblptr)和这一层过程空间下一个可用位置的相对位置top(offset)。因此初遇过程说明（即由M-或N-规也时），便有mktable(previous)创建一个符号表，指向这个符号表的指针及这个新过程的OFFSET（初值为0)推入栈顶，而这个新过程的外围过程（他们因新过程而

18、暂停处理，需待新过程退出后才能继续）则被压入栈顶以下。,（2）mktable(previous)为新过程创建新符号表，指向新符号表的指针则是它的返回值。指针参数previous指向直接嵌套外层过程（其实就是创建新过程时所在的过程）的符号表，它将被记录在新符号表表头的previous指针位置。表头位置还可存放嵌套深度及过程数据宽度等。（3）每遇到一个变量说明D-i:T,就在当前符号表【由top(tblptr)所指】中插入i的表项，这由 enter(table,name,type,offset)完成将名字为name,类型为type，相对地址为内容登记到由table所指示的符号表的新的表项中。当然在

19、这以后相对地址top(offset)的值应增加该名字的数据宽度T.width.,(4)当完成过程说明语句D-proc i:ND;S后这个过程说说明的局部变量所用的总的域宽已由top(offset)给出，应该记在这个过程的符号表表头中。这由addwidth(table,width)完成，同时从栈顶弹出top(tblptr),top(offset),即返回到外层过程，继续处理它的后续说明语句，并将退出的i过程作为外层过程的局部名记入外层过程的符号表中，这由enterproc(table,name,newtable)完成，即将i过程名、i过程的符号表指针记到table所指的外层过程符号表中。,pro

20、c sort;a:array10 of integer;x:integer;proc readarray;i:int;read(a);readarray,PMD addwidth(top(tblptr),top(offset);pop(tblptr);pop(offset)M t=mktable（nil）;push（t，tblptr）;push（0，offset）DD1;D2 Dproc id；ND1；S ttop（tblptr)；addwidth（t，top(offset)）；pop（tblptr）；pop（offset）；enterproc（top（tblptr）,id.name，t）D

21、id：T enter（top（tblptr），id.name，T.type，top(offset)）；top(offset）:=top(offset)T.width N tmktable（top（tblptr）；push(t，tblptr）；push（0，offset),记录中的域名 T record LD end T.type=record（top（tblptr）；T.width=top(offset)；pop（tblptr)；pop(offset)L t=mktable(nil)；push(t，tblptr)；push(0，offset)图 为个记录中的域名建立一张符号表 该翻译模式强调了

22、作为一个语言结构的记录的设计与活动记录之间的相似处。,数组及其在赋值语句中的翻译,在表达式或赋值语句中若出现数组元素，则翻译时将牵涉到数组元素的地址计算。数组在存储器中的存放方式决定了数组元素的地址计算法，从而也决定了应该产生什么样的中间代码。数组在存储器中的存放方式通常有按行存放和按列存放两种。在此，我们讨论以行为主序存放方式的数组元素地址计算方法。,从逻辑上说，一个数组是由同一类型数据所组成的某种N维矩形结构。沿着每一维的距离称为一个下标。每维的下标只能在该维的上下限内变动。数组的每个元素是矩形结构中的一个点，它的位置可通过给出每维的下标来确定。数组的每个元素（也称下标变量）是由数组名连同

23、各维的下标值命名的，如 Ai1,i2,in,根据数组的类型，每个数组元素在计算机中占有同样大小的存储空间。如果一个数组所需的存储空间的大小在编译时就已知道，则称此数组是一个确定数组或静态数组；否则称为可变数组或动态数组。数组的存储有多种形式，最简单的一种把整个数组按行或按列存放在一片连续存储区中。,数组的一般定义为Al1:u1,l2:u2,lk:uk,ln:un 其中，A是数组名，lk是数组A第k维的下界，uk是第k维的上界。为简单起见，假定数组A中每个元素的存储长度为1，a是数组A的首地址，则数组元素Ai1,i2,in的地址D的计算公式如下：D=a+(i1l1)d2d3dn+(i2l2)d3

24、d4dn+(in-1ln1)dn+(inln),其中，di=uili+1(i=1,2,n1)。整理后得到D=CONSPART+VARPART 其中，CONSPART=a(l1d2+l2)d3+l3)d4+ln-1)dn+lnVARPART=(i1d2+i2)d3+i3)d4+in1dn)+inCONSPART中的各项(如li、di(i=1,2,n)在处理说明语句时就可以得到，因此CONSPART值可在编译时计算出来后保存在数组A的相关符号表项里。此后，在计算数组A的元素地址时仅需计算VARPART值而直接引用CONSPART值。,CONSPART 称作不变部分，它和下标i1,i2,in 无关，

25、只和各维尺寸和下界有关；只需要计算一次，其中C在编译时就可以算出。VARPART称作不可变部分，它和下标i1,i2,in有关，它必须计算下标值，转换成相应代码，待运行时计算出。,编译程序对数组说明的处理当遇到数组说明时，必须把数组的有关信息记录在一张“内情向量”表中。以便以后计算数组下标变量地址时引用这些信息。内情向量表的结构：维数、各维上下界、首地址、类型等。,确定数组的数组元素引用的中间代码形式1、访问数组元素可设想为：把它的VARPART计算在某一个变址单元T中，用CONSPART作为“基址”，然后以变址方式访问存储单元CONSPARTT，静态数组CONSPART=a C,C 可以从内情

26、向量表中查到，而a 在运行时一定可确定下来，所以可以生成a-C的代码，待运行时再行确定。假定T1是用于存放CONSPART的临时单元，T1=a C那么用T1T表示数组元素的地址。,实现数组元素的地址计算时，将产生两组四元式序列：一组计算CONSPART，其值存放在临时变量T中；另一组计算VARPART，其值存放在临时变量T1中，即用T1T表示数组元素的地址。,2、访问数组元素引用数组元素(=,T1T,_,X)注：这是一个变址取数四元式，含义相当于：XT1T.对数组元素赋值：（=,X,_,T1T）注：这是一个变址存数四元式，含义相当于：T1T=X.,按行存放的赋值语句中的数组元素的翻译1 文法

27、A-V:=E V-iElist|I Elist-Elist,E|E E-E op E|(E)|V/*op 表示各种算数运算*/注：V 可以是简单变量也可以是下标变量 这个递归定义可以形成数组嵌套数组结构,文法改写 A-V:=E V-Elist|I Elist-Elist1,E|iE E-E op E|(E)|V注意：把数组名i和最左下标表达式写在一起就表示为数组i开始计算第一个下标，同时使我们在整个下标串Elist的翻译过程中随时都能知道数组i的符号表入口地址及表中相应信息。,3、相关语义变量和函数过程语义变量：ARRAY:数组名在符号表的入口地址 DIM：数组下标维数计数器 PLACE：语义

28、变量，存符号表入口地址或临时变量的符号 OFFSET：简单变量：OFFSET=null 下标变量：OFFSET保存已计算的VARPART,数组元素地址的计算公式一维数组A的下标为i的元素的开始地址 VAR a：ARRAY lowhigh OF real；求 ai的地址。base（ilow）*w=i*w+(bacelow*w)其中，base 是数组元素alow的地址。对于C(bace-low*w)是一个常量，可以在处理数组说明的时候确定。对于一个二维数组，可以按行或按列存放 若按行存放，则可用如下公式计算Ai1,i2的相对地址：base+（i1-low1）*n2+i2-low2）*w=base-

29、（low1*n2+low2）*w+（i1*n2+i2)*w 令c=（low1*n2+low2）*w 则常量部分=alow1，low2c=basec,计算元素Ai1，i2，.，ik 相对地址的推广公式：(.(i1*n2+i2)*n3+i3.)*nk+ik)*w+base-(.(low1*n2+low2)*n3+low3.)*nk+lowk)*w c=(.(low1*n2+low2)*n3+low3).)*nk+lowk)*w 变量部分=(.(i1*n2+i2)*n3+i3.)*nk+ik)*w ai1，i2，in的地址=basec+变量部分 x：=ai1，i2，ik 三地址代码结构：t1：=变量

30、部分 t2：=base c t3：=t2t1 x：=t3计算动态数组元素地址的公式与在固定长度数组情况下是同样的，只是上、下界在编译时是未知的。,数组元素引用的文法L id Elist|id/*数组名在形成L时与Elist联系ElistElist，E|E 为了在分析下标表达式中始终知道有关数组名的信息，改写为：LElist|id ElistElist，E|id E/*数组名与数组最左下标表达式联系 Elist可以产生k维数组引用的前m维下标，并生成：（i1n2+i2）n3+i3）nm+im则有递归公式：e1=i1，em=em-1*nm+im对于m=k时，ek*w即为计算数组元素相对地址的变量部

31、分。,有关变量与函数的说明Elist.ndim：记录Elist中的下标表达式的个数，即维数；limit（array，j）：返回nj，即由array所指示的数组的第j维长度（界差）；Elist.place：用来临时存放由Elist中的下标表达式计算出来的值；em=em-1*nmElist 引进综合属性array，指向符号表中相应数组名字表项的指针。,访问数组元素的翻译模式 给定文法：（1）SL：E（2）EEE（3）E（E）（4）EL（5)LElist（6）Lid（7）ElistElist，E（8）Elistid E,相应语义动作1 SL：E if L.offsetnull then emit(L

32、.place：E.place)else emit（L.placeL.offset：=E.Place）/如果L为简单变量，则生成一般赋值语句，否则若L为数组元素引用，则生成对L所指示地址的索引赋值。,2EE1E2 E.place：newtemp；emit（E.place：E1.placeE2.place）3E（E1）E.place：E1.place 当一个数组引用L归约到E时，我们需要L的右值，因此使用索引来获得地址L.placeL.offset 的内容：4）EL if L.offsetnull then E.place：L.place*L is a simple id*/else begin

33、E.place：=newtemp；emit（E.place：=L.placeL.offset)end（L.place：常量部分，L.offset：变量部分）/表达式中的变量，按照简单变量和下标变量分别处理。,5）LElist L.place：=newtemp；emit（L.place：=Elist.array c）/-Elist.array：base L.offset：=newtemp；emit（L.offset：=w*Elist.place）/-Elist.place：下标表达式计算出来的值em/-L.offset：数组元素相对地址的变量部分/用LElist归约时，数组元素的下标表已经结束，

34、此时由Elist.array可从数组内情向量表中查出CONSPART。而VARPART可由Elist.place指出。,6）Lid L.place：=id.place；L.offset：=null/赋值左部或表达式中出现的简单变量和下标变量的区别在于名字i后是否有下标括号。,应用递归公式扫描下一个下标表达式：7）ElistElist1，E/*（Elist1.place：em-1）t：newtemp；/*（limit（Elist1.array，m）：nm；E.place：im）m：Elist1.ndim1；emit（t：=Elist1.place*limit（Elist1.array，m）；em

35、it（t：=t+E.place）；Elist.array：Elist1.array；（em=em-1*nm+im）Elist.place：=t；Elist.ndim：m 下标表已经归约为k-1维，现分析到第k维下标表达式，现分析到第k维下标表达式，此时应该生成Dk:=Dk-1*dk+Ek三地址语句，Dk-1由Elist.place保存，第K维的dk可由Elist.array查内情向量表的第k维界差。由语义函数limit(Elist.array,k)实现。,8）ElistidE Elist.place：=E.place；（E.place：i1）Elist.ndim：=1；Elist.array：

36、id.place/其中Elist.dim记录当前的下标表达式所对应的维数。,例 设A为一个10*20的数组，即n1=10，n2=20。并设w4，数组第一个元素为 A1，1。则有：(low1*n2)low2)*w=(1*20 1)*484。赋值语句x:=Ay,z在由底向上的分析中被翻译成如下三地址语句序列：t1：=y*20 t1：=t1z t2：=A-84 t3：=4*t1 t4：=t2t3 x：=t4,S,L.place=xL.offset=null,x,:=,E.place=T4,L.place=T2L.offset=T3,Elist.place=T1Elist.ndim=2Elist.ar

37、ray=A,Elist.place=yElist.ndim=1Elist.array=A,A,E.place=y,L.place=y L.offset=null,E.place=z,L.place=zL.offset=null,z,y,访问记录中的域 编译器将记录的域的类型和相对地址保存在相应域名的符号表表项之中，可以把用在符号表中查找名字的程序同样用来查找域名。例如：表达式：pinfo1 变量P是一个指向某个记录类型的指针，info 为其中一个算术型类型的域名。编译程序内部把 p表示为：pointer（record（t），域名info将可以在t所指向的符号表中查找。,TYPE link=no

38、de；node=RECORD info：integer；next：link END；VAR p：link；,静态语义检查,按照编译工作的逻辑结构，紧接在词法分析和语法分析之后，编译程序要做的工作是进行静态语义检查和翻译。,静态语义检查,静态语义检查通常包括：类型检查。验证程序中执行的每个操作是否遵守语言的类型系统的过程，编译程序必须报告不符合类型系统的信息。控制流检查。控制流语句必须使控制转移到合法的地方。例如，在C语言中BREAK语句使控制跳离该语句的最小WHILE/FOR或SWITCH语句。如果不存在包括他的这样语句，则报错。,一致性检查。在很多场合要求对象只能被定义一次。例如PASCAL

39、规定同一个标识符在一个分程序中只能说明一次。CASE语句中标号不能相同，枚举元素不能重复出现等等。相关名字检查。名字的作用域分析。,类型系统,基类型(base types)程序设计语言通常包含基本类型：int,float,character,booleans组合类型(compound and constructed types)程序员通常需要更高层次的抽象，例如链表、图、树、表等。程序语言提供一种组合对象的机制来得到新对象的类型 例如数组、结构、指针、可列举集合等程序中的基类型和结构化类型每一种表达可以表示维一个类型表达式。,类型表达式,一个基本类型是一个类型表达式 integer,char,float用类型构造符施于类型表达式，得到一个新的类型表达式。Example int A10 A的类型表达式 array(10,integer),