analyze.c

编译原理课设

/* 张皖龙 @ SEU */

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

/* 有效内存位置 */
static int location = 0;

/* 符号表和函数表 */
static Symtab * pTable;
static FunEntry * pFun;

/* 递归访问语法树 */
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);
	}
}


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;
		}
	}
}

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

/* 插入标识符到符号表 */
static void insertNode(TreeNode * t)
{ 
	switch (t->nodekind)
	{ 
		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)
						pFun = 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) 
					{
						if (child->nodekind == Exp && 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 == Stmt && 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);
						if (pTable==NULL)
							fprintf(listing, "内存溢出在第 %d 行\n", t->lineno);
					t->attr.table = pTable;
					break;
				default:
					break;
			}
			break;
		default:
			break;
	}
}

/* 先序遍历语法树构造符号表 */
void buildSymtab(TreeNode * tree)
{
	GlobalTable = Createtab(NULL, NULL);
	if (GlobalTable==NULL)
		fprintf(listing, "内存溢出在第 %d 行\n", tree->lineno);
	pTable = GlobalTable;
	traverse(tree, insertNode, nullpostProc);
	if (TraceAnalyze)
	{ 
		printFunTab();
		printSymTab(tree);
	}
}

static void typeError(TreeNode * t, char * message)
{ 
	fprintf(listing,"类型错误在第 %d 行\n", t->lineno, message);
	Error = TRUE;
}

/* 检查单个节点的类型 */
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 != Integer && t->child[0]->type != Float) 
								|| (t->child[1]->type != Integer && t->child[1]->type != Float))
								typeError(t, "算符没有数值操作数");
							else if (t->child[0]->type == Float || t->child[1]->type == Float)
								t->type = Float;
							else
								t->type = Integer;
							break;
						case LT: 
						case LE: 
						case GT: 
						case GE: 
						case EQ: 
						case NEQ:
							if ((t->child[0]->type != Integer && t->child[0]->type != Float) 
								|| (t->child[1]->type != Integer && t->child[1]->type != Float))
								typeError(t, "算符没有布尔操作数");
							else 
								t->type = Boolean;
							break;
						case AND: 
						case OR:
							if ((t->child[0]->type != Integer && t->child[0]->type != Boolean) ||
								(t->child[1]->type != Integer && t->child[1]->type != Boolean))
								typeError(t, "算符没有布尔操作数");
							else
								t->type = Boolean;
							break;
					}
					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 (pEntry == NULL)
							typeError(t, "引用了未定义变量");
					}
				}
				break;
			}
			break;
		case Stmt:
			switch (t->kind.stmt)
			{ 
				case IfK:
					if (t->child[0]->type != Boolean && t->child[0]->type != Integer)
						typeError(t->child[0], "IF条件出不是布尔式");
					break;
				case WhileK:
					if (t->child[0]->type != Boolean && t->child[0]->type != Integer)
						typeError(t->child[0], "WHILE条件出不是布尔式");
					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, "调用函数使用了错误的参数");
						}
						if (para != NULL || t != NULL)
							typeError(t, "调用函数使用了错误的参数");
					}
					else
						typeError(t, "调用未定义函数");
				}
				break;
				case ReturnK:
					t->type = t->child[0]->type;
					if (t->type != pFun->type)
						typeError(t, "返回值类型和定义的不一样");
					break;
				case AssignK:
					if (t->child[0]->type != t->child[1]->type) 
					{
						if (t->child[0]->type == Float && t->child[1]->type == Integer)
							t->type = t->child[1]->type = Float;
						else 
						{
							if (t->child[0]->type == Integer && t->child[1]->type == Float) 
								t->type = Integer;
							else 
								typeError(t->child[0], "赋值类型不匹配");
						}
					}
					t->type = t->child[0]->type;
					break;
				}
				break;
			}
}

/* 转换一个语法树结点到恰当的结点 */
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]->type == Integer)) 
			{
				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[1]->type == Integer))
			{
				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);
			}
			break;
		}
	}
}

/* 后序遍历语法树检查类型 */
void typeCheck(TreeNode * syntaxTree)
{ 
	traverse(syntaxTree, nullpreProc, checkNode);
	traverse(syntaxTree, transNode, nullpostProc);
}