analyze.cpp

小型编译系统的源代码

#include "analyze.h"
#include "globals.h"
#include "symtab.h"

/* 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,
               int (* preProc) (TreeNode *),
               int (* postProc) (TreeNode *) )
{ if (t != NULL)
  { int result = preProc(t);
		if (result!= SKIP)
    { int i;
      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 int nullProc(TreeNode * t)
{ if (t==NULL) return SUCCESS;
  else return SUCCESS;
}

static int insertNode( TreeNode * t)
{ 
	Result result;entryType et;
	switch (t->nodekind){ 
	case StmtK:
    switch (t->kind.stmt){  
		case CompoundK:
				st_newBuck();
				//for (tt = t->child[0]; tt!=NULL; tt = tt->sibling)
				//	insertNode(tt);
				traverse(t->child[0],insertNode,nullProc);
				st_delBuck();
				return SKIP; 
    default:
        break;
    }
    break;
	case DeclK:
		switch (t->kind.decl){
		case VarDeclK:
			TreeNode * tt;
			int res;
			for (tt = t->child[1]; tt!=NULL; tt=tt->sibling){
				if (tt->kind.exp == IdK)
					res = st_insert(tt->attr.name,t->lineno,t->child[0]->attr.vartype,IdK);
				else 
					res = st_insert(tt->attr.name,t->lineno,t->child[0]->attr.vartype,ArrayK, tt->child[0]->attr.vali);
				if (res == FAIL){
				/*error: redeclaration of variable*/
						Error = TRUE;
						fprintf(listing,"Error! Line %d, redeclaration of variable.\n",t->lineno);
				}
  			else {
  				tt->type = tt->attr.vartype = t->child[0]->attr.vartype;
  			}
			}
			return SKIP;
		case FuncDeclK:
			if (st_insert(t->child[1]->attr.name,t->lineno,t->child[0]->attr.vartype,t->child[2])==FAIL){
				/*error: redeclaration of variable*/
				Error = TRUE;
				fprintf(listing,"Error! Line %d, redeclaration of function.\n",t->lineno);
			}
			return SKIP;
		case FuncDefK:
			if (st_funclookup(t->child[1]->attr.name,t->child[0]->attr.vartype,t->child[2])==UNCONFORM){
				/*error: definition unconform to former declaration*/
				Error = TRUE;
				fprintf(listing,"Error! Line %d, parameters mismatch the declaration.\n",t->lineno);
			}
			else if (st_funclookup(t->child[1]->attr.name,t->child[0]->attr.vartype,t->child[2])==INVALID){
				Error = TRUE;
				fprintf(listing,"Error! Line %d, return type mismatch.\n",t->lineno);
			}
			else {
				if (st_funclookup(t->child[1]->attr.name,t->child[0]->attr.vartype,t->child[2])==FAIL){
					st_insert(t->child[1]->attr.name,t->lineno,t->child[0]->attr.vartype,t->child[2]);
				}
				st_newBuck();
				st_inFunc(t->child[1]->attr.name);
				for (tt = t->child[2]; tt!=NULL; tt = tt->sibling){
					tt->child[1]->attr.vartype = tt->child[0]->attr.vartype;
					st_insert(tt->child[1]->attr.name,tt->lineno,tt->child[0]->attr.vartype,tt->child[1]->kind.exp);
				}
				insertNode(t->child[3]);
				st_delBuck();
				st_outFunc();
			}
			return SKIP;
		case ParamK:
			return UNSKIP;
		}
		break;
  case ExpK:
	
      switch (t->kind.exp){ 
			case IdK:	
				if ((st_lookup(t->attr.name,result) == FAIL)||result.vark == Func){
					Error = TRUE;
        /* not yet in table, so treat as error*/
          fprintf(listing,"Error! Line %d,undefined symbol %s\n",t->lineno,t->attr.name);
				}
				else {
					t->type = t->attr.vartype = result.etype;
					t->varK = result.vark;
					if (t->child[0]!=NULL)t->varK = Norm;
				}
        break;
			case CallK:
				if (st_funclookup(t->child[0]->attr.name,result) == FAIL){
          /* not yet in table, so treat as error*/
            fprintf(listing,"Error! Line %d,undefined symbol %s\n",
								t->lineno,t->child[0]->attr.name);
						Error = TRUE;
				}
				else {
					t->type = t->attr.vartype = result.etype;
					t->varK = Func;
					//insertNode(t->child[1]);
					traverse(t->child[1],insertNode,nullProc);
				}
				return SKIP;
        break;
			case ArrayK:
				et.varK = Array;
				if ((st_lookup(t->attr.name,result) == FAIL)||result.vark!=Array){
          /* not yet in table, so treat as error*/
            fprintf(listing,"Error! Line %d,undefined symbol %s\n",t->lineno,t->attr.name);
						Error = TRUE;
				}
				else {
					t->type = t->attr.vartype = result.etype;
					if (t->child[0]!=NULL)
						t->varK = Norm;
				}
        break;
			case ConstK:
				t->type = t->attr.vartype;
      default:
        break;
      }
      break;
  default:
      break;
  }
	return UNSKIP;
}

