analyze.c

在linux下实行的简单的c语言编译器

/*Analyze.c
 *Analyze the syntax tree
 */
#include "Analyze.h"
#include "Symtab.h"

static int location = 0;	/*variable memory location*/

static Symtab *pTable;		
static FunEntry *pFun;

/*traverse the syntax tree.
 *Use preProc to traverse in preorder.
 *Use postProc to traverse in post order
 */
static void traverse(TreeNode *t,
			void (*preProc) (TreeNode *),
			void (*postProc)(TreeNode *))
{
	if (t!=NULL)
	{
		int i ;
		preProc(t);
		for (i = 0; i < MAXCHILDREN; i++)
			traverse(t->child[i], preProc, postProc);
		postProc(t);
		traverse(t->sibling, preProc, postProc);
	}
}

/*do nothing in preorder travere.
 */
static void nullpreProc(TreeNode *t)
{
	if (t==NULL) 
		return;
	else if (t->nodeKind == Dec)
	{
		switch (t->kind.dec)
		{
			case FunDefK:
				pFun = Lookup_Fun(t->attr.name);
				break;
			case CompK:
				pTable = t->attr.table;
				break;
		}
	}
		
}

/*do nothing in postorder traverse;
 */
static void nullpostProc(TreeNode *t)
{
	if (t==NULL || pTable == NULL)
		return;
	else if (t->nodeKind == Dec && t->kind.dec == CompK)
		pTable = pTable->parent;
}

/*insert a node to the symtab.
 */
static void insertNode(TreeNode *t)
{
	switch (t->nodeKind)
	{
	/*Declation kind*/
	case Dec:
	switch (t->kind.dec)
	{
	case FunDecK:
		if (Lookup_Fun(t->attr.name)==NULL)
			Insert_Fun(t->attr.name, t->type, t->child[0]);
		break;
	case FunDefK:
		if (Lookup_Fun(t->attr.name)==NULL)
			Insert_Fun(t->attr.name, t->type, t->child[0]);
		break;
	case VarK:
	{
		ValEntry Entry;
		TreeNode *child;
		for (child = t->child[0]; child!=NULL;child=child->sibling)
		{
			/*handle uninit situation*/
			if (child->nodeKind==Exp&&child->kind.exp==IdK)
			{
				if (Lookup_Var(pTable, pFun, child->attr.name, &Entry)!=pTable->level)
				{
					if (child->child[0] == NULL)
						Insert_Var(pTable, child->attr.name, t->type, 1);
					else
						Insert_Var(pTable, child->attr.name, t->type, child->child[0]->attr.val.i);
				}/*if(Lookup_Var(pTable...)*/
			}/*if (child->nodeKind==Exp...)*/
			/*handle init situation*/
			else if (child->nodeKind == Stmt && child->kind.stmt == AssignK)
			{
				if (Lookup_Var(pTable, pFun, child->child[0]->attr.name, &Entry) !=pTable->level)
				{
					if (child->child[0]->child[0]==NULL)
						Insert_Var(pTable, child->child[0]->attr.name, t->type, 1);
					else
						Insert_Var(pTable, child->child[0]->attr.name, t->type, child->child[0]->child[0]->attr.val.i);
				}/*if (Lookup_Var(pTable...)*/
			}/*else if(child->nodeKind == Stmt ...)*/
		}/*for (child = ...)*/
	}/*case VarK*/
		break;
	case CompK:
		pTable = CreateTab(pTable, pFun);
		if (pTable == NULL)
			fprintf(g_lst_file, "Out of Memory! lint %d\n", t->lineno);
		t->attr.table = pTable;
		break;
	default:
		break;
	}
	break;
	default:
		break;
	}
}

/*create stmtab by preorder traversal*/
void buildSymtab(TreeNode *tree)
{
	GlobalTable = CreateTab(NULL, NULL);
	if (GlobalTable==NULL)
		fprintf(g_lst_file, "Out of Memory! line %d\n", tree->lineno);
	pTable = GlobalTable;
	
	/*check if there is a main function*/
//	if (Lookup_Fun("main") == NULL)
//		g_error = TRUE;

	traverse(tree, insertNode, nullpostProc);
	
	printFunTab();
	printSymTab(tree);
}

/*report type error*/
static void typeError(TreeNode *t, char *msg)
{
	fprintf(g_lst_file, "Type error at line %d: %s\n", t->lineno, msg);
	g_error = TRUE;
}

