第八章1中间代码.ppt

《第八章1中间代码.ppt》由会员分享，可在线阅读，更多相关《第八章1中间代码.ppt（61页珍藏版）》请在三一办公上搜索。

1、第八章符号表、中间代码及其管理,符号表中间表示的介绍中间代码的形式语言结构的翻译中间表示（IR）的设计更象一种艺术，受到设计者个人风格的影响,符号表的作用,收集符号的属性根据程序的声明部分，收集标识符的各种属性，并在符号表中登记显式声明语言和隐式声明语言临时变量表项数据类型作用域和可见性语义合法性检查的依据属性的一致性和合法性声明的唯一性 标识符的地址分配依据,标识符的存储种类、可见性和生命期（1）,存储种类大多数语言允许指定变量的存储种类指明了变量的作用域、可见性和生命期作用域规则也决定了符号表的结构和动态时变量访问的形式作用域：静态的程序单元，可嵌套分程序结构可见性：与作用域相关一个变量的

2、可见性指这个变量名指定一个特定的实例的区域C语言中全局量和局部量的可见性生命期：在运行时刻，变量从第一次可见到最后一次可见之间的时间段,标识符的存储种类、可见性和生命期（2）,全局类型的变量几乎所有的语言都有这类变量其生命期覆盖了程序的整个执行出现的位置对作用域的限定可以被局部量的声明覆盖声明的形式Pascal的最外层作用域声明的变量C语言的全局量extern：其它文件可见，全局量file、module：局部于某个文件和模块Fortran：common变量特殊性：只有声明了同名公用块的过程才可见,标识符的存储种类、可见性和生命期（3）,自动变量（栈变量）作用域只是其声明出现的程序单元，不具有全

3、局作用域生命期只是这个程序单元的一次活动程序块和过程静态变量C语言中的static属性变量或Fortran语言中的save变量在过程中声明，但其结合的存储单元在程序的整个执行期间都保持作用域不能扩展值可以跨越过程的活动有效,标识符的存储种类、可见性和生命期（4）,数据对象的动态生命期动态作用域具有易变属性（volatile）的变量其值的修改是异步的，如I/O设备对程序的优化有重要影响，编译器难以自动判断变量是否易变a=b+5c=d*(b+5)如果b或a是volatile的，则不能用a代替第二个赋值语句中的b+5寄存器变量,符号需要记录的典型属性,名字 类型描述Name 字符串符号的名字Clas

4、s 枚举类型存储种类Volatile 布尔型易变量Size 整型这个符号占据内存的字节数Bitsize 整型这个符号占据内存的数位数Boundary 整型对齐的字节数Bitbdry 整型对齐的数位数Type 指针/枚举数据类型Basetype 指针/枚举构造类型的元素类型Machtype 枚举机器定义类型Nelts 整型元素个数Register 布尔型这个变量是否存在寄存器中Reg 字符串对应的寄存器名Basereg 字符串基址寄存器名Disp 整型偏移量,标识符属性介绍（1）,符号名变量名、函数名和过程名等在一个作用域内，变量一般不允许重名重名变量根据作用域规则处理重载的过程或操作名：依靠参

5、数的个数、类型和返回值的类型区分，以达到唯一性符号的类型变量、函数名等有类型类型的种类：基本类型、组合类型为类型检查提供条件类型的描述：类型的枚举类型表,标识符属性介绍（2）,符号的存储种类存储种类的决定根据显式的关键字决定存储种类Fortran语言中的COMMON、SAVE等C语言中的Static、register等符号声明的位置存储种类是语义处理、检查和存储分配的重要依据决定了变量的作用域、可见性和生命期等符号的作用域和可见性全局量：程序的整体局部量：局部作用域、可见性，存储分配在活动记录中，结合随着活动的结束而释放静态量：局部作用域、可见性，存储分配在静态数据区域中，结合不会随着活动的结

