analyze.cpp

一个c语言的编译器的源代码

// Analyze the syntax tree(type check, etc), generate the symbol table,
// get ready for code generation
// 
// Written by bood, [e-mail], http://boodweb.126.com
// 2004-08-06

// Code changed so that the compiler does not hang while
// a typechecking error is found
// by bood, 2004-08-20

// 1. The function to build the symboltable is rewritten,
//    the scope concept is better supported now
// 2. Function node now have a direct statment-list child and
//    the previous compound child no longer exists
// 3. Necessary change for introducing function declaration
//
// Bug fix: 
// 1. Alloc space for parameter of inner function 'output',
//    so that the parameter is poped after calling
// 2. Function parameters are now put into symboltable of function
//    so that redefinition about parameters can be detected and
//    paramaters can overlay global vars correctly now
//
// by bood, 2005-01-22

// Bug fix:
// Support repeated function declaration, parameter list checked
//
// by bood, 2005-03-14

// Bug fix:
// Add checking codes of using function name without calling it in
// `preInsert`
//
// by bood, 2005-05-05

#pragma warning(disable:4786)

#include "global.h"
#include "symtable.h"
#include "util.h"
#include "analyze.h"

using namespace std;

static string FuncName;

// The traverse skeleton, to make the logical clear
typedef void NODE_PROC(TreeNode *);
void treeTraverse(TreeNode *t,
				  NODE_PROC preOrder, NODE_PROC postOrder)
{
	if(t==NULL) return;
	if(preOrder!=NULL) preOrder(t);
	for (int i=0; i < MAXCHILDREN; i++){
		treeTraverse(t->pChild[i], preOrder, postOrder);
	}
	if(postOrder!=NULL) postOrder(t);
	treeTraverse(t->pNext, preOrder, postOrder);
}

// Check to see whether the parameters of function
// definition or another function declaration consist
// with the previous declaration if there exists one
void checkDeclar(TreeNode *tFunc)
{
	SymbolRecord *s;
	TreeNode *tParamDeclar2, *tParamDeclar;

	s=st_lookup(tFunc->name);
	if(s==NULL) return;					//No previous declaration found

	tParamDeclar2 = tFunc->pChild[0];	//Params-list of definition / latter declaration
	tParamDeclar = s->pParamList;		//Params-list of declaration
	while(tParamDeclar2!=NULL && tParamDeclar!=NULL) {
		tParamDeclar2->type = GetType(tParamDeclar2);
		tParamDeclar->type = GetType(tParamDeclar);
		if(tParamDeclar2->type!=tParamDeclar->type)
			break;
		tParamDeclar = tParamDeclar->pNext;
		tParamDeclar2 = tParamDeclar2->pNext;
	}
	if(tParamDeclar2!=NULL || tParamDeclar!=NULL) {
		SemanticError("parameter list of function "
			"definition or of latter declaration "
            "differs from previous declaration",
			tFunc->lineno);
	}
}

// Insert parameter into corresponding function symbol table
void insertParams(SymbolRecord *sFunc, TreeNode *tParam)
{
	int param_loc			// location for codgen
		= Ret_and_Ofp;		// skip RetIP and OldFP
	SymbolRecord *s;
	while(tParam!=NULL) {
		if(tParam->name.empty()) {
			SemanticError("parameters of function definition "
				"must have a name", tParam->lineno);
		}
		s = st_insert(tParam->name, GetType(tParam), GetSymbolType(tParam),
			param_loc, tParam->lineno);

		sFunc->paramAlloc += Int_Bytes;
		param_loc += Int_Bytes;

		tParam = tParam->pNext;
	}
}

