仿c语言自制编程语言笔记5

2018-01-30

中间代码的转换

中间代码的目的主要有两个:

让抽象语法树的代码转成更接近机器语言的代码.直接编写从抽象语法树到汇编语言的代码比较困难.

保留一些进一步优化的意图.
比如说两条语句n=n*1;n*=1;这两条语句都属于赋值类型,都不改变n的值,如果要删去的话属于两类节点Opassignnode,BinaryOpNode,优化代码会重复出现.
还有ifelseswitchwhile这些跳转语句,尽量翻译成接近汇编指令的形式,改成一系列的代码和jump. 按照语法树的结构遍历树,生成中间代码,因此生成的中间代码本身还是树型,中间代码是单纯的语句列表,列表由一系列表达式组成.
和抽象语法树的节点结构一样,组成中间代码的节点结构也是继承关系,如下所示:

IR				//中间代码的根节点
Stmt				//基类
	Assign			//赋值
	CJump			//跳转
	Jump			//无条件跳转
	Switch			//多分支跳转
	LabelStmt		//标签
	ExprStmt		//仅包含一个表达式的语句
	Return			//返回语句
Expr				//基类
	UnaryOp			//一元运算
	BinaryOp		//二元运算
	Call			//函数调用
	Addr			//取地址
	Mem			//取值
	Var			//变量
	Int			//整数常量
	Str			//字符串常量

相比于语法树中的表达式节点,这里的表达式的类型直接定义在基类中,为asm中定义的type,而不是语法树中定义的type,asm中定义的type只含有定义不同字节长度INT类型.除此之外还要制定运算符op的类型,用一个枚举类型定义各种运算符的名称.而且运算符的定义有有无符号的区分,这样asm.Type中的类型就不需要符号.类型中的代码基本都和翻译对应的语法树节点代码相符.

IRGenerator

和语义分析的几个类的结构一样,都是对抽象语法树进行遍历,但是每个对表达式的visit方法返回的不是空,而是一个中间代码的表达式节点对象.而且这个对象要保存到对应的抽象语法树的节点上.
对stmtnode的处理不返回新生成的节点,而是用一个列表来保存每条转换后的stmt.完毕后才保存到对应的函数节点上.
总的启动入口:

public IR generate(AST ast){
    	for(DefinedVariable var:ast.definedVariables()){
    		if(var.hasInitializer()){
    			var.setIR(transformExpr(var.initializer()));
    		}
    	}
    	for(DefinedFunction func:ast.definedFunctions()){
    		func.setIR(compileFunctionBody(func));
    	}
    	if(errorHandler.errorOccured()){
    		throw new SemanticException("IR generation failed");
    	}
return new IR(ast.location(),ast.
    }

删除了分开解析表达式是否需要返回值的功能.

流程控制

跳转语句

解析break和continue时,需要一个栈来存放当前对应跳转的Label,还需要一个栈来保存作用域生成临时变量时可以使用.
对于if的解析,解析可分为有条件跳转,无条件跳转,跳转标签组成.在需要添加label的地方在stmt列表中按顺序添加一个LabelStmt对象,当做跳转目标用来控循环等.
对于switch,while,for等跳转语句实现原理类似.

没有副作用的表达式转换

主要是二元运算符的表达式转换.首先转换左右表达式和操作符,先处理右侧表达式,因为有可能表达式会改变某些值,比如右侧有i++这种,左侧也有i这个值,那么处理左侧时i的值就会被+1,还要处理指针之间的运算:

public Expr visit(BinaryOpNode node) {
    Expr right = transformExpr(node.right());
    Expr left = transformExpr(node.left());
    Op op = Op.internBinary(node.operator(), node.type().isSigned());
    type.Type t = node.type();
    type.Type r = node.right().type();
    type.Type l = node.left().type();
    //指针类型间的运算
    if (isPointerMinus(op, l, r)) {
        //指针相减的情况,添加一个除法,除去基本类型的大小.
        Expr tmp = new BinaryOp(asmType(t), op, left, right);
        return new BinaryOp(asmType(t), Op.S_DIV, tmp, ptrBaseSize(l));
    }
    else if (isPointerAddNum(l,op,r)) {
        // 指针加上一个整数的情况,要乘上基本类型的大小.
        return new BinaryOp(asmType(t), op,
                left,new BinaryOp(asmType(r), Op.MUL, right, ptrBaseSize(l)));
    }
    else if (isNumAddPointer(l,op,r)) {
        //同上
        return new BinaryOp(asmType(t), op,
                new BinaryOp(asmType(l), Op.MUL, left, ptrBaseSize(r)),
                right);
    }
    else {
        return new BinaryOp(asmType(t), op, left, right);
    }
}

有副作用的表达式转换

副作用是指执行表达式时,表达式除返回值之外产生的影响,比如赋值语句会导致内存中的某个值发生了变化,比如一个函数的调用也会改变内存中某些值,也存在副作用.
有副作用会导致语句的执行顺序会对结果产生影响,不利于程序的优化.
如何转化带副作用的表达式:

要严格保证一条语句中副作用部分和其他部分发生的顺序不变,这样生成的中间代码也按顺序排列.
有副作用的情况分为赋值和函数调用.
有副作用的表达式如果含有函数调用,那么就会多出一个表达式,visit方法只能返回一个Expr,需要向stmts列表中添加.
要灵活运用临时变量,对于有递归的表达式,先生成一个临时变量来保存子表达式的值,然后返回给上一层表达式.
什么是左值?比如一个语句int i=0;i++=i;这样编译不合法,因为赋值左边的(expr)++拆成了三个部分,int tmp=i;i=i+1; return tmp;返回的是一个临时局部变量,不是一个左值.因此int i=0;i=i++;这样的语句i的值还是0.
左值转换
C–中左值包括:

变量,节点为VariableNode
指针取值,节点为DereferenceNode
数组,节点为ArefNode
结构体和联合体的成员,节点为PtrMemberNode,MemberNode
如果一个变量写在左边那么需要转换成这个变量的地址的代码,如果写在右边,那么就转换成获取变量的值的代码.
变量的节点作为左值的话直接可以转成Addr中间节点,右值的话直接转成Var中间节点.具体对应的方法是visit到MemberNode,或者二元运算节点,转化为一个Derefer解引用节点,其中保存了一个解引用的地址.

结构体成员的偏移,要考虑字节对齐.字节对齐的调用主要通过计算每个成员的偏移量,这样在结构体调用成员时直接转成对应的地址,然后再加上一个Mem节点,既可以成为右值,也可以成为左值.代码中需要频繁用到左值和右值的情况,为了方便,将表达式先转成解引用节点或者Var节点,这些都是右值,写一个addressOf方法专门用来将右值转左值.