decl.c

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

/*decl.c:对声明符进行语法分析*/
#include "cmm.h"
Symbol cfunc;

static Type specifier(void);
static void declaration(void *(*dcl)(char*, Type, Coordinate*));
static void init_global(Symbol p, int flag);
static Symbol dcl_global(char *id, Type ty, Coordinate *pos);
static Type tnode(int op, Type ty);
static Type reverse_dclr(char **id, Symbol **params, int abstract);
static Type declarator(Type base, char **id, Symbol **params,int abstract);
static Symbol *parameter_list(Type fty);
static Symbol dcl_param(char *id, Type ty, Coordinate *pos);
static void func_defn(char *id, Type ty, Symbol params[], Coordinate *pt);
static Symbol dcllocal(char *id, Type ty, Coordinate *pos);
static void doglobal(Symbol p, void *cl);
static void doconst(Symbol p, void *cl);

void program(void)
{
	int n;

	DEBUG(fprint(2,"grammatical analysis start\n"));
	level = GLOBAL;
	voidptype = ptr(voidtype);
	for( n=0; t != EOI; n++) {
		/* kind是一个由t索引的集合，同一个集合的元素的kind[t]值相同*/
		if(CHAR == kind[t]) {/*CHAR是declaration的fist集*/
			declaration((void *)dcl_global);
			deallocate(STMT);
			deallocate(FUNC);
		}else if(';' == t) {
			warning("empty declaratoin\n");
			t = gettoken();
		}else {
			error("unrecognized declaratoin\n");
			t = gettoken();
		}
	}
	if(0 == n)
		warning("empty input file\n");
	DEBUG(fprint(2,"grammatical analysis finish\n"));
}
/*specifier:分析类型说明符*/
static Type specifier(void)
{
	int op = t;
	t = gettoken();
	switch(op) {
	case CHAR:
		return chartype;
	case INT:
		return inttype;
	case VOID:
		return voidtype;
	default:
		assert(0);
	}
	return NULL;
}

/*exit_params:退出参数作用域，但是仍然保存参数作用域的符号表。
 *使得参数和局部变量具有相同的作用域。*/
static void exit_params(void)
{
	level--;
}
/*declaration:函数分析声明符,
 *由于declaration函数需要分析全局,局部，
 *变量并且对它们的处理方法不同，
 *于是dcl函数指针就用来传递它们的处理函数。
 */
static void declaration(void *(*dcl)(char*, Type, Coordinate*))
{
	Type ty,ty1;
	static char stop[]={CHAR,ID,0};/*declaration函数遇到非法符号时，跳过错误的
									*符号，直到stop集合*/
	DEBUG(fprint(2,"declaration  start:\n"));
	ty = specifier();
	if(ID == t|| '*' == t || '(' == t || '[' == t) {
		char *id;
		Coordinate pos;
		id = NULL;
		pos = src;
		
		/*对于每个全局作用域声明符的首个说明符需要区分
		 *函数定义和函数声明*/
		if(GLOBAL == level) {
			Symbol *params = NULL;
			ty1 = declarator(ty, &id, &params,0);
			if(params && id && isfunc(ty1) && '{' == t) {
			/*函数参数与局部变量具有相同的作用域。由于后面的
			 *复合语句会进入下层作用域。对于函数定义需要先退出
			 *当前参数的作用域。*/
				exit_params();
				func_defn(id, ty1, params, &pos);
				return ;
			}
			else if (isfunc(ty1))
				exitscope();/*对于函数声明需要退出参数作用域*/
		}else 
			ty1 = declarator(ty, &id, NULL, 0);
		for(;;) {
			if(NULL == id)
				error("missing identifier\n");
			else
				(void)(*dcl)(id, ty1,&pos);
			if(t != ',')
				break;
			t = gettoken();
			id = NULL;
			pos = src;
			ty1 = declarator(ty, &id, NULL, 0);	
		}
	}else
		error("empty declaration\n");
	test(';', stop);/*test函数用于错误恢复时，跳过非法的符号直到';'或stop集合*/
	DEBUG(fprint(2,"declaration finish:\n"));
}

/*defglobal:定义符号于seg段*/
static void defglobal(Symbol p, int seg)
{
	p->u.seg = seg;
	(*IR->segment)(seg);
	(*IR->export)(p);
	(*IR->global)(p);
}

