第八章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 + 5 c = d * ( b + 5 ) 如果b或a是volatile的，

4、则不能用a代替第二个赋值语句中的b+5 寄存器变量,符号需要记录的典型属性,名字 类型 描述 Name 字符串 符号的名字 Class 枚举类型 存储种类 Volatile 布尔型 易变量 Size 整型 这个符号占据内存的字节数 Bitsize 整型 这个符号占据内存的数位数 Boundary 整型 对齐的字节数 Bitbdry 整型 对齐的数位数 Type 指针/枚举 数据类型 Basetype 指针/枚举 构造类型的元素类型 Machtype 枚举 机器定义类型 Nelts 整型 元素个数 Register 布尔型 这个变量是否存在寄存器中 Reg 字符串 对应的寄存器名 Basereg

5、 字符串 基址寄存器名 Disp 整型 偏移量,标识符属性介绍（1）,符号名 变量名、函数名和过程名等 在一个作用域内，变量一般不允许重名 重名变量根据作用域规则处理 重载的过程或操作名：依靠参数的个数、类型和返回值的类型区分，以达到唯一性 符号的类型 变量、函数名等有类型 类型的种类：基本类型、组合类型 为类型检查提供条件 类型的描述： 类型的枚举 类型表,标识符属性介绍（2）,符号的存储种类 存储种类的决定 根据显式的关键字决定存储种类 Fortran语言中的COMMON、SAVE等 C语言中的Static、register等 符号声明的位置 存储种类是语义处理、检查和存储分配的重要依据

6、决定了变量的作用域、可见性和生命期等 符号的作用域和可见性 全局量：程序的整体 局部量：局部作用域、可见性，存储分配在活动记录中，结合随着活动的结束而释放 静态量：局部作用域、可见性，存储分配在静态数据区域中，结合不会随着活动的结束而释放 形式参数：局部作用域、可见性，存储分配由于参数传递的方式不同而有所变化,标识符属性介绍（3）,符号的存储分配信息 所在存储区域 静态存储区域 动态存储区域 相对地址和偏移量 数据对齐 结构分量和结构的关系 符号的其它属性 形式参数？ 数组？ 初值？ 等价变量？ ,符号表的分类,可以构造一个统一的符号表 集中管理 各类表项存在巨大的差别，管理复杂 属性完全相同

7、的符号构成一个表 每个符号表的属性结构完全相同，个数一致 管理简单 符号表过多 分类符号表 具有类似属性的符号构成一种符号表 类型表、常数表、标号表、符号表等 同一个表中部分表项有效的属性的处理,部分表项有效的属性的处理,如果符号a和b同时进入一个符号表，a有s1, s2, s3三种属性，b有s1, s2, s4三种属性 冗余表示的方法 符号表中有4个属性域：s1, s2, s3, s4 各个符号要求的属性域的简单聚集 s3和s4可能是冗余的，浪费空间 操作简单 复用表示的方法 符号表中有3个属性域：s1, s2, s34 根据各个属性域的使用情况，当一些域的使用随着符号种类的不同而不会重叠时

8、可以考虑将其合并，引用时根据符号种类的不同来决定这个域的解释 空间比较节省 操作复杂,符号表表项的设计,元组表示 将每个符号表的表项表示为一个元组 元组的每个分量表示符号的一种属性或一组属性 a: array 13 , 15 of char; 可以表示为： , , char, 定长域的记录 可用相应的数据类型来表示，如符号存储的长度、是否为易变量或静态量等 不定长域的记录 如果最大长度适中，可以按最大长度空间，但可能浪费 可以用动态指针，动态申请数据空间 符号名、数组的内情向量等,结构化符号表表项的设计,结构化的表示方法 不同种类的符号对应不同结构类型 一类符号可能是另一类符号的特例：符号名和

