北京大学编译原理实习minijava 实验报告

资源描述

《北京大学编译原理实习minijava 实验报告》由会员分享，可在线阅读，更多相关《北京大学编译原理实习minijava 实验报告（45页珍藏版）》请在金锄头文库上搜索。

1、编译原理实习报告张弛, 00848231December 13, 2010Contents1类类类型型型检检检查查查31.1符号表. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41.1.1符号表结构. . . . . . . . . . . . . . . . . . . . . . . . . .41.1.2变量类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . .61.2重定义错误和循环继承 . . . . . . . . . . . . . .

2、 . . . . . . . . . .81.2.1符号表功能实现 . . . . . . . . . . . . . . . . . . . . . . . .81.2.2构造符号表. . . . . . . . . . . . . . . . . . . . . . . . . .101.3未定义错误和类型不匹配 . . . . . . . . . . . . . . . . . . . . . . .111.3.1具体的检查项目 . . . . . . . . . . . . . . . . . . . . . . . .121.3.2表达式节点的分析. . . . . . . . .

3、. . . . . . . . . . . . .121.3.3未定义错误. . . . . . . . . . . . . . . . . . . . . . . . . .141.3.4类型匹配错误 . . . . . . . . . . . . . . . . . . . . . . . . .151.4未初始化变量和未使用变量. . . . . . . . . . . . . . . . . . . . .162Piglet中中中间间间代代代码码码172.1Piglet简介. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4、 . .172.1.1文法BNF . . . . . . . . . . . . . . . . . . . . . . . . . . . .172.1.2语言细节 . . . . . . . . . . . . . . . . . . . . . . . . . . . .182.2数组的表示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .192.3类结构表示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .202.3.1数据和过程分离 .

5、. . . . . . . . . . . . . . . . . . . . . . .202.3.2过程的转换. . . . . . . . . . . . . . . . . . . . . . . . . .212.3.3处理继承 . . . . . . . . . . . . . . . . . . . . . . . . . . . .222.3.4实现细节 . . . . . . . . . . . . . . . . . . . . . . . . . . . .232.4翻译模式 . . . . . . . . . . . . . . . . . . . . . . . .

6、. . . . . . . .251编译原理实习报告张弛, 008482312.4.1读变量和写变量 . . . . . . . . . . . . . . . . . . . . . . . .262.4.2多于20个参数 . . . . . . . . . . . . . . . . . . . . . . . . .282.4.3布尔表达式. . . . . . . . . . . . . . . . . . . . . . . . . .282.4.4其他. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .293Spig

7、let中中中间间间代代代码码码304Kanga中中中间间间代代代码码码314.1Kanga简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .314.1.1文法BNF . . . . . . . . . . . . . . . . . . . . . . . . . . . .314.1.2语言特性 . . . . . . . . . . . . . . . . . . . . . . . . . . . .324.2构造流图 . . . . . . . . . . . . . . . . . . . . . . .

8、. . . . . . . . .334.2.1流图的定义. . . . . . . . . . . . . . . . . . . . . . . . . .344.2.2基本块的划分和流图的构造方法. . . . . . . . . . . . . .344.2.3实现细节 . . . . . . . . . . . . . . . . . . . . . . . . . . . .344.3活性分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .374.3.1算法概述 . . . . . . . . . .

9、. . . . . . . . . . . . . . . . . .374.3.2具体实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . .384.4寄存器分配 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .404.4.1干涉图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .404.4.2图染色算法. . . . . . . . . . . . . . . . . . . . . . .

10、. . .404.4.3具体实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . .404.5代码翻译 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .425MIPS目目目标标标代代代码码码435.1MIPS栈规范 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .435.2难点总结 . . . . . . . . . . . . . . . . . . . . . . . . . . .

11、. . . . .442Chapter 1类类类型型型检检检查查查在类型检查之前, 我们假设对MiniJava 源代码的词法分析已经做完. 此时词法分析器向我们提供了MiniJava 程序的抽象语法树(AST), 那么之后的类型检查将全部基于这棵语法树. 经过观察我发现类型检查项目可以根据侧重点的和复杂度的不同分为三大类. 其中后项的检查基于前面检查已经完成的基础上, 以下是三类检查的具体项目:1. 类, 方法和变量的重定义循环继承2. 对未定义的类, 方法和变量的引用; 数据类型不匹配3. 对未初始化的变量引用从未使用的变量定义为了避免歧义, 下面用一个简单的程序列举了上面出现的几个典型

12、的语法错误.1class MyClass 2int myInt;34/ DECLARATION of unused variable5boolean myBoolean;67/ REFERENCE of undefined class8MyClass2 myClass;910/ REDEFINITION of variable11boolean myBoolean;123编译原理实习报告张弛, 0084823113public int getMyInt () 1415/ REFERENCE of undefined variable16return myInt2;171819/ REDEFIN

13、ITION of method20public int getMyInt () 2122/ REFERENCE of undefined method23return this.getMyInt2 ()242526public int printInt () 27int tmp;2829/ REFERENCE of uninitialized variable30return tmp;31323334/ REDEFINITION of class35class MyClass 361.1符符符号号号表表表在进行第一步检查之前, 首先需要对MiniJava 程序结构进行分析, 然后构造出相应的符

14、号表. 符号表的功能为描述整个程序的逻辑结构, 包括类结构、方法结构、变量属性. 并且提供快速查询一个特定类和方法的属性信息. 以方便我们实时查询在检查中遇到的变量和数据.1.1.1符符符号号号表表表结结结构构构第一次遍历语法树主要是为了建立起符号表, 符号表具体应包含以下元素: MiniJava 源程序由若干类定义构成. 所以符号表中应包含一个表存储所有类的定义信息, 并且能够根据类名实现快速查找. MiniJava 中一个类由若干域和方法组成. 域即类的成员变量, 方法即成员函数. 为了区分类中的变量和方法中定义的变量, 我们将前者称为成员变量, 将后者称为局部变量. 对于每个成员变量,

15、需要保存其对应的类型信息.对于每个成员函数, 需要一个表来查找其对应的方法声明信息. 成员函数中只包含变量, 但是一个需要注意的地方是函数的参数也可以看4编译原理实习报告张弛, 00848231作是局部变量的, 而且参数有其初始值,在记录变量信息时, 需要将其顺序记录下来.在类型检查中顺序对于参数调用时类型的对应匹配很重要.综上所述, 最终符号表的实现包含了三层结构从上到下依次为AllClassesTable,ClassTable 以及MethodTable. AllClassesTable 中包含了所有的ClassTable, 而每一个ClassTable 中包含了所有其定义的方法对应的Me

16、thodTable.这里我选择Hashtable 作为查找表的数据结构. Hashtable 提供了强大的添加函数Hashtable.add () 和查找函数Hashtable.get (). Hashtable 的存储结构基于二元组(key, value) . 在此项目中我使用String 作为key 类型来定位Hashtable 集合中的每个对象. 比如, 在AllClassesTable 内Hashtable 里类名(String) 作为key 然后其对应类的ClassTable 作为value. 当然其他类似查找表的数据结构如HashMap或者TreeMap 也是不错的选择. 下面是最

17、终符号表的实现中三种类的成员变量域部分:1package minijava.typecheck.symboltable;23public class AllClassesTable extends AbstractSymbol 45protected Hashtable allClasses;6protected String mainClassName;789public class ClassTable extends AbstractSymbol 1011protected AllClassesTable allClasses;12protected String className;1

18、3protected String parentClassName;14protected int lineNumber;1516protected Hashtable memberVariables;17protected Hashtable memberVariablesLine;18protected Hashtable memberMethods;192021public class MethodTable extends AbstractSymbol 2223protected AllClassesTable allClasses;24protected String methodN

19、ame;25protected String insideClassName;26protected SymbolType returnType;27protected int lineNumber;2829protected Vector paramNames;3031protected Hashtable localVariables;32protected Hashtable localVariablesLine;335编译原理实习报告张弛, 00848231关于以上代码, 有几点要特别说明一下:AbstractSymbol 类类类符号表的总抽象类, 所有符号表类都继承自它ClassT

