astree.c

decafc的源代码

/****************************************************************************
 * File name:	ASTree.c						    *
 * Description:	abstract syntax tree routines				    *
 * Input:	none							    *
 * Output:	none							    *
 * Author:	Luojian Chen						    *
 * Date:	April 16, 1997						    *
 ****************************************************************************/


#include <stdio.h>
#include <varargs.h>

#include "ASTree.h"


/* external global variables */

extern int		currentLineNumber;
extern int		currentColumnNumber;
extern SymbolTablePtr	typeSymbolTable;

/* external function prototypes */
extern ElementPtr	Lookup(SymbolTablePtr, String);

/* global function prototypes */

Node *		CreateNode(int);
void		ReplaceNode(NodeType, NodePtr);
Node *		MergeSubTrees(int);
void		SetVarDecNodeType(NodePtr, NodePtr);
NodeType	GetNodeType(NodePtr);
void		DisplayASTree(NodePtr);
void		DeleteASTree(NodePtr);
void		DeleteNode(NodePtr);


/* static global variables */
String		nodeNames[] =
{
	"Program",
	"ClassDeclarationList",
	"ClassDeclartion",
	"ClassBody",
	"VarDeclarationList",
	"VarDeclaration",
	"Type",
	"IntArrayDeclaration",
	"OtherArrayDeclaration",
	"[]",
	"ConstructorDeclaration",
	"MethodDeclarationList",
	"MethodDeclaration",
	"ParameterList",
	"Parameter",
	"RemainingParameterList",
	"Block",
	"LocalVarDeclarationList",
	"LocalVarDeclaration",
	"StatementList",
	"Statement",
	"EmptyStatement",
	"AssignmentStatement",
	"FunctionStatement",
	"PrintStatement",
	"IfStatement",
	"WhileStatement",
	"ReturnStatement",
	"BlockStatement",
	"Name",
	"ArrayAccess",
	"ArgList",
	"RemainingArgList",
	"Expression",
	"NewExpression",
	"RelationExpression",
	"FunctionExpression",
	"ReadExpression",
	"UnaryExpression",
	"IndexList",
	"EmptyIndexList",
	"EmptyIndex",
	"Identifier",
	"Number",
	"Keyword",
	"Operator",
	"Error"
};

/****************************************************************************
 Function name:		CreateNode
 Description:		create a abstract syntax tree node
 Procedure:		1. allocate memory for the current node
			2. fill in line and column numbers
			3. fill in node information
			4. allocate memory for the pointers to child nodes
			5. fill in the pointers to child nodes
 Return value:		pointers to the current node
 Input parameter:	va_alist	variable argument list
				the first argument is the type of the node
				the second argument the lexeme of the node
				the third argument is an integer for
				  the number of child nodes
					0	if the current code is a
						leaf node
					n (>0)	if the current code is not
						a leaf node
				the rest arguments are pointers to
				  leaf child nodes
					none	if the second argument is
						0
 Output parameter:	none
 ****************************************************************************/