6、束而释放形式参数：局部作用域、可见性，存储分配由于参数传递的方式不同而有所变化,标识符属性介绍（3）,符号的存储分配信息所在存储区域静态存储区域动态存储区域相对地址和偏移量数据对齐结构分量和结构的关系符号的其它属性形式参数？数组？初值？等价变量？,符号表的分类,可以构造一个统一的符号表集中管理各类表项存在巨大的差别，管理复杂属性完全相同的符号构成一个表每个符号表的属性结构完全相同，个数一致管理简单符号表过多分类符号表具有类似属性的符号构成一种符号表类型表、常数表、标号表、符号表等同一个表中部分表项有效的属性的处理,部分表项有效的属性的处理,如果符号a和b同时进入一个符号表，a有s1,s2,s3

7、三种属性，b有s1,s2,s4三种属性冗余表示的方法符号表中有4个属性域：s1,s2,s3,s4各个符号要求的属性域的简单聚集s3和s4可能是冗余的，浪费空间操作简单复用表示的方法符号表中有3个属性域：s1,s2,s34根据各个属性域的使用情况，当一些域的使用随着符号种类的不同而不会重叠时可以考虑将其合并，引用时根据符号种类的不同来决定这个域的解释空间比较节省操作复杂,符号表表项的设计,元组表示将每个符号表的表项表示为一个元组元组的每个分量表示符号的一种属性或一组属性a:array 1.3,1.5 of char;可以表示为：,char,定长域的记录可用相应的数据类型来表示，如符号存储的长度、

8、是否为易变量或静态量等不定长域的记录如果最大长度适中，可以按最大长度空间，但可能浪费可以用动态指针，动态申请数据空间符号名、数组的内情向量等,结构化符号表表项的设计,结构化的表示方法不同种类的符号对应不同结构类型一类符号可能是另一类符号的特例：符号名和过程名、过程名和函数名等，如何表示这些种类的符号间的关系？综合成一个通用的结构：个性属性的域可以如下解决冗余项域的不同解释专用的结构：每一小类的符号有专门的结构表示不同的数据结构间存在的“基本结构 vs.特例结构”间的关系表示麻烦操作的通用性考虑某些操作对不止一类符号有意义，但是数据结构的不同导致这些操作可能难以通用可以用冗余域作为填充，实现通用

9、,struct Nameblockfield tag;int index;field vtype;field vclass;field vstg;expptr vleng;char varnameVL+2;unsigned vdovar:1;unsigned vdcldone:1;unsigned vadjdim:1;unsigned vsave:1;unsigned vprocclass:3;unsigned vregno:4;unsigned varray:1;unsigned vequiv:1;,unionint varno;struct Intrpacked intrdesc;/*bi

10、ts for intrinsic function*/vardesc;int veqno;struct Dimblock*vdim;ftnint voffset;unionstruct Headblock*hp;Chainp namelist;/*points to chain of names in*/Chainp vstfdesc;/*points to(formals,expr)pair*/varxptr;int enamep;int index_varxptr;/*名字是语函时为语函描述链头的链区索引*/*名字是段头时为符号常数链头的链区索引*/*name is namelist的链区

11、索引*/*参数块时是否要在前申明类型*/int index_dim;/*由于该结构要强制转换为Pramblock,故新加的数据结构应在末尾处*/int length;unsigned is_shared:1;/*该变量是否为共享变量*/,面向对象的符号表表项设计,不同种类的符号对应不同的类（class）符号表的一个表项就是某个类的一个实例继承关系的应用表示不同种类的符号间存在的固有关系过程名类是符号基类的子类省略了相同属性的重复声明增加新的域表示子类符号的新属性，如过程名类中增加关于形式参数链的域等父类中的某些属性在子类中是不需要的，此时可以不必考虑这些属性，如符号类中可能有类型域，但过程名类