20、able 类类类和和和MethodTable 类类类 xxxVariables 表示每个定义的变量的具体类型. SymbolType 是一个储存变量类型的类, 这个我们稍候会提到. xxxVariableLines 表示每个变量在源文件中定义的位置所在的具体行数, 在构造符号表的过程中如果出现重定义的变量, 需要由它提供重定义变量的具体位置. lineNumer 表示每个类定义开始时的具体行数, 功能同上. allClasses 是一个AllClassesTable, 当一个类中的某个变量是类类型的时候, 我们需要在AllClassesTable 中查找到该类型的具体信息.ClassTable

21、类类类 parentClassName 为该类的父类名 memberMethods 表示每个方法具体对应的MethodTable.MethodTable 类类类 insideClassName 为该方法所在类的类名 returnType 为SymbolType, 为该方法的返回值类型 paramNames 以Vector的形式保存了该函数所有参数的名字, 注意名字的顺序是有意义的,直接影响我们在类型检查中检查传入参数的对应类型. 这里我们同样把参数看成本地变量, 所以所有的参数类型信息将会保存在localVariables中(Hashtable).从上看出,在每个ClassTable 和Me

22、thodTable 中都有总体类索引表allClasses的链接, 这样的结构可以使三个类结合为一个整体, 在任任任意意意的的的结结结构构构中,我们都可以轻易访问到该该该程程程序序序里里里定定定义义义的的的所所所有有有资资资源源源信信信息息息.1.1.2变变变量量量类类类型型型在MiniJava语言的BNF中，我们可以清楚的看到一共有四种数据类型：整数类型Integer 布尔类型Boolean 整数数组IntArray 类类型Class6编译原理实习报告张弛, 00848231因此我们为他们分别用4个类型类来描述：1package minijava.typecheck.symboltable

