analyze.c

1.小型编译器 2。支持整数

/****************************************************/
/* File: analyze.c                                  */
/* Semantic analyzer implementation					*/
/* for the C_Minus compiler							*/
/****************************************************/

#include "Globals.h"
#include "Util.h"
#include "Parse.h"
#include "SymTab.h"
#include "Analyze.h"

/* counter for variable memory locations */
static int location = 0;
static int IsInRecord = 0;
static int IsField = 0;

/* current symble table */
//static Symtab * pTable;
static FunEntry * pFun;
static StructEntry *pStruct;

/* procedure traverse is a generic recursive
 * syntax tree traversal routine:
 * it applies preProc in preorder and postProc 
 * in postorder to tree pointed to by t
 */
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);
	}
}

/* nullProc is a do-nothing procedure to 
 * generate preorder-only or postorder-only
 * traversals from traverse
 */
static void nullpreProc(TreeNode * t)
{ 
	if (t == NULL) return;
	else if (t->nodekind == DecK) {
		switch (t->kind.dec)
		{
		case FunDefK:
			pFun = Lookup_Fun(t->attr.name);
			break;
		case StructDecK:
			//printf("StructDecK\n");
			IsInRecord++;
			pStruct = Lookup_Struct(t->attr.name);
			break;
		case StructEndK:
			//printf("StructEndK\n");
			IsInRecord--;
			pStruct = NULL;
			break;
		case CompK:
			pTable = t->attr.table;
			break;
		}
	}
	else if(t->nodekind == ExpK){
		if(t->kind.dec == StructIdK){
			//printf("checkNode Struct Name :%s\n", t->attr.name);
			IsField++;
			ValEntry Entry;
			if (Lookup_Var(pTable, pFun, t->attr.name, &Entry) != -1)
				pStruct = Lookup_Struct(Entry.type.name);
			else
				printf("checkNode Struct %s not found!\n", Entry.type.name);
			//printf("checkNode Struct Type :%s\n", Entry.type.name);
		}
	}
}

static void nullpostProc(TreeNode * t)
{ 
	if (t == NULL || pTable == NULL) return;
	else if (t->nodekind == DecK && t->kind.dec == CompK)
		pTable = pTable->parent;
}

/* procedure insertNode inserts 
 * identifiers stored in t into 
 * the symbol table 
 */
static void insertNode(TreeNode * t)
{ 
	switch (t->nodekind)
	{ 
    case DecK:
		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)
				pFun = Insert_Fun(t->attr.name, t->type, t->child[0]);
			break;
		case StructDecK:
			if (Lookup_Struct(t->attr.name) == NULL)
				pStruct = Insert_Struct(t->attr.name, t->child[0]);
			break;
		case VarK:
		{
			ValEntry Entry;
			TreeNode * child;
			for (child = t->child[0]; child != NULL; child = child->sibling) {
				if (child->nodekind == ExpK && child->kind.exp == IdK) {
					if (Lookup_Var(pTable, pFun, child->attr.name, &Entry) != pTable->nestlevel)
						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);
				}
				else if (child->nodekind == StmtK && child->kind.stmt == AssignK) {
					if (Lookup_Var(pTable, pFun, child->child[0]->attr.name, &Entry) != pTable->nestlevel)
						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);
				}
			}
		}
			break;
		case CompK:
			pTable = Createtab(pTable, pFun, pStruct);
			if (pTable==NULL)
				fprintf(listing, "Out of memory error at line %d\n", t->lineno);
			t->attr.table = pTable;
			break;
        default:
			break;
      }
      break;
	default:
		break;
	}
}

/* function buildSymtab constructs the symbol 
 * table by preorder traversal of the syntax tree
 */
void buildSymtab(TreeNode * tree)
{
	GlobalTable = Createtab(NULL, NULL, NULL);
	if (GlobalTable==NULL)
		fprintf(listing, "Out of memory error at line %d\n", tree->lineno);
	pTable = GlobalTable;
	traverse(tree, insertNode, nullpostProc);
	if (TraceAnalyze)
	{ 
		printFunTab();
		printStructTab();
		printSymTab(tree);
	}
	Insert_SysFun();
}