12、中，这个域是不需要填充和管理的父类中的某些域可以在子类中重新解释,class Symbol:public Basic protected:SYMBTAGm_tag;CString*m_pName;class VarSymbol:public Symbol protected:union struct unsignedm_bInitialized:1;/*has initialize value*/unsignedm_bUsed:1;/*be used in this procedure*/unsignedm_bReturn:1;/*return value*/unsignedm_bArgume

13、nt:1;/*formal argument flag*/unsignedm_bStatic:1;/*static variable*/unsignedm_bGlobal:1;/*global variable*/unsignedm_bExternal:1;/*external variable*/unsignedm_bCallRule:2;/*0:default,1:value,2:reference,3:content*/;UINT32 u;Type*m_pType;Expression*m_pInitExpr;,class ProcedureSymbol:public Symbol pr

14、otected:union struct unsignedm_bSubProcedure:1;/*subprocedure flag*/unsignedm_bHasDeclaratives:1;/*has decl part*/;UINT32 u;Type*m_pProcType;/*procedure type*/CompoundStmt*m_pBodyStmt;/*body state of this proc,including declaratives*/INT32m_iProcIndex;/*procedure index*/ProcedureSymbol*m_pParentProc

15、edure;/*parent proc symbol*/ProcedureList*m_pSubProcedureList;/*sub-proc list*/SymbList*m_pFormalArgs;/*formal argument list*/ProcSymbTable*m_pCurPorcSymbTable;/*sym tab of proc*/;,符号表表项的排列方法（1）,线性表按扫描的先后次序建立管理简单效率低：查找要扫描整个表如果符号表的表项数目比较小（如小于20项），这种方式效果比较好排序组织和二分法按符号的排序值建表可以实现为二叉树的形式，插入和查找按二分法进行空间开销和

16、存储开销与线性表基本相同效率好于线性表、但算法复杂性也高于线性表,符号表表项的排列方法（2）,散列表（hash表）根据符号名的Hash函数值决定表项的位置不同的符号具有相同Hash函数值的处理散列冲突可以通过更多次的Hash解决编译器通常采用的方法：从冲突的下一项开始寻找空白表项，找到后作为欲插入的表项，具有相同的Hash值的表项建立一个链对满的Hash表再插入新的表项会引起溢出Hash函数的设计影响符号表的效率编译器的设计者根据经验和实验决定Hash函数通常采用对名字的字符串叠加等方式决定Hash函数值在散列表的基础上，增加一个顺序链将各个表项连接起来,符号表表项的排列方法（3）,散列表的例

17、子Key1Key2Keyn Hash Keys 符号表表项,符号表的分层管理,程序的结构一个程序包含一系列的文件或模块等文件和模块包含一系列的过程等过程可能有分程序结构全局符号表：记录全局量、全局可见的过程名等各个文件和模块的符号表指针文件或模块的符号表记录文件或模块可见的名字过程符号表指针过程符号表程序块的符号表,class SymbTable:public Basic protected:SymbList*m_pSymbList;TypeList*m_pTypeList;SymbTable*m_pParentSymbTable;class ProcSymbTable:public Symb

18、Table private:ProcedureSymbol*m_pProcSymbol;SymbList*m_pArgsList;class FileSymbTable:public SymbTable protected:CString*m_pFileName;ProcSymbTabList*m_pProcdureSymbolTableList;class ProjectSymbTable:public SymbTable protected:CString*m_pProjectName;FileSymbTabList*m_pFileSymbolTableList;,局部符号表的管理,符号表

19、整体的操作创建一个新的符号表new_sym_tab:SymTabSymTab删除一个符号表：del_sym_tab:SymTabSymTab符号表表项的操作插入一个新的表项insert_sym:SymTabSymbolBoolean检查符号声明的唯一性查找一个表项lookup_sym:SymTabSymbolBoolean下一个表项next_sym:SymTabSymbolSymbol符号表表项属性的操作取符号属性值：get_sym_attr置符号属性值：set_sym_attr属性值的设置、读取等操作可能是根据具体属性的不同而有不同的方法,全局符号表的结构,符号表如何表示作用域和可见性？全局