// Preorder part(main part) of ST building
// 
// 1. Addon symboltable when necessary
// 2. Insert declarations into correct STs
// 3. Check the undeclared use of identifiers
void preInsert(TreeNode *t)
{
	//Node of current function we are in
	static SymbolRecord * pCurrentFunc;
    SymbolRecord * sr;
	switch(t->kind) {
	case DECLAR:
		switch(t->childkind.declarK) {

		// Function declaration
		case FUNC_DECLAR:
            if(st_lookup(t->name)==NULL) {
                pCurrentFunc = st_insert(t->name, GetType(t),
                    GetSymbolType(t), -1, t->lineno);
                pCurrentFunc->pParamList = t->pChild[0];
            }
            else {
                // Declaration repeating, check param list
                checkDeclar(t);
            }
			break;

		// Function definition
		case FUNC_DEFINE:
			//Local-var address begin with 0
			location = 0;
			
			if((sr=st_lookup(t->name))==NULL) {
				//Record the function we're in
				pCurrentFunc = st_insert(t->name, GetType(t),
					GetSymbolType(t), -1, t->lineno);

				//Link the function symbol to the parameter list
				pCurrentFunc->pParamList = t->pChild[0];
			}
            else {
                // Mark this function as defined
                sr->symboltype = FUNC_DEFINE_SYMBOL;
            }

			//Create the function ST
			//where all children node symbol should be inserted into
			t->pBucketList = st_new();
			pCurrentST = t->pBucketList;

			//This is necessary too, for undeclared identifier check
			st_addon(pCurrentST);

			//Check to see whether the parameters consist with
			//the declaration if there exists one
			checkDeclar(t);

			insertParams(pCurrentFunc, t->pChild[0]);

			break;
		case VAR_DECLAR:
			if(nestlevel!=0) {		//Local, stack alloc needed
				location -= Int_Bytes;
				pCurrentFunc->localAlloc += Int_Bytes;
			}
			else {					//Global
				location = 0;
				globalAlloc += Int_Bytes;
			}
			st_insert(t->name, GetType(t), GetSymbolType(t),
				location, t->lineno);
			break;
		case ARRAY_DECLAR:
			if(nestlevel!=0) {		//Local, stack alloc needed
				location -= Int_Bytes*t->arraynum;
				pCurrentFunc->localAlloc += Int_Bytes*t->arraynum;
			}
			else {
				location = 0;		//Global
				globalAlloc += Int_Bytes*t->arraynum;
			}
			st_insert(t->name, GetType(t), GetSymbolType(t),
				location, t->lineno);
			break;
		}
		break;
	case CSTMT:
		//Create the ST of compound statement
		//where all children node symbol should be inserted into
		pCurrentST=t->pBucketList=st_new();
		st_addon(t->pBucketList);
		break;
	case EXP:
		//Assign Expression
		if(t->childkind.stmtK==ASSIGN_EXP){
            sr = st_lookup(t->name);
			if(sr==NULL) {
				SemanticError(t->name + " not declared before", t->lineno);
            }
            else if(sr->symboltype==FUNC_DECLAR_SYMBOL ||
                sr->symboltype==FUNC_DEFINE_SYMBOL) {
                SemanticError(t->name + " is a function name which cannot be assigned", t->lineno);
            }
        }
        break;
    case REFER:
        sr = st_lookup(t->name);
        if(sr==NULL) {
            SemanticError(t->name + " not declared before", t->lineno);
        }
        else if(sr->symboltype==FUNC_DECLAR_SYMBOL ||
            sr->symboltype==FUNC_DEFINE_SYMBOL) {
            SemanticError(t->name + " is a function name which cannot be used in an expression", t->lineno);
        }
		break;
	case CALL:
		if(st_lookup(t->name)==NULL) {
			SemanticError(t->name + " not declared before", t->lineno);
		}
		break;
	}
}

//Postorder part of building ST
//
//Restore the ST of the previous scope and
//adjust the ST where to insert symbols
void postInsert(TreeNode *t){
	switch(t->kind) {
	case DECLAR:
		if(t->childkind.declarK==FUNC_DEFINE) {
			st_takeoff();
			pCurrentST = pSymbolTable;
		}
		break;
	case CSTMT:
		st_takeoff();
		pCurrentST = pSymbolTable;
		break;
	}
}

void BuildSymbolTable(TreeNode *t)
{
    // Though external definition supported now
	// this is really a convenience to keep these inner declaration
	// for two reasons:
	// 1. Prevent from redefining these functions
	// 2. Easy to use them

    SymbolRecord *s;

    // Library functions declarations begin
    s = st_insert("input", INTEGER_TYPE, FUNC_DECLAR_SYMBOL, 0, -1);
    s = st_insert("output", VOID_TYPE, FUNC_DECLAR_SYMBOL, 0, -1);
    s->pParamList = new TreeNode;
    s->pParamList->name = "x";
    s->pParamList->tokenT = INT;
	s->pParamList->type = INTEGER_TYPE;
	s->pParamList->pNext = NULL;
	s->paramAlloc = Int_Bytes;
    // Library functions declarations end

	treeTraverse(t, preInsert, postInsert);
}

