/*********************************************************/ /* proj2.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. */ /* define syntax tree node and pointer type */ typedef struct treenode { /* syntax tree node struct */ int NodeKind, NodeOpType, IntVal; struct treenode *LeftC, *RightC; } ILTree, *tree; tree Root; #define ProgramOp 100 #define BodyOp 101 #define DeclOp 102 #define CommaOp 103 #define ArrayTypeOp 104 #define TypeIdOp 105 #define BoundOp 106 #define RecompOp 107 #define ToOp 108 #define DownToOp 109 #define ConstantIdOp 110 #define ProceOp 111 #define FuncOp 112 #define HeadOp 113 #define RArgTypeOp 114 #define VArgTypeOp 115 #define StmtOp 116 #define IfElseOp 117 #define LoopOp 118 #define SpecOp 119 #define RoutineCallOp 120 #define AssignOp 121 #define ReturnOp 122 #define AddOp 123 #define SubOp 124 #define MultOp 125 #define DivOp 126 #define LTOp 127 #define GTOp 128 #define EQOp 129 #define NEOp 130 #define LEOp 131 #define GEOp 132 #define AndOp 133 #define OrOp 134 #define UnaryNegOp 135 #define NotOp 136 #define VarOp 137 #define SelectOp 138 #define IndexOp 139 #define FieldOp 140 #define SubrangeOp 141 #define ExitOp 142 #define IDNode 200 #define NUMNode 201 #define CHARNode 202 #define STRINGNode 203 #define DUMMYNode 204 #define EXPRNode 205 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); } /* CopyTree */ tree CopyTree(T) tree T; { tree p; if (T==NullExp()) return(NullExp()); p = (ILTree *) malloc(sizeof(ILTree)); if (p == NULL) { printf("malloc failed.\n"); exit(0); } p->NodeKind = T->NodeKind; p->IntVal= T->IntVal; p->NodeOpType = T->NodeOpType; p->LeftC = CopyTree(T->LeftC); p->RightC= CopyTree(T->RightC); return(p); } /*********************************************************** * This function will create a leafnode with it * * NodeKind and IntVal to be Kind and N, respectively * ***********************************************************/ tree MakeLeaf(Kind, N) int Kind, N; { tree p; p = (tree)malloc(sizeof(ILTree)); p->NodeKind = Kind; 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->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 * ********************************************************/ 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 * ********************************************************/ NodeKind(T) tree T; { return (T->NodeKind); } /******************************************************** * This function returns IntVal of a leafnode * ********************************************************/ 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. * ********************************************************/ IsNull(T) tree T; { return ( NodeKind(T) == DUMMYNode ); } /******************************************************** * This function sets the Target Node to be * * Source Node (only for Non Dummy Target Node) * ********************************************************/ void 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; } } /******************************************************** * This function sets the NodeOpType to be * * to be NewOp (only for Interior EXPRNode) * ********************************************************/ void SetNodeOp(T, Op) tree T; int Op; { if (NodeKind(T) != EXPRNode) printf("SetNodeOp(): This node must be an EXPRNode!\n"); else T->NodeOpType = Op; } /******************************************************** * 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 * ********************************************************/ void SetLeftTreeOp(T, Op) tree T; int Op; { tree p; p = T; do { SetNodeOp(p, Op); p = LeftChild(p); } while ( !IsNull(p)); } /******************************************************** * 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 * ********************************************************/ void SetRightTreeOp(T, Op) tree T; int Op; { tree p; p = T; do { SetNodeOp(p, Op); p = RightChild(p); } while ( !IsNull(p)); } /**************************************************************** * This function sets the LeftChild of T to be NewC * ****************************************************************/ void SetLeftChild(T, NewC) tree T, NewC; { if (NodeKind(T) != EXPRNode) printf("SetLeftChild(): This node must be an EXPRNode!\n"); else T->LeftC = NewC; } /**************************************************************** * This function sets the RightChild of T to be NewC * ****************************************************************/ void SetRightChild(T, NewC) tree T, NewC; { if (NodeKind(T) != EXPRNode) printf("SetRightChild(): This node must be an EXPRNode!\n"); else T->RightC = NewC; } /*****************************************************************/ /* 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 char string_buff[20000]; char * getname(index) int index; { return (string_buff+ index);} char *getstring(index) int index; { return (string_buff + index); } #include 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 [1000]; 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 < 1000; 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; 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 */ #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); }