23、;23public class SymbolType extends AbstractSymbol 4private String name;56public String getName () 7return name;8910public boolean isTheSameType (SymbolType other) 11return name.equals(other.getName ();12131415public class IntType extends SymbolType 16public IntType () 17super (int);18192021public cl

24、ass BoolType extends SymbolType 22public BoolType () 23super (boolean);24252627public class IntArrayType extends SymbolType 28public IntArrayType () 29super (int);30313233public class ClassType extends SymbolType 34public ClassType (String className) 35super (className);3637在代码中可以看到，所有类型类以SymbolType

25、作为超类, 只包含一个成员name. 然后四个类型类只是在构造函数中传入相应的name为构造参数.其中判断类型不匹配的代码也是比较name是否相同而已. 在本质上, 我只是对String作了一下包装而已. 但是这样使得程序架构更清晰且易于调试.综上所述, 符号表的类结构如下, 箭头指向的类继承自箭头发出所在的类.7编译原理实习报告张弛, 00848231AbstractSymbolAllClassesTableClassTableMethodTableSymbolTypeIntTypeBoolTypeIntArrayTypeClassType1.2重重重定定定义义义错错错误误误和和和循循循环环

26、环继继继承承承在完整的勾画出符号表的结构以后, 我们就可以开始遍历语法树尝试构造出整个符号表了. 在构造符号表的同时, 类型重定义是可以被检查出来的, 具体来说有四种重定义的情况: 程序中出现类的重定义在同一个类中出现方法的重定义, 因为MiniJava不不不允允允许许许方方方法法法的的的重重重载载载, 所以在同一类里只要出现同名的方法即算错误. 但是请注意MiniJava支支支持持持多多多态态态,所以子类对父类方法的重写是允许的, 这个在下面符号表功能实现部分会具体介绍. 在同一类里或者同一个方法中出现变量的重定义. 注意子类对父父父类类类变变变量量量的的的覆覆覆盖盖盖和方法中对对对成成成

27、员员员变变变量量量的的的覆覆覆盖盖盖都是支持的, 所以变量重定义只需要在同一类和同一个方法中检查即可. 在同一方法中出现参数名的重定义其实第四点本质上也是变量的重定义, 但是为了出错信息不跟第三点混淆, 故特意区分出参数和本地变量.在构造完整个符号表以后, 我们可以根据整体的类定义信息, 检查是否出现了循环继承, 其本质就是检查一个单出边的有向图里是否出现了环.1.2.1符符符号号号表表表功功功能能能实实实现现现在创建符号表时, 基本上都是往符号表中添加功能. 根据本阶段所需实现的方法有:1package minijava.typecheck.symboltable;23public clas

28、s AllClassesTable extends AbstractSymbol 8编译原理实习报告张弛, 008482314public boolean insertClass (String className, ClassTableclassDeclar);5public ClassTable getClassTable (String className);6public boolean isInheritanceLoop ();7public boolean isUndefinedClassExist ();8public boolean isOverrideError ();910

29、1112public class ClassTable extends AbstractSymbol 13public boolean insertVariable (14String varName, SymbolType varType, int lineNumber);15public boolean insertMethod (16String methodName, MethodTable method);17public SymbolType getVariableType (String varName);18public int getVariableLine (String

30、varName);19public MethodTable getMethodTable (String methodName);20public boolean isUndefinedClassExist ();21public boolean isOverrideError () 222324public class MethodTable extends AbstractSymbol 25public boolean insertParam (26String paramName, SymbolType paramType, int lineNumber);27public boolea

31、n insertVariable (28String varName, SymbolType varType, int lineNumber);29public boolean isParamListCompatible (30Vector paramList);31public boolean canOverride (MethodTable superMethod);32public SymbolType getVariableType (String varName);33public int getVariableLine (String varName);34public boole

32、an isUndefinedClassExist ();35在在在所所所有有有类类类中中中 insertXXXXX 的返回值全部是一个boolean, 表示如果插入相应表项时发现已有同名表项, 则返回false.AllClassesTable类类类 isInheritanceLoop (), isUndefinedClassExist (), isOverrideError ()三个方法都是在构造完符号表以后再调用, 只有当所有类信息收集完成以后才有可能对类变量进行相应的存在性检查 isUndefinedClassExist () 检查在所有定义的变量, 方法中的参数及返回值中检查其是否是类类

33、型, 如果是的话,检查相应的类是否存在. 只要有一个不存在, 返回true. 另外还要对每个类的父类进行检查. 为后面两个过程作准备.9编译原理实习报告张弛, 00848231 isInheritanceLoop () 检查是否出现了类循环继承. 出现则返回true isOverrideError () 检查所有类对其父类方法中同名方法的重写是否出现了错误. MiniJava 允许子类对其父类方法进行覆盖以实现多态,但是为了简化实现的难度规定: 如果子类中的方法m覆盖了父类中的方法m,那么要求两个方法的参数个数, 参数类型, 返回值类型完全一致.ClassTable 类类类 isUndefin

34、edClassExist()功能见上. AllClassesTable.isUndefinedClassExist() 对所有ClassTable调用此方法. 在此方法中需要检查该类的父类是否存在 isOverrideError () 功能见上. AllClassesTable.isOverrideError () 对所有ClassTable调用此方法. 在所有在该类中定义的method, 查找父类中是否有同名的method,如果有的话,使用MethodTable.canOverride(MethodTable superMethod) 进行检查.MethodTable 类类类 isParam

35、ListCompatible () 检查两个方法的参数是否对应一致 canOverride () 对两个方法的返回值及参数列表进行类型对应检查. isUndefinedClassExist () 功能同上每个方法的实现都是对前面定义好的成员域的简单读写, 细节可以参见源代码.1.2.2构构构造造造符符符号号号表表表因为符号表中的所有信息仅仅依赖程序的定义部分,对程序执行体不用关心.所以经过分析, 我们只需要在遍历下列语法树节点时需要添加属性动作: Goal MainClass ClassDeclaration ClassExtendsDeclaration VarDeclaration Met

36、hodDeclaration FormalParameter10编译原理实习报告张弛, 00848231除了上述节点以外我们都不需要关心.属性动作很明显, 比如在ClassDeclaration节点生成相应的ClassTable插入AllClassesTable, 在VarDeclaration 节点生成相应的变量名和SymbolType插入其定义位置对应的ClassTable或者MethodTable中.其中需要特别说明的是MainClass 的处理, 这里我们将其看作一个普通的Class定义, 只是其中没有变量定义信息和只有一个过程,过程中只有一句话.所以我们在MainClass 中要将其

37、对应的ClassTable和MethodTable都创建好,然后插入AllClassesTable, 并且通知AllClassTable将类名做好标记作为将来运行调用的入口.在我的代码中, minijava.typecheck.visitor 包下BuildSymbolTableVisitor类用于创建符号表.1.3未未未定定定义义义错错错误误误和和和类类类型型型不不不匹匹匹配配配在进行具体的匹配检查之前, 我们首先需要明确“类型匹配” 这个概念的具体含义, 即针对一条赋值语句1:A = B什么样的情况算作类型匹配? 我们需要对两种情况分开讨论:当当当A和和和B都都都是是是非非非类类类类类类型

38、型型时时时类型匹配当且仅当A和B的类型完全一致当当当A和和和B都都都是是是类类类类类类型型型时时时类型匹配当且仅当A和B同类或者A是B的祖先类当明确了这个概念以后, 那么在这一部检查中的关键函数isTypeMatch 就可以了. 因为类型匹配可能涉及到对两个不同的类的信息进行查找, 所以检查函数我们考虑由符号表类型AllClassesTable来提供:1package minijava.typecheck.symboltable;23public class AllClassesTable extends AbstractSymbol 4public boolean isSubClass

39、(String subClass, StringsuperClass) 5while (subClass != null & !subClass.equals(superClass) 6subClass = getClassTable (subClass).getParentClassName();789return (subClass != null);10111无论是赋值还是传参数其本质都是一种赋值11编译原理实习报告张弛, 0084823112public boolean isTypeMatch (SymbolType type, SymbolTypeparam) 13if (!type

40、.isTheSameType(param) 14if (! (type instanceof ClassType & (paraminstanceof ClassType) 15return false;16 else 17if (!isSubClass(18(ClassType) param).getClassName(),19(ClassType) type).getClassName() 20return false;2122232425return true;26271.3.1具具具体体体的的的检检检查查查项项项目目目1. System.out.println 语句打印的值只能为整数类

41、型2. 方法中实际返回的值和在定义的返回值类型匹配3. 赋值时左右操作数类型匹配4. 数组下标只能是整数5. if 和while 语句中的表达式只能是布尔类型6. & 左右的和!右边的表达式只能是布尔类型7. , +, -, * 左右的表达式只能是整数8. 调用过程时, 参数值和过程声明的参数类型匹配9. 创建数组时, 数组长度只能是整数类型1.3.2表表表达达达式式式节节节点点点的的的分分分析析析纵观MiniJava语言的BNF, 其大部分的内容都是在对Expression进行描述. 其定义如下:Expression:=AndExpression|CompareExpression12编译原

43、maryExpression” ”PrimaryExpressionTimesExpression:=PrimaryExpression” ”PrimaryExpressionArrayLookup:=PrimaryExpression”PrimaryExpression”ArrayLength:=PrimaryExpression”.”length”MessageSend:=PrimaryExpression”.”Identifier”(”(ExpressionList)?”)”ExpressionList:=Expression(ExpressionRest) ExpressionRest

45、int”Expression”AllocationExpression:=”new”Identifier”(”)”NotExpression:=”!”ExpressionBracketExpression:=”(”Expression”)”13编译原理实习报告张弛, 00848231从中可以看到, PrimaryExpression主要表示一些简单的表达式, 比如整数, 布尔值, 或者一个变量等. 而Expression则主要是一类复合求值表达式如算数表达式, 过程调用, 数组取值等等. 这个部分是MiniJava中唯唯唯一一一出出出现现现递递递归归归定定定义义义的地方,可以看到Express

46、ion PrimaryExpression (Expression) 的产生式链. 因此需要特别注意, 顺着产生式链往下走, 底层的表达式类型结果需要返回给父亲节点进行进一步检查. 比如在检查一个MessageSend节点时:MessageSend := PrimaryExpression”.”Identifier”(”(ExpressionList)?”)”首先需要给产生式右边所有的Expression进行检查(因为参数有可能是复合表达式, 比如算数表达式, 或者有可能是又一次过程调用), 当检查无误后, 需要返回该表达式的类型. 当收集完右边所有产生式的类型信息后, 就可以检查1. Pri

47、maryExpression是否是类类型2. PrimaryExpression类中是否有Identifier方法3. PrimaryExpression中的Identifier方法的相应参数类型和调用的参数表类型是否一一对应.都满足以后, 那么对该MessageSend节点检查结束, 返回该过程应该返回的类型以供上层节点继续检查.所以类型检查的所有Visitor都继承自GJDepthFirst接口, 表示它检查一个节点之后会返回一个语法节点对应的类型信息.1.3.3未未未定定定义义义错错错误误误未定义错误主要在使用表达式和过程调用时进行检查, 其主要有4种情况的未定义错误.1. 使用的变量未

48、定义2. 实例化类对象时类未定义3. 过程调用时相应类的调用过程未定义未定义错误因为情况比较少, 所以检查的时候涉及到的语法树节点相对也很少, 可以很快的检查完毕, 需要检查的节点如下:语法树节点待检查项目AssignmentStatement未定义变量ArrayAssignmentStatement未定义数组变量MessageSend调用过程未定义2PrimaryExpression未定义变量3AllocationExpression未定义的类2在这之前还需要检查相应的类是否为类类型, 因为类在语法树中只是一个PrimaryExpression3当PrimaryExpression是一个Id

49、entifier时, 可以确定它是一个变量调用14编译原理实习报告张弛, 00848231在我的代码中, minijava.typecheck.visitor包下UndefinedExceptionVisitor类用于检查未定义符号错误.1.3.4类类类型型型匹匹匹配配配错错错误误误类型匹配错误相对比较琐碎. 需要检查的项目很多.1. 过程定义中的返回值类型和实际返回的表达式类型不匹配2. 赋值过程中左右值类型不匹配3. 数组操作时数组变量不是数组类型(操作包括取值和取数组长度)4. 数组下标不是整数5. 数组赋值的右值不是整数6. if和while语句中的判断条件不是布尔类型7. print

50、ln语句中打印内容不是整数类型8. &, ! 表达式的子表达式不是布尔类型9. , +, -, *表达式左右的子表达式不是布尔类型10. 过程调用时传入参数类型和过程声明参数类型不匹配11. 实例化数组变量时数组长度不是整数类型每个检查项目相应的检查位置如下:语法树节点待检查项目MethodDeclaration过程返回值与定义值不匹配AssignmentStatement左右值类型不匹配ArrayAssignmentStatement数组变量不是数组类型数组下标不是整数类型右值不是整数类型IfStatement判断条件表达式不是布尔表达式WhileStatement判断条件表达式不是布尔表达

51、式PrintStatement打印内容不是整数类型AndExpression子表达式不是布尔类型CompareExpression子表达式不是整数类型PlusExpression子表达式不是整数类型MinusExpression子表达式不是整数类型TimesExpression子表达式不是整数类型ArrayLookup数组变量不是数组类型数组下标不是整数类型15编译原理实习报告张弛, 00848231ArrayLength数组变量不是数组类型MessageSend过程传入参数与声明参数不匹配ArrayAllocationExpression数组下标不是整数类型NotExpression子表达式

52、不是布尔类型在我的代码中, minijava.typecheck.visitor 包下TypeIncompatibleVisitor类用于检查类型不匹配错误.1.4未未未初初初始始始化化化变变变量量量和和和未未未使使使用用用变变变量量量这个部分是作为Bonus的选作部分. 其中未使用的变量我使用一个简单的标记表记录每个变量是否被使用过, 未初始化变量也是类似的用一个标记表来在翻译时模拟运行流之前是否有赋值操作. 所有这些检查仅仅只对本地变量进行了检查, 而不涉及类成员变量. 所以太过复杂的情况也检查不出来.展开代码叙述将会很繁琐, 就不赘述了,有兴趣的话可以参见minijava.typeche

53、ck.visitor包下的VariableExceptionVisitor 中的具体代码.16Chapter 2Piglet中中中间间间代代代码码码MiniJava是一种支持面向对象的高级语言, 而在底层汇编语言级别上, 支持的仅仅是算数运算和命令跳转这样的简单指令, 如何从复杂的高级语言等价的对应到底层语言级别上, 将继承, 多态这样的机制实现为一条条基本指令, 是这个阶段最重要也最核心的任务.2.1Piglet简简简介介介Piglet是一种接近中间代码的语言面向MIPS, 采用后缀式表达, 操作符在最前面比一般的中间代码抽象层次高, 语句中允许包含复杂的表达式, 不是严格的三地址码2.

55、HStoreStmt:=”HSTORE” Exp IntegerLiteral ExpHLoadStmt:=”HLOAD” Temp Exp IntegerLiteralMoveStmt:=”MOV E” Temp ExpPrintStmt:=”PRINT” ExpExp:=StmtExp|Call|HAllocate|BinOp|Temp|IntegerLiteral|LabelStmtExp:=”BEGIN” StmtList ”RETURN” Exp ”END”Call:=”CALL” Exp”(”(Exp) ”)”HAllocate:=”HALLOCATE” ExpBinOp:=Ope

56、rator Exp ExpOperator:=”LT”|”PLUS”|”MINUS”|”TIMES”Temp:=”TEMP” IntegerLiteralIntegerLiteral:=Label:=2.1.2语语语言言言细细细节节节TEMP寄寄寄存存存器器器一共有10000个TEMP寄存器可供使用, 其中TEMP 0, TEMP 1, , TEMP 19用于传递调用参数. 其它临时单元可以用作本本本过过过程程程内内内的的的局部变量(不用声明)条条条件件件跳跳跳转转转指指指令令令: CJUMP Exp Label18编译原理实习报告张弛, 00848231首先计算Exp 的值，如果值为1，执行

57、下一条指令，否则（一般为0）跳转到Label 处。比比比较较较指指指令令令: LT Exp1 Exp2首先计算Exp1，Exp2，如果Exp1 小于Exp2, 返回值为1，否则返回0。这个指令也可以用来测试一个内存地址是否为空（值为0）：将其与1进行比较。内内内存存存分分分配配配指指指令令令: HALLOCATE Exp首先计算Exp 的值，得到一个整数，对应于需要从堆空间分配到的字节数。该指令返回一个地址，指向新分配内存块的基址。整数与内存地址（例如指针）都是4 字节的，因此，分配得到的内存大小总是4的倍数。存存存储储储指指指令令令: HSTORE Exp1 IntegerLiteral E

58、xp2首先计算Exp1，得到一个地址，再计算Exp2，得到一个值，然后将Exp2求得的值存储到地址Exp1+IntegerLiteral中。Exp1是一个地址,IntegerLiteral是偏移地址。加加加载载载指指指令令令: HLOAD Temp Exp IntegerLiteral首先计算Exp，得到一个地址，然后将地址Exp+IntegerLiteral 中的值加载到临时单元Temp中从上可以看到, Piglet主要以动态内存空间和无限寄存器来组织数据, 其中动态申请的内存空间为我们处理类和数组提供了很大的便利, 在下面将详细讲述.2.2数数数组组组的的的表表表示示示先从简单开始, 首先

59、需要将MiniJava中的复合数据类型转换到Piglet中的简单表示, 那么这里我们使用动态空间来表示数组. 假设数组的长度为L, 那么动态空间的长度为L + 1, 空间的头四个字节存储长度L, 后面的空间顺序存储相应的数组数据.L01.L 2L 1具体细节是, 当使用new语句int arr = new int10;申请空间实例化一个数组变量arr时, 我们可以得到其申请的数组长度L =10, 使用L创建好动态空间后, 将动态空间的首地址返回给数组变量arr, 那么以后所有对数组arr的操作, 都基于这个空间的首地址进行访问.19编译原理实习报告张弛, 008482312.3类类类结结结构构

60、构表表表示示示更复杂的复合数据类型是类. 在面向对象语言中, 类是操作的主体. 数据和过程都是类的一部分, 称为类的成员. 类也是数据类型的一种. 但是在Piglet中间代码中, 数据类型只有基本类型整数和布尔, 并且严格区分过程和数据. 完成中间代码的转换, 第一步就是将类拆解.2.3.1数数数据据据和和和过过过程程程分分分离离离实际上类的处理方法和Java真正处理类的时候是一样的, 即一个类只有在真真真正正正实实实例例例化化化的的的时时时候候候才为其分配空间. 这个时候我们将使用HALLOCATE指令申请一段动态空间, 该空间存储结构如下:VtableDtable linkfield1fi

61、eld2.fieldnDtablemethod1method2.methodk一个类实例由两个表组成, Vtable代表Variable Table, 主要储存类的成员变量, Dtable代表Dispatch Table, 主要负责储存类的成员函数. Vtable表的头四个字节储存Dtable表的首地址, 这样两个表就结合到了一起. 类似数组的处理方法, 当为一个类变量实例化时, 我们就将生成的Vtable表首地址传给该变量. 因此在Piglet中, 对于复合类型, 储存都是其其其对对对应应应空空空间间间的的的首首首地地地址址址.Vtable field代表该类包含的所有成员变量, 如果是简单

62、类型, 则直接储存其值(整数或者布尔), 如果是复合类型(数组或者类), 则field中储存了相应的空间首地址.Dtable 在Piglet代码中, 标明一个函数主要是以该函数的入口Label为标志, 因为不同的类可以使用相同的函数名, 所以为了避免重复, 将MiniJava中一个类的函数转换为Piglet中过程名时, 我们使用类名+下划线+函数名的方法,这样就可以避免过程名重复了. 在上图中, 每个method都是该函数对应过程的Label.举一个直观的例子, 假设有MiniJava类定义信息如下:1class LinkedList 2int element;3boolean end;20编

63、译原理实习报告张弛, 008482314LinkedList next;56public boolean insert (int data);7public boolean delete (LinkedList data);8public boolean search (int data);9那么当我实例化LinkedList给变量赋值时, 将产生这样的结构:VtableDtable linkelementendnextDtableLinkedList insertLinkedList deleteLinkedList search2.3.2过过过程程程的的的转转转换换换这里产生了一个问题.

64、对于同一类的不同实例, 他们共享有同一个Dtable! 因为他们对应的过程名都一样. 可以让他们回收共用么? 当然可以, 只要编译初始化时为所有类在动态空间里开出一篇区域, 为每个类创建一个Dtable, 那么实例化类变量时, 就只需要创建一个Vtable了, 相应的Dtable link指向初始创建的公共Dtable即可.但是这个不是重点, MiniJava中的过程调用是以实例为前提的, 就是说首先要给出调用的是哪个实例, 然后再指明是该实例的哪个方法, 该方法调用期间仅仅能修改该实例中包含的成员变量. 但是到了Piglet中, 没有了实例的概念, 只有过程单独存在了, 如何决定过程中操作的

65、是哪个实例的数据?在将一个类的成员函数转化为Piglet中的过程时, 我们将所有的参数顺序后推一个, 将强制预留出的第一个寄存器(TEMP 0), 作为调用该函数的相应实例的空间首地址. 那么该过程执行的时候就知道了相应变量去哪里存取了:1. 如果使用的变量是本地变量(即过程的参数或者函数内部定义的变量), 那么直接使用相应的TEMP寄存器存取2. 如果使用的是类的成员变量, 那么根据该变量在Vtable中的位置作为偏移址, TEMP 0作为基地址, 对相应的内存区域进行存取.扩展上面的例子, 如果LinkedList中的insert函数的定义是:1class LinkedList 2publ

66、ic int insert (int data) 3LinkedList head;4boolean tmp;21编译原理实习报告张弛, 0084823156head = new LinkedList ();7next = head;8return data;910该函数中既有对类变量的实例化, 也有对本地变量和类成员变量的分别读写, 正好对涵盖了前面工作中的三个方面. 那么根据设计, 翻译出来的Piglet程序中LinkedList insert过程应该为:1LinkedList_insert2/*TEMP 1 stores parameter data*/2BEGIN3MOVE TEMP

67、2 0/*TEMP 2 stores local var tmp*/4MOVE TEMP 3 0/*TEMP 3 stores local var head*/5MOVE TEMP 36BEGIN/*Allocate space for head*/7MOVE TEMP 48BEGIN9MOVE TEMP 5 HALLOCATE 12/*Allocate Dtable*/10HSTORE TEMP 5 0 LinkedList_setElement11HSTORE TEMP 5 4 LinkedList_insert12HSTORE TEMP 5 8 LinkedList_setNext13M

68、OVE TEMP 6 HALLOCATE 16/*Allocate Vtable*/14HSTORE TEMP 6 4 0/*element at offset 4*/15HSTORE TEMP 6 8 0/*next at offset 8*/16HSTORE TEMP 6 12 0/*end at offset 12*/17HSTORE TEMP 6 0 TEMP 5 /*Dtable at offset 0*/18RETURN TEMP 6/*return base address*/19END20RETURN TEMP 421END22HSTORE TEMP 0 8/*write me

69、mber var next*/23BEGIN24RETURN TEMP 3/*loadmember var head*/25END26RETURN27BEGIN28RETURN TEMP 1/*loadlocal var data*/29END30END2.3.3处处处理理理继继继承承承上述设计只是考虑了最简单的类结构, 现在我们一步步解决更难的问题: 继承和多态. 如果一个类B继承自类A, 那么相应的的Vtable和Dtable要作怎样的修改?22编译原理实习报告张弛, 00848231成成成员员员变变变量量量表表表Vtable首先, 一个类的成员变量集合为其父类的成员变量集合加上它自己的成

70、员变量集合, 并且, 同名的变量不会发生覆盖. 即如果类B有成员变量m, 其父类A也有成员变量m, 那么在A的成员变量集合中, 两个成员m是不同的并且是同时存在的. 但是在B的成员函数中只能见到其自己的m, 除非把B上转型给一个A的类变量, 那么在A的函数中才能看到父类的成员m.基于这个原则, 在有类继承的情况出现时, Vtable的结构相应的变化为一个层次性的变量表. 表的前4个字节仍然指向类对应的Dtable, 但是第一层是该类的第一代祖先类的成员变量表, 第二层为相应第二代的祖先类变量表, ., 直到最后一层, 才是该类自己的变量表. 他们顺序的存放在连续的动态空间里组成了该类最终的Vt

71、able.这样层次结构的好处就是, 非常适合类的上上上转转转型型型赋赋赋值值值. 因为每个类都可以知道其层次变量表中应该有多少变量, 并且父类变量表是子类变量表的“前缀”. 那么将一个子类实例赋值给一个父类的句柄时, 父类的变量能够看到的就是从该地址空间开始的相应父类变量表的长度个变量. 这样我们赋值的时候不需要作任何转换的操作, 只要直接赋值即可.过过过程程程分分分配配配表表表Dtable类似的, 一个类的成员函数集合等于其父类的成员函数集合加上它自己的,但是和成员变量不同的是, 成员函数存在覆盖! 即如果在子类中存在方法m,父类中也存在方法m, 那么子类中的方法会将父类中的覆盖, 也就是说

72、子类中的Dtable里将不会有父类的方法.Dtable具体组织方式也类似于Vtable的层次结构, 顶层仍然是第一代祖先, 然后依次往下. 但是这里要注意的是, 如果子类函数覆盖了父类中的函数的话, 那么在Dtable里, 需要将父类函数对应位置的Label替替替换换换为子类函数的Label, 然后在子类的层次表中就不必再将该Label填入了.这样作替换的意义在于, 所有被覆盖的同名函数对应的Label位置都是同一个(即所有祖先类中第一个定义该函数的类所在层次的位置), 然后一个类所对应的Dtable是在实例化该类对象是就确定了的, 如果发生上转型赋值(比如类B是A的子类, B重写了A的函数m

73、, A = new B();) 那么这时父类句柄里对应空间的Dtable中的过程Label仍然是子类的, 那么当调用被覆盖的函数时, 执行的仍是子类的函数. 这样的机制成功的实现了多多多态态态!2.3.4实实实现现现细细细节节节实现Vtable和Dtable分别使用了两个类: VariableTable和DispatchTable, 以下是类声明体部分.1package minijava.translate.util;23public class DispatchTable 423编译原理实习报告张弛, 008482315private Hashtable methodAddressLabel

74、s;6private Vector methodList;78public DispatchTable ();9public DispatchTable (DispatchTable other);10public Vector getMethodList ();11public Vector getMethodMapping ();12public int getMethodOffset (String methodName);13public String getMethodAddressLabel (String methodName);14public int getMethodNum

75、ber ();15public void addMethod (String methodName, StringmethodAddressLabel);161718public class VariableTable 1920private HashtablevariableAddressOffsets;21private Vector variableList;2223public VariableTable ();24public VariableTable (VariableTable other);25public Vector getVariableList ();26public

76、 int getVariableAddressOffset (StringvariableName);27public int getVaribaleNumber ();28public void addVariable (String variableName);29因为层次性结构, 所以两个表都有一个带参数的复制构造函数. 因为构造一个类的Vtable时, 先取得其父类的构造好的Vtable, 然后在尾部添加上相应多出来的变量即可, 这样就需要用到复制构造函数了.VariableTable getVariableList返回该Vtable中所有变量的名字, 按他们在Vtable从上到下的顺

77、序. getVariableAddressOffset返回一个变量在Vtable中的偏移位置. 如果有重名变量, 返回最后那一个(即最靠近自身类中的那个)DispatchTable getMethodList返回该Dtable中所有过程的名字(注意是过程名不是Label名,即原来在类中的函数名), 按出现顺序. getMethodMapping返回上个函数中每个函数对应的Label名. getMethodOffset返回一个函数在Dtable中的偏移位置. 注意Dtable中函数不会有重名的情况, 因为子类函数会将父类的Label覆盖.24编译原理实习报告张弛, 00848231然后在符号表中

78、我们要把两个表的信息整合进符号表, 使得我们进行翻译时随时可以查到对应的变量和方法信息, 我们扩展了原来的ClassTable, 创建AdvancedClassTable:1package minijava.translate.symboltable;23public class AdvanceClassTable extends ClassTable 45DispatchTable dispatchTable = null;6VariableTable variableTable = null;78public DispatchTable getDispatchTable ();9publi

79、c VariableTable getVariableTable ();10这样作的好处是前面创建的符号表的Visitor可以几乎不用修改, 只需要在实例化ClassTable类的地方修改为AdvanceClassTable就可以了, 其他的地方都可以原封不动.2.4翻翻翻译译译模模模式式式接下来我们就可以一步一步将MiniJava程序翻译成Piglet程序了. 实现时,我们用类PigletStatement包装一条翻译好的Piglet语句, 其实本质上它就是一个String, 方便我们调试. 然后用PigletStatementList封装一段翻译好的Piglet代码,它对应一个MiniJa

80、va语法树翻译好的结果.PigletStatement和PigletStatementList都继承于超类AbstractPigletStatement. 其定义如下:1package minijava.translate.symboltable;23public class PigletStatement extends AbstractPigletStatement 4private String statement;56public PigletStatement (String statement);7public String toString ();89public static

81、PigletStatement getLabelStatement (Stringlabel) 10return new PigletStatement (label + NOOP);11121314public class PigletStatementList extendsAbstractPigletStatement 1516private Vector statementList;17private SymbolType valueType;18private PigletStatement tempAddress;25编译原理实习报告张弛, 0084823119private Pi

82、gletStatement originAddress;2021public PigletStatementList ();22public PigletStatement getTempAddress ();23public void setTempAddress (PigletStatement address);24public PigletStatement getOriginAddress ();25public void setOriginAddress (PigletStatement address);26public SymbolType getValueType();27p

83、ublic void setValueType(SymbolType valueType);28public int getSize ();29public void addPigletStatement (PigletStatementstatement);30public void emit (String code);31public void merge (PigletStatementList list);32public Vector getStatementList ();33public void outputAllPigletStatement ();34其中PigletSt

84、atementList包括四个成员:statementList所有Piglet语句集合valueType对应的原来MiniJava程序中算出的值的类型. 这个值主要用于MiniJava语法树中的MessageSend 节点的翻译MessageSend := PrimaryExpression”.”Identifier”(”(ExpressionList)?”)”这里调用类是个复合表达式PrimaryExpression, 所以在翻译过程中, 对于每一个Expression节点都要对其返回的PigletStatementList设置相应的类型信息. 以便在MessageSend 里能够知道具体是

85、哪一个类.tempAddress表示当前的Piglet程序中结果算完了是存放在了哪个寄存器里.originAddress如果这段PigletStatementList仅仅是简单的对一个变量取值, 并且该变量是一个类类类变变变量量量, 那么按照前段类的转换规则, 该变量应该储存在一片动态空间里, 那么orginAddress保存的就是该地址空间, 以”TEMP XX Offset”的形式.2.4.1读读读变变变量量量和和和写写写变变变量量量存取变量的相应函数需要添加在MethodTable中, 因为MiniJava语法树中所有的Statement都是相应MethodDeclaration下的子节

86、点.26编译原理实习报告张弛, 00848231因此我们扩展了原来的MethodTable, 新的AdvanceMethodTable继承自它,最大的区别就是添加了存取变量函数getVariableInfo,该函数返回一个PigletStatementList完成对应变量的取值工作, 具体实现是:1package minijava.translate.symboltable;23public class AdvanceMethodTable extends MethodTable 4private VariableTable variableTable = null;56public Vari

87、ableTable getVariableTable ();7public int getLocalVariableNumber ();89public PigletStatementList getVariableInfo (StringvariableName, ResourceManager r) 10PigletStatementList ret = new PigletStatementList ();11if (localVariables.containsKey(variableName) 12ret.setTempAddress(new PigletStatement (13T

88、EMP +14(getVariableTable ()15.getVariableAddressOffset(variableName)16+ 1);17ret.setOriginAddress(null);18 else 19PigletStatement newAddress = new PigletStatement (r.getNewTemp();20AdvanceClassTable classTable = (AdvanceClassTable)allClasses.getClassTable(insideClassName);21PigletStatement originAdd

89、ress = new PigletStatement(22TEMP 0 +23(4*24(classTable.getVariableTable()25.getVariableAddressOffset(variableName)26+ 1);27ret.emit(HLOAD + newAddress + +originAddress);28ret.setTempAddress(newAddress);29ret.setOriginAddress(originAddress);303132ret.setValueType(getVariableType(variableName);3334re

90、turn ret;3536不仅AdvanceClassTable会有VariableTable (对应我们前面提到的Vtable),AdvanceMethodTable自己也有一个VariableTable, 储存在过程中定义的本地变量偏移信息, 这个信息用于给本地变量分配TEMP寄存器.27编译原理实习报告张弛, 00848231注意, 无论是对类变量取值还是本地变量取值, 最后值都被放入了一个TEMP寄存器, 可以在PigletStatementList.getTempAddress ()中直接读取得到相应的值.其中出现了ResourceManager类, 其实它是一个接口, 负责统一进行

91、TEMP寄存器和Label的分配, 接口定义为1package minijava.translate.interfaces;23public interface ResourceManager 4public String getNewLabel ();5public String getNewTemp ();6翻译过程中该接口被翻译访问器minijava.translate.visitor.PigletTranslateVisitor实现.有了getVariableInfo的支持, 那么在一个表达式里存取任意一个变量就都很简单了.如果是想读取,那么最后结果肯定是存在其返回的PigletSta

92、tementList.getTempAddress()里.如果是想写入一个变量,那么需要先检查PigletStatementList.getOriginAddress()是否为空, 如果是, 则该变量为本地变量存储在TEMP寄存器里, 否则就是类变量存储在动态空间里. 前者直接写入getTempAddress ()得到的寄存器即可, 后者使用HSTORE写入动态空间.MiniJava提供的语法对变量进行写入的地方不多,只有AssignmentStatement和ArrayAssignmentStatement两个节点.2.4.2多多多于于于20个个个参参参数数数Piglet的语言特性只能支持过

93、程最多传20个参数, 在转换类结构时, 我们又使用了TEMP 0作为类地址, 所以实际可用的参数个数就只有19个了. 如果参数个数多于19个怎么办? 我使用的办法是前18个参数仍然使用TEMP1TEMP 18存取,从第19个参数起, 申请一片动态空间存入后面的所有参数, 然后将该空间的首地址放入TEMP 19作为参数传入. 在每个参数的开头再解开相应的动态空间.2.4.3布布布尔尔尔表表表达达达式式式在Java语言中, 如果有下面条件语句:if (false & someMethod () . else .如果someMethod函数中对类成员变量进行了修改的话, 那是否执行它将对后面的程序产

94、生影响.28编译原理实习报告张弛, 00848231实际上, Java在发现布尔表达式第一个子表达式已经为false的情况下是不会求第二个函数的.因此我们在翻译的过程中也应该遵循Java标准.还好MiniJava中只支持AndExpression, 因此我们只要在求值它过程中略作修改即可.即在翻译AndExpression:AndExpression := PrimaryExpression”&”PrimaryExpression设右边第一个PrimaryExpression的翻译结果为SubPigletExp1, 结果存放在TEMP A里, 第二个为SubPigletExp2, 结果存在在T

95、EMP B, 设最终结果存放在TEMP C里, 那么该AndExpression的翻译结果为:12.3SubPigletExp14.567CJUMP TEMP A falseLabel89.10SubPigletExp211.121314CJUMP TEMP B falseLabel15MOVE TEMP C 116JUMP doneLabel17faseLabel NOOP18MOVE TEMP C 019doneLabel NOOP2.4.4其其其他他他其他的语句难度都不太大, 参照上个学期编译原理课上讲的翻译模式即可.有几个小的细节需要注意的是: 在生成一个类的Vtable时, 需要将所

96、有变量清0 在生成一个数组时, 需要将数组元素清0 进入一个过程时, 需要将所有本地变量清0 对一个数组变量或者类变量引用时, 需要检查其地址是否为空对一个数组引用时, 需要检查下标是否越界29Chapter 3Spiglet中中中间间间代代代码码码Spiglet基本上是Piglet语法的一个子集. 和Piglet语法之间的最大差别就是去除了StmtExp, 即Spiglet中不允许复合表达式的存在.解决办法非常简单, 只要出现复合表达式的地方, 再它算完之后申请一个新的TEMP寄存器, 将结果存入TEMP, 然后返回这个寄存器就可以了.具体实现不再赘述.30Chapter 4Kanga中中

97、中间间间代代代码码码Spiglet中间代码中可以无限使用寄存器, 而最终的MIPS代码中可以使用的寄存器却是有限的. 在这一步中, 最重要的任务就是完成寄存器分配.4.1Kanga简简简介介介Kanga是一种面向MIPS的中间代码, 不过和Spiglet非常类似4.1.1文文文法法法BNFGoal:=”MAIN”IntegerLiteral”IntegerLiteral”IntegerLiteral”StmtList”END”(Procedure) StmtList:=(Label)?Stmt) Procedure:=Label”IntegerLiteral”IntegerLiteral”In

99、HLoadStmt:=”HLOAD” Reg Reg IntegerLiteralMoveStmt:=”MOV E” Reg ExpPrintStmt:=”PRINT” SimpleExpALoadStmt:=”ALOAD” Reg SpilledArgAStoreStmt:=”ASTORE” SpilledArg RegPassArgStmt:=”PASSARG” IntegerLiteral RegCallStmt:=”CALL” SimpleExpExp:=HAllocate|BinOp|SimpleExpHAllocate:=”HALLOCATE” SimpleExpBinOp:=Op

101、1还可用于表达式求值s0 - s7 ：存放局部变量, 在发生函数调用时一般要保存它们的内容t0 - t9 ：存放临时运算结果, 在发生函数调用时不必保存它们的内容3. 开始使用运行栈。有专门的指令用于从栈中加载（ALOAD）、向栈中存储（ASTORE）值 SPILLEDARG i 指示栈中的第i 个值第一个值在SPILLEDARG 0 中例如：ALOAD s3 (SPILLEDARG 1) 将栈中的第二个值取出放到寄存器s3中4. Call 指令的格式发生较大的变化没有显式调用参数，需要通过寄存器传递没有显式“RETURN” a0 - a3存放向子函数传递的参数如果需要传递多于4个的参

102、数，需要使用PASSARG 指令将其它参数存到栈中注意：PASSARG 是从1 开始的！PASSARG i 需要用SPILLEDARG i- 1 访问！5. 过程的头部含3个整数（例如：procA 5 3 4）第一个整数的含义与Spiglet 相同：参数个数第二个整数用于表示过程需要的栈单元个数，包含参数（如果需要）、溢出（spilled）单元、需要保存的寄存器第三个整数是procA 过程体中的最大参数数目例如，如果procA 调用procB 时用3个参数，而调用procC 用2个参数，调用procD 用4 个参数, 那么这个整数设为44.2构构构造造造流流流图图图为了能够高效的利用寄存

103、器, 我们需要知道在任意时刻同时活跃的寄存器有哪些. 这就需要进行活性分析. 在这之前, 所所所有有有的的的过过过程程程都要转化成一个流图, 流图由基本块构成.33编译原理实习报告张弛, 008482314.2.1流流流图图图的的的定定定义义义基基基本本本块块块(Basic Block)定定定义义义 1 程程程序中一个连续的语句序列，它的每次执行都是从这个序列中的第一语句开始，依次执行序列中的各个语句（每个语句执行且仅执行一次），直到执行完序列的最后一个语句为止。流流流图图图(Control Flow Graph)定定定义义义 2 表示各基本块（可能发生的）执行次序的有向图。流图的结点代表基本

104、块、有向边代表基本块之间的执行次序。4.2.2基基基本本本块块块的的的划划划分分分和和和流流流图图图的的的构构构造造造方方方法法法1. 对于每个过程, 找出所有的入口语句（leader,即基本块的第一个语句），所用的规则是：过程的第一个语句是入口语句过程中任何由Label开始的语句都是入口语句任何紧跟在JUMP和CJUMP语句之后的语句都是入口语句。2. 对于每个入口语句，其相应的基本块是由它和直到下一个入口语句（但不包含该入口语句）或程序结束语句（包含程序结束语句）的所有语句构成。3. 每个基本块都是流图的一个结点，包含程序第一个语句的基本块称为流图的首结点。4. 若基本块Bj紧跟在基

105、本块Bi之后，并且Bi的最后一句不是无条件转移语句，也不是程序结束语句，则从Bi到Bj有一条有向边；若基本块Bi的最后一句是条件转移语句或无条件转移语句，并且转移到Bj的第一个语句，则从Bi到Bj有一条有向边。4.2.3实实实现现现细细细节节节我分别实现了两个类FlowGraphNode和FlowGraph分别对应基本块和流图两个类. 其中FlowGraph的结构比较简单, 边关系都不用它储存, FlowGraphN-ode自己负责储存自己相连的边.1package spiglet.flowgraph.util;23public class FlowGraphNode 4private Vec

106、tor Vector statementRef;56private Vector successor;34编译原理实习报告张弛, 008482317private Vector predecessor;89private Vector jumpLabels;1011private String nodeLabel;12private MyBitSet inpSet;13private MyBitSet outSet;14private MyBitSet defSet;15private MyBitSet useSet;1617private MyBitSet livenessState;18p

107、rivate int statement;19202122public class FlowGraph 23private Vector nodes;24private Hashtable mapping;2526private TempReference exitCondition;2728private int maxCalledParameter;29private int parameter;30简单的解释一下各个成员变量的含义.FlowGraph mapping 为Label 基本块节点的映射. 方便跳转语句查找Label对应的基本块节点用. TempReference 是一个表明T

108、EMP寄存器引用类型的类, 它的声明为:package spiglet.flowgraph.util;public class TempReference private int temp_num;private boolean use;public TempReference (int temp_num);public void changeMode ();public int getTempNum ();public boolean isUse ();public String toString ();35编译原理实习报告张弛, 00848231一个TEMP寄存器在Spiglet语句中只有

109、两种状态, 第一种是读, 这时use = true, 另一种是写, 则use = false这里的exitCondition是表明该流图代表的过程是否有返回值, 如果有,那么RETURN的那个TEMP寄存器就对应了一个读类型的TempReference,否则如果是主过程的话, TempReference为空. 因为在活性分析时, 我们需要知道流图出口是有哪些寄存器是活跃的. maxCalledParameter 记录当前流图对应的过程中调用的其他过程的最大参数个数, 这个在实际翻译中要用到; parameter 表明当前流图对应过程的参数个数;FlowGraphNode statementRe

110、f表示基本块节点中每句Spiglet语句中的每个对TEMP寄存器的引用类型, Vector套Vector的原因是一条语句会访问多个寄存器. jumpLabels 表示当前基本块所有跳转出去的Label集合; nodeLabel 表示当前基本块的第一条语句的Label, 也有可能为空. inpSet, outSet都是稍候在活性分析时用到的.他们提供的方法如下:1package spiglet.flowgraph.util;23public class FlowGraphNode 45public FlowGraphNode (String nodeLabel);67public Vector

111、getSuccessor();8public Vector getPredecessor();910public String getNodeLabel();11public Vector getJumpLabels ();12public void addJumpLabel (String label);1314public void addSuccessor (FlowGraphNode n);15public void addPredecessor (FlowGraphNode n);16public void addStatement (17Vector statement, Stri

112、ng type);181920public class FlowGraph 2122public FlowGraph (TempReference condition, int parameter);2324public void updateParameter (int num);25public int getMaxCalledParameter ();36编译原理实习报告张弛, 0084823126public int getParameter ();2728public void addNode (29FlowGraphNode n, boolean linkPredecessor);

113、30public FlowGraphNode getNodeByLabel (String label);31public Vector getNodes ();3233public void linkJumpNodes ();34public void addEdge (FlowGraphNode src, FlowGraphNode dst);35在实际创建时, 注意对于每个过程都对应的是一个流图, 所以对所有的过程分析完以后实际上得到的是一个FlowGraph集合.而且会有一个流图中一个基本块都没有的情况: 例如SampleProcedure 0RETURN 0因为RETURN 语句不算

114、Statement, 那么这个流图中就出现了0基本块的情况, 注意这样边界情况的处理.4.3活活活性性性分分分析析析我们的目标是把临时无限寄存器替换为固定的寄存器集合, 首先, 需要知道在每条指令之后哪些变量是活跃的(live variable analysis). 这样就可以确定两个同时活跃的变量不能分配相同的寄存器.4.3.1算算算法法法概概概述述述定定定义义义 3 一个寄存器v在p点活跃当且仅当v在某个以p开始的路径上被读取了(use)并且没有写入(definition)出现在读取之前.换言之:定定定义义义 4 一个寄存器v在p点不活跃当v在没有在任何一个以p开始的路径上被读取了(use

115、) 或者所有以p开始的路径上写入(definition)都出现在读取之前.37编译原理实习报告张弛, 00848231Algorithm 1: Liveness AnalysisInput: N basic block node set Exit last node in basic blocksData: IN set of variables live at start of block OUT set of variables live at end of block USE set of variables with upwards exposed uses in block (use

116、 priorto definition) DEF set of variables defined in block prior to usebeginfor n N Exit do INn ;OUTExit INExit USEExitChanged N Exitwhile Changed 6= dochoose a node n ChangedChanged Changed nOUTn for s successors(n) doOUTn OUTn INsINn USEn (OUTn DEFn)if INn changed thenfor p predecessors(n) doChang

117、ed Changed pend4.3.2具具具体体体实实实现现现首先算法计算一直都是集合运算, Java本身提供一个不错的工具BitSet, 但是它只提供过程式的运算, 我们希望的是一种函数式的计算方式, 能够时调用过程更灵活, 于是我们扩展继承它重写了我们需要的函数.public class MyBitSet extends BitSet public MyBitSet (MyBitSet other);public MyBitSet OR (MyBitSet other);public MyBitSet subtract (MyBitSet other);38编译原理实习报告张弛, 008

118、48231这样就可以方便的进行活性分析要求的运算了,相应的我们在FlowGraphNode和FlowGraph类里添加了以下成员函数进行活性分析的计算:1package spiglet.flowgraph.util;23public class FlowGraphNode 45public void setInpSet(MyBitSet inpSet);6public void setOutSet(MyBitSet outSet);78public MyBitSet getInpSet();9public MyBitSet getOutSet();10public MyBitSet getDe

119、fSet();11public MyBitSet getUseSet();1213public void initUseAndDef ();1415private void updateUseAndDef (TempReference v);16private void updateLivenessState (MyBitSet liveness,TempReference v);17public void initLivenessState ();1819public MyBitSet getNextLivenessState ();202122public class FlowGraph

120、23public void doLivenessAnalysis ();24在FlowGraphNode中,initUseAndDef 求出初始的DEF和USE集合.updateUseAndDef 在initUseAndDef中被调用, 根据一条语句中TEMP寄存器引用情况对DEF和USE集合作相应的修改.initLivenessState 初始化活性信息, 因为活性分析算法求得的是一个基本块的入口和出口相应的活性信息, 在后面的寄存器分配算法中, 我们要得到任何一个时刻的活性信息, 就需要从相应的入口开始一步一步模拟语句的执行,得到所有的中间结果, initLivenessState的作用就

121、是, 将活性信息初始化为基本块的OUT.getNextLivenessState 不断的调用该函数, 就可以得到基本块中每个语句执行之后的活性状态信息.updateLivenessState 和updateUseAndDef的功能类似,不过是在getNextLivenessState中被调用39编译原理实习报告张弛, 008482314.4寄寄寄存存存器器器分分分配配配两个变量相互干扰(interfere)的条件: 初始状态都是活跃的(例如函数参数),或对于任一结点n同时属于outn, 或一个正在定义,另一个属于outn x = b c x不活跃,如果b活跃则相互干扰注意第三种情况很容易被

122、人忽略, 我们过于关注活跃变量而忽略了无关定义变量对这些变量的干扰.4.4.1干干干涉涉涉图图图图图图的的的结结结点点点变量图图图的的的边边边两个结点之间相互干扰则用边连起来采用图论中的图着色算法对干涉图G进行着色, 如果两个顶点之间存在一条边,则它们不能使用相同的颜色。利用图着色的算法给干涉图着色之后,就可以给相同颜色的顶点分配同一个寄存器。着色所需不同颜色的种类就是寄存器分配所需的顶点个数。4.4.2图图图染染染色色色算算算法法法算法略复杂, 且情况比较多, 故不再赘述, 可以参考去年郭耀老师编译原理课上的课件,也可以参见下面提供的地址:http:/ranger.uta.edu/nys

123、trom/courses/cse5317-sp10/lec/5317-16.pdf4.4.3具具具体体体实实实现现现1package spiglet.translate.util;23public class InterferenceGraph 45private static int MAX_NODE = 10000;6private HashSet edgeExistence;7private Vector Vector links;8private int degrees;910private int colors;40编译原理实习报告张弛, 008482311112private in

124、t max_color;1314private int maxCalledParameter;15private int total_spilled;16private int total_Sreg;17private int total_Treg;1819public InterferenceGraph (FlowGraph flowGraph);20public int getMaxCalledParameter ();2122public void addInterference (MyBitSet liveness);2324public void addEdge (int a, in

125、t b);25public int getSpilled ();26public int getSreg ();27public int getTreg ();2829public void deleteEdge (int a, int b);30public void deleteNode (int node);3132private void doColor (int remain);33private void doRegAllocation ();3435public boolean isTempSpilled (int temp_num);36public int getTempCo

126、lor (int temp_num);37真正实现时需要注意的几个地方: 因为一个流图对应一个干涉图, 所以构造函数的参数是一个FlowGraph 因为两个变量可能干涉多次, 但是很明显在干涉图里只需要连一条边, 为了不重复添加边我们使用一个哈希表edgeExistence存储已经添加进的边, 一条边用a MAX NODE + b 来表示 max color表示最大色数, 这里我们取max color = 18, 因为我们只选取s0,s1,.,s7,t0,t1,.,t9 一共18个寄存器, 保留a0,a1,a2,a3,v0,v1作特殊用途. doColor (0) 开始染色, 选取点的策略是:

127、如果存在度数小于max color的点, 那么选取所有满足条件中的最大度点如果上述条件不存在, 那么直接选取一个度数最大的点, Spill它如果是选取的Spill点, 那么该点从干涉图中永久删除, 然后继续对后面的图进行染色41编译原理实习报告张弛, 00848231如果不是Spill点, 那么该点从干涉图中删除, 但是删除之前必须保存该点连出的所有边, 以便后来对该点进行回染. 删除点的同时维护每个点的度数情况,以便后续的选取过程. doRegAllocation 完成真正的寄存器分配. 在染色过程中, 如果变量v被成功染色了, 那么colorv中存储了相应的颜色数, 如果不幸是被spi

128、ll出去了, 那么colorv = 1, 所以这个时候我们需要收集一共有多少个变量被spill了, 然后相应的为他们标号. 还有根据color信息统计有多少个s和t寄存器被使用了, 方便翻译的时候写入Kanga程序头的三个参数. isTempSpilled和getTempColor为最终提供给翻译程序使用的接口. is-TempSpilled查询一个TEMP寄存器是否被spill了,如果不是,那么该TEMP被分配到了寄存器, 调用getTempColor将返回具体寄存器名称, 如果isTempSpilled为真, 那么调用getTempColor将返回栈中Spill的具体位置.4.5代代代码码

129、码翻翻翻译译译语法树节点注意事项Procedure进入函数之前, 首先要对所有本函数中用到的Callee savedregister即s0,s1,.,s7进行保存在函数的开头将a0,a1,a2,a3的值拷贝到相应TEMP 0, TEMP1, TEMP 2, TEMP 3对应的本地寄存器.如果函数参数多余4个, 那么需要将栈中的初始若干个位置的值拷贝出来到TEMP 4, TEMP 5, .对应的相应寄存器中.退出函数之前, 首先要对所有本函数中用到的s0,s1,.,s7进行恢复CJumpStmt因为Spiglet中的Label 还是局部的, 但是Kanga中的Label是全局的, 所以如果在不同

130、的Spiglet过程中使用了同样的Label, 那么直接使用会出现问题. 我们这里将所有Spiglet中的Label转换成“过程名” + 下划线+ Label, 这样转换以后就不会出现同名Label了JumpStmt同上Call在向具体参数对应的寄存器传值时, 首先要对所有本函数中用到的Caller saved register即t0,t1,.,t9进行保存, 完成调用后把他们恢复Temp注意任何一个Spiglet语句使用TEMP寄存器之前, 先说明它是要读和还是写, 那么在Temp节点的位置, 如果是读的话, 并且该TEMP是被spill的, 那么我们为将它读取到一个v0或者v1寄存器里1,

131、作为结果寄存器返回, 否则的话, 如果是写寄存器, 那么需要返回其对应的储存位置, 无论是寄存器还是spill到内存.1视v0和v1的使用情况决定具体返回哪一个42Chapter 5MIPS目目目标标标代代代码码码底层MIPS代码中, 没有提供系统自动维护的栈, 需要我们通过手动维护栈指针sp来完成栈的转换.5.1MIPS栈栈栈规规规范范范MIPS Stack Frame LayoutArgument n.Argument 1Return Register ($ra)Old Frame Pointer ($fp)Register Save AreaLocal & TemporaryVaria

132、ble AreaNext Argument Build Area.Framepointer$fpStackpointer$spHighMemoryLowMemory上图是MIPS的规范栈的布局, 我的程序中就是按这个来布置的. 栈中分为五大部分:1. 第一部分保存$ra和$fp 寄存器43编译原理实习报告张弛, 008482312. 第二部分保存Callee Saved Register, 即$s0,$s1,.,$s73. 第三部分保存Caller Saved Register, 即$t0,$t1,.,$t94. 第四部分保存寄存器分配中被Spill的寄存器5. 第五部分为下一过程的调用参数预

133、留空间这样的布局, 每个过程刚进入时, 可以通过栈指针加上特定偏移址去上一帧里取超过4个的其他参数, 然后使用$fp对本帧的所有地址进行访问.5.2难难难点点点总总总结结结这一步总体没有太大的难度, 按照规范一步一步翻译就行了, 基本都是一对一的直接翻译. 只是有几个点需要注意的是: MIPS的打印和申请动态空间都是通过系统调用来完成的, 其中调用传参通过寄存器$a0,$v0来完成, 因为我的程序里特意保留下了这些寄存器没有分配给变量使用, 所以可以随便拿来. 但是如果这些通用寄存器用作了寄存器分配, 则在使用之前预先需要保存, 可以通过在栈里预留2个位置或者存入全局寄存器$gp, 两种方法都可以. 在Kanga的MOVERegOP型语句中, 翻译时是最繁琐的, 因为OP对应的MIPS操作可以是add, sub, mul, slt等, 而且根据操作数的不同, 还有立即数版本的addi, slti, multi等等. 当然根据操作数精确翻译到MIPS的效率是最好的, 但是如果觉得太繁琐了, 可以偷一点点懒, 如果遇到立即数的话, 将其装载到寄存器后统一使用寄存器性语句, 会使得程序比较易于维护.44

展开阅读全文

北京大学编译原理实习minijava 实验报告

最新文档