Node * CreateNode(va_alist)
va_dcl
{
	va_list ap;
	NodePtr	nodePtr;
	int	numberOfChildren;
	int	i;

	va_start (ap);
	
	/* allocate memory for the current node */

	nodePtr = (NodePtr)malloc(sizeof(Node));

	nodePtr->lineNumber = currentLineNumber;
	nodePtr->columnNumber = currentColumnNumber;

	/* set the type of the node */

	nodePtr->type = (NodeType)(va_arg(ap, NodeType));

	switch (nodePtr->type) {
		case NODE_TYPE_KEYWORD:

			/* set the lexeme of the type node */
			
			nodePtr->info.lexeme = strdup(va_arg(ap, char *));
			nodePtr->typePtr = Lookup(typeSymbolTable,
						  nodePtr->info.lexeme);
			break;

		case NODE_TYPE_OPERATOR:

			/* set the lexeme of the type node */

			nodePtr->info.lexeme = strdup(va_arg(ap, char *));
			break;

		case NODE_TYPE_IDENTIFIER:
			
			/* set the name of the identifier node */
			
			nodePtr->info.lexeme = strdup(va_arg(ap, char *));
			nodePtr->typePtr = Lookup(typeSymbolTable,
						  nodePtr->info.lexeme);
			break;

		case NODE_TYPE_NUMBER:
			
			/* set the value of the number node */
			
			nodePtr->info.value = va_arg(ap, int);
			break;
		default:
			nodePtr->info.lexeme = NULL;
			/* nodePtr->info.value = 0; */
			break;
	}

	/* set the number of child nodes */

	numberOfChildren = va_arg(ap, int);
	nodePtr->numberOfChildren = numberOfChildren;

	if (numberOfChildren == 0) {

		/* leaf node */

		nodePtr->children = NULL;
		return(nodePtr);
	}

	/* allocated an arry holding pointers to child nodes */

	nodePtr->children = (NodePtr *)malloc(sizeof(NodePtr) *
					      numberOfChildren);

	/* set pointers to child nodes */

	for (i = 0; i < numberOfChildren; i ++) {
		(nodePtr->children)[i] = va_arg(ap, NodePtr);
	}

	va_end(ap);

	/* return the pointer to the current node */

	return(nodePtr);
}

void ReplaceNode(NodeType	nodeType,
		 NodePtr	nodePtr)
{
	nodePtr->type = nodeType;
}

/****************************************************************************
 Function name:		MergeSubTrees
 Description:		merge sub trees
 Procedure:		1. allocate memory
 Return value:		pointers to the current node
 Input parameter:	va_alist	variable argument list
				the first argument is the type of the node
				the second argument is an integer for
				  the number of child nodes
				the rest arguments are pointers to
				  leaf child nodes
 Output parameter:	none
 ****************************************************************************/
Node * MergeSubTrees(va_alist)
va_dcl
{
	va_list ap;
	NodePtr	nodePtr = NULL;
	NodePtr	subTreeRootPtr = NULL;
	int	numberOfSubTrees;
	int	numberOfChildren;
	int	i;
	int	j;
	int	k;

	va_start (ap);
	
	/* allocate memory for the current node */

	nodePtr = (NodePtr)malloc(sizeof(Node));

	/* set the type of the node */

	nodePtr->type = (NodeType)(va_arg(ap, NodeType));

	nodePtr->info.lexeme = NULL;

	/* set the number of child nodes */

	numberOfSubTrees = va_arg(ap, int);
	numberOfChildren = 0;
	j = 0;

	for (i = 0; i < numberOfSubTrees; i ++) {
	  subTreeRootPtr = va_arg(ap, NodePtr);
	  if (subTreeRootPtr->type != nodePtr->type) {
	    if (numberOfChildren == 0) {
	      numberOfChildren = 1;
	      nodePtr->children = (NodePtr *)malloc(sizeof(NodePtr) *
						    numberOfChildren);
	    } else {
	      numberOfChildren ++;
	      nodePtr->children = (NodePtr *)realloc(nodePtr->children,
						     sizeof(NodePtr) *
						     numberOfChildren);
	    }
	    nodePtr->children[j] = subTreeRootPtr;
	    j ++;
	  } else {
	    if (numberOfChildren == 0) {
	      numberOfChildren = subTreeRootPtr->numberOfChildren;
	      nodePtr->children = (NodePtr *)malloc(sizeof(NodePtr) *
						    numberOfChildren);
	    } else {
	      numberOfChildren += subTreeRootPtr->numberOfChildren;
	      nodePtr->children = (NodePtr *)realloc(nodePtr->children,
						     sizeof(NodePtr) *
						     numberOfChildren);
	    }
	    k = 0;
	    while (j < numberOfChildren) {
	      nodePtr->children[j] = subTreeRootPtr->children[k];
	      j ++;
	      k ++;
	    }

	    nodePtr->lineNumber = subTreeRootPtr->lineNumber;
	    nodePtr->columnNumber = subTreeRootPtr->columnNumber;
	    DeleteNode(subTreeRootPtr);
	    /*
	    free(subTreeRootPtr->name);
	    free(subTreeRootPtr->children);
	    free(subTreeRootPtr);
	    */
	  }
	}

	nodePtr->numberOfChildren = numberOfChildren;

	va_end(ap);

	/* return the pointer to the current node */

	return(nodePtr);
}