20、符号表的结构受到作用域和可见性的影响在分程序结构类的语言中，可以以树型结构来表示符号表根结点是全局符号表被嵌套的程序块的符号表是其外围程序块的符号表的子结点在一个编译时刻，只对部分树结点进行处理（从当前程序块的符号表到根结点路径上的所有结点）可以用一个栈来实现名字的查找从当前结点开始，逐步扩展到上层结点，直至找到这个名字最内层符号表的表项,program e;var a,b,c:integer;procedure f;var a,b,c:integer;begina:=b+cend;procedure g;var a,b:integer;procedure h;var c,d:integer;

21、beginc:=a+bend;procedure i;var b,d:integer;beginb:=a+cend;beginb:=a+cend;procedure j;var b,d:integer;beginb:=a+dend;begina:=b+cend.,上页例子的局部符号表的树,被编译的过程 e()f()g()h()i()j()e()符号表的栈编译时的符号表栈,利用两个栈表示符号表的层次结构,结构：一个栈存储所有的符号表表项：symbol stack一个栈存放指向当前局部符号表首地址的指针：block stack操作创建一个新的符号表在block stack中压入一个新的项，指向新符

22、号表的栈底插入一个表项在symbol stack栈顶增加一个新的项该表项作为对应的Hash链的链头查找一个表项直接按Hash表查找即可，对应的Hash链的第一个同名项删除一个符号表将symbol stack栈位于该符号表的栈底以上的所有项弹出更新Hash表,封闭作用域（close scope）的处理,开放作用域（open scope）严格按照最接近的作用域规则决定符号适用的声明可以按前面的介绍处理封闭作用域：显式制定符号的可见性如C+中的继承Modula-2中的import和exportAda中的类属闭包和use语句export：只能作用于可见的符号一个名字可以引入指它显式的由export引入

23、，或者在这个作用域内是可见的在symbol栈中增加一个域：记录可见的作用域的层次,Programvar a,b,c,dprocedure f()var bprocedure g()var d import a,b from PendendEndPackage Pexport a,bEnd假设b和d有相同的Hash值,中间表示的要考虑的问题（1）,中间表示（Intermediate Representation）编译系统中最重要的部分个性和通用性可以分层：方便不同阶段或目的的编译处理使用已有的中间表示？可望节省设计和编码的开销是否适合新的应用被编译的语言目标系统的结构移植的代价对新的优化措施是否

24、适用：已有的IR可能很不适应新的优化要求,中间表示的要考虑的问题（2）,设计新的中间表示？IR的层次：面向源语言、通用的还是面向目标结构？特别是：如何划分与机器相关的表示和与机器无关的表示IR的结构IR的表示形式对特定优化的支持对代码生成的支持,面向多用途的IR（1）,多层的中间表示为什么编译的不同阶段的要求前端和与机器无关的优化更关注源语言结构代码生成和机器相关优化关注目标体系结构的特点编译的不同目的的要求源-源变换不必关注机器的指令集等通用性多层的IR：不是唯一的形式高层IR(High Level IR)中层IR(Medium Level IR)低层IR(Low Level IR)不同层次

25、的IR间的转换,面向多用途的IR（2）,如果有声明float a2010，则数组引用aij+2在不同的IR中的表示t1 ai,j+2t1 j+2r1 fp-4t2 i*20r2 r1+2t3 t1+t2r3 fp-8t4 4*t3r4 r3*20t5 addr ar5 r4+r2t6 t5+t4r6 4*r5t7*t6r7 fp-216f1 r7+r6高层 IR中层 IR低层 IR,高层 IR,一般用于编译的前端或预处理由编译前端生成可以方便地转换为低层次的IR可以方便地还原成原语言程序或其它语言的程序高层的并行优化源-源变换抽象语法树是一种常用的高层IR,中层 IR,一般针对一类语言的特性而