/*check type, in postorder*/
static void checkNode(TreeNode *t)
{
	switch (t->nodeKind)
	{
	case Dec:
		if (t->kind.dec == CompK)
			pTable = pTable->parent;
		break;
	case Exp:
		switch (t->kind.exp)
		{
		case OpK:
			switch (t->attr.op)
			{
			case PLUS:
			case SUB:
			case MUT:
			case DIV:
				if ((t->child[0]->type!=Int&&t->child[0]->type!=Float)||(t->child[1]->type!=Int&&t->child[1]->type!=Float))
					typeError(t, "Op applied to non-number");
				else if (t->child[0]->type==Float||t->child[1]->type==Float)
					t->type = Float;
				else
					t->type = Int;
				break;
			case LT:
			case LE:
			case GT:
			case GE:
			case EQ:
			case NEQ:
				if ((t->child[0]->type!=Int&&t->child[0]->type!=Float)||(t->child[1]->type!=Int&&t->child[1]->type!=Float))
					typeError(t, "Op applied to non-number");
				else
					t->type = Bool;
				break;
			case AND:
			case OR:
				if ((t->child[0]->type!=Int&&t->child[0]->type!=Bool)||(t->child[1]->type!=Int&&t->child[1]->type!=Bool))
					typeError(t, "Op applied to non-boolean");
				else
					t->type = Bool;
				break;
				
			}/*switch (t->attr.op)*/
			break;
		case IdK:
		{
			ValEntry Entry;
			if (Lookup_Var(pTable, pFun, t->attr.name,&Entry)!=-1)
				t->type = Entry.type;
			else
			{
				ValEntry *pEntry;
				for (pEntry = pFun->para; pEntry!=NULL; pEntry = pEntry->next)
					if (strcmp(t->attr.name, pEntry->name)==0)
					{
						t->type = pEntry->type;
						break;
					}/*if(strcmp(t->attr...)*/
				if (pEntry == NULL)
					typeError(t, "reference to undefined id");
			}/*if (Lookup_Var...) else*/
		}/*case IdK*/
		break;
	case Stmt:
		switch(t->kind.stmt)
		{
			case IfK:
				if (t->child[0]->type!=Bool&&t->child[0]->type!=Int)
					typeError(t->child[0], "if test is not Boolean");
				break;
			case WhileK:
	//			if (t->child[0]->type!=Bool&&t->child[0]->type!=Int)
	//				typeError(t->child[0], "while test is not Boolean");
				break;
			case CallK:
			{
				FunEntry *pEntry = Lookup_Fun(t->attr.name);
				if (pEntry != NULL)
				{
					ValEntry *para;
					t->type = pEntry->type;
					for (para = pEntry->para, t=t->child[0]; para != NULL && t!=NULL; para = para->next, t=t->sibling)
						if (para->type!=t->type)
							typeError(t, "Call to function with wrong parameter");
					if (para != NULL || t != NULL)
							typeError(t, "Call to function with wrong parameter");
				}/*if (pEntry != NULL)*/
				else
					typeError(t, "call to undefined function");
			}/*case CallK*/
			break;
		case ReturnK:
			t->type = t->child[0]->type;
			if (t->type != pFun->type)
				typeError(t, "return type inconsistent with definition");
			break;
		case AssignK:
			if (t->child[0]->type != t->child[1]->type)
			{
				/*force the type convertion*/
				if (t->child[0]->type==Float&&t->child[1]->type==Int)
					t->type=t->child[1]->type=Float;
				else if (t->child[0]->type = Int && t->child[1]->type == Float)
					t->type = Int;
				else
					typeError(t->child[0], "assignment type mismatched");
			}/*if (t->child[0]->type...)*/
			t->type = t->child[0]->type;
			break;
		}
		break;
		}/*switch (t->kind.exp)*/
		break;
	}/*switch(t->nodeKine)*/
}

/*transform type*/
static void transNode(TreeNode *t)
{
	if (t->nodeKind == Exp && t->kind.exp == OpK)
	{
		switch(t->attr.op)
		{
			case PLUS:
			case SUB:
			case MUT:
			case DIV:
				if (t->type==Float&&t->child[0]->kind.exp == NumK)
				{
					t->child[0]->type = Float;
					if (t->child[0]->nodeKind == Exp&& t->child[0]->kind.exp == NumK)
						t->child[0]->attr.val.f = (float)(t->child[0]->attr.val.i);
				}/*if (t->type==Float&&t->child[0]...)*/
				if (t->type == Float&&t->child[1]->type == Int)
				{
					t->child[1]->type = Float;
					if (t->child[1]->nodeKind == Exp && t->child[1]->kind.exp == NumK)
						t->child[1]->attr.val.f = (float)(t->child[1]->attr.val.i);
				}/*if (t->type == Float&&t->child[1]...)*/
				break;
		}/*switch(t->attr.op)*/
	}/*if (t->nodeKind==Exp...)*/
}

void typeCheck(TreeNode *syntaxTree)
{
	/*type check*/
	traverse(syntaxTree, nullpreProc, checkNode);
	/*type transform*/
	traverse(syntaxTree, transNode, nullpostProc);
}