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