/*init_global:对全局变量进行初始化。*/
static void init_global(Symbol p, int flag)
{
	Type ty;
	
	assert(p);
	if('=' == t || flag) {
		defglobal(p, DATA);
		if ('=' == t)
			t = gettoken();
		ty = initializer(p->type, 0);
		/*对于如int a[];形式的声明，initializer函数
		 *通过对初始化列表的分析来确定数组的长度
		 */
		if(isarray(p->type) && 0 == p->type->size)
			p->type = ty;
		p->defined = 1;
	}
}

/* dcl_global:函数进行语义检查，并将全局变量安装至
 * 符号表，为已初始化的变量分配空间。
 */
static Symbol dcl_global(char *id, Type ty, Coordinate *pos)
{
	Symbol p;

	assert(id && ty && pos);
	p = lookup(id, identifiers);

	/* 如果全局符号表中己存在该符号,
	 * 且它们类型不相等，或者对已定义的
	 * 符号进行重复定义，则报告出错信息。
	 */
	if (p && GLOBAL == p->scope) {
		if(!eqtype(ty, p->type)
		||(!isfunc(ty) && p->defined && '=' == t))
			error("redeclaration of '%s' previously declared _\
			at %w\n", p->name,&p->src);
	}else {
		p = install(id, &globals, GLOBAL,PERM);
		p->type = ty;
		p->sclass = AUTO;
		p->src = *pos;
		(*IR->defsymbol)(p);
	}
	if('=' == t && isfunc(p->type)) {
		error("illegal initialization for '%s' \n", p->name);
		t = gettoken();
	}else if('=' == t)
		init_global(p,0);
	return p;
}

static Type tnode(int op, Type ty)
{
	Type p;
	NEW0(p, STMT);
	p->op = op;
	p->type = ty;
	return p;
}

/*reverse_dclr:函数按照相反的顺序建立
 *起说明符的类型结构。
 */
static Type reverse_dclr(char **id, Symbol **params, int abstract)
{
	Type ty = NULL;
	switch(t) {
	case '*':
		t = gettoken();
		ty = reverse_dclr(id, params, abstract);
		ty = tnode(POINTER,ty);
		break;
	case ID:
		if (id)
			*id = token;
		else 
			error("extraneous identifier `%s'\n", token);
		t = gettoken();
		break;
	case '(':
		t = gettoken();
		if (abstract && (istypename(t) || ')' == t)) {
			/*抽象声明省略了变量名*/
			Symbol *args;
			ty = tnode(FUNCTION, ty);
			enterscope();
			args = parameter_list(ty);
			exitscope();
		}else {
			ty = reverse_dclr(id, params, abstract);
			expect(')');

			/*在象int (!);抽象声明中出现了非法符号，首先忽略非法
			 *符号，然后仍把它当做函数声明*/
			if (abstract && NULL == ty
			&& (NULL == id || NULL == *id))
				return tnode(FUNC, NULL);
		}
		break;
	case '[':
		break;
	default: 
		return ty;
	}
	while('(' == t || '[' == t) {
		switch(t) {
		case '(': /*函数声明*/
			t = gettoken();
			{Symbol *args;
				ty = tnode(FUNCTION, ty);
				enterscope();
				args = parameter_list(ty);
				if(params)
					*params = args;
				if (level > LOCALS) /*退出形参为函数的形参的作用域*/
					exitscope();
				break;
			}
		case '[': /*数组声明*/
			t = gettoken();
			{	int n = 0;
				if(ID == kind[t]) {
					n = intexpr(']');
					if(n <= 0 ) {
						error("'%d' is an illegal array size\n", n);
						n = 1;
					}
				}else 
					expect(']');
				ty = tnode(ARRAY, ty);
				ty->size = n;
			}break;
		default:
			assert(0);
		}
	}
	return ty;
}

/* declarator:函数分析说明符.
 * 首先调用reverse_dclr按反序建立Type结构.
 * 然后建立并返回变量的类型。形参abstract为1时
 * 表示抽象声明符。
 */
static Type declarator(Type base, char **id, Symbol **params,int abstract)
{
	DEBUG(fprint(2,"declarator start\n"));
	Type ty = reverse_dclr(id, params, abstract);
	
	for( ; ty; ty = ty->type)
		switch(ty->op) {
		case POINTER:
			base = ptr(base);
			break;
		case ARRAY:
			base = array(base, ty->size, 0);
			break;
		case FUNCTION:
			base = func(base, ty->proto);
			break;
		default:
			assert(0);
		}
	DEBUG(fprint(2,"declarator finish\n"));
	return base;
}

