1 #ifndef lint 2 static char sccsid[] = "@(#)tree.c 4.3 (Berkeley) 07/22/88"; 3 #endif not lint 4 5 # include "y.tab.h" 6 #include "b.h" 7 #include <stdio.h> 8 9 extern char *malloc(); 10 11 struct node * 12 addroot(string,type,n1,n2) 13 char *string; 14 int type; 15 struct node *n1, *n2; 16 { 17 struct node *p; 18 p = (struct node *)malloc(sizeof(*p)); 19 p->left = n1; 20 p->right = n2; 21 p->op = type; 22 p->lit = malloc(slength(string) + 1); 23 str_copy(string,p->lit,slength(string) + 1); 24 return(p); 25 } 26 27 28 freetree(tree) 29 struct node *tree; 30 { 31 if (tree) 32 {freetree(tree->left); 33 freetree(tree->right); 34 freenode(tree); 35 } 36 } 37 38 freenode(treenode) 39 struct node *treenode; 40 { 41 free(treenode->lit); 42 free(treenode); 43 } 44 45 int compop[] = { '&', '|', '<', '>', xxeq, xxle, xxne, xxge}; 46 int notop[] = { '|', '&', xxge, xxle, xxne, '>', xxeq, '<'}; 47 char *opstring[] = { "||", "&&", ">=", "<=", "!=", ">", "==", "<"}; 48 49 struct node * 50 checkneg(tree,neg) /* eliminate nots if possible */ 51 struct node *tree; 52 int neg; 53 { 54 int i; 55 struct node *t; 56 if (!tree) return(0); 57 for (i = 0; i < 8; ++i) 58 if (tree->op == compop[i]) break; 59 if (i > 1 && i < 8 && tree ->left ->op == '-' && str_eq(tree->right->lit,"0")) 60 { 61 t = tree->right; 62 tree->right = tree->left->right; 63 freenode(t); 64 t = tree->left; 65 tree->left = tree->left->left; 66 freenode(t); 67 } 68 69 70 if (neg) 71 { 72 if (tree ->op == '!') 73 { 74 t = tree->left; 75 freenode(tree); 76 return(checkneg(t,0)); 77 } 78 if (i < 8) 79 { 80 tree->op = notop[i]; 81 free(tree->lit); 82 tree->lit = malloc(slength(opstring[i])+1); 83 str_copy(opstring[i],tree->lit, slength(opstring[i])+1); 84 if (tree->op == '&' || tree->op == '|') 85 { 86 tree->left = checkneg(tree->left,1); 87 tree->right = checkneg(tree->right,1); 88 } 89 return(tree); 90 } 91 if (tree->op == xxident && str_eq(tree->lit,".false.")) 92 str_copy(".true.",tree->lit, slength(".true.")+1); 93 else if (tree->op == xxident && str_eq(tree->lit,".true.")) 94 { 95 free(tree->lit); 96 tree->lit = malloc(slength(".false.")+1); 97 str_copy(".false.",tree->lit, slength(".false.")+1); 98 } 99 else 100 { 101 tree = addroot("!",'!',tree,0); 102 tree->lit = malloc(2); 103 str_copy("!",tree->lit, slength("!")+1); 104 } 105 return(tree); 106 } 107 else 108 if (tree->op == '!') 109 { 110 t = tree; 111 tree = tree->left; 112 freenode(t); 113 return(checkneg(tree,1)); 114 } 115 else 116 {tree->left = checkneg(tree->left,0); 117 tree->right = checkneg(tree->right,0); 118 return(tree); 119 } 120 } 121 122 yield(tree,fprec) 123 struct node *tree; 124 int fprec; /* fprec is precedence of father of this node */ 125 { 126 int paren,p; 127 static int oplast; /* oplast = 1 iff last char printed was operator */ 128 if (!tree) return; 129 p = prec(tree ->op); 130 paren = (p < fprec || (oplast && tree->op == xxuminus)) ? 1 : 0; 131 132 if (paren) 133 { 134 putout('(',"("); 135 oplast = 0; 136 } 137 138 switch(tree->op) 139 { 140 case xxuminus: 141 tree->op = '-'; 142 case '!': 143 putout(tree->op,tree->lit); 144 oplast = 1; 145 yield(tree->left,p); 146 break; 147 case '&': 148 case '|': 149 case '<': 150 case '>': 151 case xxeq: 152 case xxle: 153 case xxge: 154 case '+': 155 case '-': 156 case '*': 157 case '/': 158 case '^': 159 yield(tree->left,p); 160 putout(tree->op, tree->lit); 161 oplast = 1; 162 yield(tree->right,p); 163 break; 164 case xxidpar: 165 yield(tree->left,0); 166 putout('(',"("); 167 oplast = 0; 168 yield(tree->right,0); 169 putout('(',")"); 170 oplast = 0; 171 break; 172 default: 173 yield(tree->left,p); 174 putout(tree->op, tree->lit); 175 oplast = 0; 176 yield(tree->right,p); 177 break; 178 } 179 if (paren) 180 { 181 putout(')',")"); 182 oplast = 0; 183 } 184 } 185 186 puttree(tree) 187 struct node *tree; 188 { 189 yield(tree,0); 190 freetree(tree); 191 } 192 193 194 prec(oper) 195 int oper; 196 { 197 switch(oper) 198 { 199 case ',': return(0); 200 case '|': return(1); 201 case '&': return(2); 202 case '!': return(3); 203 204 case '<': case '>': case xxeq: 205 case xxne: case xxle: case xxge: 206 return(4); 207 case '+': 208 case '-': return(5); 209 case '*': 210 case '/': return(6); 211 case xxuminus: return(7); 212 case '^': return(8); 213 default: return(9); 214 } 215 } 216 str_copy(s,ptr,length) /* copy s at ptr, return length of s */ 217 char *s, *ptr; 218 int length; 219 {int i; 220 for (i = 0; i < length; i++) 221 { 222 ptr[i] = s[i]; 223 if (ptr[i] == '\0') 224 return(i + 1); 225 } 226 fprintf(2,"string %s too long to be copied by str_copy at address %d\n", 227 *s,ptr); 228 exit(1); 229 } 230 str_eq(s,t) 231 char s[],t[]; 232 {int j; 233 for (j = 0; s[j] == t[j]; j++) 234 {if (s[j] == '\0') return(1);} 235 return(0); 236 } 237 238 slength(s) /* return number of chars in s, not counting '\0' */ 239 char *s; 240 { 241 int i; 242 if (!s) return(-1); 243 for (i = 0; s[i] != '\0'; i++); 244 return(i); 245 } 246