expr.c

unix环境下实现的cmm语言编译器

/*expr.c:对表达式进行语法分析*/
#include "cmm.h"

static int oper[] = { /*运算符对应于生成树上的操作符*/
#define xx(a,b,c,d,e,f,g) e,
#define yy(a,b,c,d,e,f,g) e,
#include "token.h"
};
static char prec[] = {/*运算符对应的优先级数组*/
#define xx(a,b,c,d,e,f,g) d,
#define yy(a,b,c,d,e,f,g) d,
#include "token.h"
};

float refinc = 1.0;	/*引用计数*/
static Tree expr1(int k);
static Tree unary(void);
static Tree postfix(Tree);
static Tree primary(void);
static Type super(Type ty);

/*expression: assignment | binary
 *assignment: unary '=' assignment
 */
Tree expr(int tok)
{
	static char stop[] = {IF,ID,0};
	DEBUG(fprint(2,"expr(%d) begin\n", tok));
	Tree p = expr1(3);
	if ('=' == t) {/*赋值运算是右结合的*/ 
		t = gettoken();
		p = asgntree(ASGN,p,expr(0));
	}
	if (tok)
		test(tok, stop);	
	DEBUG(fprint(2,"expr(%d) end\n", tok));
	return p;
}

/*binary: unary {binary-operator unary}
 *binary-operator: == != < > <= >= + - * / %
 *expr1函数处理所有的二元运算符。由于所有的二元
 *表达式都有相同的形式，所以它们可以用一个函数来处理。
 *形参k对应于expr1当前所处优先级。
 *prec[t]为当前运算符的优先级。
 */
static Tree expr1(int k)
{
	int k1;
	DEBUG(fprint(2,"expr1(%d) begin\n",k));
	Tree p = unary();
	
	/*外层循环控制只有优先级高于k的运算符才被处理,
     *它按照优先级从高向低的顺序处理。
	 */
	for (k1 = prec[t]; k1 >= k; k1--)
		while (prec[t] == k1) {
		/*对于相同优先级的运算符按照左结合的顺序处理*/
			Tree r;
			int op = t;
			t = gettoken();
			r = expr1(k1+1);
			p = (*optree[op])(oper[op], p,r);
		}
	DEBUG(fprint(2,"expr1(%d) end\n",k));
	return p;
}

/*unary: postfix | unary-operator unary
 *unary-operator: & * = - !
 */
static Tree unary(void)
{
	Tree p;
	
	DEBUG(fprint(2,"unary begin\n"));
	switch(t) {
	case '*': /*指针引用*/
		t = gettoken();
		p = unary();
		p = pointer(p);	/*将数组或函数当做指针，这样就可以
						 *引用它们的右值*/
		/*对函数的指针引用不能做为左值，
		 *对二维以上的数组的指针引用，将返回右边数组的类型*/
		if(isptr(p->type)
		&& (isfunc(p->type->type) || isarray(p->type->type)))
			p = retype(p, p->type->type);
		else
			p = rvalue(p);
		break;
				
	case '&':/*取地址运算符*/
		t = gettoken();
		p = unary();
		if(isarray(p->type) || isfunc(p->type))
			p = retype(p,ptr(p->type));
		else
			p = lvalue(p);
		if(isaddrop(p->op)) /*标记局部变量不能分配在寄存器中*/
			p->u.sym->addressed = 1;
		break;
	case '+':
		t = gettoken();
		p = unary();
		if (isarith(p->type))
			p = cast(p, promote(p->type));
		else
			typeerror(ADD,p,NULL);
		break;
			
	case '-':
		t = gettoken();
		p = unary();
		p = pointer(p);
		if (isint(p->type) || ischar(p->type))
			p = simplify(NEG, p->type,p,NULL);
		else
			typeerror(SUB,p,NULL);
		break;
	case '!':
		t = gettoken();
		p = unary();
		if(isarith(p->type))
			p = simplify(NOT,inttype,cond(p),NULL);
		else
			typeerror(NOT,p,NULL);
		break;
	case SIZEOF: {Type ty;
		t = gettoken();
		p = NULL;
		if ('(' == t) {
			t = gettoken();
			if (istypename(t)) {
				ty = type_name();
				expect(')');
			}
			else {
				p = postfix(primary());
				ty = p->type;
			}
		}else {
			p = unary();
			ty = p->type;
		}
		assert(ty);
		if (isfunc(ty) || 0 == ty->size)
			error("invalid type argument `%t' to `sizeof'\n",ty);
		p = consttree(ty->size, inttype);
	 }break;
	case '(':
		t = gettoken();
		if (istypename(t)) {/*强制类型转换*/
			Type ty,pty = NULL;
			ty = type_name();
			expect(')');
			p = pointer(unary());
			pty = p->type;
			if ((isarith(pty) && isarith(ty))
			|| (isptr(pty) && isptr(ty)))
				p = cast(p, ty);
			else if ((isptr(pty) && isint(ty))
			|| (isint(pty) && isptr(ty))) {
				p = cast(p, ty);
			}else if (ty != voidtype) {
				error("cast from `%t' to `%t' is illegal\n",
					p->type, ty);
				ty = inttype;
			}
			p = retype(p, ty);	
		}else
			p = postfix(expr(')'));
		break;
	default:
		p = postfix(primary());
	}
	DEBUG(fprint(2,"unary end\n"));
	return p;
}

