/* seman.c * routines used to augment the syntax tree generated by the parser and * create the symbol table for the source code. */ #include #include "tree.h" #include "seman.h" /*********************************data structures**********************/ int error_count=0; tree intTypeT, charTypeT, booleanTypeT, stringTypeT; FILE *errors; /* struct of symbol table stack */ struct { bool marker; /* mark the beginning of a block */ int name; /* point to the lexeme of the id */ int st_ptr; /* point to the id's symble table entry */ bool dummy; /* dummy element to indicate a undeclared id */ bool used; /* this id is used? */ } stack[STACK_SIZE]; /* stack array */ /* struct of element of attribute list */ typedef struct { char attr_num; /* attribute number ( < 256 ) */ int attr_val; /* attribute value */ int next_attr; } attr_type; /* define the struct type and the pointer type */ /* symbol table array */ int st[ST_SIZE]; /* attribute array. attributes are allocated from this array instead of from */ /* dynamically allocated space. It may easy testing and debugging. */ attr_type attrarray[ATTR_SIZE]; /******************* * global counters * *******************/ int stack_top = 0; /* stack top counter */ int st_top = 0; /* symbol table top counter */ int nesting = 0; /* nesting level counter */ int attr_top = 0; /* attribute array counter */ /* function prototypes */ extern int hash_lookup(); /* imported from table.c */ extern void ValProgramOp(); /* from traverse.c */ extern tree MakeLeaf(); /* from tree.c */ extern tree MakeTree(); extern tree NullExp(); extern int getname(); /* from table.c */ void error_msg(); /* from this program */ void SetAttr(); void OpenBlock(); void CloseBlock(); void STInit(); void STPrint(); void Push(); extern int outtable; /* flag: print out symbol table or not? */ /* imported and set at main() in driver4.c */ tree seman(T) tree T; { if (!IsNull(T)) { STInit(); ValProgramOp(T); } return(T); } /************************ routines *****************************/ /***************************************************************************** * STInit(): initialize the symbol table. put predefined names into it and * * build trees for those names. * *****************************************************************************/ void STInit() { tree LT,RT,root; int stid, bufid; int chrP, ordP, writeP, readP; /************************************************************** * build syntax tree for integer and put it into symbol table * **************************************************************/ bufid = hash_lookup("INTEGER"); stid = InsertEntry(bufid); intTypeT = MakeLeaf(INTEGERTNode,stid); SetAttr(stid, TREE_ATTR, intTypeT); SetAttr(stid, PREDE_ATTR,true); SetAttr(stid, KIND_ATTR, TYPE); SetAttr(stid, TYPE_ATTR, intTypeT); /************************************************************ * build syntax tree for char and put it into symbol table * ************************************************************/ bufid = hash_lookup("CHAR"); stid = InsertEntry(bufid); charTypeT = MakeLeaf(CHARTNode,stid); SetAttr(stid, TREE_ATTR, charTypeT); SetAttr(stid, PREDE_ATTR,true); SetAttr(stid, KIND_ATTR, TYPE); SetAttr(stid, TYPE_ATTR, charTypeT); /************************************************************** * build syntax tree for string and put it into symbol table * **************************************************************/ bufid = hash_lookup("STRING"); stid = InsertEntry(bufid); LT = MakeTree(BoundOp,NullExp(), MakeTree(SubrangeOp,MakeLeaf(NUMNode,0), MakeLeaf(NUMNode,STRING_SIZE - 1))); stringTypeT = MakeTree(ArrayTypeOp, LT, charTypeT); SetAttr(stid, TREE_ATTR, stringTypeT); SetAttr(stid, PREDE_ATTR,true); SetAttr(stid, KIND_ATTR, TYPE); SetAttr(stid, TYPE_ATTR, stringTypeT); SetAttr(stid, DIM_ATTR, 1); /*************************************************************** * build syntax tree for boolean and put it into symbol table * ***************************************************************/ bufid = hash_lookup("BOOLEAN"); stid = InsertEntry(bufid); booleanTypeT = MakeLeaf(BOOLEANTNode,stid); SetAttr(stid, TREE_ATTR, booleanTypeT); SetAttr(stid, PREDE_ATTR,true); SetAttr(stid, KIND_ATTR, TYPE); SetAttr(stid, TYPE_ATTR, booleanTypeT); /*********************************************************************/ /* build syntax tree for eof and put it in the symbol table */ /*********************************************************************/ stid = InsertEntry(hash_lookup("EOF")); LT = MakeTree(FuncOp, MakeTree(HeadOp, MakeLeaf(STNode, stid), MakeTree(SpecOp, NullExp(), intTypeT)), NullExp()); SetAttr(stid, TREE_ATTR, LT); SetAttr(stid, PREDE_ATTR, true); SetAttr(stid, KIND_ATTR, FUNC); SetAttr(stid, TYPE_ATTR, LT); SetAttr(stid, VALUE_ATTR, 0); SetAttr(stid, OFFSET_ATTR, 0); /********************************************************************* * build syntax tree for procedure read and put it into symbol table * *********************************************************************/ readP = InsertEntry(hash_lookup("read")); LT = MakeTree(HeadOp, MakeLeaf(STNode,readP), NullExp()); root = MakeTree(ProceOp, LT , NullExp()); SetAttr(readP, TREE_ATTR, root); SetAttr(readP, PREDE_ATTR,true); SetAttr(readP, TYPE_ATTR, root); /********************************************************************** * build syntax tree for procedure write and put it into symbol table * **********************************************************************/ writeP = InsertEntry(hash_lookup("write")); LT = MakeTree(HeadOp, MakeLeaf(STNode,writeP), NullExp()); root = MakeTree(ProceOp, LT, NullExp()); SetAttr(writeP, TREE_ATTR, root); SetAttr(writeP, PREDE_ATTR,true); SetAttr(writeP, KIND_ATTR, PROCE); SetAttr(writeP, TYPE_ATTR, root); /******************************************************************* * build syntax tree for function chr and put it into symbol table * *******************************************************************/ chrP = InsertEntry(hash_lookup("chr")); OpenBlock(); stid = InsertEntry(hash_lookup("i")); LT = MakeLeaf(STNode,stid); SetAttr(stid, TREE_ATTR, LT); SetAttr(stid, PREDE_ATTR,true); SetAttr(stid, KIND_ATTR, VALUE_ARG); SetAttr(stid, TYPE_ATTR, intTypeT); CloseBlock(); /********************** * attributes for chr * ***********************/ RT = MakeTree(SpecOp, MakeTree(VArgTypeOp, MakeTree(CommaOp,LT,intTypeT), NullExp()), charTypeT); root = MakeTree(FuncOp, MakeTree(HeadOp, MakeLeaf(STNode,chrP), RT), NullExp()); SetAttr(chrP, TREE_ATTR, root); SetAttr(chrP, PREDE_ATTR,true); SetAttr(chrP, KIND_ATTR, FUNC); SetAttr(chrP, TYPE_ATTR, root); SetAttr(chrP, VALUE_ATTR, 1); SetAttr(chrP, OFFSET_ATTR, 0); /********************************************************************** * build syntax tree for function ord and put it into symbol table * **********************************************************************/ ordP = InsertEntry(hash_lookup("ord")); OpenBlock(); stid = InsertEntry(hash_lookup("ch")); LT = MakeLeaf(STNode,stid); SetAttr(stid, TREE_ATTR, LT); SetAttr(stid, PREDE_ATTR,true); SetAttr(stid, KIND_ATTR, VALUE_ARG); SetAttr(stid, TYPE_ATTR, charTypeT); CloseBlock(); /*********************** * attributes for ord * **********************/ RT = MakeTree(SpecOp, MakeTree(VArgTypeOp, MakeTree(CommaOp,LT,charTypeT), NullExp()), intTypeT); root = MakeTree(FuncOp, MakeTree(HeadOp, MakeLeaf(STNode,ordP), RT), NullExp()); SetAttr(ordP, TREE_ATTR, root); SetAttr(ordP, PREDE_ATTR,true); SetAttr(ordP, KIND_ATTR, FUNC); SetAttr(ordP, TYPE_ATTR, root); SetAttr(ordP, VALUE_ATTR, 1); SetAttr(ordP, OFFSET_ATTR, 0); } /***************************************************************************** * InsertEntry(): builds a symbol table entry for id. the current block is * * searched for redeclaration error. the id's name and nesting level * * attributes are set by this function. * *****************************************************************************/ int InsertEntry(id) int id; { if (LookUpHere(id)) { error_msg(REDECLARATION, CONTINUE, id); return (0); } if (st_top >= ST_SIZE-1) error_msg(ST_OVERFLOW, ABORT,id); st_top++; st[st_top] = 0; SetAttr(st_top, NAME_ATTR, id); SetAttr(st_top, NEST_ATTR, nesting); Push(false, id, st_top, false); return (st_top); } /****************************************************************************** * IsAttr(): return the index to the searched attribute in attrarray if it is * * in (nonzero). otherwise, return false. ******************************************************************************/ int IsAttr(st_ptr, attr_num) int st_ptr, attr_num; { int i; i = st[st_ptr]; while (i) { if (attrarray[i].attr_num == attr_num) return (i); if (attrarray[i].attr_num > attr_num) break; i = attrarray[i].next_attr; } return (0); } /****************************************************************************** * SetAttr(): set attribute. if the attribute is already there, print * * debugging message. attributes for a symbol table entry are sorted by their * * attr_num. * ******************************************************************************/ void SetAttr(st_ptr, attr_num, attr_val) int st_ptr, attr_num, attr_val; { int *p, next; if (IsAttr(st_ptr, attr_num)) { printf("DEBUG--The attribute number %d ", attr_num); printf("to be added already exists for table entry: %d\n", st_ptr); return; } p = &st[st_ptr]; next = st[st_ptr]; /* search the link list for the right insert position */ while (next) { if (attrarray[next].attr_num < attr_num) { p = &(attrarray[next].next_attr); next = attrarray[next].next_attr; } else break; } attr_top++; attrarray[attr_top].attr_num = attr_num; attrarray[attr_top].attr_val = attr_val; attrarray[attr_top].next_attr = next; *p = attr_top; } /****************************************************************************** * ChangeAttr(): change attribute. if the attribute is not there, print * * debugging message. attributes for a symbol table entry are sorted by their * * attr_num. * ******************************************************************************/ void ChangeAttr(st_ptr, attr_num, attr_val) int st_ptr, attr_num, attr_val; { int next; if (!IsAttr(st_ptr, attr_num)) { printf("DEBUG--The attribute number %d ", attr_num); printf("to be changed dos not exist for table entry: %d\n", st_ptr); return; } next = st[st_ptr]; /* search the link list for the right insert position */ while (next) { if (attrarray[next].attr_num < attr_num) next = attrarray[next].next_attr; else if (attrarray[next].attr_num == attr_num) break; else { printf("DEBUG--something is wrong in ChangeAttr()\n"); return; } } attrarray[next].attr_val = attr_val; } /****************************************************************************** * Push(): push an element onto the stack. * ******************************************************************************/ void Push(marker, name, st_ptr, dummy) int marker, name, st_ptr, dummy; { if (stack_top >= STACK_SIZE-1) error_msg(STACK_OVERFLOW, ABORT,0); stack_top++; stack[stack_top].marker = (bool) marker; stack[stack_top].name = name; stack[stack_top].st_ptr = st_ptr; stack[stack_top].dummy = (bool) dummy; stack[stack_top].used = false; if (st_top <= PRE_DEFINED) stack[stack_top].used = true; } /****************************************************************************** * OpenBlock(): build a mark on the stack to indecate the beginning of a new * * block. increment nesting level counter. It is called when reserved words * * "program", "procedure", "function" or "record" is encountered. Note: * * procedure or function name should be inserted into symbol table before * * calling this routine. * ******************************************************************************/ void OpenBlock() { nesting++; Push(true,0,0,false); /* push a marker onto stack */ } /*************************************************************************** * CloseBlock(): decrement nesting level counter and remove the current * * block from the stack. called when exitting from a program, procedure, * * function or a record definition. each element is checked to see if it is* * used in the block * ***************************************************************************/ void CloseBlock() { int i; for (i = stack_top; !stack[i].marker; i--) if (!stack[i].used && !stack[i].dummy) error_msg(NOT_USED, CONTINUE, stack[i].name); nesting--; stack_top = i - 1; /* trim the stack */ } /***************************************************************************** * GetAttr(): return the specified attribute value for a symbol table entry * * if found. otherwise, report error. Note, this error is not the fault of * * source program but of the compiler writer. It is printed for testing and * * debugging. * *****************************************************************************/ int GetAttr(st_ptr, attr_num) int st_ptr, attr_num; { int i; i = IsAttr(st_ptr, attr_num); if (!i) { printf("DEBUG--The wanted attribute number %d ", attr_num); printf("does not exist for table entry: %d\n", st_ptr); return (0); } return (attrarray[i].attr_val); } /****************************************************************************** * LookUp(): search an id in the stack and return the symbol table entry * * pointer, if found. if the id is not in the stack, report error and push a * * dummy item on the stack so that the same error will not be reported * * repeatedly * ******************************************************************************/ int LookUp(id) int id; { int i; for (i = stack_top; i > 0; i--) if (!stack[i].marker && stack[i].name == id) { stack[i].used = true; return (stack[i].st_ptr); } /**************************************************** *id is undefined, push a dummy element onto stack * ****************************************************/ error_msg(UNDECLARATION, CONTINUE, id); Push(false, id, 0, true); return 0; } /****************************************************************************** * LookUpHere(): search an id in the stack for the current block. It * * returns the symbol table pointer if the id is found. otherwise, return 0 * * this routine can be used to check if there is a forward declaration * * for a procedure/function * ******************************************************************************/ int LookUpHere(id) int id; { int i; for (i = stack_top; !stack[i].marker; i--) if (stack[i].name == id && !stack[i].dummy) return (stack[i].st_ptr); return (0); } /************************************************ * error_msg: error handling routine * ************************************************/ void error_msg(message,action,id) int message, action, id; { int func; errors = stdout; switch (message) { case STACK_OVERFLOW: fprintf(errors,"ERROR: Stack Overflow\n"); error_count++; break; case REDECLARATION: fprintf(errors,"ERROR: Symbol '%s'", getname(id)); fprintf(errors," is re-declared\n"); error_count++; break; case ST_OVERFLOW: fprintf(errors,"ERROR: Symbol Table Overflow\n"); error_count++; break; case UNDECLARATION: fprintf(errors,"ERROR: Symbol '%s'", getname(id)); fprintf(errors," is undefined\n"); error_count++; break; case ATTR_OVERFLOW: fprintf(errors,"ERROR: Attribute array Overflow\n"); error_count++; break; case NOT_USED: fprintf(errors,"WARNING: Symbol '%s'", getname(id)); fprintf(errors," is declared but not used\n"); break; case NOT_INT_CONSTANT: fprintf(errors,"ERROR: Subrange '%s'", getname(id)); fprintf(errors," must be an integer constant\n"); error_count++; break; case NOT_TYPE: fprintf(errors,"ERROR: Symbol '%s'", getname(id)); fprintf(errors," is not a type\n"); error_count++; break; case DIM_MISMATCH: fprintf(errors,"ERROR: Array reference '%s'", getname(id)); fprintf(errors," has a mismatched dimension or incorrect format\n"); error_count++; break; case ASSIGN_ERR: fprintf(errors,"ERROR: Symbol '%s'", getname(id)); fprintf(errors," cannot be assigned with a new value\n"); error_count++; break; case PARA_MISMATCH: fprintf(errors,"ERROR: Routine call '%s'", getname(id)); fprintf(errors," has mismatched parameters\n"); error_count++; break; case REF_ARG_MISMATCH: fprintf(errors,"ERROR: Routine call '%s'", getname(id)); fprintf(errors," uses non-variable as a reference parameter\n"); error_count++; break; case PROC_AS_VAR: fprintf(errors,"ERROR: Procedure '%s'", getname(id)); fprintf(errors," cannot be used as a variable\n"); error_count++; break; case TYPE_AS_VAR: fprintf(errors,"ERROR: Type '%s'", getname(id)); fprintf(errors," cannot be used as a variable\n"); error_count++; break; case NOT_ARRAY: fprintf(errors,"ERROR: Simbol '%s'", getname(id)); fprintf(errors," can not be accessed as an array\n"); error_count++; break; case NOT_RECORD: fprintf(errors,"ERROR: Simbol '%s'", getname(id)); fprintf(errors," can not be accessed as a record\n"); error_count++; break; case ROUTINE_CALL_ERR: fprintf(errors,"ERROR: Routine call '%s'", getname(id)); fprintf(errors," is in an incorrect format\n"); error_count++; break; case NOT_FIELD: fprintf(errors,"ERROR: Simbol '%s'", getname(id)); fprintf(errors," is not a valid record field\n"); error_count++; break; case FORWD_MISMATCH: fprintf(errors,"ERROR: Routine declaration '%s'", getname(id)); fprintf(errors," is inconsistant with its forward definition\n"); error_count++; break; case LOOP_VAR: fprintf(errors,"ERROR: Loop variable '%s'", getname(id)); fprintf(errors," must be a simple variable of integer/char type\n"); error_count++; break; default: fprintf(errors,"I forgot to include something important\n"); break; } switch(action) { case CONTINUE: break; case ABORT: exit(1); break; default: fprintf(errors,"Something is wrong in error_msg, neither "); fprintf(errors,"CONTINUE nor ABORT!\n"); break; } } char *kind_name[] = {"constant", "variable", "procedure", "function", "ref_arg", "val_arg", "field", "type", "array_str"}; /************************************ * STPrint(): print symbol table. * ************************************/ extern FILE *tablelst; /* set at main() in driver4.c */ void STPrint() { int i, attr_num, attr_val, attr_ptr, type_attr; fprintf(tablelst,"\n SYMBOL TABLE\n"); fprintf(tablelst,"+----+----------+----+-----------+----+------------+----------"); fprintf(tablelst,"--+-------+------+\n"); fprintf(tablelst,"| # | Name | Lev| TreeNode |Pred| Kind | Type"); fprintf(tablelst," | Value |Offset|\n"); fprintf(tablelst,"+----+----------+----+-----------+----+------------+----------"); fprintf(tablelst,"--+-------+------+\n"); for (i = 1; i <= st_top; i++) { fprintf(tablelst,"|%3d ", i); for (attr_num = NAME_ATTR; attr_num <= OFFSET_ATTR; attr_num++) if (attr_ptr = IsAttr(i, attr_num)) { attr_val = attrarray[attr_ptr].attr_val; switch (attr_num) { case NAME_ATTR: fprintf(tablelst,"%-10s ", getname(attr_val)); break; case NEST_ATTR: fprintf(tablelst,"%3d ", attr_val); break; case TREE_ATTR: fprintf(tablelst," x%lx ", attr_val); break; case PREDE_ATTR: if (attr_val) fprintf(tablelst," %3s ", "yes"); else fprintf(tablelst," %3s ", "no"); break; case KIND_ATTR: fprintf(tablelst,"%12s ", kind_name[attr_val - CONSTANT]); break; case TYPE_ATTR: if (attr_val == (int)intTypeT) fprintf(tablelst,"%12s ","integer"); else if (attr_val == (int)charTypeT) fprintf(tablelst,"%12s ","character"); else if (attr_val == (int)booleanTypeT) fprintf(tablelst,"%12s ","boolean"); else if (attr_val == (int)stringTypeT) fprintf(tablelst,"%12s ","string"); else switch (NodeOp1(attr_val)) { case ArrayTypeOp: fprintf(tablelst,"%12s ","array"); break; case RecompOp: fprintf(tablelst,"%12s ","record"); break; case SubrangeOp: fprintf(tablelst,"%12s ","subrange"); break; default: fprintf(tablelst,"%12s ","checkProg"); break; } break; case VALUE_ATTR: type_attr = GetAttr(i, TYPE_ATTR); if (type_attr == (int)intTypeT) fprintf(tablelst,"%7d ", attr_val); else if (type_attr == (int)charTypeT) fprintf(tablelst,"%7c ", (char) attr_val); else if (type_attr == (int)booleanTypeT) if (attr_val) fprintf(tablelst,"%7s ", "true"); else fprintf(tablelst,"%7s ", "false"); else if (type_attr == (int)stringTypeT) fprintf(tablelst,"%7s ", getname(attr_val)); else fprintf(tablelst,"%7d ", attr_val); break; case OFFSET_ATTR: fprintf(tablelst,"%7d", attr_val); break; } } else switch (attr_num) { case NAME_ATTR: fprintf(tablelst,"%11s", " "); break; case NEST_ATTR: fprintf(tablelst,"%4s", " "); break; case TREE_ATTR: fprintf(tablelst,"%11s", " "); break; case PREDE_ATTR: fprintf(tablelst,"%5s", " "); break; case KIND_ATTR: fprintf(tablelst,"%13s", " "); break; case TYPE_ATTR: fprintf(tablelst,"%13s"," "); break; case VALUE_ATTR: fprintf(tablelst,"%8s", " "); break; case OFFSET_ATTR: fprintf(tablelst,"%7s", " "); break; } fprintf(tablelst,"|\n"); } fprintf(tablelst,"+----+----------+----+-----------+----+------------+----------"); fprintf(tablelst,"--+-------+------+\n"); }