static ExpType getType(TreeNode * t){
	//printf("getType\n");
	static FunEntry * pFun2, *pFun3;	
	if(t->kind.exp == StructIdK){
		//printf("StructIdK\n");
		return getType(t->child[0]);
	}
	return t->type.type;
}

static void setType(TreeNode * t, ExpType type){
	if(t->kind.exp == StructIdK)
		setType(t->child[0], type);
	else
		t->type.type = type;
}

static void typeError(TreeNode * t, const char * message)
{ 
	fprintf(listing,"Type error at line %d: %s\n", t->lineno, message);
	Error = TRUE;
}

/* procedure checkNode performs
 * type checking at a single tree node
 */
static void checkNode(TreeNode * t)
{ 
	switch (t->nodekind)
	{ 
    case DecK:
		if (t->kind.dec == CompK)
			pTable = pTable->parent;
		break;
	case ExpK:
		switch (t->kind.exp)
		{ 
		case OpK:
			switch(t->attr.op) {
			case PLUS: case SUB: case MUT: case DIV:
				if ((getType(t->child[0]) != Integer && getType(t->child[0]) != Double) ||
					(getType(t->child[1]) != Integer && getType(t->child[1]) != Double))
					typeError(t, "Op applied to non-number");
				else if (getType(t->child[0]) == Double || getType(t->child[1]) == Double)
					t->type.type = Double;
				else
					t->type.type = Integer;
				break;
			case LT: case LE: case GT: case GE: case EQ: case NEQ:
				if ((getType(t->child[0]) != Integer && getType(t->child[0]) != Double && getType(t->child[0]) != Char) ||
					(getType(t->child[1]) != Integer && getType(t->child[1]) != Double && getType(t->child[1]) != Char))
					typeError(t, "Op applied to non-number");
				else 
					t->type.type = Boolean;
				break;
			case AND: case OR:
				if ((getType(t->child[0]) != Integer && getType(t->child[0]) != Boolean) ||
					(getType(t->child[1]) != Integer && getType(t->child[1]) != Boolean))
					typeError(t, "Op applied to non-boolean");
				else
					t->type.type = Boolean;
				break;
			}
			break;
			
		case StructIdK:						
			break;
			
        case IdK:
			{
				ValEntry Entry;
				if(IsInRecord){
					ValEntry *pEntry;
					for (pEntry = pStruct->field; pEntry != NULL; pEntry = pEntry->next)
						if (strcmp(t->attr.name, pEntry->name) == 0) {
							t->type.type = pEntry->type.type;
							break;
						}
					if (pEntry == NULL){
						printf("IdK: %s\n", t->attr.name);
						typeError(t, "reference to undefined id");
					}
					printf("IsInRecord IdK: %s, type: %d\n", t->attr.name, pEntry->type.type);
					
				} else if(IsField){
					if (Lookup_Struct_Field(pStruct, t->attr.name, &Entry) != -1)
						t->type.type = Entry.type.type;
					else {
						printf("IdK: %s\n", t->attr.name);
						typeError(t, "reference to undefined id");
					}
					printf("Lookup_Struct_Field IdK: %s, type: %d\n", t->attr.name, Entry.type.type);
					if(IsField)
						IsField=0;
				} else {
					if (Lookup_Var(pTable, pFun, t->attr.name, &Entry) != -1){
						t->type.type = Entry.type.type;

						//printType(t->type);
						//printf("size:%d\n",Entry.size);
						
						//字符串转换						
						if((t->child[0] == NULL)&&(Entry.type.type == Char)&&(Entry.count > 1)){
							printf("IdK: %s\n", t->attr.name);
							t->type.type = String;
						}
						
						//printf("Name:%s:",t->attr.name);
						//printType(Entry.type);
					} else {
						ValEntry *pEntry;
						for (pEntry = pFun->para; pEntry != NULL; pEntry = pEntry->next)
							if (strcmp(t->attr.name, pEntry->name) == 0) {
								t->type.type = pEntry->type.type;
								break;
							}
						if (pEntry == NULL){
							printf("IdK: %s\n", t->attr.name);
							typeError(t, "reference to undefined id");
						}
					}
				}
			}
			break;
		}
		break;
    case StmtK:
		switch (t->kind.stmt)
		{ 
		case IfK:
			if (getType(t->child[0]) != Boolean && getType(t->child[0]) != Integer)
				typeError(t->child[0], "if test is not Boolean");
			break;
        case WhileK:
			if (getType(t->child[0]) != Boolean && getType(t->child[0]) != Integer)
				typeError(t->child[0], "while test is not Boolean");
			break;
		case CallK: 
		{
			//printf("Fun:%s\n",t->attr.name);
			FunEntry * pEntry = Lookup_Fun(t->attr.name);
			FunEntry * pEntry2 = Lookup_SysFun(t->attr.name);
			if (pEntry != NULL) {
				printf("Fun:%s\n",t->attr.name);
				ValEntry * para;
				t->type.type = pEntry->type.type;
				for (para = pEntry->para, t = t->child[0]; para != NULL && t != NULL;
					para = para->next, t = t->sibling)
					if (para->type.type != getType(t))
						typeError(t, "call to function with wrong parameter");
				if (para != NULL || t != NULL)
					typeError(t, "call to function with wrong parameter");
				//printf("Fun:%s\n",t->attr.name);
			}
			else if(pEntry2 != NULL){
				if(strcmp(t->attr.name, "read") == 0){
					if(t->child[0] == NULL)
						typeError(t, "read has no parameter");
					else if(t->child[0]->sibling)
						typeError(t, "read has more than one parameter");
					t->type.type = Void;
				}else if(strcmp(t->attr.name, "write") == 0){
					if(t->child[0] == NULL)
						typeError(t, "write has no parameter");
					else if(t->child[0]->sibling)
						typeError(t, "write has more than one parameter");
					t->type.type = Void;
				}else if(strcmp(t->attr.name, "abs") == 0){
					if(t->child[0] == NULL)
						typeError(t, "abs has no parameter");
					else if(t->child[0]->sibling)
						typeError(t, "abs has more than one parameter");
					else if(getType(t->child[0]) != Integer)
						typeError(t, "abs function with wrong parameter");
					t->type.type = Integer;
				}else if(strcmp(t->attr.name, "floor") == 0){
					if(t->child[0] == NULL)
						typeError(t, "floor has no parameter");
					else if(t->child[0]->sibling)
						typeError(t, "floor has more than one parameter");
					else if(getType(t->child[0]) != Double)
						typeError(t, "floor function with wrong parameter");
					t->type.type = Double;
				}else if(strcmp(t->attr.name, "ceil") == 0){
					if(t->child[0] == NULL)
						typeError(t, "ceil has no parameter");
					else if(t->child[0]->sibling)
						typeError(t, "ceil has more than one parameter");
					else if(getType(t->child[0]) != Double)
						typeError(t, "ceil function with wrong parameter");
					t->type.type = Double;
				}else if(strcmp(t->attr.name, "fabs") == 0){
					if(t->child[0] == NULL)
						typeError(t, "fabs has no parameter");
					else if(t->child[0]->sibling)
						typeError(t, "fabs has more than one parameter");
					else if(getType(t->child[0]) != Double)
						typeError(t, "fabs function with wrong parameter");
					t->type.type = Double;
				}else if(strcmp(t->attr.name, "fmod") == 0){
					if((t->child[0] == NULL)||(t->child[0]->sibling == NULL))
						typeError(t, "fmod has less two parameter");
					else if(t->child[0]->sibling->sibling)
						typeError(t, "fmod has more than two parameter");
					else if(getType(t->child[0]) != Double || getType(t->child[0]->sibling) != Double)
						typeError(t, "fmod function with wrong parameter");
					t->type.type = Double;
				}else if(strcmp(t->attr.name, "strcmp") == 0){
					if((t->child[0] == NULL)||(t->child[0]->sibling == NULL))
						typeError(t, "strcmp has less two parameter");
					else if(t->child[0]->sibling->sibling)
						typeError(t, "strcmp has more than two parameter");
					else if(getType(t->child[0]) != String || getType(t->child[0]->sibling) != String)
						typeError(t, "strcmp function with wrong parameter");
					t->type.type = Integer;
				}else if(strcmp(t->attr.name, "strcat") == 0){
					if((t->child[0] == NULL)||(t->child[0]->sibling == NULL))
						typeError(t, "strcat has less two parameter");
					else if(t->child[0]->sibling->sibling)
						typeError(t, "strcat has more than two parameter");
					else if(getType(t->child[0]) != String || getType(t->child[0]->sibling) != String)
						typeError(t, "strcat function with wrong parameter");
					t->type.type = Integer;
				}else if(strcmp(t->attr.name, "strcpy") == 0){
					printType(t->child[0]->type);
					printType(t->child[0]->sibling->type);
					if((t->child[0] == NULL)||(t->child[0]->sibling == NULL))
						typeError(t, "strcpy has less two parameter");
					else if(t->child[0]->sibling->sibling)
						typeError(t, "strcpy has more than two parameter");
					else if(getType(t->child[0]) != String || getType(t->child[0]->sibling) != String)
						typeError(t, "strcpy function with wrong parameter");
					t->type.type = Integer;
				}
			} else
				typeError(t, "call to undefined function");
		}
			break;
		case ReturnK:
			t->type.type = getType(t->child[0]);
			if (t->type.type != pFun->type.type)
				typeError(t, "return type inconsistent with definition");
			break;
		case AssignK:	
			//printf("AssignK:\n");
			if (getType(t->child[0]) != getType(t->child[1])) {
				printf("Not Equal:\n");
				printType(t->child[0]->type);
				printType(t->child[1]->type);
				if (getType(t->child[0]) == Double && getType(t->child[1]) == Integer){
					setType(t->child[1], Double);
					t->type.type = Double;
				} else if (getType(t->child[0]) == Integer && getType(t->child[1]) == Double) 
					t->type.type = Integer;
				else 
					typeError(t->child[0], "assignment type mismatched");
			}
			//printf("AssignK2:\n");
			t->type.type = getType(t->child[0]);;
			break;
		}
		break;
	}
}