#ifdef 0
void SetVarDecNodeType(NodePtr	nodePtr,
		       NodePtr	typeNodePtr)
{
	/* nodePtr->info.symbolTablePtr = typeNodePtr->info.symbolTablePtr
 	   typeNode has put the type name in the type name table */

	nodePtr->info.type = strdup("int");

	DeleteNode(typeNodePtr);
}
#endif

NodeType GetNodeType(NodePtr	nodePtr)
{
	return(nodePtr->type);
}

/****************************************************************************
 Function name:		DisplayASTree
 Description:		display the abstract syntax tree in pre-order
 Procedure:		1. if not leaf node
				display production
			2. recursively display sub abstract syntax tree
			   in pre-order
 Return value:		none
 Input parameter:	nodePtr	pointers to a abstract syntax tree node
 Output parameter:	none
 ****************************************************************************/
void DisplayASTree(Node *	nodePtr)
{
	int	numberOfChildren;
	NodePtr	childNodePtr;
	int	i;

	if (nodePtr == NULL) {

		/* empty node pointer , do nothing */

		return;
	}

	numberOfChildren = nodePtr->numberOfChildren;

	if (numberOfChildren == 0) {

		/* leaf node, do nothing */

		return;
	}

	/* display production for the current node */

	printf("<%s> -> ", nodeNames[nodePtr->type]);

	for (i = 0; i < numberOfChildren; i ++) {

		childNodePtr = nodePtr->children[i];

		if (childNodePtr == NULL) {
			continue;
		}

		if (childNodePtr->numberOfChildren != 0) {
			printf("<%s> ", nodeNames[childNodePtr->type]);
		} else {
			printf("%s", nodeNames[childNodePtr->type]);
		}

		switch (childNodePtr->type) {
			case NODE_TYPE_TYPE:
			case NODE_TYPE_IDENTIFIER:
			case NODE_TYPE_UNARY_EXP:
			case NODE_TYPE_EXP:
				printf("(%s) ", childNodePtr->info.lexeme);
				break;
			case NODE_TYPE_NUMBER:
				printf("(%d) ", childNodePtr->info.value);
				break;
			default:
				printf(" ", childNodePtr->info.value);
				break;
		}
	}

	printf("\n");

	/* recursively display sub abstract syntax tree in pre-order */

	for (i = 0; i < numberOfChildren; i ++) {

		childNodePtr = nodePtr->children[i];

		/* Remember to uncomment this before submission */
		/*
		if ((childNodePtr != NULL) &&
		    (childNodePtr->numberOfChildren != 0)) {
		*/
		if (childNodePtr != NULL) {
			DisplayASTree(childNodePtr);
		}
	}
}

/****************************************************************************
 Function name:		DeleteASTree
 Description:		free memory for the abstract syntax tree
 Procedure:		1. recursively free memory for each sub
			   abstract syntax tree
			2. free memory for the current node
 Return value:		none
 Input parameter:	nodePtr	pointer to a abstract syntax tree node
 Output parameter:	none
 ****************************************************************************/
void DeleteASTree(Node *	nodePtr)
{
	int	i;

	if (nodePtr == NULL) {

		/* empty node pointer, do nothing */

		return;
	}

	/* recursively free memory space for each sub abstract syntax tree */

	for (i = 0; i < nodePtr->numberOfChildren; i ++) {
		if ((nodePtr->children)[i] != NULL) {
			DeleteASTree((nodePtr->children)[i]);
		}
	}

	/* free memory space for the current node */

	DeleteNode(nodePtr);
	/*
	free(nodePtr->name);
	free(nodePtr->children);
	free(nodePtr);
	*/
}

void DeleteNode(NodePtr	nodePtr)
{
	if (nodePtr == NULL) {
		return;
	}

	if (nodePtr->children != NULL) {
		free(nodePtr->children);
	}

	if (nodePtr->info.lexeme != NULL) {
		free(nodePtr->info.lexeme);
	}

	free(nodePtr);
}