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