9、过程名、过程名和函数名等，如何表示这些种类的符号间的关系？ 综合成一个通用的结构：个性属性的域可以如下解决 冗余项 域的不同解释 专用的结构：每一小类的符号有专门的结构表示 不同的数据结构间存在的“基本结构 vs. 特例结构”间的关系表示麻烦 操作的通用性考虑 某些操作对不止一类符号有意义，但是数据结构的不同导致这些操作可能难以通用 可以用冗余域作为填充，实现通用,struct Nameblock field tag; int index; field vtype; field vclass; field vstg; expptr vleng; char varnameVL+2; unsign

10、ed vdovar:1; unsigned vdcldone:1; unsigned vadjdim:1; unsigned vsave:1; unsigned vprocclass:3; unsigned vregno:4; unsigned varray:1; unsigned vequiv:1;,union int varno; struct Intrpacked intrdesc; /* bits for intrinsic function*/ vardesc; int veqno; struct Dimblock *vdim; ftnint voffset; union struc

11、t 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的链区索引 */ /* 参数块时是否要在前申明类型*/ int index_dim; /* 由于该结构要强制转换为Pramblock,故新加

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

13、 public Basic protected: SYMBTAG m_tag; CString* m_pName; ; class VarSymbol : public Symbol protected: union struct unsigned m_bInitialized : 1; /* has initialize value */ unsigned m_bUsed : 1; /* be used in this procedure */ unsigned m_bReturn : 1; /* return value */ unsigned m_bArgument : 1; /* fo

14、rmal argument flag */ unsigned m_bStatic : 1; /* static variable */ unsigned m_bGlobal : 1; /* global variable */ unsigned m_bExternal : 1; /* external variable */ unsigned m_bCallRule : 2; /* 0: default, 1: value, 2: reference, 3: content */ ; UINT32 u; ; Type* m_pType; Expression* m_pInitExpr; ;,c

15、lass ProcedureSymbol : public Symbol protected: union struct unsigned m_bSubProcedure : 1; /* subprocedure flag */ unsigned m_bHasDeclaratives : 1; /* has decl part */ ; UINT32 u; ; Type* m_pProcType; /* procedure type */ CompoundStmt* m_pBodyStmt; /* body state of this proc, including declaratives

16、*/ INT32 m_iProcIndex; /* procedure index */ ProcedureSymbol* m_pParentProcedure; /*parent proc symbol */ ProcedureList* m_pSubProcedureList; /* sub-proc list */ SymbList* m_pFormalArgs; /* formal argument list */ ProcSymbTable* m_pCurPorcSymbTable; /*sym tab of proc*/ ;,符号表表项的排列方法（1）,线性表 按扫描的先后次序建立

17、 管理简单 效率低：查找要扫描整个表 如果符号表的表项数目比较小（如小于20项），这种方式效果比较好 排序组织和二分法 按符号的排序值建表 可以实现为二叉树的形式，插入和查找按二分法进行 空间开销和存储开销与线性表基本相同 效率好于线性表、但算法复杂性也高于线性表,符号表表项的排列方法（2）,散列表（hash表） 根据符号名的Hash函数值决定表项的位置 不同的符号具有相同Hash函数值的处理 散列冲突可以通过更多次的Hash解决 编译器通常采用的方法：从冲突的下一项开始寻找空白表项，找到后作为欲插入的表项，具有相同的Hash值的表项建立一个链 对满的Hash表再插入新的表项会引起溢出 Has

18、h函数的设计影响符号表的效率 编译器的设计者根据经验和实验决定Hash函数 通常采用对名字的字符串叠加等方式决定Hash函数值 在散列表的基础上，增加一个顺序链将各个表项连接起来,符号表表项的排列方法（3）,散列表的例子 Key1 Key2 Keyn Hash Keys 符号表表项,符号表的分层管理,程序的结构 一个程序包含一系列的文件或模块等 文件和模块包含一系列的过程等 过程可能有分程序结构 全局符号表： 记录全局量、全局可见的过程名等 各个文件和模块的符号表指针 文件或模块的符号表 记录文件或模块可见的名字 过程符号表指针 过程符号表 程序块的符号表,class SymbTable :

19、public Basic protected: SymbList* m_pSymbList; TypeList* m_pTypeList; SymbTable* m_pParentSymbTable; ; class ProcSymbTable : public SymbTable private: ProcedureSymbol* m_pProcSymbol; SymbList* m_pArgsList; ; class FileSymbTable : public SymbTable protected: CString* m_pFileName; ProcSymbTabList* m_p

