Creating ast.c and ast.h

Once the Parser has accepted a series of tokens as a valid grammar, it will execute C code within the braces after the grammar:

return_st: RETURN ID SEMICOLON {/*C code to be executed when grammar is encountered*/}

What we want the Parser to produce is some form of intermediate representation (IR) that the compiler can analyze to eventually output the program in the XM3 machine’s language. Therefore, most of the C code to be executed when a valid grammar is encountered will produce IR. The IR output by the Parser take the form of abstract syntax trees (AST).

An abstract syntax tree is a tree of nodes that represent a program. For example, take the line of code: “a = 1+2-1;”. An AST for this code could be:

For the compiler, we will use nodes of various types to represent the initial C program as an AST. This AST can be traversed by later sections of the compiler to eventually produce the desired output program.

The first thing required for an AST is a basic node. Note that this node will be type cast later to hold more specific details for the different types of nodes. This basic node will have fields for a node type, left node pointer, and a right node pointer:

 typedef struct AST_node_t {
	Node_Type type;
	struct AST_Node_t* left;
	struct AST_Node_t* right;
} AST_Node;

Node_Type is an enum of the various possible node types. To start with, the following node types are declared (note that many more types will be required):

typedef enum Node_Type
{
	BASIC_NODE,
	// functions
	FUNC_NODE,
	// declarations
	CONST_NODE,
        ID_NODE,
	EXPR_NODE,
	// statements
	RETURN_NODE
} Node_Type;

The declarations for the various node type structs are as follows:

/* Function Nodes */
typedef struct AST_Node_Func_t {
	Node_Type type;
	AST_Node* statement;
} AST_Node_Func;

typedef struct AST_Node_Const_t {
	Node_Type type;
	int const_type;
	int val;
}AST_Node_Const;

typedef struct AST_Node_ID_t {
	Node_Type type;
	char* varname;
	int vartype;
	list_t* val;
} AST_Node_ID;

typedef struct AST_Node_Expr_t {
	Node_Type type;
	Operator op;
	AST_Node* left;
	AST_Node* right;
} AST_Node_Expr;

typedef struct AST_Node_Return_t {
	Node_Type type;
	int ret_type;
	AST_Node* ret_val;
} AST_Node_Return;

In the expression node, an enum is used to hold the operator. For now, the available operators are:

typedef enum Operator_t
{
        ASSIGNop
	PLUSop,
	MINUSop,
	MULTop,
	DIVop
} Operator;

Now that the initial node types have been declared in a header file (ast.h), we need functions for the Parser to execute to create these nodes. These functions allocate space for the node, fill the fields of the nodes with the parameters of the function, and return the node. The following functions (in ast.c) are used:

AST_Node* new_ast_node(Node_Type type, AST_Node* left, AST_Node* right) 
{
	// allocate memory
	AST_Node* node = malloc(sizeof(AST_Node));
	// set members
	node->type = type;
	node->left = left;
	node->right = right;

	return node;
}

AST_Node* new_ast_func_node(AST_Node* statement) {
	AST_Node_Func* node = malloc(sizeof(AST_Node_Func));

	node->type = FUNC_NODE;
	node->statement = statement;
	return (AST_Node*) node;
}

AST_Node* new_ast_const_node(int const_type, int val) 
{	
	AST_Node_Const* node = malloc(sizeof(AST_Node_Const));

	node->type = CONST_NODE;
	node->const_type = const_type;
	node->val = val;

	return (AST_Node*) node;
}

AST_Node* new_ast_ID_node(int vtype, char* vname, Value* val)
{
	AST_Node_ID* node = malloc(sizeof(AST_Node_ID));
	node->type = ID_NODE;
	node->vartype = vtype;
	node->varname = _strdup(vname);
	node->val = val;
	return (AST_Node*)node;
}

AST_Node* new_ast_expr_node(AST_Node* left, int op, AST_Node* right)
{
	AST_Node_Expr* node = calloc(1, sizeof(AST_Node_Expr));

	node->type = EXPR_NODE;
	node->left = left;
	node->op = op;
	node->right = right;

	return (AST_Node*) node;
}

AST_Node* new_ast_return_node(int ret_type, AST_Node* ret_val)
{
	AST_Node_Return* node = malloc(sizeof(AST_Node_Return));

	node->type = RETURN_NODE;
	node->ret_type = ret_type;
	node->ret_val = ret_val;

	return (AST_Node*) node;
}

Now that we have declared various node types and have functions to create them, it is possible to generate an AST. However, we still need a function to traverse the AST. To traverse the AST, we can use recursion to travel to the leftmost node of the tree, then work all the way back to the starting node visiting the right node each step of the way. The following function is used to traverse the AST (note that tab_count is a variable used to help print the tree):

int tab_count = -1;

/* Traverse the AST starting from given node, this is done with recursive calls on the child nodes*/
void ast_traverse(AST_Node* node)
{
	tab_count++;
	// check for empty node
	if (!node) {
		return;
	}

	// Nodes with one left child and one right child
	if (node->type == BASIC_NODE) {
		ast_traverse(node->left);
		ast_traverse(node->right);
		ast_print_node(node, tab_count);
	}
	//Function nodes
	else if (node->type == FUNC_NODE) {
		AST_Node_Func* temp_func = (AST_Node_Func*)node;
		ast_traverse(temp_func->statement);
		ast_print_node(node, tab_count);
	}
	// Return nodes
	else if (node->type == RETURN_NODE) {
		AST_Node_Return* temp_return = (AST_Node_Return*) node;
		ast_traverse(temp_return->ret_val);
		ast_print_node(node, tab_count);
	}
	else if (node->type == EXPR_NODE) {
		AST_Node_Expr* temp_expr = (AST_Node_Expr*) node;
		ast_traverse(temp_expr->left);
		ast_traverse(temp_expr->right);
		ast_print_node(node, tab_count);
	}
	// Nodes with no children
	else {
		ast_print_node(node, tab_count);
	}
	tab_count--;
}

Finally, for debugging, a print node function was created. This print node function performs a switch case on the node type then prints out the important details of the node. tab_count is also passed to the print node function as it enables the user to see which nodes are children of other nodes. The print function is below:

/* Print a node of any type */
void ast_print_node(AST_Node* node, int tab_cnt)
{
	//declare temp node pointers for each node type
	AST_Node_Const* temp_const;
        AST_Node_ID* temp_ID;
	AST_Node_Return* temp_return;
	AST_Node_Func* temp_func;
	AST_Node_Expr* temp_expr;

	for (int i = 0; i < tab_cnt; i++) {
		printf("\t");
	}

	// do a switch on the node type
	switch (node->type) {
	case BASIC_NODE:
		printf("Basic Node\n");
		break;
	case FUNC_NODE:
		temp_func = (AST_Node_Func*) node;
		printf("Function Node");
		break;
	case CONST_NODE:
		temp_const = (AST_Node_Const*) node;
		printf("Const Node val: %d\n", temp_const->val);
		break;
	case ID_NODE:
		temp_ID = (AST_Node_ID*)node;
		printf("ID node: %s\n", temp_ID->varname);
		break;
	case EXPR_NODE:
		temp_expr = (AST_Node_Expr*)node;
		printf("Expression node: %c\n", ops[temp_expr->op]);
		break;
	case RETURN_NODE:
		temp_return = (AST_Node_Return*)node;
		printf("Return Node type: %d\n", temp_return->ret_type);
		break;
	default:
		printf("Error finding node type, aborting...\n");
		break;
	}
}