/*********************************************************/ /* tree.c This file consists of 4 parts a. the data structure of a tree node b. the tree operation functions, from "CopyTree" to "SetRightChild" c. the tree printing function d. the tree checker The functions in this file are contributed by Chunmin Qiao and Aggelos Varvitsiotis. */ #include #include "tree.h" #include "seman.h" extern int GetAttr(); /* used to get name attribute from symbol table */ /* from seman.c */ tree Root; ILTree dummy = { DUMMYNode, 0, 0, 0, 0 }; /******************************************************** * This function return a DUMMYNode to the caller * * Note: All the dummy nodes are corresponding to * * the save memory location. So any attampt to * * use it for the other purposes will cause * * trouble * ********************************************************/ tree NullExp() { return (&dummy); } /*********************************************************** * This function makes an exact copy of a tree. * * Used to duplicate type tree in order to malipulate * * the copy and build a new type tree with another * * type tree attached to it instead of a STNode. ***********************************************************/ tree DupTree(T) tree T; { tree p; if (T==NullExp()) return(NullExp()); p = (tree) malloc(sizeof(ILTree)); p->NodeKind = T->NodeKind; p->IntVal= T->IntVal; p->NodeOpType = T->NodeOpType; p->LeftC = DupTree(T->LeftC); p->RightC= DupTree(T->RightC); return(p); } /***************************************************************** * This function compares two trees T1 and T2, * * returns true if they are identical and false otherwise. * *****************************************************************/ bool IsSameTree(T1, T2) tree T1, T2; { if (IsNull(T1) && IsNull(T2)) return true; else if (!IsNull(T1) && !IsNull(T2)) if (T1->NodeKind != T2->NodeKind || T1->NodeOpType != T2->NodeOpType) /* || T1->IntVal != T2->IntVal) */ return false; else return (IsSameTree(T1->LeftC, T2->LeftC) && IsSameTree(T1->RightC, T2->RightC)); else return false; } /*********************************************************** * This function will create a leafnode with it * * NodeKind and IntVal to be Kind and N, respectively * * NullExp is explictly assigned to LeftC/RightC * * Added by Bohr He, Oct. 1994 * ***********************************************************/ tree MakeLeaf(Kind, N) int Kind, N; { tree p; p = (tree)malloc(sizeof(ILTree)); p->NodeKind = Kind; p->NodeOpType = 0; p->IntVal = N; p->LeftC = NullExp(); p->RightC = NullExp(); return (p); } /*********************************************************** * This function create a interior node of NodeOptype * * with children to be Left and Right, respectively, * ***********************************************************/ tree MakeTree(NodeOp, Left, Right) int NodeOp; tree Left, Right; { tree p; p = (tree)malloc(sizeof(ILTree)); p->NodeKind = EXPRNode; p->NodeOpType = NodeOp; p->IntVal = 0; p->LeftC = Left; p->RightC = Right; return (p); } /********************************************************* * This function returns leftchild of the treenode * *********************************************************/ tree LeftChild(T) tree T; { if (NodeKind(T) != EXPRNode) return (NullExp()); return (T->LeftC); } /********************************************************* * This function returns rightchild of the treenode * *********************************************************/ tree RightChild(T) tree T; { if (NodeKind(T) != EXPRNode) return (NullExp()); return (T->RightC); } /******************************************************** * This function makes subtree T1 to be the * * leftmost child of the tree T2, return T2 * ********************************************************/ tree MkLeftC(T1, T2) tree T1, T2; { tree p,q; p = T2; q = LeftChild(p); /* replace the leftmost DUMMYNode */ while ( !IsNull(q) ) { p = q; q = LeftChild(p); } p->LeftC = T1; return(T2); } /******************************************************** * This function makes subtree T1 to be the * * rightmost child of the tree T2, return T2 * ********************************************************/ tree MkRightC(T1, T2) tree T1, T2; { tree p,q; p = T2; q = RightChild(p); /* replace the rightmost DUMMYNode */ while ( !IsNull(q) ) { p = q; q = RightChild(p); } p->RightC = T1; return(T2); } /******************************************************** * This function returns NodeOpType of a node * ********************************************************/ int NodeOp(T) tree T; { if (NodeKind(T) != EXPRNode) { printf("NodeOP(): This node must be an EXPRNode!\n"); return(0); } return (T->NodeOpType); } /******************************************************** * This function returns NodeKind of a node * ********************************************************/ int NodeKind(T) tree T; { return (T->NodeKind); } /******************************************************** * This function returns IntVal of a leafnode * ********************************************************/ int IntVal(T) tree T; { if ( NodeKind(T) == EXPRNode ) { printf("IntVal(): This node must be a leaf node!\n"); return(-1); } return (T->IntVal); } /******************************************************** * This function return true if the node is * * DUMMYNode, false otherwise. * ********************************************************/ int IsNull(T) tree T; { return ( NodeKind(T) == DUMMYNode ); } /******************************************************** * This function sets the Target Node to be * * Source Node (only for Non Dummy Target Node) * ********************************************************/ tree SetNode(Target, Source) tree Target, Source; { if ((Target->NodeKind = Source->NodeKind) != EXPRNode) { Target->IntVal = Source->IntVal; Target->LeftC = NullExp(); Target->RightC = NullExp(); } else { Target->NodeOpType = Source->NodeOpType; Target->LeftC = Source->LeftC; Target->RightC = Source->RightC; } return Target; } /******************************************************** * This function sets the NodeOpType to be * * to be NewOp (only for Interior EXPRNode) * ********************************************************/ tree SetNodeOp(T, Op) tree T; int Op; { if (NodeKind(T) != EXPRNode) printf("SetNodeOp(): This node must be an EXPRNode!\n"); else { T->NodeOpType = Op; return T; } } /******************************************************** * This function sets the tree root and all its * * left subtree root to be a NewOp node, used only * * in construct a Record Component subtree. * * Name Changed by Hui-Jung Chang, Oct.30, 1992 * * Function is changed to return the tree - * * Bohr He, Oct. 1994 * ********************************************************/ tree SetLeftTreeOp(T, Op) tree T; int Op; { tree p; p = T; do { SetNodeOp(p, Op); p = LeftChild(p); } while ( !IsNull(p)); return T; } /******************************************************** * This function sets the tree root and all its * * right subtree root to be a NewOp node, used * * only in construct a Procedure or function call * * subtree with arguments * * Added by Hui-Jung Chang , Oct.30, 1992 * * Function is changed to return the tree - * * Bohr He, Oct. 1994 * ********************************************************/ tree SetRightTreeOp(T, Op) tree T; int Op; { tree p; p = T; do { SetNodeOp(p, Op); p = RightChild(p); } while ( !IsNull(p)); return T; } /**************************************************************** * This function sets the LeftChild of T to be NewC * ****************************************************************/ tree SetLeftChild(T, NewC) tree T, NewC; { if (NodeKind(T) != EXPRNode) printf("SetLeftChild(): This node must be an EXPRNode!\n"); else { T->LeftC = NewC; return T; } } /**************************************************************** * This function sets the RightChild of T to be NewC * ****************************************************************/ tree SetRightChild(T, NewC) tree T, NewC; { if (NodeKind(T) != EXPRNode) printf("SetRightChild(): This node must be an EXPRNode!\n"); else { T->RightC = NewC; return T; } } /*********************************************************** * This function will assign a type T to a variable * * list L with left recursion, and the updated list * * gets returned with each variable having type T * * Written by Bohr He, Oct. 1994 * ***********************************************************/ tree AssignTypeL(L, T) tree L, T; { tree p, q; p = L; while (!IsNull(p)) { q = p->RightC; SetRightChild(q, T); p = p->LeftC; } return L; } /*********************************************************** * This function will assign a type T to a variable * * list L with right recursion, and the updated list * * gets returned with each variable having type T * * Written by Bohr He, Oct. 1994 * ***********************************************************/ tree AssignTypeR(L, T) tree L, T; { tree p, q; p = L; while (!IsNull(p)) { q = p->LeftC; SetRightChild(q, T); p = p->RightC; } return L; } /*****************************************************************/ /* This is syntax tree printer, "treelst" is the output file pointer. call printtree with the root node pointer and the depth level (could be 0 if you do not want the root to be indent) writing "getname()" and "getstring()" is your responsibility ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */ extern FILE *treelst; char *opnodenames [] = { "ProgramOp", "BodyOp", "DeclOp", "CommaOp", "ArrayTypeOp", "TypeIdOp", "BoundOp", "RecompOp", "ToOp", "DownToOp", "ConstantIdOp", "ProceOp", "FuncOp", "HeadOp", "RArgTypeOp", "VargTypeOp", "StmtOp", "IfElseOp", "LoopOp", "SpecOp", "RoutineCallOp", "AssignOp", "ReturnOp", "AddOp", "SubOp", "MultOp", "DivOp", "LTOp", "GTOp", "EQOp", "NEOp", "LEOp", "GEOp", "AndOp", "OrOp", "UnaryNegOp", "NotOp", "VarOp", "SelectOp", "IndexOp", "FieldOp", "SubrangeOp", "ExitOp" }; static int crosses [162]; /**************************************************************** * Added by Bohr He, Oct. 1994 * ****************************************************************/ extern char string_buff[]; char *getname(index) int index; { return (string_buff+index); } char *getstring(index) int index; {return (string_buff+index); } /***************************************************************/ void indent (x) int x; { register i; for (i = 0; i < x; i++) { fprintf (treelst,"%s", crosses [i]? "| " : " "); } fprintf (treelst,"%s", x ? "+-" : "R-"); if (x) crosses [x] = (crosses [x] + 1) % 2; } void zerocrosses () { register i; for (i = 0; i < 162; i++) crosses [i] = 0; } void printtree (nd, depth) tree nd; int depth; { if (!depth) { zerocrosses (); fprintf (treelst,"************* SYNTAX TREE PRINTOUT ***********\n\n"); } if (IsNull (nd)) { indent (depth); fprintf (treelst,"[DUMMYnode]\n"); return; } if (NodeKind (nd) == EXPRNode) printtree (RightChild (nd), depth + 1); indent (depth); switch (NodeKind (nd)) { case IDNode: fprintf (treelst,"[IDNode,%d,\"%s\"]\n", IntVal (nd), getname(IntVal(nd))); break; case NUMNode: fprintf (treelst,"[NUMNode,%d]\n", IntVal (nd)); break; case CHARNode: if (isprint (IntVal (nd))) fprintf (treelst,"[CHARNode,%d,\'%c\']\n", IntVal (nd), IntVal (nd)); else fprintf (treelst,"[CHARNode,%d,\'\\%o\']\n", IntVal (nd), IntVal (nd)); break; case STRINGNode:fprintf (treelst,"[STRINGNode,%d,\"%s\"]\n", IntVal (nd), getstring(IntVal(nd))); break; case EXPRNode: fprintf (treelst,"[%s]\n", opnodenames [NodeOp(nd) - ProgramOp]); break; case INTEGERTNode: fprintf (treelst,"[INTEGERTNode,%d,\"INTEGER\"]\n", IntVal(nd)); break; case CHARTNode: fprintf (treelst,"[CHARTNode,%d,\"CHAR\"]\n", IntVal(nd)); break; case BOOLEANTNode: fprintf (treelst,"[BOOLEANTNode,%d,\"BOOLEAN\"]\n", IntVal(nd)); break; case STNode: fprintf (treelst,"[STNode,%d,\"%s\"]\n", IntVal(nd), getname(GetAttr(IntVal(nd), NAME_ATTR))); break; default: fprintf (treelst,"INVALID!!!\n"); break; } if (NodeKind (nd) == EXPRNode) printtree (LeftChild (nd), depth + 1); } /*****************************************************************/ /* syntax tree checker. call checktree with the root node pointer */ /* These two are defined in seman.h #define true 1 #define false 0 */ /* This is a tree-checker for PAC. Purpose: The function ValidTree( ILTree ) returns true if the tree has a legal structure. Algorithm: The tree checker is written very much like a recursive descent parser. */ extern char *opnodenames[]; /******************************************************** * This function returns NodeOpType of a node * * It keeps silent when the node is not a EXPRNode * * and return 0 so that it won't match any NodeOp * * It is only used by tree checker * ********************************************************/ NodeOp1(T) tree T; { if (NodeKind(T) != EXPRNode) return(0); return (T->NodeOpType); } PrintStr(N) int N; { printf(" %s\n", opnodenames[N-ProgramOp]); } void checktree(T) struct ILTree *T; { printf("\nchecking the syntax tree ... \n"); if(ValidTree(T)==1) printf("==> The Syntax Tree Is Valid \n\n"); else printf("INVALID TREE\n"); } ValidTree(T) /*returns boolean*/ struct ILTree *T; { if (IsNull(T) == 1) { printf("Null tree detected.\n"); return(true); } else if (NodeOp1(T) != ProgramOp) { printf("The root should be ProgramOp.\n"); return(false); } else return(ValidProgramOp(T)); } ValidProgramOp(T) /*returns boolean*/ struct ILTree *T; { int leftmark = true; int rightmark = true; if (NodeOp1(LeftChild(T)) == BodyOp) leftmark = ValidBodyOp(LeftChild(T)); else if (! IsNull(LeftChild(T))) { printf("Left child of ProgramOp must be BodyOp or null.\n"); leftmark = false; } if (NodeOp1(RightChild(T)) == StmtOp) rightmark = ValidStmtOp(RightChild(T)); else if (! IsNull(RightChild(T))) { printf("Right child of ProgramOp must be StmtOp or null.\n"); rightmark = false; } return(leftmark && rightmark); } ValidBodyOp(T) /*returns boolean*/ struct ILTree *T; { int leftmark = true; int rightmark = true; if (NodeOp1(LeftChild(T)) == BodyOp) leftmark = ValidBodyOp(LeftChild(T)); else if (! IsNull(LeftChild(T))) { printf("Left child of BodyOp must be BodyOp or null.\n"); leftmark = false; } rightmark = ValidDef(RightChild(T)); if (! rightmark) printf("Right child of BodyOp must be a definition or declaration.\n"); return(leftmark && rightmark); } ValidDef(T) /*returns boolean*/ struct ILTree *T; { if ((NodeOp1(T) == ProceOp) || (NodeOp1(T) == FuncOp)) return(ValidRoutineOp(T)); else if (NodeOp1(T) == ConstantIdOp) return(ValidConstantIdOp(T)); else if (NodeOp1(T) == TypeIdOp) return(ValidTypeIdOp(T)); else if (NodeOp1(T) == DeclOp) return(ValidDeclOp(T)); else { printf("A definition or declaration is expected.\n"); return(false); } } /* ValidDef */ ValidTypeIdOp(T) /*returns boolean*/ struct ILTree *T; /* only used to check TypeIdOp with id and type */ { int leftmark = true; int rightmark = true; if (NodeKind(LeftChild(T)) != IDNode) { printf("Left child of TypeIdOp must be IDNode.\n"); leftmark = false; } rightmark = ValidType(RightChild(T)); if (! rightmark) printf("Right child of TypeIdOp must be a type.\n"); return(leftmark && rightmark); } ValidDeclOp(T) /*returns boolean*/ struct ILTree *T; { int leftmark = true; int rightmark = true; if (NodeOp1(LeftChild(T)) == DeclOp) leftmark = ValidDeclOp(LeftChild(T)); else if (! IsNull(LeftChild(T))) { printf("Left child of DeclOp must be DeclOp or null.\n"); leftmark = false; } if (NodeOp1(RightChild(T)) == CommaOp) rightmark = ValidCommaOp(RightChild(T)); else { printf("Right child of DeclOp must be CommaOp.\n"); rightmark = false; } return(leftmark && rightmark); } ValidCommaOp(T) /*returns boolean*/ struct ILTree *T; /* only used to check CommaOp with id and type */ { int leftmark = true; int rightmark = true; if (NodeKind(LeftChild(T)) != IDNode) { printf("Left child of CommaOp must be IDNode.\n"); leftmark = false; } rightmark = ValidType(RightChild(T)); if (! rightmark) printf("Right child of CommaOp must be a type.\n"); return(leftmark && rightmark); } ValidType(T) /*returns boolean*/ struct ILTree *T; { if (NodeOp1(T) == ArrayTypeOp) return(ValidArrayTypeOp(T)); else if (NodeOp1(T) == RecompOp) return(ValidRecompOp(T)); else if (NodeOp1(T) == SubrangeOp) return(ValidSubrangeOp(T)); else if (NodeKind(T) == IDNode) return(true); printf("A type or an id is expected.\n"); return(false); } /* ValidType */ ValidArrayTypeOp(T) /*returns boolean*/ struct ILTree *T; { int leftmark = true; int rightmark = true; if (NodeOp1(LeftChild(T)) == BoundOp) leftmark = ValidBoundOp(LeftChild(T)); else { printf("Left child of ArrayTypeOp must be BoundOp.\n"); leftmark = false; } rightmark = ValidType(RightChild(T)); if (! rightmark) printf("Left child of ArrayTypeOp must be a type subtree.\n"); return(leftmark && rightmark); } /*--------------------------------------------------------------* * Modified by Hui-Jung Chang, Oct.22, 1992 * * RightChild of BoundOp should be SubrangeOp, not the CommaOp. * *--------------------------------------------------------------*/ ValidBoundOp(T) /*returns boolean*/ struct ILTree *T; { int leftmark = true; int rightmark = true; tree temp; if (NodeOp1(LeftChild(T)) == BoundOp) leftmark = ValidBoundOp(LeftChild(T)); else if (! IsNull(LeftChild(T))) { printf("Left child of BoundOp must be BoundOp or null.\n"); leftmark = false; } /* if (NodeOp1(RightChild(T)) != CommaOp) { printf("Right child of BoundOp must be CommaOp.\n"); rightmark = false; } else { temp = RightChild(T); if ((NodeKind(LeftChild(temp)) != NUMNode && NodeKind(LeftChild(temp)) != IDNode ) || (NodeKind(RightChild(temp)) != NUMNode && NodeKind(RightChild(temp)) != IDNode )) { printf("Two children of CommaOp must be NUMNode or IDNode.\n"); rightmark = false; } } */ if (NodeOp1(RightChild(T)) != SubrangeOp ) { printf("Right child of BoundOp must be SubrangeOp.\n"); rightmark = false; } else rightmark = ValidSubrangeOp(RightChild(T)); return(leftmark && rightmark); } ValidRecompOp(T) /*returns boolean*/ struct ILTree *T; { int leftmark = true; int rightmark = true; if (NodeOp1(LeftChild(T)) == RecompOp) leftmark = ValidRecompOp(LeftChild(T)); else if (! IsNull(LeftChild(T))) { printf("Left child of RecompOp must be RecompOp or null.\n"); leftmark = false; } if (NodeOp1(RightChild(T)) == CommaOp) rightmark = ValidCommaOp(RightChild(T)); else { printf("Right child of RecompOp must be CommaOp.\n"); rightmark = false; } return(leftmark && rightmark); } /*----------------------------------------------* * Modified by Hui-Jung Chang, Oct.22, 1992 * * integer constant can be signed or unsigned. * *----------------------------------------------*/ ValidSubrangeOp(T) /*returns boolean*/ struct ILTree *T; { /* if ((NodeKind(LeftChild(T)) != IDNode && NodeKind(LeftChild(T)) != NUMNode) || (NodeKind(RightChild(T)) != NUMNode && NodeKind(RightChild(T)) != IDNode)) */ if ((NodeKind(LeftChild(T)) != IDNode && ValidIntegerConstant(LeftChild(T)) != true) || (NodeKind(RightChild(T)) != IDNode && ValidIntegerConstant(RightChild(T)) != true )) { printf("Bounds of a subrange type must integer or constant id.\n"); return(false); } return(true); } /*----------------------------------------------* * Added by Hui-Jung Chang, Oct.22, 1992 * * integer constant can be signed or unsigned. * *----------------------------------------------*/ ValidIntegerConstant(T) struct ILTree *T; { if (NodeKind(T) == NUMNode) /* it's unsigned integer constant */ return(true); if (NodeOp1(T) != UnaryNegOp || NodeKind(LeftChild(T)) != NUMNode ) { printf("Integer constant should be signed or unsigned only.\n"); return(false); } return(true); } ValidConstantIdOp(T) /*returns boolean*/ struct ILTree *T; { int mark = true; if (NodeKind(LeftChild(T)) != IDNode) { printf("Left child of ConstantIdOp must IDNode.\n"); mark = false; } if (NodeKind(RightChild(T)) != NUMNode && NodeKind(RightChild(T)) != CHARNode && NodeKind(RightChild(T)) != STRINGNode) { printf("Right child of ConstantIdOp must be a constant.\n"); mark = false; } return(mark); } ValidRoutineOp(T) /*returns boolean*/ struct ILTree *T; { int leftmark = true; int rightmark = true; tree temp; if (NodeOp1(LeftChild(T)) != HeadOp) { printf("Left child of ProceOp/FuncOp must be HeadOp.\n"); leftmark = false; } else leftmark = ValidHeadOp(LeftChild(T)); if (NodeOp1(RightChild(T)) == BodyOp) { temp = RightChild(T); if (NodeOp1(LeftChild(temp)) == BodyOp) rightmark = ValidBodyOp(LeftChild(temp)); else if (! IsNull(LeftChild(temp))) { printf("Left child of BodyOp must be BodyOp or null.\n"); rightmark = false; } if (NodeOp1(RightChild(temp)) == StmtOp) rightmark = rightmark && ValidStmtOp(RightChild(temp)); else if (! IsNull(RightChild(temp))) { printf("Right child of BodyOp must be Stmt or null.\n"); rightmark = false; } } else if (! IsNull(RightChild(T))) { printf("Right child of ProceOp/FuncOp must be BodyOp or null.\n"); rightmark = false; } return(leftmark && rightmark); } ValidHeadOp(T) /*returns boolean*/ struct ILTree *T; { int leftmark = true; int rightmark = true; if (NodeKind(LeftChild(T)) != IDNode) { printf("Left child of HeadOp must be IDNode.\n"); leftmark = false; } if (NodeOp1(RightChild(T)) == SpecOp) rightmark = ValidSpecOp(RightChild(T)); else if (! IsNull(RightChild(T))) { printf("Right child of HeadOp must be SpecOp or null.\n"); rightmark = false; } return(leftmark && rightmark); } ValidSpecOp(T) /*returns boolean*/ struct ILTree *T; { int leftmark = true; int rightmark = true; if (NodeOp1(LeftChild(T)) == RArgTypeOp || NodeOp1(LeftChild(T)) == VArgTypeOp) leftmark = ValidArgs(LeftChild(T)); else if (! IsNull(LeftChild(T))) { printf("Left child of SpecOp must be R/VArgTypeOp or null.\n"); leftmark = false; } if (! IsNull(RightChild(T))) { rightmark = ValidType(RightChild(T)); if (! rightmark) printf("Right child of SpecOp must be null or a type.\n"); } return(leftmark && rightmark); } ValidArgs(T) /*returns boolean*/ struct ILTree *T; { int leftmark = true; int rightmark = true; if (NodeOp1(LeftChild(T)) != CommaOp) { printf("Left child of R/VArgTypeOp must be CommaOp.\n"); leftmark = false; } else leftmark = ValidCommaOp(LeftChild(T)); if (NodeOp1(RightChild(T)) == RArgTypeOp || NodeOp1(RightChild(T)) == VArgTypeOp) rightmark = ValidArgs(RightChild(T)); else if (! IsNull(RightChild(T))) { printf("Right child of R/VArgTypeOp must be R/VArgTypeOp or null.\n"); rightmark = false; } return(leftmark && rightmark); } ValidStmtOp(T) /*returns boolean*/ struct ILTree *T; { int leftmark = true; int rightmark = true; if (NodeOp1(LeftChild(T)) == StmtOp) leftmark = ValidStmtOp(LeftChild(T)); else if (! IsNull(LeftChild(T))) { printf("Left child of StmtOp must be StmtOp or null.\n"); leftmark = false; } rightmark = ValidStmt(RightChild(T)); if (! rightmark) printf("Right child of StmtOp must be a statement or null.\n"); return(leftmark && rightmark); } ValidStmt(T) /*returns boolean*/ struct ILTree *T; { if (NodeOp1(T) == LoopOp) return(ValidLoopOp(T)); else if (NodeOp1(T) == IfElseOp) return(ValidIfElseOp(T)); else if (NodeOp1(T) == RoutineCallOp) return(ValidRoutineCallOp(T)); else if (NodeOp1(T) == AssignOp) return(ValidAssignOp(T)); else if (NodeOp1(T) == ReturnOp) return(ValidReturnOp(T)); else if (NodeOp1(T) == ExitOp) return(ValidExitOp(T)); else if (NodeOp1(T) == StmtOp) return(ValidStmtOp(T)); else if (NodeKind(T) == DUMMYNode) return(true); printf("A statment or null is expected.\n"); return(false); } /* ValidStmt */ ValidIfElseOp(T) /*returns boolean */ struct ILTree *T; { int leftmark = true; int rightmark = true; if (NodeOp1(LeftChild(T)) == IfElseOp) leftmark = ValidIfElse(LeftChild(T)); else { printf("Left child of first IfElseOp must be IfElseOp .\n"); leftmark = false; } if (NodeOp1(RightChild(T)) == StmtOp) rightmark = ValidStmtOp(RightChild(T)); else if (! IsNull(RightChild(T))) { printf("Right child of first IfElseOp must be StmtOp or null.\n"); rightmark = false; } return(leftmark && rightmark); } ValidIfElse(T) /*returns boolean*/ struct ILTree *T; { int leftmark = true; int rightmark = true; tree temp; if (NodeOp1(LeftChild(T)) == IfElseOp) leftmark = ValidIfElse(LeftChild(T)); else if (! IsNull(LeftChild(T))) { printf("Left child of IfElseOp must be IfElseOp or null.\n"); leftmark = false; } if (NodeOp1(RightChild(T)) != CommaOp) { printf("Right child of IfElseOp must be CommaOp.\n"); rightmark = false; } else { temp = RightChild(T); /* CommaOp */ rightmark = ValidExp(LeftChild(temp)); if (!rightmark) printf("Left child of CommaOp must be an expression.\n"); if (NodeOp1(RightChild(temp)) != StmtOp) { rightmark = false; printf("Right child of CommaOp must be StmtOp.\n"); } else rightmark = rightmark && ValidStmtOp(RightChild(temp)); } return(leftmark && rightmark); } ValidLoopOp(T) /*returns boolean*/ struct ILTree *T; { int leftmark = true; int rightmark = true; tree temp; /* for loop */ if (NodeOp1(LeftChild(T)) == CommaOp) { temp = LeftChild(T); if (NodeKind(LeftChild(temp)) != IDNode) { leftmark = false; printf("Left child of CommaOp in for-loop must be an IDNode.\n"); } if ((NodeOp1(RightChild(temp)) != ToOp) && (NodeOp1(RightChild(temp)) != DownToOp)) { leftmark = false; printf("Left child of CommaOp in for-loop must be either a ToOp"); printf(" or DownToOp node.\n"); } else leftmark = leftmark && ValidIterOp(RightChild(temp)); if (NodeOp1(RightChild(T)) != StmtOp) { rightmark = false; printf("Right child of For LoopOp must be StmtOp.\n"); } else rightmark = ValidStmtOp(RightChild(T)); return (leftmark && rightmark); } /* repeat loop */ if (NodeOp1(LeftChild(T)) == StmtOp) { leftmark = ValidStmtOp(LeftChild(T)); rightmark = ValidExp(RightChild(T)); if (! rightmark) printf("Right child of Repeat LoopOp must be an expression.\n"); return (leftmark && rightmark); } /* While loop */ leftmark = ValidExp(LeftChild(T)); if (! leftmark) printf("Left child of While LoopOp must be an expression.\n"); if (NodeOp1(RightChild(T)) != StmtOp) { rightmark = false; printf("Right child of For LoopOp must be StmtOp.\n"); } else rightmark = ValidStmtOp(RightChild(T)); return(leftmark && rightmark); } ValidIterOp(T) /*returns boolean*/ struct ILTree *T; { if (ValidExp(LeftChild(T)) && ValidExp(RightChild(T))) return(true); printf("Both children of ToOp or DownToOp must be expressions.\n"); return(false); } ValidReturnOp(T) struct ILTree *T; { int leftmark = true; int rightmark = true; if (! IsNull(RightChild(T))) { rightmark = false; printf("Right child of ReturnOp must be a null.\n"); } if (! IsNull(LeftChild(T))) { leftmark = ValidExp(LeftChild(T)); if (! leftmark) printf("Left child of ReturnOp must be an expression or null.\n"); } return (leftmark && rightmark); } ValidExitOp(T) struct ILTree *T; { int leftmark = true; int rightmark = true; if (! IsNull(RightChild(T))) { rightmark = false; printf("Right child of an ExitOp must be a null.\n"); } if (! IsNull(LeftChild(T))) { leftmark = false; printf("Left child of an ExitOp must be a null.\n"); } return (leftmark && rightmark); } ValidAssignOp(T) struct ILTree *T; { int leftmark = true; int rightmark = true; if(NodeOp1(LeftChild(T)) == AssignOp) leftmark = ValidAssign(LeftChild(T)); else { printf("Left child of topmost AssignOp must be AssignOp .\n"); leftmark = false; } rightmark = ValidExp(RightChild(T)); if (! rightmark) printf("Right child of topmost AssignOp must be an expression.\n"); return(leftmark && rightmark); } ValidAssign(T) struct ILTree *T; { int leftmark = true; int rightmark = true; if(NodeOp1(LeftChild(T)) == AssignOp) leftmark = ValidAssign(LeftChild(T)); else if (! IsNull(LeftChild(T))) { printf("Left child of AssignOp must be AssignOp or null.\n"); leftmark = false; } if (NodeOp1(RightChild(T)) == VarOp) rightmark = ValidVarOp(RightChild(T)); else { rightmark = false; printf("Right child of non-top AssignOp must be VarOp.\n"); } return (leftmark && rightmark); } ValidRoutineCallOp(T) /*returns boolean*/ struct ILTree *T; { int leftmark = true; int rightmark = true; if (NodeKind(LeftChild(T)) != IDNode) { leftmark = false; printf("Left child of RoutineCallOp must be an IDNode.\n"); } if (NodeOp1(RightChild(T)) == CommaOp) rightmark = ValidCommaInCall(RightChild(T)); else if(! IsNull(RightChild(T))) { printf("Right child of RoutineCallOp must be CommaOp or null.\n"); rightmark = false; } return(leftmark && rightmark); } ValidCommaInCall(T) struct ILTree *T; { int leftmark = true; int rightmark = true; leftmark = ValidExp(LeftChild(T)); if (! leftmark) printf("Left child of CommaOp in rountine call must be an expression.\n"); if (NodeOp1(RightChild(T)) == CommaOp) rightmark = ValidCommaInCall(RightChild(T)); else if (! IsNull(RightChild(T))) { printf("Right child of CommaOp in rountine call must be CommaOp or null.\n"); rightmark = false; } return(leftmark && rightmark); } ValidExp(T) /*returns boolean*/ struct ILTree *T; { int i; int mark = true; switch (NodeKind(T)) { case NUMNode: case STRINGNode: case CHARNode: return(true); case EXPRNode: if (((i=NodeOp1(T)) ==AddOp) || (i== SubOp) || (i==MultOp) || (i==DivOp) || (i==LTOp) || (i==GTOp) || (i==EQOp) || (i==AndOp) || (i==OrOp) || (i==LEOp) || (i==NEOp) || (i==GEOp)) if (ValidExp(LeftChild(T)) && ValidExp(RightChild(T))) return(true); else { printf("Both children of binop must be expressions.\n"); return(false); } else if ((i==UnaryNegOp) || (i==NotOp)) { if (! ValidExp(LeftChild(T))) { printf("Left child of unop must be an expression.\n"); mark = false; } if (! IsNull(RightChild(T))) { printf("Right child of unop must be a NullTree.\n"); mark = false; } return(mark); } else if (NodeOp1(T) == RoutineCallOp) return(ValidRoutineCallOp(T)); else if (NodeOp1(T) == VarOp) return(ValidVarOp(T)); else { printf("Expression expected, but found"); PrintStr(NodeOp1(T)); } break; default: printf("DummyNode and IdNode are invalid in expression.\n"); } return(false); } /* ValidExp */ ValidVarOp(T) struct ILTree *T; { int leftmark = true; int rightmark = true; if (NodeKind(LeftChild(T)) != IDNode) { printf("Left child of VarOp must be IDNode.\n"); leftmark = false; } if (NodeOp1(RightChild(T)) == SelectOp) rightmark = ValidSelectOp(RightChild(T)); else if (! IsNull(RightChild(T))) { printf("Right child of VarOp must be SelectOp or null.\n"); rightmark = false; } return(leftmark && rightmark); } ValidSelectOp(T) struct ILTree *T; { int leftmark = true; int rightmark = true; if (NodeOp1(LeftChild(T)) == IndexOp) leftmark = ValidIndexOp(LeftChild(T)); else if (NodeOp1(LeftChild(T)) == FieldOp) leftmark = ValidFieldOp(LeftChild(T)); else { printf("Left child of SelectOp must be FieldOp or IndexOp.\n"); leftmark = false; } if (NodeOp1(RightChild(T)) == SelectOp) rightmark = ValidSelectOp(RightChild(T)); else if (! IsNull(RightChild(T))) { printf("Right child of SelectOp must be SelectOp or null.\n"); rightmark = false; } return(leftmark && rightmark); } ValidIndexOp(T) struct ILTree *T; { int leftmark = true; int rightmark = true; leftmark = ValidExp(LeftChild(T)); if (! leftmark) printf("Left child of IndexOp must be an expression.\n"); if (NodeOp1(RightChild(T)) == IndexOp) rightmark = ValidIndexOp(RightChild(T)); else if (! IsNull(RightChild(T))) { printf("Right child of IndexOp must be IndexOp or null.\n"); rightmark = false; } return(leftmark && rightmark); } ValidFieldOp(T) struct ILTree *T; { int mark = true; if (NodeKind(LeftChild(T)) != IDNode) { printf("Left child of FieldOp must be an IDNode.\n"); mark = false; } if (NodeKind(RightChild(T)) != DUMMYNode) { printf("Right child of FieldOp must be a DUMMYNode.\n"); mark = false; } return(mark); }