FILE *fp; SYM_ENTRY *p; NODE * prog;
prog = Program (fp); showSymbolTable(); scoping(prog); printDefinitionTable(); typeChecking(prog); show_tree (prog);
void scoping(NODE * program) {
preOrderScoping(program, NULL, TYPE_ILLEGAL);
}
void typeChecking(NODE * program) {
postOrdertypeChecking(program);
}
Created by the parser, it is referenced by the node structure (int symval;).
typedef struct sym_entry {
char *name;
int val;
enum token toktype;
struct sym_entry *link;
} SYM_ENTRY;
|
Created by the scoping routine use a preorder (node-left-right) tree traversal. Entries are added for parameters or variables. The definition table is referenced by the node structure (int defval).
typedef struct def {
enum type_t type;
enum v_kind kind;
} DEFINITION;
|
enum v_kind {
PARAMETER,
VARIABLE
};
|
enum type_t {
TYPE_ILLEGAL, /* initial value */
TYPE_INT,
TYPE_FLOAT,
TYPE_ERROR,
TYPE_NONE /* for typeless nodes */
};
|
Performed after the scoping procedure. Performs a post order traversal (left-right-node) of the expression tree. Adds nodetype to each node and adds INT_TO_FLOAT and TRUNCATE as appropriate..
The token values as recorded in the symbol table.
enum token {
TOK_PLUS, TOK_MINUS, TOK_MULT, TOK_DIV, TOK_PERCENT, TOK_BANG, TOK_QUES, TOK_COLON,
TOK_ASSIGN, TOK_COMMA, TOK_LT, TOK_GT, TOK_OPAR, TOK_CLPAR, TOK_OCURLY, TOK_CLCURLY,
TOK_OR, TOK_AND, TOK_EQUAL, TOK_SEMI, TOK_BREAK, TOK_CONTIN, TOK_ELSE, TOK_FLOAT,
TOK_IF, TOK_INT, TOK_RETURN, TOK_WHILE, TOK_IDENT, TOK_INTNUM, TOK_FLOATNUM, TOK_EOF,
TOK_COMMENT, TOK_SPACE, TOK_ERR, TOK_UNKNOWN };
Node type added to each node by the type checking procedure.
enum node_ty {
/* use this for initializing */
ILLEGAL_NODE,
/* this is the top node of the tree */
SOURCE,
/* these are the two types in C-- */
INTTYPE, FLOATTYPE,
/* this is a declaration */
DECL,
/* these are leaves with values */
INTNUM, FLOATNUM, IDENT,
/* these are statements */
COMPOUND, CONDITIONAL, ITERATION, BREAK, CONTINUE, RETURN, COMPUTATION, EMPTY,
/* these are expressions */
ASSIGN, CONDITION, OR_OP, AND_OP, NOT_OP, EQUAL_OP, GT_OP, LT_OP,
ADD_OP, SUB_OP, MULT_OP, DIV_OP, MOD_OP, NEG_OP,
/* new nodes needed after overloading has been resolved */
ADD_OP_INT, ADD_OP_FLOAT, SUB_OP_INT, SUB_OP_FLOAT, MULT_OP_INT, MULT_OP_FLOAT,
DIV_OP_INT, DIV_OP_FLOAT, NEG_OP_INT, NEG_OP_FLOAT, GT_OP_INT, GT_OP_FLOAT,
LT_OP_INT, LT_OP_FLOAT, EQUAL_OP_INT, EQUAL_OP_FLOAT, INT_TO_FLOAT, TRUNCATE };
typedef struct node {
enum node_ty nodetype;
struct node *child[3]; /* used for tree structure */
struct node *link; /* used for linked lists */
union
{
int intval;
int symval;
float floatval;
} val;
int defval; /* set by scoping routine */
enum type_t valtype; /* set by typing routine */
int line, column;
} NODE;
|
Two fields are added to the existing NODE structure (from phase 4): an index into the definition table (defval, applicable only to IDENT nodes), and the value type (valtype) of the node as described above.
void showSymbolTable() {
SYM_ENTRY * x;
char * symbolTokStr[] =
{
"TOK_PLUS", "TOK_MINUS", "TOK_MULT", "TOK_DIV", "TOK_PERCENT",
"TOK_BANG", "TOK_QUES", "TOK_COLON", "TOK_ASSIGN", "TOK_COMMA",
"TOK_LT", "TOK_GT", "TOK_OPAR", "TOK_CLPAR", "TOK_OCURLY",
"TOK_CLCURLY", "TOK_OR", "TOK_AND", "TOK_EQUAL", "TOK_SEMI",
"TOK_BREAK", "TOK_CONTIN", "TOK_ELSE", "TOK_FLOAT", "TOK_IF",
"TOK_INT", "TOK_RETURN", "TOK_WHILE", "TOK_IDENT", "TOK_INTNUM",
"TOK_FLOATNUM", "TOK_EOF", "TOK_COMMENT", "TOK_SPACE", "TOK_ERR",
"TOK_UNKNOWN" };
printf("symbol table entries follows\n");
for (x=sym_table; x!=NULL; x=x->link) {
printf("# = %3d ", x->val);
printf("token # = %3d ", x->toktype);
printf("token type = %12s ", symbolTokStr[x->toktype]);
printf("name = %s\n",x->name);
}
}
void printDefinitionTable() {
char * type_t_string[] = {
"TYPE_ILLEGAL", /* initial value */
"TYPE_INT ",
"TYPE_FLOAT ",
"TYPE_ERROR ",
"TYPE_NONE " /* for typeless nodes */
};
char * v_kind_string[] = {
"PARAMETER",
"VARIABLE "
};
printf("DEFINITION def_table[%d]\n", def_cnt);
for(int i = 0; i < def_cnt; i++) {
printf("entry = %2d ",i);
printf("kind = %12s ", v_kind_string[def_table[i].kind]);
printf("type = %12s\n", type_t_string[def_table[i].type]);
}
}
void printNode(NODE * n) {
char * node_ty_string[] =
{ "ILLEGAL_NODE", "SOURCE", "INTTYPE", "FLOATTYPE", "DECL",
"INTNUM", "FLOATNUM", "IDENT", "COMPOUND", "CONDITIONAL",
"ITERATION", "BREAK", "CONTINUE", "RETURN", "COMPUTATION",
"EMPTY", "ASSIGN", "CONDITION", "OR_OP", "AND_OP",
"NOT_OP", "EQUAL_OP", "GT_OP", "LT_OP", "ADD_OP",
"SUB_OP", "MULT_OP", "DIV_OP", "MOD_OP", "NEG_OP",
"ADD_OP_INT", "ADD_OP_FLOAT", "SUB_OP_INT", "SUB_OP_FLOAT", "MULT_OP_INT",
"MULT_OP_FLOAT", "DIV_OP_INT", "DIV_OP_FLOAT", "NEG_OP_INT", "NEG_OP_FLOAT",
"GT_OP_INT", "GT_OP_FLOAT", "LT_OP_INT", "LT_OP_FLOAT", "EQUAL_OP_INT",
"EQUAL_OP_FLOAT", "INT_TO_FLOAT", "TRUNCATE"
};
char * type_t_string[] = {"TYPE_ILLEGAL","TYPE_INT","TYPE_FLOAT",
"TYPE_ERROR","TYPE_NONE"};
char * loc_string[] = {"NO_LOC", "M_LOC", "I_REG", "F_REG" };
int node_ty_string_entries = sizeof(node_ty_string) / sizeof(char *);
int type_t_string_entries = sizeof(type_t_string) / sizeof(char *);
int loc_string_entries = sizeof(loc_string) / sizeof(char *);
if(n == NULL) {
printf("node pointer is NULL in printnode\n");
return;
}
printf("node type = %s\n",node_ty_string[n->nodetype]);
if(n->child[0] == NULL) printf("child[0] = NULL\n");
else
if(n->child[0]->nodetype < 0 || n->child[0]->nodetype >= node_ty_string_entries)
printf("child[0] = %s\n", "***ILLEGAL***");
else
printf("child[0] = %s\n",node_ty_string[n->child[0]->nodetype]);
if(n->child[1] == NULL) printf("child[1] = NULL\n");
else
if(n->child[1]->nodetype < 0 || n->child[1]->nodetype >= node_ty_string_entries)
printf("child[0] = %s\n", "***ILLEGAL***");
else
printf("child[1] = %s\n",node_ty_string[n->child[1]->nodetype]);
if(n->child[2] == NULL) printf("child[2] = NULL\n");
else
if(n->child[2]->nodetype < 0 || n->child[2]->nodetype >= node_ty_string_entries)
printf("child[0] = %s\n", "***ILLEGAL***");
else
printf("child[2] = %s\n",node_ty_string[n->child[2]->nodetype]);
if(n->link == NULL) printf("link = NULL\n");
else
if(n->link->nodetype < 0 || n->link->nodetype >= node_ty_string_entries)
printf("link = %s\n", "***ILLEGAL***");
else
printf("link = %s\n",node_ty_string[n->link->nodetype]);
printf("intval = %d symval = %d floatval = %f\n",
n->val.intval, n->val.symval, n->val.floatval);
printf("defval = %d\n",n->defval);
if(n->valtype < 0 || n->valtype >= type_t_string_entries)
printf("valtype = %s\n", "***ILLEGAL***");
else
printf("valtype = %s\n",type_t_string[n->valtype]);
printf("\n");
}
For the tree shown below, the order of first visiting for a depth first search would be: A B D H E C F I G J
A
/ \
/ \
B C
/ \ / \
D E F G
/ \ \
H I J
In the case of binary trees there are 3 common variants of depth-first search called pre-order, in-order, and post-order traversal.
The variants distinguish between first visiting a node, and processing that node, i.e. doing something with the data stored
in the node (e.g. printing out the name of the node). There are six possible orders for three objects, of which the three
orders commonly used are as follows:
process node, visit left subtree, visit right subtree. This variant is called pre-order traversal. In order traversal
of the binary tree shown above processes the nodes in the order A B D H E C F I G J as for simple depth-first search.
visit left subtree, process node, visit right subtree. This variant is called in-order traversal. In order traversal
of the binary tree shown above processes the nodes in the order H D B E A F I C G J.
visit left subtree, visit right subtree, process node. This variant is called post-order traversal. In order traversal
of the binary tree shown above processes the nodes in the order H D E B I F J G C A.
This is provided as an example. If you don't care for it's functionality, please develop your own.
const int stackNodeListSize = 1000;
class parserStack {
public:
parserStack();
~parserStack();
void push(int symVal, int defVal, NODE * nodePtr);
void pop();
sNode * find(int symVal);
sNode * peek();
void dump(char *);
int empty();
private:
sNode * stackList[stackNodeListSize];
int stackCount;
};
parserStack::parserStack() {
stackCount = 0;
}
parserStack::~parserStack() {
//for(int i = 0; i < stackNodeListSize; i++)
// if(stackList[i] != NULL) delete stackList[i];
}
void parserStack::push(int symVal, int defVal, NODE * nodePtr) {
assert(stackCount < stackNodeListSize);
stackList[stackCount] = new sNode;
stackList[stackCount]->symVal = symVal;
stackList[stackCount]->defVal = defVal;
stackList[stackCount]->parent = nodePtr;
stackCount++;
}
void parserStack::pop() {
assert(stackCount != 0);
delete stackList[stackCount--];
}
sNode * parserStack::find(int symVal) {
for(int i = stackCount - 1; i >= 0; i--)
if(symVal == stackList[i]->symVal) return stackList[i];
return NULL;
}
sNode * parserStack::peek() {
if(stackCount == 0) return NULL;
else return stackList[stackCount-1];
}
int parserStack::empty() {
if(stackCount == 0) return 1;
else return 0;
}
void parserStack::dump(char * message) {
char * node_str[] =
{
"ILLEGAL", "SOURCE", "INTTYPE", "FLOATTYPE", "DECL", "INTNUM", "FLOATNUM",
"IDENT", "COMPOUND", "CONDITIONAL", "ITERATION", "BREAK", "CONTINUE", "RETURN",
"COMPUTATION", "EMPTY", "ASSIGN", "CONDITION", "OR_OP", "AND_OP", "NOT_OP",
"EQUAL_OP", "GT_OP", "LT_OP", "ADD_OP", "SUB_OP", "MULT_OP", "DIV_OP",
"MOD_OP", "NEG_OP", "ADD_OP_INT", "ADD_OP_FLOAT", "SUB_OP_INT", "SUB_OP_FLOAT",
"MULT_OP_INT", "MULT_OP_FLOAT", "DIV_OP_INT", "DIV_OP_FLOAT", "NEG_OP_INT",
"NEG_OP_FLOAT", "GT_OP_INT", "GT_OP_FLOAT", "LT_OP_INT", "LT_OP_FLOAT", "EQUAL_OP_INT",
"EQUAL_OP_FLOAT", "INT_TO_FLOAT", "TRUNCATE"
};
char * type_str[] =
{
"(type ILLEGAL)", "(type INT)", "(type FLOAT)", "(type ERROR)", "(type NONE)" };
char * v_kind_str[] = { "PARAMETER", "VARIABLE" };
printf(" current stack contents (%s):\n",message);
if(stackCount == 0) printf(" stack empty\n");
for(int i = 0; i < stackCount; i++) {
printf("entry = %3d symVal = %3d defVal = %3d ",
i, stackList[i]->symVal , stackList[i]->defVal);
if(stackList[i]->parent == NULL) printf(" parent null");
else printf("parent address %p",stackList[i]->parent);
printf("\n");
}
}