4.3BSD - /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 = 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:     }

Defined functions

Defined variables