2.9BSD - /usr/src/cmd/awk/b.c

   1: #include "awk.def"
   2: #include "stdio.h"
   3: #include "awk.h"
   4: 
   5: extern node *op2();
   6: extern struct fa *cgotofn();
   7: #define MAXLIN 256
   8: #define NCHARS 128
   9: #define NSTATES 256
  10: 
  11: #define type(v) v->nobj
  12: #define left(v) v->narg[0]
  13: #define right(v)    v->narg[1]
  14: #define parent(v)   v->nnext
  15: 
  16: #define LEAF    case CCL: case NCCL: case CHAR: case DOT:
  17: #define UNARY   case FINAL: case STAR: case PLUS: case QUEST:
  18: 
  19: /* encoding in tree nodes:
  20: 	leaf (CCL, NCCL, CHAR, DOT): left is index, right contains value or pointer to value
  21: 	unary (FINAL, STAR, PLUS, QUEST): left is child, right is null
  22: 	binary (CAT, OR): left and right are children
  23: 	parent contains pointer to parent
  24: */
  25: 
  26: struct fa {
  27:     int cch;
  28:     struct fa *st;
  29: };
  30: 
  31: int *state[NSTATES];
  32: int *foll[MAXLIN];
  33: char    chars[MAXLIN];
  34: int setvec[MAXLIN];
  35: node    *point[MAXLIN];
  36: 
  37: int setcnt;
  38: int line;
  39: 
  40: 
  41: struct fa *makedfa(p)   /* returns dfa for tree pointed to by p */
  42: node *p;
  43: {
  44:     node *p1;
  45:     struct fa *fap;
  46:     p1 = op2(CAT, op2(STAR, op2(DOT, (node *) 0, (node *) 0), (node *) 0), p);
  47:         /* put DOT STAR in front of reg. exp. */
  48:     p1 = op2(FINAL, p1, (node *) 0);        /* install FINAL node */
  49: 
  50:     line = 0;
  51:     penter(p1); /* enter parent pointers and leaf indices */
  52:     point[line] = p1;   /* FINAL node */
  53:     setvec[0] = 1;      /* for initial DOT STAR */
  54:     cfoll(p1);  /* set up follow sets */
  55:     fap = cgotofn();
  56:     freetr(p1); /* add this when alloc works */
  57:     return(fap);
  58: }
  59: 
  60: penter(p)   /* set up parent pointers and leaf indices */
  61: node *p;
  62: {
  63:     switch(type(p)) {
  64:         LEAF
  65:             left(p) = (node *) line;
  66:             point[line++] = p;
  67:             break;
  68:         UNARY
  69:             penter(left(p));
  70:             parent(left(p)) = p;
  71:             break;
  72:         case CAT:
  73:         case OR:
  74:             penter(left(p));
  75:             penter(right(p));
  76:             parent(left(p)) = p;
  77:             parent(right(p)) = p;
  78:             break;
  79:         default:
  80:             error(FATAL, "unknown type %d in penter\n", type(p));
  81:             break;
  82:     }
  83: }
  84: 
  85: freetr(p)   /* free parse tree and follow sets */
  86: node *p;
  87: {
  88:     switch(type(p)) {
  89:         LEAF
  90:             xfree(foll[(int) left(p)]);
  91:             xfree(p);
  92:             break;
  93:         UNARY
  94:             freetr(left(p));
  95:             xfree(p);
  96:             break;
  97:         case CAT:
  98:         case OR:
  99:             freetr(left(p));
 100:             freetr(right(p));
 101:             xfree(p);
 102:             break;
 103:         default:
 104:             error(FATAL, "unknown type %d in freetr", type(p));
 105:             break;
 106:     }
 107: }
 108: char *cclenter(p)
 109: register char *p;
 110: {
 111:     register i, c;
 112:     char *op;
 113: 
 114:     op = p;
 115:     i = 0;
 116:     while ((c = *p++) != 0) {
 117:         if (c == '-' && i > 0 && chars[i-1] != 0) {
 118:             if (*p != 0) {
 119:                 c = chars[i-1];
 120:                 while (c < *p) {
 121:                     if (i >= MAXLIN)
 122:                         overflo();
 123:                     chars[i++] = ++c;
 124:                 }
 125:                 p++;
 126:                 continue;
 127:             }
 128:         }
 129:         if (i >= MAXLIN)
 130:             overflo();
 131:         chars[i++] = c;
 132:     }
 133:     chars[i++] = '\0';
 134:     dprintf("cclenter: in = |%s|, out = |%s|\n", op, chars, NULL);
 135:     xfree(op);
 136:     return(tostring(chars));
 137: }
 138: 
 139: overflo()
 140: {
 141:     error(FATAL, "regular expression too long\n");
 142: }
 143: 
 144: cfoll(v)        /* enter follow set of each leaf of vertex v into foll[leaf] */
 145: register node *v;
 146: {
 147:     register i;
 148:     int prev;
 149:     int *add();
 150: 
 151:     switch(type(v)) {
 152:         LEAF
 153:             setcnt = 0;
 154:             for (i=1; i<=line; i++)
 155:                 setvec[i] = 0;
 156:             follow(v);
 157:             if (notin(foll, ( (int) left(v))-1, &prev)) {
 158:                 foll[(int) left(v)] = add(setcnt);
 159:             }
 160:             else
 161:                 foll[ (int) left(v)] = foll[prev];
 162:             break;
 163:         UNARY
 164:             cfoll(left(v));
 165:             break;
 166:         case CAT:
 167:         case OR:
 168:             cfoll(left(v));
 169:             cfoll(right(v));
 170:             break;
 171:         default:
 172:             error(FATAL, "unknown type %d in cfoll", type(v));
 173:     }
 174: }
 175: 
 176: first(p)            /* collects initially active leaves of p into setvec */
 177: register node *p;       /* returns 0 or 1 depending on whether p matches empty string */
 178: {
 179:     register b;
 180: 
 181:     switch(type(p)) {
 182:         LEAF
 183:             if (setvec[(int) left(p)] != 1) {
 184:                 setvec[(int) left(p)] = 1;
 185:                 setcnt++;
 186:             }
 187:             if (type(p) == CCL && (*(char *) right(p)) == '\0')
 188:                 return(0);      /* empty CCL */
 189:             else return(1);
 190:         case FINAL:
 191:         case PLUS:
 192:             if (first(left(p)) == 0) return(0);
 193:             return(1);
 194:         case STAR:
 195:         case QUEST:
 196:             first(left(p));
 197:             return(0);
 198:         case CAT:
 199:             if (first(left(p)) == 0 && first(right(p)) == 0) return(0);
 200:             return(1);
 201:         case OR:
 202:             b = first(right(p));
 203:             if (first(left(p)) == 0 || b == 0) return(0);
 204:             return(1);
 205:     }
 206:     error(FATAL, "unknown type %d in first\n", type(p));
 207:     return(-1);
 208: }
 209: 
 210: follow(v)
 211: node *v;        /* collects leaves that can follow v into setvec */
 212: {
 213:     node *p;
 214: 
 215:     if (type(v) == FINAL)
 216:         return;
 217:     p = parent(v);
 218:     switch (type(p)) {
 219:         case STAR:
 220:         case PLUS:  first(v);
 221:                 follow(p);
 222:                 return;
 223: 
 224:         case OR:
 225:         case QUEST: follow(p);
 226:                 return;
 227: 
 228:         case CAT:   if (v == left(p)) { /* v is left child of p */
 229:                     if (first(right(p)) == 0) {
 230:                         follow(p);
 231:                         return;
 232:                     }
 233:                 }
 234:                 else        /* v is right child */
 235:                     follow(p);
 236:                 return;
 237:         case FINAL: if (setvec[line] != 1) {
 238:                     setvec[line] = 1;
 239:                     setcnt++;
 240:                 }
 241:                 return;
 242:     }
 243: }
 244: 
 245: member(c, s)    /* is c in s? */
 246: register char c, *s;
 247: {
 248:     while (*s)
 249:         if (c == *s++)
 250:             return(1);
 251:     return(0);
 252: }
 253: 
 254: notin(array, n, prev)       /* is setvec in array[0] thru array[n]? */
 255: int **array;
 256: int *prev; {
 257:     register i, j;
 258:     int *ptr;
 259:     for (i=0; i<=n; i++) {
 260:         ptr = array[i];
 261:         if (*ptr == setcnt) {
 262:             for (j=0; j < setcnt; j++)
 263:                 if (setvec[*(++ptr)] != 1) goto nxt;
 264:             *prev = i;
 265:             return(0);
 266:         }
 267:         nxt: ;
 268:     }
 269:     return(1);
 270: }
 271: 
 272: int *add(n) {       /* remember setvec */
 273:     int *ptr, *p;
 274:     register i;
 275:     if ((p = ptr = (int *) malloc((n+1)*sizeof(int))) == NULL)
 276:         overflo();
 277:     *ptr = n;
 278:     dprintf("add(%d)\n", n, NULL, NULL);
 279:     for (i=1; i <= line; i++)
 280:         if (setvec[i] == 1) {
 281:             *(++ptr) = i;
 282:             dprintf("  ptr = %o, *ptr = %d, i = %d\n", ptr, *ptr, i);
 283:         }
 284:     dprintf("\n", NULL, NULL, NULL);
 285:     return(p);
 286: }
 287: 
 288: struct fa *cgotofn()
 289: {
 290:     register i, k;
 291:     register int *ptr;
 292:     char c;
 293:     char *p;
 294:     node *cp;
 295:     int j, n, s, ind, numtrans;
 296:     int finflg;
 297:     int curpos, num, prev;
 298:     struct fa *where[NSTATES];
 299: 
 300:     int fatab[257];
 301:     struct fa *pfa;
 302: 
 303:     char index[MAXLIN];
 304:     char iposns[MAXLIN];
 305:     int sposns[MAXLIN];
 306:     int spmax, spinit;
 307: 
 308:     char symbol[NCHARS];
 309:     char isyms[NCHARS];
 310:     char ssyms[NCHARS];
 311:     int ssmax, ssinit;
 312: 
 313:     for (i=0; i<=line; i++) index[i] = iposns[i] = setvec[i] = 0;
 314:     for (i=0; i<NCHARS; i++)  isyms[i] = symbol[i] = 0;
 315:     setcnt = 0;
 316:     /* compute initial positions and symbols of state 0 */
 317:     ssmax = 0;
 318:     ptr = state[0] = foll[0];
 319:     spinit = *ptr;
 320:     for (i=0; i<spinit; i++) {
 321:         curpos = *(++ptr);
 322:         sposns[i] = curpos;
 323:         iposns[curpos] = 1;
 324:         cp = point[curpos];
 325:         dprintf("i = %d, spinit = %d, curpos = %d\n", i, spinit, curpos);
 326:         switch (type(cp)) {
 327:             case CHAR:
 328:                 k = (int) right(cp);
 329:                 if (isyms[k] != 1) {
 330:                     isyms[k] = 1;
 331:                     ssyms[ssmax++] = k;
 332:                 }
 333:                 break;
 334:             case DOT:
 335:                 for (k=1; k<NCHARS; k++) {
 336:                     if (k != HAT) {
 337:                         if (isyms[k] != 1) {
 338:                             isyms[k] = 1;
 339:                             ssyms[ssmax++] = k;
 340:                         }
 341:                     }
 342:                 }
 343:                 break;
 344:             case CCL:
 345:                 for (p = (char *) right(cp); *p; p++) {
 346:                     if (*p != HAT) {
 347:                         if (isyms[*p] != 1) {
 348:                             isyms[*p] = 1;
 349:                             ssyms[ssmax++] = *p;
 350:                         }
 351:                     }
 352:                 }
 353:                 break;
 354:             case NCCL:
 355:                 for (k=1; k<NCHARS; k++) {
 356:                     if (k != HAT && !member(k, (char *) right(cp))) {
 357:                         if (isyms[k] != 1) {
 358:                             isyms[k] = 1;
 359:                             ssyms[ssmax++] = k;
 360:                         }
 361:                     }
 362:                 }
 363:         }
 364:     }
 365:     ssinit = ssmax;
 366:     n = 0;
 367:     for (s=0; s<=n; s++)  {
 368:     dprintf("s = %d\n", s, NULL, NULL);
 369:         ind = 0;
 370:         numtrans = 0;
 371:         finflg = 0;
 372:         if (*(state[s] + *state[s]) == line) {      /* s final? */
 373:             finflg = 1;
 374:             goto tenter;
 375:         }
 376:         spmax = spinit;
 377:         ssmax = ssinit;
 378:         ptr = state[s];
 379:         num = *ptr;
 380:         for (i=0; i<num; i++) {
 381:             curpos = *(++ptr);
 382:             if (iposns[curpos] != 1 && index[curpos] != 1) {
 383:                 index[curpos] = 1;
 384:                 sposns[spmax++] = curpos;
 385:             }
 386:             cp = point[curpos];
 387:             switch (type(cp)) {
 388:                 case CHAR:
 389:                     k = (int) right(cp);
 390:                     if (isyms[k] == 0 && symbol[k] == 0) {
 391:                         symbol[k] = 1;
 392:                         ssyms[ssmax++] = k;
 393:                     }
 394:                     break;
 395:                 case DOT:
 396:                     for (k=1; k<NCHARS; k++) {
 397:                         if (k != HAT) {
 398:                             if (isyms[k] == 0 && symbol[k] == 0) {
 399:                                 symbol[k] = 1;
 400:                                 ssyms[ssmax++] = k;
 401:                             }
 402:                         }
 403:                     }
 404:                     break;
 405:                 case CCL:
 406:                     for (p = (char *) right(cp); *p; p++) {
 407:                         if (*p != HAT) {
 408:                             if (isyms[*p] == 0 && symbol[*p] == 0) {
 409:                                 symbol[*p] = 1;
 410:                                 ssyms[ssmax++] = *p;
 411:                             }
 412:                         }
 413:                     }
 414:                     break;
 415:                 case NCCL:
 416:                     for (k=1; k<NCHARS; k++) {
 417:                         if (k != HAT && !member(k, (char *) right(cp))) {
 418:                             if (isyms[k] == 0 && symbol[k] == 0) {
 419:                                 symbol[k] = 1;
 420:                                 ssyms[ssmax++] = k;
 421:                             }
 422:                         }
 423:                     }
 424:             }
 425:         }
 426:         for (j=0; j<ssmax; j++) {   /* nextstate(s, ssyms[j]) */
 427:             c = ssyms[j];
 428:             symbol[c] = 0;
 429:             setcnt = 0;
 430:             for (k=0; k<=line; k++) setvec[k] = 0;
 431:             for (i=0; i<spmax; i++) {
 432:                 index[sposns[i]] = 0;
 433:                 cp = point[sposns[i]];
 434:                 if ((k = type(cp)) != FINAL)
 435:                     if (k == CHAR && c == (int) right(cp)
 436:                      || k == DOT
 437:                      || k == CCL && member(c, (char *) right(cp))
 438:                      || k == NCCL && !member(c, (char *) right(cp))) {
 439:                         ptr = foll[sposns[i]];
 440:                         num = *ptr;
 441:                         for (k=0; k<num; k++) {
 442:                             if (setvec[*(++ptr)] != 1
 443:                                 && iposns[*ptr] != 1) {
 444:                                 setvec[*ptr] = 1;
 445:                                 setcnt++;
 446:                             }
 447:                         }
 448:                     }
 449:             } /* end nextstate */
 450:             if (notin(state, n, &prev)) {
 451:                 if (n >= NSTATES) {
 452:                     dprintf("cgotofn: notin; state = %d, n = %d\n", state, n, NULL);
 453:                     overflo();
 454:                 }
 455:                 state[++n] = add(setcnt);
 456:                 dprintf("	delta(%d,%o) = %d", s,c,n);
 457:                 dprintf(", ind = %d\n", ind+1, NULL, NULL);
 458:                 fatab[++ind] = c;
 459:                 fatab[++ind] = n;
 460:                 numtrans++;
 461:             }
 462:             else {
 463:                 if (prev != 0) {
 464:                     dprintf("	delta(%d,%o) = %d", s,c,prev);
 465:                     dprintf(", ind = %d\n", ind+1, NULL, NULL);
 466:                     fatab[++ind] = c;
 467:                     fatab[++ind] = prev;
 468:                     numtrans++;
 469:                 }
 470:             }
 471:         }
 472:     tenter:
 473:         if ((pfa = (struct fa *) malloc((numtrans + 1) * sizeof(struct fa))) == NULL)
 474:             overflo();
 475:         where[s] = pfa;
 476:         if (finflg)
 477:             pfa->cch = -1;      /* s is a final state */
 478:         else
 479:             pfa->cch = numtrans;
 480:         pfa->st = 0;
 481:         for (i=1, pfa += 1; i<=numtrans; i++, pfa++) {
 482:             pfa->cch = fatab[2*i-1];
 483:             pfa->st = (struct fa *) fatab[2*i];
 484:         }
 485:     }
 486:     for (i=0; i<=n; i++) {
 487:         xfree(state[i]);    /* free state[i] */
 488:         pfa = where[i];
 489:         pfa->st = where[0];
 490:         dprintf("state %d: (%o)\n", i, pfa, NULL);
 491:         dprintf("	numtrans = %d,	default = %o\n", pfa->cch, pfa->st, NULL);
 492:         for (k=1; k<=pfa->cch; k++) {
 493:             (pfa+k)->st = where[ (int) (pfa+k)->st];
 494:             dprintf("	char = %o,	nextstate = %o\n",(pfa+k)->cch, (pfa+k)->st, NULL);
 495:         }
 496:     }
 497:     pfa = where[0];
 498:     if ((num = pfa->cch) < 0)
 499:         return(where[0]);
 500:     for (pfa += num; num; num--, pfa--)
 501:         if (pfa->cch == HAT) {
 502:             return(pfa->st);
 503:         }
 504:     return(where[0]);
 505: }
 506: 
 507: match(pfa, p)
 508: register struct fa *pfa;
 509: register char *p;
 510: {
 511:     register count;
 512:     char c;
 513:     if (p == 0) return(0);
 514:     if (pfa->cch == 1) {        /* fast test for first character, if possible */
 515:         c = (++pfa)->cch;
 516:         do
 517:             if (c == *p) {
 518:                 p++;
 519:                 pfa = pfa->st;
 520:                 goto adv;
 521:             }
 522:         while (*p++ != 0);
 523:         return(0);
 524:     }
 525:    adv: if ((count = pfa->cch) < 0) return(1);
 526:     do {
 527:         for (pfa += count; count; count--, pfa--)
 528:             if (pfa->cch == *p) {
 529:                 break;
 530:             }
 531:         pfa = pfa->st;
 532:         if ((count = pfa->cch) < 0) return(1);
 533:     } while(*p++ != 0);
 534:     return(0);
 535: }

Defined functions

Defined variables

Defined struct's

Defined macros