2.11BSD#431 - /usr/src/usr.bin/struct/tree.c

   1: #ifndef lint
   2: static char sccsid[] = "@(#)tree.c	4.1	(Berkeley)	2/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 = (struct node *)malloc(sizeof(*p));
  17:     p->left = n1;
  18:     p->right = n2;
  19:     p->op = type;
  20:     p->lit = (char *)malloc(slength(string) + 1);
  21:     str_copy(string,p->lit,slength(string) + 1);
  22:     return((int)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 = (char *)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 = (char *)malloc(slength(".false.")+1);
  95:             str_copy(".false.",tree->lit, slength(".false.")+1);
  96:             }
  97:         else
  98:             {
  99:             tree = (struct node *)addroot("!",'!',tree,0);
 100:             tree->lit = (char *)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:     }

Defined functions

Defined variables