20、ProcdureSymbolTableList; ; class ProjectSymbTable : public SymbTable protected: CString* m_pProjectName; FileSymbTabList* m_pFileSymbolTableList; ;,局部符号表的管理,符号表整体的操作 创建一个新的符号表new_sym_tab: SymTabSymTab 删除一个符号表：del_sym_tab: SymTabSymTab 符号表表项的操作 插入一个新的表项insert_sym: SymTabSymbolBoolean 检查符号声明的唯一性 查找一个表

21、项lookup_sym: SymTabSymbolBoolean 下一个表项next_sym: SymTabSymbolSymbol 符号表表项属性的操作 取符号属性值：get_sym_attr 置符号属性值：set_sym_attr 属性值的设置、读取等操作可能是根据具体属性的不同而有不同的方法,全局符号表的结构,符号表如何表示作用域和可见性？ 全局符号表的结构受到作用域和可见性的影响 在分程序结构类的语言中，可以以树型结构来表示符号表 根结点是全局符号表 被嵌套的程序块的符号表是其外围程序块的符号表的子结点 在一个编译时刻，只对部分树结点进行处理（从当前程序块的符号表到根结点路径上的所有结

22、点） 可以用一个栈来实现 名字的查找从当前结点开始，逐步扩展到上层结点，直至找到这个名字最内层符号表的表项,program e; var a, b, c : integer; procedure f; var a, b, c : integer; begin a := b + c end; procedure g; var a, b : integer; procedure h; var c, d : integer; begin c := a + b end; procedure i; var b, d : integer; begin b := a + c end; begin b :=

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

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

25、个作用域内是可见的 在symbol栈中增加一个域：记录可见的作用域的层次,Program var a, b, c, d procedure f( ) var b procedure g( ) var d import a, b from P end end End Package P export a, b End 假设b和d有相同的Hash值,中间表示的要考虑的问题（1）,中间表示（Intermediate Representation） 编译系统中最重要的部分 个性和通用性 可以分层：方便不同阶段或目的的编译处理 使用已有的中间表示？ 可望节省设计和编码的开销 是否适合新的应用 被编译的语

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

27、 ) 中层IR ( Medium Level IR ) 低层IR ( Low Level IR ) 不同层次的IR间的转换,面向多用途的IR（2）,如果有声明float a2010，则数组引用aij+2在不同的IR中的表示 t1 ai , j+2 t1 j+2 r1 fp-4 t2 i * 20 r2 r1+2 t3 t1 + t2 r3 fp-8 t4 4 * t3 r4 r3 * 20 t5 addr a r5 r4 + r2 t6 t5 + t4 r6 4 * r5 t7 *t6 r7 fp-216 f1 r7 + r6 高层 IR 中层 IR 低层 IR,高层 IR,一般用于编译的前端

28、或预处理 由编译前端生成 可以方便地转换为低层次的IR 可以方便地还原成原语言程序或其它语言的程序 高层的并行优化 源-源变换 抽象语法树是一种常用的高层IR,中层 IR,一般针对一类语言的特性而设计 尽量作到与要处理的语言无关 考虑到易于生成一种或几种体系结构的目标代码 主要包括： 变量、临时量和寄存器等的表示 简化程序的控制结构 适于大多数程序的优化处理 三地址代码可以认为是一种常用的中层IR,低层 IR,一般针对具体机器的结构特点而设计 与机器密切相关 方便生成高效的目标代码 硬件特点和指令集在IR中体现 适用于面向机器的代码优化,IR结构的存储形式和分配,IR一般表示为二进制形式 各种