26、设计尽量作到与要处理的语言无关考虑到易于生成一种或几种体系结构的目标代码主要包括：变量、临时量和寄存器等的表示简化程序的控制结构适于大多数程序的优化处理三地址代码可以认为是一种常用的中层IR,低层 IR,一般针对具体机器的结构特点而设计与机器密切相关方便生成高效的目标代码硬件特点和指令集在IR中体现适用于面向机器的代码优化,IR结构的存储形式和分配,IR一般表示为二进制形式各种表格间的联系纷繁复杂抽象：保持一种良好的结构关系动态指针：操作灵活，但效率和安全性要关注静态指针：效率、操作各种表格的申请：长度：固定 vs.不固定表格的申请：静态 vs.动态操作的效率IR占据的空间大小IR是否一直在内

27、存中？,IR结构的内外存交换,IR在外存中的保存原因IR太大编译“遍”的要求IR显示的要求调试的要求要解决的问题指针的固定化：如何转化为相对偏移如何处理编译生成的对象这些对象一般是处理某个模块时引入的，且是不重名的，如何保证写到外存后仍然不重名如何实现外部表示和内存中的IR间的快速转换,中间代码的形式（1）,后缀表示表达式E的后缀表示递归定义如果E是变量和常数，则E的后缀表示是E本身如果E是形如E1 op E2的表达式，其中op是任意的二元算符，则E的后缀表示是E1 E2 op，其中E1和E2分别是E1和E2的后缀表示如果E是形如(E1)的表达式，则E1的后缀表示也是E的后缀表示后缀表示不需要

28、括号后缀表示易于用栈实现,中间代码的形式（2）,图形表示描述了源程序的自然层次结构语法树dag后缀表示是语法树的线性化表示赋值语句产生语法树的语法制导定义产生式语义规则S id:=ES.nptr:=mknode(:=,mkleaf(id,id.place),E.nptr)E E1+E2E.nptr:=mknode(+,E1.nptr,E2.nptr)E E1*E2E.nptr:=mknode(*,E1.nptr,E2.nptr)E-E1E.nptr:=mknode(uminus,E1.nptr)E(E1)E.nptr:=E1.nptrE idE.nptr:=mkleaf(id,id.place

29、),中间代码的形式：三地址代码,一般形式x:=y op z是一系列的上述形式x,y,z是名字、常数和编译器产生的临时变量op是算符复杂程序结构的规整化x+y*z翻译成t1:=y*z t2:=x+t1三地址代码是语法树的线性化表示比后缀表示容易安排dag图对应的三地址代码可能比相应的语法树对应的三地址代码要优化，因为可以复用中间结果,三地址代码的种类（1）,语句的标号符号标号可以用三地址代码的序号代替标号标号的替换可以由独立的一遍完成控制流语句：通过规整化得到等价的简单控制语句常用的三地址语句赋值语句：x:=y op z，op是二元算术算符或逻辑算符赋值语句：x:=op z，op是一元算符复写语

30、句：x:=y无条件转移：goto L，L是下一步要执行的三地址语句,三地址代码的种类（2）,条件转移语句：if x relop y goto L，根据逻辑运算的结果决定是否执行转移过程调用：param x和call p,nn表示实参个数param x1param x2 param xncall p,n等价于call p(x1,x2,xn)过程返回：return y，y表示返回值,三地址代码的种类（3）,数组引用赋值x:=y i x i:=y地址和指针的使用x:=&yx:=*y*x:=y,三地址代码的实现（1）,四元式x:=y op z有4个域的记录结构op：算符的内部编码arg1和arg2分别

31、表示y和zresult表示xarg1、arg2和result的内容通常是符号表条目指针临时名字要进入符号表一元运算不需要使用arg2的域param不使用arg2和result域条件转移和无条件转移把目标语句的标号放在result中,三地址代码的实现（2）,赋值语句：a:=b*-c+b*-c的四元式表示oparg1arg2result(0)uminus c t1(1)*b t1 t2(2)uminus c t3(3)*b t2 t4(4)+t2 t4 t5(5):=t5 a四元式易于调整次序，便于优化的实施占用空间大，要增加新的符号表表项,三地址代码的实现（3）,三元式x:=y op z避免四元

