2.9BSD - /usr/src/cmd/struct/tree.c

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

Defined functions

Defined variables