29、表格间的联系纷繁复杂 抽象：保持一种良好的结构关系 动态指针：操作灵活，但效率和安全性要关注 静态指针：效率、操作 各种表格的申请： 长度：固定 vs. 不固定 表格的申请：静态 vs. 动态 操作的效率 IR占据的空间大小 IR是否一直在内存中？,IR结构的内外存交换,IR在外存中的保存 原因 IR太大 编译“遍”的要求 IR显示的要求 调试的要求 要解决的问题 指针的固定化：如何转化为相对偏移 如何处理编译生成的对象 这些对象一般是处理某个模块时引入的，且是不重名的，如何保证写到外存后仍然不重名 如何实现外部表示和内存中的IR间的快速转换,中间代码的形式（1）,后缀表示 表达式E的后缀表示

30、递归定义 如果E是变量和常数，则E的后缀表示是E本身 如果E是形如E1 op E2的表达式，其中op是任意的二元算符，则E的后缀表示是E1 E2 op，其中E1和E2分别是E1和E2的后缀表示 如果E是形如(E1)的表达式，则E1的后缀表示也是E的后缀表示 后缀表示不需要括号 后缀表示易于用栈实现,中间代码的形式（2）,图形表示 描述了源程序的自然层次结构 语法树 dag 后缀表示是语法树的线性化表示 赋值语句产生语法树的语法制导定义 产生式 语义规则 S id := E S.nptr := mknode(:=, mkleaf(id, id.place), E.nptr ) E E1 + E2

31、 E.nptr := mknode(+, E1.nptr, E2.nptr ) E E1 * E2 E.nptr := mknode(*, E1.nptr, E2.nptr ) E -E1 E.nptr := mknode(uminus, E1.nptr ) E ( E1 ) E.nptr := E1.nptr E id E.nptr := mkleaf(id , id.place ),中间代码的形式：三地址代码,一般形式 x := y op z 是一系列的上述形式 x, y, z是名字、常数和编译器产生的临时变量 op是算符 复杂程序结构的规整化 x + y * z翻译成t1 := y *

32、z t2 := x + t1 三地址代码是语法树的线性化表示 比后缀表示容易安排 dag图对应的三地址代码可能比相应的语法树对应的三地址代码要优化，因为可以复用中间结果,三地址代码的种类（1）,语句的标号 符号标号 可以用三地址代码的序号代替标号 标号的替换可以由独立的一遍完成 控制流语句：通过规整化得到等价的简单控制语句 常用的三地址语句 赋值语句：x := y op z，op是二元算术算符或逻辑算符 赋值语句：x := op z，op是一元算符 复写语句：x := y 无条件转移：goto L，L是下一步要执行的三地址语句,三地址代码的种类（2）,条件转移语句：if x relop y g

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

34、ult的内容通常是符号表条目指针 临时名字要进入符号表 一元运算不需要使用arg2的域 param不使用arg2和result域 条件转移和无条件转移把目标语句的标号放在result中,三地址代码的实现（2）,赋值语句：a := b * -c + b * -c的四元式表示 op arg1 arg2 result (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 :=

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

36、1) * b (0) (2) uminus c (3) * b (2) (4) + (1) (3) (5) := a (4) 三元式难于用于优化编译器 空间较省,三地址代码的实现（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实

37、现 空间和四元式类似，但如果临时值引用不止一次，间接三元式的空间要节省一些,过程声明的处理（1）,过程的声明 计算名字的类型和相对地址 P offset := 0 D DD ; D Did : T enter( id.name , T.type , 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

38、 := num.val * T1.width TT1 T.type := pointer( T1.type ); T.width := 4 ,过程声明的处理（2）,综合属性type和width表示非终结符的类型和宽度 初始化的工作由第一个产生式完成 P offset := 0 D 改写上述产生式，使得所有动作出现在产生式的右部的末端 P M D M offset := 0 ,作用域信息的保存（1）,嵌套过程的声明 P D D D ; D | id : T | proc id ; D ; S 在处理嵌套过程时，外面过程的处理暂时停止 符号表的处理：可以简单地为每个过程建立一个独立的符号表 mkt

39、able(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( offset ) M t := mktable( nil ); push( t , tblprt ); push( 0 , offset ) DD1 ; D2 Dproc id ; N D

40、1 ; 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 , offset

41、 ) ,作用域信息的保存（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，用于恢复记录中的域名的名字、类型和宽度,