![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to eg.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / gre|
Return to eg.c CVS log | Up to [Research Unix] / researchv10no / cmd / gre |
1.1 ! root 1: #include "re.h" ! 2: #include "lre.h" ! 3: #include "hdr.h" ! 4: ! 5: int re_debug = 0; ! 6: ! 7: #define RESET(r, ps) COPY(r, ps, begin) ! 8: #define SET(r, ps, n) {if(r->ps.base[n] == 0) r->ps.count++, r->ps.base[n] = r->ps.last, r->ps.last = n; } ! 9: #define GET(ps, n) for(n = ps.last; n > 0; n = ps.base[n]) ! 10: #define COPY(r, to, from) memmove((char *)r->to.base, (char *)r->from.base, r->maxid*sizeof(int)), r->to.count = r->from.count, r->to.last = r->from.last ! 11: ! 12: static State *addstate(re_re *r, Positionset *ps); ! 13: static int first(re_re *, Expr *); ! 14: static int match(re_re *, Expr *, int); ! 15: static State *nextstate(re_re *, State *, int); ! 16: #ifdef DEBUG ! 17: static void ppr(Positionset *, char *); ! 18: #endif ! 19: ! 20: typedef enum { NORMAL, ACCEPT, ACCEPT_EOP, FAIL } Out; ! 21: ! 22: static void ! 23: eptr(register re_re *r, register Expr *e) ! 24: { ! 25: if((e->id < 0) || (e->id >= r->maxid)){ ! 26: EPR "eptr abort: r=%ld[maxid=%d] e=%ld[id=%d]\n", r, r->maxid, e, e->id); ! 27: abort(); ! 28: } ! 29: r->ptr[e->id] = e; ! 30: if((e->type != Charclass) && (e->type != Compcharclass)){ ! 31: if(e->l) ! 32: eptr(r, e->l); ! 33: if(e->r) ! 34: eptr(r, e->r); ! 35: } ! 36: } ! 37: ! 38: re_re * ! 39: egprep(enum Parsetype parser, unsigned char *b, unsigned char *e, unsigned char *map, int dotstar) ! 40: { ! 41: register re_re *r; ! 42: Expr *ecomp; ! 43: int i; ! 44: ! 45: r = (re_re *)egmalloc(sizeof (re_re), "allocating re_re"); ! 46: if(r == 0) ! 47: return 0; ! 48: memset((char *)r, 0, sizeof (re_re)); ! 49: eg_lexinit((char *)b, (char *)e); ! 50: if(map) ! 51: memmove(r->mymap, (char *)map, 256); ! 52: else ! 53: for(i = 0; i < 256; i++) ! 54: r->mymap[i] = i; ! 55: eg_lex(); ! 56: if(dotstar){ ! 57: ecomp = eg_newexpr(Star, 0, eg_newexpr(Dot, '.', (Expr *)0, (Expr *)0), (Expr *)0); ! 58: ecomp = eg_newexpr(Cat, 0, ecomp, eg_eall(parser, r->mymap)); ! 59: } else ! 60: ecomp = eg_eall(parser, r->mymap); ! 61: r->root = eg_newexpr(EOP, '#', ecomp, (Expr *)0); ! 62: egpost(r); ! 63: r->carat = 0; ! 64: if(r->backref || r->parens) ! 65: egbr(r); ! 66: else ! 67: eginit(r, dotstar); ! 68: return(r); ! 69: } ! 70: ! 71: void ! 72: eginit(register re_re *r, int dotstar) ! 73: { ! 74: int n; ! 75: ! 76: #ifdef DEBUG ! 77: if(TRACE(6)) ! 78: PR "eginit(r=%d, dotstar=%d)\n", r, dotstar); ! 79: #endif ! 80: #ifdef DEBUG ! 81: if(TRACE(10)){ ! 82: char buf[EPRINTSIZE]; ! 83: eg_epr(r->root, buf, 0); ! 84: PR "eginit: r=%d expr='%s'\n", r, buf); ! 85: } ! 86: #endif ! 87: r->ptr = (Expr **)egmalloc(r->maxid*sizeof(Expr *), "ptr"); ! 88: if (!r->ptr) ! 89: return; ! 90: eptr(r, r->root); ! 91: r->firstpos.base = (int *)egmalloc(n = r->maxid*sizeof(int), "first base"); ! 92: if (!r->firstpos.base){ ! 93: free((char*)r->ptr); ! 94: return; ! 95: } ! 96: r->begin.base = (int *)egmalloc(n, "begin base"); ! 97: if (!r->begin.base){ ! 98: free((char*)r->firstpos.base); ! 99: free((char*)r->ptr); ! 100: return; ! 101: } ! 102: r->tmp.base = (int *)egmalloc(n, "tmp base"); ! 103: if (!r->tmp.base){ ! 104: free((char*)r->begin.base); ! 105: free((char*)r->firstpos.base); ! 106: free((char*)r->ptr); ! 107: return; ! 108: } ! 109: memset((char *)r->begin.base, 0, n); ! 110: r->begin.count = 0; ! 111: r->begin.last = -1; ! 112: r->carat = dotstar; ! 113: RESET(r, firstpos); ! 114: if(first(r, r->root->l) == 0){ ! 115: /* ! 116: nullable, so include me ! 117: */ ! 118: SET(r, firstpos, r->root->id) ! 119: } ! 120: if(dotstar) ! 121: COPY(r, begin, firstpos); ! 122: eg_stateinit(r); ! 123: eg_clrstates(r); ! 124: eg_posinit(r); ! 125: (void)addstate(r, &r->firstpos); ! 126: eg_savestate(r, dotstar? nextstate(r, r->states, RE_CARAT):r->states); ! 127: eg_posset(r); ! 128: } ! 129: ! 130: unsigned char * ! 131: eg_quickmatch(register re_re *r, register unsigned char *b, register unsigned char *e, int endpts) ! 132: { ! 133: register State *s, *t; ! 134: ! 135: #ifdef DEBUG ! 136: if(TRACE(10)){ ! 137: char buf[EPRINTSIZE]; ! 138: eg_epr(r->root, buf, 0); ! 139: PR "qm: r=%d expr='%s' endpts=%d\n", r, buf, endpts); ! 140: } ! 141: #endif ! 142: s = eg_startstate(r); ! 143: if(endpts&RE_BEG){ ! 144: if(!r->carat){ ! 145: if(t = s->tab[RE_CARAT]) ! 146: s = t; ! 147: else ! 148: s = nextstate(r, s, RE_CARAT); ! 149: if(s->out == FAIL) ! 150: s = eg_startstate(r); ! 151: } ! 152: if(s->out){ ! 153: #ifdef DEBUG ! 154: if(TRACE(6)) ! 155: PR "match at ^: '%s' out=%d\n", b, s->out); ! 156: #endif ! 157: return((s->out == FAIL)? 0:b); ! 158: } ! 159: } ! 160: while(b < e){ ! 161: #ifdef DEBUG ! 162: if(TRACE(4)) ! 163: PR "state %d@%d[%d pos]: char '%c'\n", s-r->states, (int)s, s->npos, *b); ! 164: #endif ! 165: if(t = s->tab[*(unsigned char *)b]) ! 166: s = t; ! 167: else ! 168: s = nextstate(r, s, *(unsigned char *)b); ! 169: if(s->out){ ! 170: #ifdef DEBUG ! 171: if(TRACE(6)) ! 172: PR "match at input '%s' out=%d\n", b, s->out); ! 173: #endif ! 174: return((s->out == FAIL)? 0:b); ! 175: } ! 176: b++; ! 177: } ! 178: if(endpts&RE_END){ ! 179: if(t = s->tab[RE_DOLLAR]) ! 180: s = t; ! 181: else ! 182: s = nextstate(r, s, RE_DOLLAR); ! 183: } ! 184: if(s->out){ ! 185: #ifdef DEBUG ! 186: if(TRACE(6)) ! 187: PR "match at $ '%s' out=%d\n", b, s->out); ! 188: #endif ! 189: return((s->out == FAIL)? 0:b); ! 190: } ! 191: #ifdef DEBUG ! 192: if(TRACE(3)){ ! 193: char buf[EPRINTSIZE]; ! 194: ! 195: eg_epr(r->root, buf, 1); ! 196: PR "pat = %s\n", buf); ! 197: } ! 198: #endif ! 199: return(0); ! 200: } ! 201: ! 202: unsigned char * ! 203: eg_lquickmatch(register re_re *r, register unsigned char *b, register unsigned char *e, int endpts) ! 204: { ! 205: register State *s, *t; ! 206: int outedness = 0; ! 207: ! 208: #ifdef DEBUG ! 209: if(TRACE(10)){ ! 210: char buf[EPRINTSIZE]; ! 211: eg_epr(r->root, buf, 0); ! 212: PR "lqm: r=%d carat=%d expr='%s' endpts=%d\n", r, r->carat, buf, endpts); ! 213: } ! 214: #endif ! 215: s = eg_startstate(r); ! 216: if(endpts&RE_BEG){ ! 217: if(!r->carat){ ! 218: if(t = s->tab[RE_CARAT]) ! 219: s = t; ! 220: else ! 221: s = nextstate(r, s, RE_CARAT); ! 222: if(s->out == FAIL) ! 223: s = eg_startstate(r); ! 224: } ! 225: if(s->out){ ! 226: #ifdef DEBUG ! 227: if(TRACE(6)) ! 228: PR "match at ^: '%s' out=%d\n", b, s->out); ! 229: #endif ! 230: if(s->out == ACCEPT_EOP) ! 231: return(b); ! 232: else if(s->out == FAIL) ! 233: return(0); ! 234: outedness = 1; ! 235: } ! 236: } ! 237: /* ! 238: look for first match ! 239: */ ! 240: if(outedness == 0) ! 241: for(; b < e; b++){ ! 242: #ifdef DEBUG ! 243: if(TRACE(4)) ! 244: PR "state %d@%d[%d pos]: char '%c'\n", s-r->states, (int)s, s->npos, *b); ! 245: #endif ! 246: if(t = s->tab[*(unsigned char *)b]) ! 247: s = t; ! 248: else ! 249: s = nextstate(r, s, *(unsigned char *)b); ! 250: if(s->out){ ! 251: #ifdef DEBUG ! 252: if(TRACE(4)) ! 253: PR " out=%d, state %d@%d\n", s->out, ! 254: s-r->states, (int)s); ! 255: #endif ! 256: b++; ! 257: if((s->out == ACCEPT_EOP) || (s->out == FAIL)) ! 258: goto finish; ! 259: outedness = 1; ! 260: break; ! 261: } ! 262: } ! 263: /* ! 264: in the following loop, we have seen a match already ! 265: because only way outedness is zero is if b>=e ! 266: */ ! 267: for(; b < e; b++){ ! 268: #ifdef DEBUG ! 269: if(TRACE(4)) ! 270: PR "statex %d@%d[%d pos]: char '%c'\n", s-r->states, (int)s, s->npos, *b); ! 271: #endif ! 272: if(t = s->tab[*(unsigned char *)b]) ! 273: s = t; ! 274: else ! 275: s = nextstate(r, s, *(unsigned char *)b); ! 276: if(s->out == ACCEPT) ! 277: continue; ! 278: if((s->out == NORMAL) || (s->out == FAIL)){ ! 279: #ifdef DEBUG ! 280: if(TRACE(6)) ! 281: PR "unmatch at input '%s' out=%d\n", b, s->out); ! 282: #endif ! 283: return(b); ! 284: } ! 285: } ! 286: if(endpts&RE_END){ ! 287: if(t = s->tab[RE_DOLLAR]) ! 288: s = t; ! 289: else ! 290: s = nextstate(r, s, RE_DOLLAR); ! 291: } ! 292: finish: ! 293: if((s->out && (s->out != FAIL)) || outedness){ ! 294: #ifdef DEBUG ! 295: if(TRACE(6)) ! 296: PR "match at $ '%s' out=%d\n", b, s->out); ! 297: #endif ! 298: return(b); ! 299: } ! 300: #ifdef DEBUG ! 301: if(TRACE(3)){ ! 302: char buf[EPRINTSIZE]; ! 303: ! 304: eg_epr(r->root, buf, 1); ! 305: PR "lqm('%s') failed; out=%d, s->out=%d \n", buf, outedness, s->out); ! 306: } ! 307: #endif ! 308: return(0); ! 309: } ! 310: ! 311: static ! 312: match(register re_re *r, register Expr *e, int a) ! 313: { ! 314: switch(e->type) ! 315: { ! 316: case Dollar: return(a == RE_DOLLAR); ! 317: case Carat: return(a == RE_CARAT); ! 318: case Dot: return(a < 256); ! 319: case Literal: return(r->mymap[a] == r->mymap[e->lit]); ! 320: case Charclass: if(a >= 256) return(0); ! 321: return(memchr((char *)e->r, r->mymap[a], (int)e->l) != 0); ! 322: case Compcharclass: ! 323: if(a >= 256) return(0); ! 324: return(memchr((char *)e->r, r->mymap[a], (int)e->l) == 0); ! 325: } ! 326: return(0); ! 327: } ! 328: ! 329: /* ! 330: generates the followset for a node in firstpos ! 331: */ ! 332: ! 333: static void ! 334: follow(register re_re *r, register Expr *e) ! 335: { ! 336: register Expr *p; ! 337: ! 338: if(e->type == EOP) ! 339: return; ! 340: else ! 341: p = e->parent; ! 342: switch(p->type) ! 343: { ! 344: case EOP: ! 345: SET(r, firstpos, p->id) ! 346: break; ! 347: case Plus: ! 348: case Star: ! 349: (void)first(r, e); ! 350: follow(r, p); ! 351: break; ! 352: case Quest: ! 353: case Alternate: ! 354: follow(r, p); ! 355: break; ! 356: case Cat: ! 357: if(e == p->l){ ! 358: if(first(r, p->r) == 0){ ! 359: follow(r, p); ! 360: break; ! 361: } ! 362: } else ! 363: follow(r, p); ! 364: break; ! 365: case Group: ! 366: follow(r, p); ! 367: break; ! 368: } ! 369: } ! 370: ! 371: /* ! 372: first returns 0 if e is nullable and in the process, ! 373: sets up firstpos. ! 374: */ ! 375: ! 376: static ! 377: first(register re_re *r, register Expr *e) ! 378: { ! 379: int k; ! 380: ! 381: switch(e->type) ! 382: { ! 383: case Carat: ! 384: case Dollar: ! 385: case Literal: ! 386: case Dot: ! 387: case Charclass: ! 388: case Compcharclass: ! 389: SET(r, firstpos, e->id) ! 390: return(1); ! 391: case EOP: ! 392: case Star: ! 393: case Quest: ! 394: (void)first(r, e->l); ! 395: return(0); ! 396: case Group: ! 397: case Plus: ! 398: return(first(r, e->l)); ! 399: case Cat: ! 400: return(first(r, e->l) || first(r, e->r)); ! 401: case Alternate: ! 402: k = first(r, e->r); ! 403: return(first(r, e->l) && k); ! 404: default: ! 405: EPR "bad type %d\n", e->type); ! 406: abort(); ! 407: return(0); ! 408: } ! 409: } ! 410: ! 411: static void ! 412: efollow(register re_re *r, register Expr *e) ! 413: { ! 414: register i, *p; ! 415: ! 416: RESET(r, firstpos); ! 417: follow(r, e); ! 418: e->flen = r->firstpos.count; ! 419: e->follow = (int *)malloc((unsigned)(e->flen*sizeof(int))); ! 420: if(e->follow == 0){ ! 421: char buf[100]; ! 422: SPR buf, "efollow malloc fail(%ld)\n", e->flen); ! 423: re_error(buf); ! 424: return; ! 425: } ! 426: p = e->follow; ! 427: GET(r->firstpos, i) ! 428: *p++ = i; ! 429: if(p != e->follow+e->flen){ ! 430: char buf[100]; ! 431: SPR buf, "efollow length error: %d %ld\n", p-e->follow, e->flen); ! 432: re_error(buf); ! 433: return; ! 434: } ! 435: } ! 436: ! 437: static State * ! 438: addstate(register re_re *r, register Positionset *ps) ! 439: { ! 440: register *p, j; ! 441: register State *s; ! 442: ! 443: s = r->states + eg_getstate(r); ! 444: memset((char *)s->tab, 0, sizeof(s->tab)); ! 445: s->pos = eg_posalloc(r, (int)ps->count); ! 446: s->npos = ps->count; ! 447: p = r->posbase+s->pos; ! 448: GET((*ps), j) ! 449: *p++ = j; ! 450: if(s->out = (ps->base[r->root->id] != 0)){ ! 451: if((ps->base[r->root->id] <= 0) && (ps->last == r->root->id)) ! 452: s->out = ACCEPT_EOP; /* marker for only the EOP marker */ ! 453: else ! 454: s->out = ACCEPT; ! 455: } ! 456: if(s->npos == 0) ! 457: s->out = FAIL; ! 458: #ifdef DEBUG ! 459: if(TRACE(3)){ ! 460: char buf[2000]; ! 461: eg_spr(s->npos, s->pos+r->posbase, buf); ! 462: PR "new state[%d]@%d %s,pos=%d out=%d\n", s-r->states, s, buf, s->pos, s->out); ! 463: } ! 464: #endif ! 465: return(s); ! 466: } ! 467: ! 468: static State * ! 469: nextstate(register re_re *r, register State *s, int a) ! 470: { ! 471: register int p, *q, *eq; ! 472: register long i; ! 473: State *news; ! 474: Expr *e; ! 475: ! 476: RESET(r, tmp); ! 477: #ifdef DEBUG ! 478: if(TRACE(5)){ ! 479: char buf[2000]; ! 480: ppr(&r->tmp, buf); ! 481: PR "nextstate: reset: %s\n", buf); ! 482: } ! 483: #endif ! 484: for(i = s->npos, p = s->pos; i > 0; i--){ ! 485: e = r->ptr[r->posbase[p++]]; ! 486: #ifdef DEBUG ! 487: if(TRACE(11)){ ! 488: PR "i=%d e->type=%d\n", i, e->type); ! 489: } ! 490: #endif ! 491: if(e->type == EOP) continue; ! 492: if(match(r, e, a)){ ! 493: #ifdef DEBUG ! 494: if(TRACE(11)){PR "matched %c\n", a);} ! 495: #endif ! 496: if(e->follow == 0) ! 497: efollow(r, e); ! 498: for(q = e->follow, eq = q+e->flen; q < eq; q++){ ! 499: SET(r, tmp, *q) ! 500: } ! 501: } ! 502: } ! 503: #ifdef DEBUG ! 504: if(TRACE(5)){ ! 505: char buf[2000]; ! 506: ppr(&r->tmp, buf); ! 507: PR "nextstate(%d, '%c'): found %s\n", s-r->states, a, buf); ! 508: } ! 509: #endif ! 510: if(news = eg_stateof(r, &r->tmp)){ ! 511: if(a <= RE_DOLLAR) ! 512: s->tab[a] = news; ! 513: } else ! 514: news = addstate(r, &r->tmp); ! 515: #ifdef DEBUG ! 516: if(TRACE(5)){ ! 517: PR "nextstate(%d, '%c'): returning %ld %d out=%d\n", s-r->states, a, ! 518: (long)news, news-r->states, news->out); ! 519: } ! 520: #endif ! 521: return(news); ! 522: } ! 523: ! 524: void * ! 525: egmalloc(int n, char *s) ! 526: { ! 527: char *x; ! 528: char buf[256]; ! 529: ! 530: if((x = malloc(n)) == 0){ ! 531: SPR buf, "malloc fail(%d): %s", n, s); ! 532: re_error(buf); ! 533: return 0; ! 534: } ! 535: return((void *)x); ! 536: } ! 537: ! 538: void * ! 539: egrealloc(char *p, int n, char *s) ! 540: { ! 541: char *x; ! 542: char buf[256]; ! 543: ! 544: if((x = realloc(p, n)) == 0){ ! 545: SPR buf, "realloc fail(%d): %s", n, s); ! 546: re_error(buf); ! 547: return 0; ! 548: } ! 549: return((void *)x); ! 550: } ! 551: ! 552: #ifdef DEBUG ! 553: static void ! 554: ppr(register Positionset *ps, register char *p) ! 555: { ! 556: register n; ! 557: ! 558: if(ps->count < 1){ ! 559: SPR p, "{}"); ! 560: return; ! 561: } ! 562: *p++ = '{'; ! 563: GET((*ps), n){ ! 564: SPR p, "%d[=%d],", n, ps->base[n]); ! 565: p = strchr(p, 0); ! 566: } ! 567: p[-1] = '}'; ! 568: } ! 569: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.