/*parameter_list:分析函数形参列表。
 *为函数类型建立原型，并返回形参的
 *符号列表
 */
static Symbol *parameter_list(Type fty)
{
	List list = NULL;
	int n = 0;
	Symbol *params;
	static char stop[] = {CHAR,IF,')',0};

	DEBUG(fprint(2,"parameter start\n"));
	if(istypename(t)) {
		Type ty1 = NULL;
		for(;;) {
			Type ty;
			char *id = NULL;
			if(!istypename(t))
				error("missing parameter type\n");
			n++;

			/*在函数参数声明中，可以省略参数名*/
			ty = declarator(specifier(), &id, NULL,1);
			
			/*如果有void类型，则其只能做为函数的唯一参数,
			 *且不能有变量名*/
			if((ty == voidtype && (ty1 || id))
			|| ty1 == voidtype)
				error("illegal formal parameter types\n");
			if (NULL == id) /*函数声明中允许形参的变量名为空*/
				id = stringd(n);
	
			/*append函数将形参添加至list链表*/
			if(ty != voidtype)
				list = append(dcl_param(id, ty, &src), list);
			if(NULL == ty1)
				ty1 = ty;
			if(t != ',')
				break;
			t = gettoken();
		}
	}
	fty->proto = newarray(length(list) + 1,
	sizeof (Type), PERM);
	params = ltov(&list, FUNC);/*ltov将list列表转换为数组*/
	for (n = 0; params[n]; n++)
		fty->proto[n] = params[n]->type;
	fty->proto[n] = NULL;
	test(')',stop);
	DEBUG(fprint(2,"paramater finish\n"));
	return params;
}

/*dcl_param:函数将对形参进行语义检查，并将其安装至符号表*/
static Symbol dcl_param(char *id, Type ty, Coordinate *pos)
{
	Symbol p;
	
	/*形参中的函数和数组将做为指针引用*/
	if(isfunc(ty))
		ty = ptr(ty);
	else if(isarray(ty))
		ty = atop(ty);
	assert(id && ty);
	p = lookup(id, identifiers);
	if(p && p->scope == level)
			error("redeclaration of '%s' previously declared _\
			at %w\n", p->name,&p->src);
	else { 
		p = install(id, &identifiers,level,FUNC); 
		p->type = ty;
		p->sclass = AUTO;
		p->src = *pos;
		p->defined = 1;
	}
	if('=' == t) {
		error("illegal initialization for parameter '%'\n", id);
		t = gettoken();
		(void)expr(0);
	}
	return p;
}

/*func_defn:进行函数定义。id为函数名，ty为函数类型，params为参数符号列表。
 *function-definition:
 *			type-specifier declarator compound-statement
 */
static void func_defn(char *id, Type ty, Symbol params[], Coordinate *pt)
{
	int i, n;
	Symbol *callee, *caller, p;

	DEBUG(fprint(2,"function define start\n"));
	for (n = 0;params && params[n]; n++)
		;
	callee = params;
	caller = newarray(n + 1, sizeof *caller, FUNC);
	for(i = 0; (p = callee[i]) != NULL && p->name; i++) {
		NEW(caller[i], FUNC);
		*caller[i] = *p;
		caller[i]->type = promote(p->type);
		if('1' <= *p->name && *p->name <= '9')
			error("missing name for parameter %d to function '%s'", i+1, id);
	}
	caller[i] = NULL;
	p = lookup(id, identifiers);
	if (p && isfunc(p->type) && p->defined)
		error("redefinition of '%s' previously defined at %w\n",
			p->name, &p->src);
	cfunc = dcl_global(id, ty, pt);
	assert(cfunc);
	cfunc->u.f.label = genlabel(1);
	cfunc->u.f.callee = callee;
	cfunc->defined = 1;
	labels = table(NULL,LABELS);
	refinc = 1.0;
	codelist = &codehead;
	codelist->next = NULL;
	compound(0, 0);
	definelab(cfunc->u.f.label);
	walk(NULL, 0, 0);
	(*IR->segment)(CODE);
	(*IR->export)(cfunc);
	(*IR->function)(cfunc, caller, callee);
	outflush();
	labels = NULL;
	cfunc = NULL;
	DEBUG(fprint(2,"function define finish\n"));
}	

static List autos;	/*局部变量的链表*/
/*dcllocal:函数将局部变量进行语义检查，并将其安装至符号表。
 */