32、式引入临时变量，可以用三地址语句的序号表示临时值有3个域的记录结构op：算符的内部编码arg1和arg2分别表示y和z这个语句的结果通过这个语句的序号引用arg1、arg2的内容通常是符号表条目指针避免引入临时名字有些三地址语句要多个三元式表示xi:=yy:=xiop arg1 arg2 op arg1 arg2(0)=x i(0)=x i(1):=(0)y(1):=y(0),三地址代码的实现（4）,赋值语句：a:=b*-c+b*-c的三元式表示oparg1arg2(0)uminus c(1)*b(0)(2)uminus c(3)*b(2)(4)+(1)(3)(5):=a(4)三元式难于用于优

33、化编译器空间较省,三地址代码的实现（5）,间接三元式在三元式基础上，增加一个索引列表Statement op arg1 arg2(0)(14)(14)uminus c(1)(15)(15)*b(14)(2)(16)(16)uminus c(3)(17)(17)*b(16)(4)(18)(18)+(15)(17)(5)(19)(19):=a(18)语句的移动通过重排statement实现空间和四元式类似，但如果临时值引用不止一次，间接三元式的空间要节省一些,过程声明的处理（1）,过程的声明计算名字的类型和相对地址P offset:=0 DDD;DDid:T enter(id.name,T.typ

34、e,offset);offset:=offset+T.width Tinteger T.type:=integer;T.width:=4 Treal T.type:=real;T.width:=8 Tarray num of T1 T.type:=array(num.val,T1.type);T.width:=num.val*T1.width TT1 T.type:=pointer(T1.type);T.width:=4,过程声明的处理（2）,综合属性type和width表示非终结符的类型和宽度初始化的工作由第一个产生式完成P offset:=0 D改写上述产生式，使得所有动作出现在产生式的右

35、部的末端P M DM offset:=0,作用域信息的保存（1）,嵌套过程的声明P DD D;D|id:T|proc id;D;S在处理嵌套过程时，外面过程的处理暂时停止符号表的处理：可以简单地为每个过程建立一个独立的符号表mktable(previous)enter(table,name,type,offset)addwidth(table,width)：记录符号表table中所有条目的累加宽度enterproc(table,name,newtable),作用域信息的保存（2）,P M D addwidth(top(tblptr),top(offset);pop(tblptr);pop(of

36、fset)M t:=mktable(nil);push(t,tblprt);push(0,offset)DD1;D2Dproc id;N D1;S t:=top(tblptr);addwidth(t,top(offset);pop(tblptr);pop(offset);enterproc(top(tblptr),id.name,t)Did:T enter(top(tblptr),id.name,T.type,top(offset);top(offset):=top(offset)+T.width N t:=mktable(top(tblptr);push(t,tblprt);push(0,o

37、ffset),作用域信息的保存（3）,非终结符M的语义动作最先完成建立最外层作用域的符号表用最外层符号表初始栈tblptr用0初始化offset栈非终结符N的语义动作建立一个新的作用域的符号表在符号表栈中压入新的符号表指针用0作为offset栈顶变量声明id:T不改变符号表栈建立新的符号条目累加符号的宽度过程的声明处理结束时addwidth记录该符号表的所有名字的宽度更改符号表栈和offset栈过程名进入外围符号表,记录的域名,记录声明的产生式T record D end为记录的域名建立符号表T record L D end T.type:=record(top(tblptr);T.width:=top(offset);pop(tblptr);pop(offset)L t:=mktable(nil);push(t,tblprt);push(0,offset)看见关键字record后，标记非终结符L为域名建立一个新的符号表end后的动作将总宽度作为综合属性T.width返回把构造器record作用于该记录的符号表指针，得到T.type，用于恢复记录中的域名的名字、类型和宽度,