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