/* Function buildSymtab constructs the symbol 
 * table by preorder traversal of the syntax tree
 */
void buildSymtab(TreeNode * syntaxTree)
{ 
	traverse(syntaxTree,insertNode,nullProc);
}

static void typeError(TreeNode * t, char * message)
{ fprintf(listing,"Error! Line %d: %s\n",t->lineno,message);
  Error = true;
}

/* Procedure checkNode performs
 * type checking at a single tree node
 */
/*two variable used for function return type checking*/

ExpType funcReturn = Void;
bool valid = false;
bool nullarray = false;

/* Procedure checkParams performs
 * function type checking
 */
int CheckParams(TreeNode * p1,paramType * p2){
	TreeNode * tt;
	paramType * tp;
	Result result;
	for (tt = p1, tp = p2; tt!=NULL&&tp!=NULL; tt=tt->sibling,tp = tp->next){
		if (tt->type!=tp->type.type||(tt->varK==Array&&tp->type.varK!=Array))
			return FAIL;
		else if (tt->varK!=Array&&tp->type.varK == Array){
			//int suc = st_lookup(tt->attr.name,result);
			//if (!(tt->kind.exp==IdK&&suc!=FAIL&&result.vark==Array))
				return FAIL;
		}
	}
	if (tt==NULL&&tp==NULL)
		return SUCCESS;
	else return FAIL;
}

static int checkNode(TreeNode * t)
{ 
	Result result;
	switch (t->nodekind)
  { 
	case ExpK:
      switch (t->kind.exp)
      { case OpK:
					if (nullarray == true)
						fprintf(listing,"Error! Null index to array\n");
					if (t->child[0]->type != t->child[1]->type||
						t->child[0]->varK!=Norm||t->child[1]->varK!=Norm){
						if ((!((t->child[0]->type == Float&&t->child[1]->type == Integer)||
							(t->child[0]->type == Integer&&t->child[1]->type == Float)))
							||t->child[0]->varK!=Norm||t->child[1]->varK!=Norm)
							typeError(t,"Type mismatch on two sides of the operator"); //error
					}
          if ((t->attr.op == EQ) || (t->attr.op == LT)|| (t->attr.op == LE)
						|| (t->attr.op == GT)|| (t->attr.op == GE)|| (t->attr.op == NE)
						|| (t->attr.op == OR)|| (t->attr.op == AND))
            t->type = t->attr.vartype = Boolean;
          else{
						if (t->child[0]->type == Float||t->child[1]->type==Float)
							t->type = t->attr.vartype = Float;
						else t->type = t->attr.vartype = t->child[0]->type;
					}
					t->varK = Norm;
          break;
        case ConstK:
					t->type = t->attr.vartype;
					t->varK = Norm;
					break;
        case IdK:

          break;
				case CallK:
					entryType et;
					et.varK = Func;
					st_funclookup(t->child[0]->attr.name,result);
					if(CheckParams(t->child[1],result.params)==FAIL)
						/*error! Parameters mismatched*/
						typeError(t,"Parameters mismatch the function definition.");
					else {
						t->type = t->attr.vartype = result.etype;
						t->varK = Norm;
					}
					break;
				case ArrayK:
					if (t->child[0] == NULL)
						nullarray = true;
					else if (t->child[0]->type!=Integer)
						/*error! Invalid index type*/
						typeError(t,"Index is not integer type.");
					break;
				case NotK:
					t->type = Boolean;
					break;
				
        default:
          break;
      }
      break;
    case StmtK:
      switch (t->kind.stmt)//IfK,WhileK,ForK,ReturnK,CompoundK
      { case IfK:
          if (t->child[0]->type != Boolean)
            typeError(t->child[0],"if test is not Boolean");
          break;
        case ForK:
          if (t->child[1]->type != Boolean)
            typeError(t->child[0],"for test is not Boolean");
          break;
        case WhileK:
          if (t->child[0]->type != Boolean)
            typeError(t->child[0],"while test is not Boolean");
          break;
        case ReturnK:
					t->type = t->child[0]->type;
					if (valid == false)funcReturn = t->type;
					else if (funcReturn!=t->type){
						//!error!function return type mismatched!
						typeError(t,"Function return type mismatch.");
						funcReturn = t->type;
						}
					valid = true;
          break;
				case CompoundK:
					break;
        default:
          break;
      }//switch t->kind.stmt
      break;
		case DeclK:
			switch(t->kind.decl){//VarDeclK,ArrayDeclK,FuncDeclK,FuncDefK,ParamK
			case FuncDefK:
				t->type = t->child[0]->attr.vartype;
				if (t->type!=funcReturn)
					/*error! function return type mismatch*/
					typeError(t,"Function return type mismatch.");
				funcReturn = Void;
				valid = false;
			}//switch t->kind.decl
		case ParamK:
				nullarray = false;
				t->type = t->child[0]->attr.vartype;
    default:
      break;
	
  }
	return SKIP;
}

/* Procedure typeCheck performs type checking 
 * by a postorder syntax tree traversal
 */
void typeCheck(TreeNode * syntaxTree)
{ traverse(syntaxTree,nullProc,checkNode);
}