/* procedure transNode transforms
 * a tree node type to the appropriate one 
 */
static void transNode(TreeNode * t)
{
	if (t->nodekind == ExpK && t->kind.exp == OpK) {
		switch(t->attr.op) {
		case PLUS: case SUB: case MUT: case DIV:
			if ((t->type.type == Double && getType(t->child[0]) == Integer)) {
				setType(t->child[0], Double);
				if (t->child[0]->nodekind == ExpK && t->child[0]->kind.exp == NumK)
					t->child[0]->attr.val.f = (double)(t->child[0]->attr.val.i);
			}
			if ((t->type.type == Double && getType(t->child[1]) == Integer)) {
				setType(t->child[1], Double);
				if (t->child[1]->nodekind == ExpK && t->child[1]->kind.exp == NumK)
					t->child[1]->attr.val.f = (double)(t->child[1]->attr.val.i);
			}
			break;
		}
	} else if (t->nodekind == StmtK && t->kind.exp == AssignK){
		if(getType(t->child[1]) == Double){
			if (t->child[1]->nodekind == ExpK && t->child[1]->kind.exp == NumK)
				t->child[1]->attr.val.f = (double)(t->child[1]->attr.val.i);
		}
	}
}

/* procedure typeCheck performs type checking 
 * by a postorder syntax tree traversal
 */
void typeCheck(TreeNode * syntaxTree)
{ 
	traverse(syntaxTree, nullpreProc, checkNode);
	traverse(syntaxTree, transNode, nullpostProc);
}