static Symbol dcllocal(char *id, Type ty, Coordinate *pos)
{	
	Symbol p;
	assert(id && ty && pos);
	
	if(isfunc(ty)) 
		error("invalid storage class '%t %s'\n",
		ty, id);
	p = lookup(id,identifiers);
	if(p && p->scope == level)
			error("redeclaration of '%s' previously declared _\
			at %w\n", p->name,&p->src);	
	else {
		p = install(id, &identifiers, level, FUNC);
		p->src = *pos;
		p->type = ty;
		p->sclass = AUTO;
		p->defined = 1;
	}
	autos = append(p, autos);
	if('=' == t) {
		Tree e;
		t = gettoken();
		if(isscalar(ty)) {
			if('{' == t) {
				t = gettoken();
				e = expr(0);
				expect('}');
			}else
				e = expr(0);
		}else{ /*对局部数组的初始化*/

			Symbol t1;
			t1 = genident(ty, GLOBAL);
			init_global(t1,1);
			if(isarray(p->type) && p->type->size == 0
			&& t1->type->size > 0) 
				p->type = array(p->type->type,
						 t1->type->size/t1->type->type->size, 0);
			e = idtree(t1);
		}
		walk(asgn(p, e),0,0);
		p->ref = 1;
	}
	return p;
}
/*compound:函数分析复合语句
 *compound-statement:
 *			'{' {declaration} {statement} '}'
 */
void compound(int loop, int lev)
{
	Code cp;
	DEBUG(fprint(2,"compound statement begin:%d\n",lev));	
	walk(NULL, 0, 0);
	cp = code(Blockbeg);
	enterscope();
	expect('{');
	while (CHAR == kind[t])
		declaration((void *)dcllocal);
	cp->u.block.locals = ltov(&autos, FUNC);
	while (IF == kind[t] ||ID == kind[t])
		statement(loop, lev);
	walk(NULL, 0, 0);
	{ /*对局部变量按引用频率排序*/
        int i = 0,n,j,k;
        Symbol *p = cp->u.block.locals;
        for (n = 0; *p ; n++)
            p++;
        for (p = cp->u.block.locals; i < n-1; i++) {
            for (k=i,j=i+1; j < n; j++)
                if (p[j]->ref > p[k]->ref)
                    k = j;
            if (p[k] != p[i]) {
                Symbol tp = p[k]; p[k] = p[i]; p[i] = tp;
            }
        }
    }
	cp->u.block.level = level;
	code(Blockend)->u.begin = cp;
	exitscope();
	expect('}');
	DEBUG(fprint(2,"compound statement end:%d\n",lev));	
}

/*finalize:对全局变量和常量表中的还未定义的符号进行处理*/
void finalize()
{
	foreach(identifiers, GLOBAL, doglobal, NULL);
	foreach(constants,CONSTANT , doconst, NULL);
}

/*doglobal:处理在全局作用域中未定义的符号*/
static void doglobal(Symbol p, void *cl)
{
	if (!p->defined && isfunc(p->type) /*对于没有定义的函数声明，假定它的定义在外部*/
		 &&AUTO == p->sclass)
		(*IR->import)(p);
	else if (!p->defined && !isfunc(p->type)
	&& (AUTO == p->sclass)) {
		if (isarray(p->type)
		&& p->type->size == 0 && p->type->type->size > 0)
			p->type = array(p->type->type, 1, 0);
		if (p->type->size > 0) { /*对于未初始化的数组将其定义在BSS中*/
			defglobal(p, BSS);
			(*IR->space)(p->type->size);
		} else
			error("undefined size for `%t %s'\n",
				p->type, p->name);
		p->defined = 1;
	}
}

static void doconst(Symbol p, void *cl)
{
	if (p->u.c.loc) {
		assert(p->u.c.loc->u.seg == 0); 
		(*IR->segment)(DATA);
		(*IR->global)(p->u.c.loc);
		if (isarray(p->type))
			(*IR->defstring)(p->type->size, p->u.c.v.p);
		else
			(*IR->defconst)(ttob(p->type), p->u.c.v);
		p->u.c.loc->defined = 1;
		p->u.c.loc = NULL;
	}
}

/*typename分析强制转换中的抽象声明*/
Type type_name(void) 
{
	Type ty = specifier();

	if ('*' == t ||'(' ==  t ||'[' == t) 
		ty = declarator(ty, NULL, NULL, 1);
	return ty;
}