// Check just one node(sometimes childrens included)
// and set its type, because its a root-last traverse
// so when checking a node, its childrens are all checked
// and set already
//
// These codes are just simple, so no more comments...
void checkNode(TreeNode *t)
{
	SymbolRecord *s=st_lookup(t->name);
	switch(t->kind)
	{
	case DECLAR:
		break;
	case OP:
		if(t->pChild[0]->type!=INTEGER_TYPE ||
			t->pChild[1]->type!=INTEGER_TYPE) {
			SemanticError(string("Operands of '")+t->name+"' not consist",
				t->lineno);
		}
		t->type=INTEGER_TYPE;
		break;
	case RELOP:
		if(t->pChild[0]->type!=INTEGER_TYPE ||
			t->pChild[1]->type!=INTEGER_TYPE) {
			SemanticError(string("Operands of '")+t->name+"' not consist",
				t->lineno);
		}
		t->type=BOOLEAN_TYPE;
		break;
	case STMT:
		switch(t->childkind.stmtK)
		{
		case IF_STMT:
			if(t->pChild[0]->type!=BOOLEAN_TYPE){
				SemanticError("The expression of 'if' statement is not type of boolean",
					t->lineno);
			}
			break;
		case WHILE_STMT:
			if(t->pChild[0]->type!=BOOLEAN_TYPE){
				SemanticError("The expression of 'while' statement is not type of boolean",
					t->lineno);
			}
			break;
		case RETURN_STMT:
			s=st_lookup(FuncName);
			if(s->type==VOID_TYPE){
				if(t->pChild[0]!=NULL){
					SemanticError(string("Function '")+FuncName+"' do not return a value",
						t->lineno);
				}
			}
			else if(t->pChild[0]==NULL){
				SemanticError(string("Function '")+FuncName+"' must return a value",
					t->lineno);
			}
			else if(s->symboltype!=FUNC_DECLAR_SYMBOL &&
                s->symboltype!=FUNC_DEFINE_SYMBOL ||
				t->pChild[0]->type!=s->type) {
				SemanticError(string("Function '")+FuncName+"' must return a value of type int",
					t->lineno);
			}
			break;
		}
		break;
	case REFER:
		if(t->pChild[0]!=NULL)
			if(s->symboltype!=ARRAY_SYMBOL &&
				s->symboltype!=ARRAYADDR_SYMBOL){
				SemanticError(string("ID '")+t->name+"' must be an array",
					t->lineno);
			}
		t->type=s->type;
		break;
	case CALL:
		t->type=s->type;
		if(s->symboltype!=FUNC_DECLAR_SYMBOL &&
            s->symboltype!=FUNC_DEFINE_SYMBOL){
			SemanticError(string("'")+t->name+"' is not a function",
				t->lineno);
		}
		else{
            //Check arguments one by one
			TreeNode *ttemp=t->pChild[0], *tParam;
			tParam=s->pParamList;
			while(tParam!=NULL && ttemp!=NULL){
				if(ttemp->type!=tParam->type) break;
				tParam=tParam->pNext;
				ttemp=ttemp->pNext;
			}
			if(ttemp!=NULL || tParam!=NULL){
				SemanticError(string("Function call '")+t->name+"' has an error in its arguments",
					t->lineno);
			}
		}
		break;
	case PARAM:
		t->type = GetType(t);
		break;
	case CSTMT:
		break;
	case EXP:
		switch(t->childkind.expK)
		{
		case ASSIGN_EXP:
			if(s->type!=t->pChild[1]->type){
				SemanticError(string("Oprands of '=' not consist"),
					t->lineno);
			}
			if(t->pChild[0]!=NULL)
				if(s->symboltype!=ARRAY_SYMBOL &&
					s->symboltype!=ARRAYADDR_SYMBOL){
					SemanticError(string("ID '")+t->name+"' must be an array",
						t->lineno);
				}
			t->type=s->type;
			break;
		}
		break;
	case NUM:
		t->type=INTEGER_TYPE;
		break;	
	}
}

// Preorder part of the type checking
//
// When a function declaration is met, we save the function
// name in a globle variable so that we can check the return
// type when needed.
// And if a compound statement is met, we just addon its symbol
// table to act the scope overlay.
void preCheck(TreeNode * t)
{ 
        // Function declaration, set the function name for symbol
        // searching in the params
		if(t->kind==DECLAR && t->childkind.declarK==FUNC_DEFINE){
			st_addon(t->pBucketList);
			FuncName=t->name;
			location=0;
		}
		else if(t->kind==CSTMT) st_addon(t->pBucketList);
}

// Postorder part of type checking
//
// Restore the ST of the previous scope
// Call actual type check function at last
void postCheck(TreeNode *t)
{
	if(t->kind==DECLAR && t->childkind.declarK==FUNC_DEFINE){
		st_takeoff();
		FuncName="";
	}
	else if(t->kind==CSTMT) st_takeoff();

	checkNode(t);
}

// Another traverse, but mainly in postorder, to do type checking
void TypeCheck(TreeNode *t)
{
	treeTraverse(t, preCheck, postCheck);
}