/*postfix: primary {postfix-operator}
 *postfix-operator: '['expression']' 
 *					 '('[assignment {,assignment}]')' 
 *形参p是由primary返回的。
 */
static Tree postfix(Tree p)
{
	DEBUG(fprint(2,"postfix begin\n"));
	for(;;)
		switch(t) {
		case '[':{
		/*对数组的下标引用总是可以转换成通过指针间接引用*/
			Tree q;
			t = gettoken();
			q = expr(']');
			p = (*optree['+'])(ADD,pointer(p),pointer(q));
			
			/*把二维以上的数组，当成数组的数组。对它们下
			 *标操作结果的类型为子数组的类型，例如：
			 *int a[2][3]; 则a[1]的类型为int [3]的数组
			 */
			if(isptr(p->type) && isarray(p->type->type))
				p = retype(p, p->type->type);
			else
				p = rvalue(p);
				 }break;
		case '(':
		{
			Type ty;
			Coordinate pt;
			p = pointer(p);
			if(isptr(p->type) && isfunc(p->type->type))
				ty = p->type->type;
			else {
				error("found '%t' expected a function\n",p->type);
				ty = func(voidtype,NULL);
			}
			pt = src;
			t = gettoken();
			p = call(p, ty, &pt);
		}
		default:
			return p;
		} 
		DEBUG(fprint(2,"postfix end\n"));
		return p;
}
/*primary: identifer | constant | string-literal
 *			| '('expression')'
 *constant: integer-constant | charater-constant
 *	
 */
static Tree primary(void)
{
	Tree p;
	DEBUG(fprint(2,"primary begin\n"));
	switch(t) {
	case CCON:
	case ICON: 
		p = tree(CNST + ttob(tsym->type), tsym->type,NULL,NULL);
		p->u.v = tsym->u.c.v;
		break;
	case SCON:
		tsym = constant(tsym->type, tsym->u.c.v);
		if (NULL == tsym->u.c.loc)
			tsym->u.c.loc = genident(tsym->type, GLOBAL);
		p = idtree(tsym->u.c.loc);
		break;
	case ID:
		DEBUG(fprint(2,"id: %s\n",token));
		if((tsym = lookup(token, identifiers)) == NULL) {
			error("undeclared identifier '%s'\n",token);
			tsym = install(token,&identifiers,level,level > GLOBAL?FUNC:PERM);
			tsym->type = inttype;	
		}
		p = idtree(tsym);
		break;
	default:
		error("illegal expression\n");
		p = consttree(0,inttype);
		break;
	}
	t = gettoken();
	DEBUG(fprint(2,"primary end\n"));
	return p;
}

