4.3BSD - /usr/src/new/spms/src/lib/libspms/src/pdtparse.c

   1: /* $Header$ */
   2: 
   3: /*
   4:  * Author: Peter J. Nicklin
   5:  */
   6: 
   7: /*
   8:  * pdtparse() translates an infix project directory boolean type label
   9:  * expression to postfix, using operator-precedence parsing. An adjacency
  10:  * matrix augments the parsing method by detecting tokens that must not
  11:  * be adjacent to one another. Returns NO if syntax error or out of memory,
  12:  * otherwise YES.
  13:  *
  14:  * The maximum size of the input stack used by the parser determines the
  15:  * size of the postfix expression evaluation stack.
  16:  */
  17: #include "null.h"
  18: #include "macro.h"
  19: #include "pdtyp.h"
  20: #include "truefalse.h"
  21: #include "yesno.h"
  22: 
  23: #define INCRISTAK   20      /* amount to increase input stack */
  24: #define MAXISTAK    20      /* initial size of input stack */
  25: #define INCRPEXP    40      /* amount to increase postfix expr */
  26: #define MAXPEXP     40      /* initial size of postfix expr */
  27: #define TOKTABSIZE  256     /* token lookup table size */
  28: 
  29: static char *type;          /* current type label */
  30: static int intok;           /* current input token */
  31: static int typlen;          /* length of current type label */
  32: static short *istak;            /* boolean expression input stack */
  33: static short toktab[TOKTABSIZE];    /* token lookup table */
  34: 
  35: static short opr[7][7] =        /* operator precedence relations */
  36:     {
  37:     /*id   !    &    |    (    )    B_EOS	*/
  38:     { 0 ,  0 , '>', '>',  0 , '>', '>'},    /* id */
  39:     {'<',  0 , '>', '>', '<', '>', '>'},    /* ! */
  40:     {'<', '<', '>', '>', '<', '>', '>'},    /* & */
  41:     {'<', '<', '<', '>', '<', '>', '>'},    /* | */
  42:     {'<', '<', '<', '<', '<', '=',  0 },    /* ( */
  43:     { 0 ,  0 , '>', '>',  0 , '>', '>'},    /* ) */
  44:     {'<', '<', '<', '<', '<',  0 ,  0 },    /* B_EOS */
  45:     };
  46: 
  47: static short adj[7][7] =        /* token adjacency matrix */
  48:     {
  49:     /*id   !    &    |    (    )    B_EOS	*/
  50:     { NO,  NO, YES, YES,  NO, YES, YES},    /* id */
  51:     {YES,  NO,  NO,  NO, YES,  NO,  NO},    /* ! */
  52:     {YES, YES,  NO,  NO, YES,  NO,  NO},    /* & */
  53:     {YES, YES,  NO,  NO, YES,  NO,  NO},    /* | */
  54:     {YES, YES,  NO,  NO, YES,  NO,  NO},    /* ( */
  55:     { NO,  NO, YES, YES,  NO, YES, YES},    /* ) */
  56:     {YES, YES,  NO,  NO, YES,  NO,  NO},    /* B_EOS */
  57:     };
  58: 
  59: pdtparse(typexpr, postfix)
  60:     char *typexpr;          /* boolean type expression */
  61:     PDTYP *postfix;         /* postfix expression struct */
  62: {
  63:     register int lastok;        /* previous input token */
  64:     register int maxestak;      /* maximum size of evaluation stack */
  65:     register int poptok;        /* token most recently popped */
  66:     register int pp;        /* postfix expression pointer */
  67:     register int toi;       /* top-of-input-stack pointer */
  68:     register int toitok;        /* topmost token on stack */
  69:     char *getnextok();      /* get next type expression token */
  70:     char *malloc();         /* memory allocator */
  71:     char *realloc();        /* reallocate memory block */
  72:     int maxistak;           /* maximum size of input stack */
  73:     int maxpexp;            /* maximum size of postfix expression */
  74: 
  75:     /* initialize token lookup table */
  76:     toktab['\0'] = B_EOS;
  77:     toktab['\t'] = B_WHITE;
  78:     toktab[' '] = B_WHITE;
  79:     toktab['&'] = B_AND;
  80:     toktab['|'] = B_OR;
  81:     toktab['!'] = B_NOT;
  82:     toktab['('] = B_LPAREN;
  83:     toktab[')'] = B_RPAREN;
  84:     /* the rest of the lookup table is B_ID which is 0 */
  85: 
  86:     /* initialize boolean type expression input stack */
  87:     maxistak = MAXISTAK;
  88:     if ((istak = (short *) malloc((unsigned)maxistak*sizeof(short))) == NULL)
  89:         goto nomemory;
  90:     maxestak = toi = 0;
  91:     istak[toi] = B_EOS;
  92: 
  93:     /* initialize postfix type expression */
  94:     maxpexp = MAXPEXP;
  95:     if ((postfix->pfx = (POSTFIX *) malloc((unsigned)maxpexp*sizeof(POSTFIX))) == NULL)
  96:         goto nomemory;
  97:     pp = 0;
  98: 
  99:     /* get first token */
 100:     lastok = B_EOS;
 101:     typexpr = getnextok(typexpr);
 102:     if (adj[lastok][intok] == NO)
 103:         goto badsyntax;
 104: 
 105:     while (TRUE)
 106:         {
 107:         if (toi == 0 && intok == B_EOS)
 108:             break;  /* ACCEPT */
 109:         toitok = istak[toi];
 110:         if (opr[toitok][intok] == '<' || opr[toitok][intok] == '=')
 111:             { /* SHIFT current input token onto the stack */
 112:             toi++;
 113:             maxestak = MAX(maxestak, toi);
 114:             if (toi >= maxistak)
 115:                 { /* increase input stack size */
 116:                 maxistak += INCRISTAK;
 117:                 if ((istak = (short *) realloc((char *)istak,
 118:                      (unsigned)maxistak*sizeof(short))) == NULL)
 119:                     goto nomemory;
 120:                 }
 121:             istak[toi] = lastok = intok;
 122:             typexpr = getnextok(typexpr);
 123:             if (adj[lastok][intok] == NO)
 124:                 goto badsyntax;
 125:             }
 126:         else if (opr[toitok][intok] == '>')
 127:             do  { /* REDUCE */
 128:                 if (pp >= maxpexp)
 129:                     { /* increase postfix expression size */
 130:                     maxpexp += INCRPEXP;
 131:                     if ((postfix->pfx = (POSTFIX *)
 132:                          realloc((char *)postfix->pfx,
 133:                              (unsigned)maxpexp*sizeof(POSTFIX))) == NULL)
 134:                         goto nomemory;
 135:                     }
 136:                 switch (toitok)
 137:                     {
 138:                     case B_ID:
 139:                         type[typlen] = '\0';
 140:                         (postfix->pfx)[pp].p_id = type;
 141:                     case B_AND:
 142:                     case B_OR:
 143:                     case B_NOT:
 144:                         (postfix->pfx)[pp].p_class = toitok;
 145:                         pp++;
 146:                         break;
 147:                     }
 148:                 toi--;
 149:                 poptok = toitok;
 150:                 toitok = istak[toi];
 151:                 } while (opr[toitok][poptok] != '<');
 152:         else    {
 153:             goto badsyntax;
 154:             }
 155:         }
 156:     free((char *)istak);
 157:     if ((postfix->eval = (short *) malloc((unsigned)(maxestak+1)*sizeof(short))) == NULL)
 158:         goto nomemory;
 159:     postfix->pfxsize = pp;
 160:     return(YES);
 161: badsyntax:
 162:     warn("type expression syntax error");
 163:     free((char *) istak);
 164:     free((char *) postfix->pfx);
 165:     return(NO);
 166: nomemory:
 167:     warn("out of memory");
 168:     return(NO);
 169: }
 170: 
 171: 
 172: 
 173: /*
 174:  * getnextok() identifies the next token in the boolean type expression
 175:  * and returns an updated pointer to the expression. `type' points to
 176:  * the current type label in the boolean expression.
 177:  */
 178: static char *
 179: getnextok(t)
 180:     register char *t;       /* current pointer to type expr */
 181: {
 182:     register int i;         /* type label buffer index */
 183: 
 184:     while (WHITESPACE(*t))
 185:         t++;
 186:     intok = toktab[*t];
 187:     if (intok == B_ID)
 188:         {
 189:         type = t;
 190:         for (i = 0; toktab[*t] == B_ID; i++, t++)
 191:             continue;
 192:         typlen = i;
 193:         }
 194:     else if (intok != B_EOS)
 195:         {
 196:         t++;
 197:         }
 198:     return(t);
 199: }

Defined functions

Defined variables

Defined macros