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