/*idtree建立变量名引用的机制。
 *对于除数组和函数以外的变量名，idtree将其当成一指针，
 *然后通过间接引用它的值。这时,idtree建立的就是变量的右值。
 *当变量名在表达式的左边，可以通过lvalue使用变量名的左值。
 */
Tree idtree(Symbol p)
{
	int op;
	Tree e;
	
	assert(p);
	p->ref += refinc;
	op = (GLOBAL == p->scope) ? ADDRG+P:ADDRL+P;
 	if(isfunc(p->type) || isarray(p->type)) {
	/*对于函数名和数组名不能做为左值使用，idtree
	 *没有生成引用它们的右值，对它们处理由在表达式中的
	 *位置决定*/
		e = tree(op, p->type, NULL,NULL);
		e->u.sym = p;
	}else {
		e = tree(op,ptr(p->type),NULL,NULL);
		e->u.sym = p;
		e = rvalue(e);
	}		
	return e;	
}

/*引用p的右值*/
Tree rvalue(Tree p)
{
	Type ty = deref(p->type);
	return tree(INDIR + ttob(ty),ty,p,NULL);
}

/*使用p的左值*/
Tree lvalue(Tree p)
{
	if(generic(p->op) != INDIR) {
		error("lvalue required\n");
		return p;
	}else if(p->type == voidtype)
		warning("'%t' used as an lvalue\n",p->type);
	return p->kids[0];
}

/*返回p的类型为ty的副本*/
Tree retype(Tree p, Type ty)
{
	Tree q;
	assert(p);
	if(p->type == ty)
		return p;
	q = tree(p->op, ty,p->kids[0],p->kids[1]);
	q->u.sym = p->u.sym;
	return q;
}

/*pointer:将函数和数组类型转换成指针*/
Tree pointer(Tree p)
{
	assert(p);
	if(isarray(p->type))
		p = retype(p, atop(p->type));
	else if(isfunc(p->type))
		p = retype(p, ptr(p->type));
	return p;
}

/*cond:将p转换成条件表达式*/
Tree cond(Tree p)
{
	int op = generic(p->op);
	if (op == EQ || op == NE || op == NOT 
	|| op == LE || op == LT || op == GE || op == GT)
		return p;
	p = pointer(p);
	p = cast(p, promote(p->type));
	return  (*optree[NEQ])(NE,p,consttree(0,inttype));
}

/*cast:将p转换成类型为ty的树*/
Tree cast(Tree p, Type ty)
{
	Type pty = p->type;
	if (pty == ty)
		return p;
	switch (pty->op) {
	case CHAR: p = simplify(CVC,inttype,p,NULL);break;
	case INT:	break;
	case UNSIGNED: break;
	case POINTER:
		if(isptr(ty)) {
			if((isfunc(pty->type) && !isfunc(ty->type))
			|| (isfunc(ty->type) && !isfunc(pty->type)))
			warning("conversion for '%t' to '%t' is compiler dependent\n",
			p->type,ty);
			return retype(p, ty);
		}else
			p = simplify(CVP, unsignedtype,p,NULL);
			break;
	default: assert(0);
	}
	{	Type sty = super(ty);
		pty = p->type;
		if(pty != sty) {
			if(pty == inttype)
				p = simplify(CVI, sty, p, NULL);
			else 
				p = simplify(CVU, sty, p, NULL);
		}
	}
	if(p->type == ty)
		return p;	
	if(ty == chartype)
		p = simplify(CVI, ty, p, NULL);
	else if(ty == unsignedtype || isptr(ty))
		p = simplify(CVU, ty, p, NULL);
	else
		p = retype(p, ty);
	return p;
} 

static Type super(Type ty)
{
	if(ty == chartype || ty == inttype)
		return inttype;
	if(isptr(ty) || ty == unsignedtype)
		return unsignedtype;
	assert(0);
	return NULL;
}

char *funcname(Tree f)
{
	if(isaddrop(f->op))
		return stringf("'%s'", f->u.sym->name);
	return "a function";
}