Annotation of src/usr.bin/awk/b.c, Revision 1.15
1.15 ! millert 1: /* $OpenBSD: b.c,v 1.14 2007/09/02 15:19:31 deraadt Exp $ */
1.1 tholo 2: /****************************************************************
1.5 kstailey 3: Copyright (C) Lucent Technologies 1997
1.1 tholo 4: All Rights Reserved
5:
6: Permission to use, copy, modify, and distribute this software and
7: its documentation for any purpose and without fee is hereby
8: granted, provided that the above copyright notice appear in all
9: copies and that both that the copyright notice and this
10: permission notice and warranty disclaimer appear in supporting
1.5 kstailey 11: documentation, and that the name Lucent Technologies or any of
12: its entities not be used in advertising or publicity pertaining
13: to distribution of the software without specific, written prior
14: permission.
15:
16: LUCENT DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
17: INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
18: IN NO EVENT SHALL LUCENT OR ANY OF ITS ENTITIES BE LIABLE FOR ANY
19: SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
20: WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER
21: IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
22: ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
23: THIS SOFTWARE.
1.1 tholo 24: ****************************************************************/
25:
1.15 ! millert 26: /* lasciate ogne speranza, voi ch'intrate. */
1.1 tholo 27:
28: #define DEBUG
29:
30: #include <ctype.h>
31: #include <stdio.h>
32: #include <string.h>
33: #include <stdlib.h>
34: #include "awk.h"
1.5 kstailey 35: #include "ytab.h"
1.1 tholo 36:
1.12 millert 37: #define HAT (NCHARS+2) /* matches ^ in regular expr */
1.1 tholo 38: /* NCHARS is 2**n */
39: #define MAXLIN 22
40:
1.7 millert 41: #define type(v) (v)->nobj /* badly overloaded here */
42: #define info(v) (v)->ntype /* badly overloaded here */
1.1 tholo 43: #define left(v) (v)->narg[0]
44: #define right(v) (v)->narg[1]
45: #define parent(v) (v)->nnext
46:
47: #define LEAF case CCL: case NCCL: case CHAR: case DOT: case FINAL: case ALL:
1.15 ! millert 48: #define ELEAF case EMPTYRE: /* empty string in regexp */
1.1 tholo 49: #define UNARY case STAR: case PLUS: case QUEST:
50:
51: /* encoding in tree Nodes:
1.15 ! millert 52: leaf (CCL, NCCL, CHAR, DOT, FINAL, ALL, EMPTYRE):
1.1 tholo 53: left is index, right contains value or pointer to value
54: unary (STAR, PLUS, QUEST): left is child, right is null
55: binary (CAT, OR): left and right are children
56: parent contains pointer to parent
57: */
58:
59:
60: int *setvec;
61: int *tmpset;
62: int maxsetvec = 0;
63:
64: int rtok; /* next token in current re */
1.4 millert 65: int rlxval;
1.10 millert 66: static uschar *rlxstr;
67: static uschar *prestr; /* current position in current re */
68: static uschar *lastre; /* origin of last re */
1.1 tholo 69:
1.4 millert 70: static int setcnt;
71: static int poscnt;
1.1 tholo 72:
73: char *patbeg;
74: int patlen;
75:
76: #define NFA 20 /* cache this many dynamic fa's */
77: fa *fatab[NFA];
78: int nfatab = 0; /* entries in fatab */
79:
1.11 millert 80: fa *makedfa(const char *s, int anchor) /* returns dfa for reg expr s */
1.1 tholo 81: {
82: int i, use, nuse;
83: fa *pfa;
1.6 millert 84: static int now = 1;
1.1 tholo 85:
86: if (setvec == 0) { /* first time through any RE */
87: maxsetvec = MAXLIN;
1.14 deraadt 88: setvec = (int *) calloc(maxsetvec, sizeof(int));
89: tmpset = (int *) calloc(maxsetvec, sizeof(int));
1.1 tholo 90: if (setvec == 0 || tmpset == 0)
91: overflo("out of space initializing makedfa");
92: }
93:
94: if (compile_time) /* a constant for sure */
95: return mkdfa(s, anchor);
96: for (i = 0; i < nfatab; i++) /* is it there already? */
97: if (fatab[i]->anchor == anchor
1.11 millert 98: && strcmp((const char *) fatab[i]->restr, s) == 0) {
1.6 millert 99: fatab[i]->use = now++;
1.1 tholo 100: return fatab[i];
1.10 millert 101: }
1.1 tholo 102: pfa = mkdfa(s, anchor);
103: if (nfatab < NFA) { /* room for another */
104: fatab[nfatab] = pfa;
1.6 millert 105: fatab[nfatab]->use = now++;
1.1 tholo 106: nfatab++;
107: return pfa;
108: }
109: use = fatab[0]->use; /* replace least-recently used */
110: nuse = 0;
111: for (i = 1; i < nfatab; i++)
112: if (fatab[i]->use < use) {
113: use = fatab[i]->use;
114: nuse = i;
115: }
116: freefa(fatab[nuse]);
117: fatab[nuse] = pfa;
1.6 millert 118: pfa->use = now++;
1.1 tholo 119: return pfa;
120: }
121:
1.11 millert 122: fa *mkdfa(const char *s, int anchor) /* does the real work of making a dfa */
1.1 tholo 123: /* anchor = 1 for anchored matches, else 0 */
124: {
125: Node *p, *p1;
126: fa *f;
127:
128: p = reparse(s);
129: p1 = op2(CAT, op2(STAR, op2(ALL, NIL, NIL), NIL), p);
130: /* put ALL STAR in front of reg. exp. */
131: p1 = op2(CAT, p1, op2(FINAL, NIL, NIL));
132: /* put FINAL after reg. exp. */
133:
134: poscnt = 0;
135: penter(p1); /* enter parent pointers and leaf indices */
136: if ((f = (fa *) calloc(1, sizeof(fa) + poscnt*sizeof(rrow))) == NULL)
137: overflo("out of space for fa");
138: f->accept = poscnt-1; /* penter has computed number of positions in re */
139: cfoll(f, p1); /* set up follow sets */
140: freetr(p1);
1.13 pvalchev 141: if ((f->posns[0] = (int *) calloc(*(f->re[0].lfollow), sizeof(int))) == NULL)
1.1 tholo 142: overflo("out of space in makedfa");
1.4 millert 143: if ((f->posns[1] = (int *) calloc(1, sizeof(int))) == NULL)
1.1 tholo 144: overflo("out of space in makedfa");
145: *f->posns[1] = 0;
146: f->initstat = makeinit(f, anchor);
147: f->anchor = anchor;
1.10 millert 148: f->restr = (uschar *) tostring(s);
1.1 tholo 149: return f;
150: }
151:
152: int makeinit(fa *f, int anchor)
153: {
154: int i, k;
155:
156: f->curstat = 2;
157: f->out[2] = 0;
158: f->reset = 0;
159: k = *(f->re[0].lfollow);
160: xfree(f->posns[2]);
1.13 pvalchev 161: if ((f->posns[2] = (int *) calloc(k+1, sizeof(int))) == NULL)
1.1 tholo 162: overflo("out of space in makeinit");
163: for (i=0; i <= k; i++) {
164: (f->posns[2])[i] = (f->re[0].lfollow)[i];
165: }
166: if ((f->posns[2])[1] == f->accept)
167: f->out[2] = 1;
168: for (i=0; i < NCHARS; i++)
169: f->gototab[2][i] = 0;
170: f->curstat = cgoto(f, 2, HAT);
171: if (anchor) {
172: *f->posns[2] = k-1; /* leave out position 0 */
173: for (i=0; i < k; i++) {
174: (f->posns[0])[i] = (f->posns[2])[i];
175: }
176:
177: f->out[0] = f->out[2];
178: if (f->curstat != 2)
179: --(*f->posns[f->curstat]);
180: }
181: return f->curstat;
182: }
183:
184: void penter(Node *p) /* set up parent pointers and leaf indices */
185: {
186: switch (type(p)) {
1.15 ! millert 187: ELEAF
1.1 tholo 188: LEAF
1.7 millert 189: info(p) = poscnt;
1.1 tholo 190: poscnt++;
191: break;
192: UNARY
193: penter(left(p));
194: parent(left(p)) = p;
195: break;
196: case CAT:
197: case OR:
198: penter(left(p));
199: penter(right(p));
200: parent(left(p)) = p;
201: parent(right(p)) = p;
202: break;
203: default: /* can't happen */
1.8 millert 204: FATAL("can't happen: unknown type %d in penter", type(p));
1.1 tholo 205: break;
206: }
207: }
208:
209: void freetr(Node *p) /* free parse tree */
210: {
211: switch (type(p)) {
1.15 ! millert 212: ELEAF
1.1 tholo 213: LEAF
214: xfree(p);
215: break;
216: UNARY
217: freetr(left(p));
218: xfree(p);
219: break;
220: case CAT:
221: case OR:
222: freetr(left(p));
223: freetr(right(p));
224: xfree(p);
225: break;
226: default: /* can't happen */
1.8 millert 227: FATAL("can't happen: unknown type %d in freetr", type(p));
1.1 tholo 228: break;
229: }
230: }
231:
232: /* in the parsing of regular expressions, metacharacters like . have */
233: /* to be seen literally; \056 is not a metacharacter. */
234:
235: int hexstr(char **pp) /* find and eval hex string at pp, return new p */
1.2 millert 236: { /* only pick up one 8-bit byte (2 chars) */
1.10 millert 237: uschar *p;
1.1 tholo 238: int n = 0;
1.2 millert 239: int i;
1.1 tholo 240:
1.10 millert 241: for (i = 0, p = (uschar *) *pp; i < 2 && isxdigit(*p); i++, p++) {
1.1 tholo 242: if (isdigit(*p))
243: n = 16 * n + *p - '0';
244: else if (*p >= 'a' && *p <= 'f')
245: n = 16 * n + *p - 'a' + 10;
246: else if (*p >= 'A' && *p <= 'F')
247: n = 16 * n + *p - 'A' + 10;
248: }
1.10 millert 249: *pp = (char *) p;
1.1 tholo 250: return n;
251: }
252:
1.2 millert 253: #define isoctdigit(c) ((c) >= '0' && (c) <= '7') /* multiple use of arg */
1.1 tholo 254:
255: int quoted(char **pp) /* pick up next thing after a \\ */
256: /* and increment *pp */
257: {
258: char *p = *pp;
259: int c;
260:
261: if ((c = *p++) == 't')
262: c = '\t';
263: else if (c == 'n')
264: c = '\n';
265: else if (c == 'f')
266: c = '\f';
267: else if (c == 'r')
268: c = '\r';
269: else if (c == 'b')
270: c = '\b';
271: else if (c == '\\')
272: c = '\\';
273: else if (c == 'x') { /* hexadecimal goo follows */
274: c = hexstr(&p); /* this adds a null if number is invalid */
275: } else if (isoctdigit(c)) { /* \d \dd \ddd */
276: int n = c - '0';
277: if (isoctdigit(*p)) {
278: n = 8 * n + *p++ - '0';
279: if (isoctdigit(*p))
280: n = 8 * n + *p++ - '0';
281: }
282: c = n;
283: } /* else */
284: /* c = c; */
285: *pp = p;
286: return c;
287: }
288:
1.11 millert 289: char *cclenter(const char *argp) /* add a character class */
1.1 tholo 290: {
291: int i, c, c2;
1.10 millert 292: uschar *p = (uschar *) argp;
293: uschar *op, *bp;
294: static uschar *buf = 0;
1.5 kstailey 295: static int bufsz = 100;
1.1 tholo 296:
297: op = p;
1.10 millert 298: if (buf == 0 && (buf = (uschar *) malloc(bufsz)) == NULL)
1.8 millert 299: FATAL("out of space for character class [%.10s...] 1", p);
1.5 kstailey 300: bp = buf;
301: for (i = 0; (c = *p++) != 0; ) {
1.1 tholo 302: if (c == '\\') {
1.10 millert 303: c = quoted((char **) &p);
1.5 kstailey 304: } else if (c == '-' && i > 0 && bp[-1] != 0) {
1.1 tholo 305: if (*p != 0) {
1.5 kstailey 306: c = bp[-1];
1.1 tholo 307: c2 = *p++;
308: if (c2 == '\\')
1.10 millert 309: c2 = quoted((char **) &p);
1.1 tholo 310: if (c > c2) { /* empty; ignore */
1.5 kstailey 311: bp--;
1.1 tholo 312: i--;
313: continue;
314: }
315: while (c < c2) {
1.15 ! millert 316: if (!adjbuf((char **) &buf, &bufsz, bp-buf+2, 100, (char **) &bp, "cclenter1"))
1.8 millert 317: FATAL("out of space for character class [%.10s...] 2", p);
1.5 kstailey 318: *bp++ = ++c;
1.1 tholo 319: i++;
320: }
321: continue;
322: }
323: }
1.15 ! millert 324: if (!adjbuf((char **) &buf, &bufsz, bp-buf+2, 100, (char **) &bp, "cclenter2"))
1.8 millert 325: FATAL("out of space for character class [%.10s...] 3", p);
1.5 kstailey 326: *bp++ = c;
1.1 tholo 327: i++;
328: }
1.5 kstailey 329: *bp = 0;
330: dprintf( ("cclenter: in = |%s|, out = |%s|\n", op, buf) );
1.1 tholo 331: xfree(op);
1.10 millert 332: return (char *) tostring((char *) buf);
1.1 tholo 333: }
334:
1.11 millert 335: void overflo(const char *s)
1.1 tholo 336: {
1.8 millert 337: FATAL("regular expression too big: %.30s...", s);
1.1 tholo 338: }
339:
340: void cfoll(fa *f, Node *v) /* enter follow set of each leaf of vertex v into lfollow[leaf] */
341: {
342: int i;
1.4 millert 343: int *p;
1.1 tholo 344:
345: switch (type(v)) {
1.15 ! millert 346: ELEAF
1.1 tholo 347: LEAF
1.7 millert 348: f->re[info(v)].ltype = type(v);
349: f->re[info(v)].lval.np = right(v);
1.1 tholo 350: while (f->accept >= maxsetvec) { /* guessing here! */
351: maxsetvec *= 4;
352: setvec = (int *) realloc(setvec, maxsetvec * sizeof(int));
353: tmpset = (int *) realloc(tmpset, maxsetvec * sizeof(int));
1.5 kstailey 354: if (setvec == 0 || tmpset == 0)
1.1 tholo 355: overflo("out of space in cfoll()");
356: }
357: for (i = 0; i <= f->accept; i++)
358: setvec[i] = 0;
359: setcnt = 0;
360: follow(v); /* computes setvec and setcnt */
1.13 pvalchev 361: if ((p = (int *) calloc(setcnt+1, sizeof(int))) == NULL)
1.1 tholo 362: overflo("out of space building follow set");
1.7 millert 363: f->re[info(v)].lfollow = p;
1.1 tholo 364: *p = setcnt;
365: for (i = f->accept; i >= 0; i--)
366: if (setvec[i] == 1)
367: *++p = i;
368: break;
369: UNARY
370: cfoll(f,left(v));
371: break;
372: case CAT:
373: case OR:
374: cfoll(f,left(v));
375: cfoll(f,right(v));
376: break;
377: default: /* can't happen */
1.8 millert 378: FATAL("can't happen: unknown type %d in cfoll", type(v));
1.1 tholo 379: }
380: }
381:
382: int first(Node *p) /* collects initially active leaves of p into setvec */
1.15 ! millert 383: /* returns 0 if p matches empty string */
1.1 tholo 384: {
1.4 millert 385: int b, lp;
1.1 tholo 386:
387: switch (type(p)) {
1.15 ! millert 388: ELEAF
1.1 tholo 389: LEAF
1.7 millert 390: lp = info(p); /* look for high-water mark of subscripts */
1.1 tholo 391: while (setcnt >= maxsetvec || lp >= maxsetvec) { /* guessing here! */
392: maxsetvec *= 4;
393: setvec = (int *) realloc(setvec, maxsetvec * sizeof(int));
394: tmpset = (int *) realloc(tmpset, maxsetvec * sizeof(int));
1.7 millert 395: if (setvec == 0 || tmpset == 0)
1.1 tholo 396: overflo("out of space in first()");
397: }
1.15 ! millert 398: if (type(p) == EMPTYRE) {
! 399: setvec[lp] = 0;
! 400: return(0);
! 401: }
1.1 tholo 402: if (setvec[lp] != 1) {
403: setvec[lp] = 1;
404: setcnt++;
405: }
406: if (type(p) == CCL && (*(char *) right(p)) == '\0')
407: return(0); /* empty CCL */
408: else return(1);
409: case PLUS:
410: if (first(left(p)) == 0) return(0);
411: return(1);
412: case STAR:
413: case QUEST:
414: first(left(p));
415: return(0);
416: case CAT:
417: if (first(left(p)) == 0 && first(right(p)) == 0) return(0);
418: return(1);
419: case OR:
420: b = first(right(p));
421: if (first(left(p)) == 0 || b == 0) return(0);
422: return(1);
423: }
1.8 millert 424: FATAL("can't happen: unknown type %d in first", type(p)); /* can't happen */
1.1 tholo 425: return(-1);
426: }
427:
428: void follow(Node *v) /* collects leaves that can follow v into setvec */
429: {
430: Node *p;
431:
432: if (type(v) == FINAL)
433: return;
434: p = parent(v);
435: switch (type(p)) {
436: case STAR:
437: case PLUS:
438: first(v);
439: follow(p);
440: return;
441:
442: case OR:
443: case QUEST:
444: follow(p);
445: return;
446:
447: case CAT:
448: if (v == left(p)) { /* v is left child of p */
449: if (first(right(p)) == 0) {
450: follow(p);
451: return;
452: }
453: } else /* v is right child */
454: follow(p);
455: return;
456: }
457: }
458:
1.11 millert 459: int member(int c, const char *sarg) /* is c in s? */
1.1 tholo 460: {
1.10 millert 461: uschar *s = (uschar *) sarg;
462:
1.1 tholo 463: while (*s)
464: if (c == *s++)
465: return(1);
466: return(0);
467: }
468:
1.11 millert 469: int match(fa *f, const char *p0) /* shortest match ? */
1.1 tholo 470: {
471: int s, ns;
472: uschar *p = (uschar *) p0;
473:
474: s = f->reset ? makeinit(f,0) : f->initstat;
475: if (f->out[s])
476: return(1);
477: do {
1.15 ! millert 478: /* assert(*p < NCHARS); */
1.1 tholo 479: if ((ns = f->gototab[s][*p]) != 0)
480: s = ns;
481: else
482: s = cgoto(f, s, *p);
483: if (f->out[s])
484: return(1);
485: } while (*p++ != 0);
486: return(0);
487: }
488:
1.11 millert 489: int pmatch(fa *f, const char *p0) /* longest match, for sub */
1.1 tholo 490: {
491: int s, ns;
492: uschar *p = (uschar *) p0;
493: uschar *q;
494: int i, k;
495:
1.12 millert 496: /* s = f->reset ? makeinit(f,1) : f->initstat; */
497: if (f->reset) {
498: f->initstat = s = makeinit(f,1);
499: } else {
500: s = f->initstat;
501: }
1.1 tholo 502: patbeg = (char *) p;
503: patlen = -1;
504: do {
505: q = p;
506: do {
507: if (f->out[s]) /* final state */
508: patlen = q-p;
1.15 ! millert 509: /* assert(*q < NCHARS); */
1.1 tholo 510: if ((ns = f->gototab[s][*q]) != 0)
511: s = ns;
512: else
513: s = cgoto(f, s, *q);
1.9 deraadt 514: if (s == 1) { /* no transition */
1.1 tholo 515: if (patlen >= 0) {
516: patbeg = (char *) p;
517: return(1);
518: }
519: else
520: goto nextin; /* no match */
1.9 deraadt 521: }
1.1 tholo 522: } while (*q++ != 0);
523: if (f->out[s])
524: patlen = q-p-1; /* don't count $ */
525: if (patlen >= 0) {
526: patbeg = (char *) p;
527: return(1);
528: }
529: nextin:
530: s = 2;
531: if (f->reset) {
532: for (i = 2; i <= f->curstat; i++)
533: xfree(f->posns[i]);
534: k = *f->posns[0];
1.13 pvalchev 535: if ((f->posns[2] = (int *) calloc(k+1, sizeof(int))) == NULL)
1.1 tholo 536: overflo("out of space in pmatch");
537: for (i = 0; i <= k; i++)
538: (f->posns[2])[i] = (f->posns[0])[i];
539: f->initstat = f->curstat = 2;
540: f->out[2] = f->out[0];
541: for (i = 0; i < NCHARS; i++)
542: f->gototab[2][i] = 0;
543: }
544: } while (*p++ != 0);
545: return (0);
546: }
547:
1.11 millert 548: int nematch(fa *f, const char *p0) /* non-empty match, for sub */
1.1 tholo 549: {
550: int s, ns;
551: uschar *p = (uschar *) p0;
552: uschar *q;
553: int i, k;
554:
1.12 millert 555: /* s = f->reset ? makeinit(f,1) : f->initstat; */
556: if (f->reset) {
557: f->initstat = s = makeinit(f,1);
558: } else {
559: s = f->initstat;
560: }
1.1 tholo 561: patlen = -1;
562: while (*p) {
563: q = p;
564: do {
565: if (f->out[s]) /* final state */
566: patlen = q-p;
1.15 ! millert 567: /* assert(*q < NCHARS); */
1.1 tholo 568: if ((ns = f->gototab[s][*q]) != 0)
569: s = ns;
570: else
571: s = cgoto(f, s, *q);
1.9 deraadt 572: if (s == 1) { /* no transition */
1.1 tholo 573: if (patlen > 0) {
574: patbeg = (char *) p;
575: return(1);
576: } else
577: goto nnextin; /* no nonempty match */
1.9 deraadt 578: }
1.1 tholo 579: } while (*q++ != 0);
580: if (f->out[s])
581: patlen = q-p-1; /* don't count $ */
582: if (patlen > 0 ) {
583: patbeg = (char *) p;
584: return(1);
585: }
586: nnextin:
587: s = 2;
588: if (f->reset) {
589: for (i = 2; i <= f->curstat; i++)
590: xfree(f->posns[i]);
591: k = *f->posns[0];
1.13 pvalchev 592: if ((f->posns[2] = (int *) calloc(k+1, sizeof(int))) == NULL)
1.1 tholo 593: overflo("out of state space");
594: for (i = 0; i <= k; i++)
595: (f->posns[2])[i] = (f->posns[0])[i];
596: f->initstat = f->curstat = 2;
597: f->out[2] = f->out[0];
598: for (i = 0; i < NCHARS; i++)
599: f->gototab[2][i] = 0;
600: }
601: p++;
602: }
603: return (0);
604: }
605:
1.11 millert 606: Node *reparse(const char *p) /* parses regular expression pointed to by p */
1.1 tholo 607: { /* uses relex() to scan regular expression */
608: Node *np;
609:
610: dprintf( ("reparse <%s>\n", p) );
1.10 millert 611: lastre = prestr = (uschar *) p; /* prestr points to string to be parsed */
1.1 tholo 612: rtok = relex();
1.11 millert 613: /* GNU compatibility: an empty regexp matches anything */
1.15 ! millert 614: if (rtok == '\0') {
1.11 millert 615: /* FATAL("empty regular expression"); previous */
1.15 ! millert 616: return(op2(EMPTYRE, NIL, NIL));
! 617: }
1.1 tholo 618: np = regexp();
619: if (rtok != '\0')
1.8 millert 620: FATAL("syntax error in regular expression %s at %s", lastre, prestr);
1.1 tholo 621: return(np);
622: }
623:
624: Node *regexp(void) /* top-level parse of reg expr */
625: {
626: return (alt(concat(primary())));
627: }
628:
629: Node *primary(void)
630: {
631: Node *np;
632:
633: switch (rtok) {
634: case CHAR:
1.7 millert 635: np = op2(CHAR, NIL, itonp(rlxval));
1.1 tholo 636: rtok = relex();
637: return (unary(np));
638: case ALL:
639: rtok = relex();
640: return (unary(op2(ALL, NIL, NIL)));
1.15 ! millert 641: case EMPTYRE:
! 642: rtok = relex();
! 643: return (unary(op2(ALL, NIL, NIL)));
1.1 tholo 644: case DOT:
645: rtok = relex();
646: return (unary(op2(DOT, NIL, NIL)));
647: case CCL:
1.10 millert 648: np = op2(CCL, NIL, (Node*) cclenter((char *) rlxstr));
1.1 tholo 649: rtok = relex();
650: return (unary(np));
651: case NCCL:
1.10 millert 652: np = op2(NCCL, NIL, (Node *) cclenter((char *) rlxstr));
1.1 tholo 653: rtok = relex();
654: return (unary(np));
655: case '^':
656: rtok = relex();
1.7 millert 657: return (unary(op2(CHAR, NIL, itonp(HAT))));
1.1 tholo 658: case '$':
659: rtok = relex();
660: return (unary(op2(CHAR, NIL, NIL)));
661: case '(':
662: rtok = relex();
663: if (rtok == ')') { /* special pleading for () */
664: rtok = relex();
665: return unary(op2(CCL, NIL, (Node *) tostring("")));
666: }
667: np = regexp();
668: if (rtok == ')') {
669: rtok = relex();
670: return (unary(np));
671: }
672: else
1.8 millert 673: FATAL("syntax error in regular expression %s at %s", lastre, prestr);
1.1 tholo 674: default:
1.8 millert 675: FATAL("illegal primary in regular expression %s at %s", lastre, prestr);
1.1 tholo 676: }
677: return 0; /*NOTREACHED*/
678: }
679:
680: Node *concat(Node *np)
681: {
682: switch (rtok) {
1.15 ! millert 683: case CHAR: case DOT: case ALL: case EMPTYRE: case CCL: case NCCL: case '$': case '(':
1.1 tholo 684: return (concat(op2(CAT, np, primary())));
685: }
686: return (np);
687: }
688:
689: Node *alt(Node *np)
690: {
691: if (rtok == OR) {
692: rtok = relex();
693: return (alt(op2(OR, np, concat(primary()))));
694: }
695: return (np);
696: }
697:
698: Node *unary(Node *np)
699: {
700: switch (rtok) {
701: case STAR:
702: rtok = relex();
703: return (unary(op2(STAR, np, NIL)));
704: case PLUS:
705: rtok = relex();
706: return (unary(op2(PLUS, np, NIL)));
707: case QUEST:
708: rtok = relex();
709: return (unary(op2(QUEST, np, NIL)));
710: default:
711: return (np);
712: }
713: }
714:
1.11 millert 715: /*
716: * Character class definitions conformant to the POSIX locale as
717: * defined in IEEE P1003.1 draft 7 of June 2001, assuming the source
718: * and operating character sets are both ASCII (ISO646) or supersets
719: * thereof.
720: *
721: * Note that to avoid overflowing the temporary buffer used in
722: * relex(), the expanded character class (prior to range expansion)
723: * must be less than twice the size of their full name.
724: */
1.12 millert 725:
726: /* Because isblank doesn't show up in any of the header files on any
727: * system i use, it's defined here. if some other locale has a richer
728: * definition of "blank", define HAS_ISBLANK and provide your own
729: * version.
730: * the parentheses here are an attempt to find a path through the maze
731: * of macro definition and/or function and/or version provided. thanks
732: * to nelson beebe for the suggestion; let's see if it works everywhere.
733: */
734:
735: #ifndef HAS_ISBLANK
736:
737: int (isblank)(int c)
738: {
739: return c==' ' || c=='\t';
740: }
741:
742: #endif
743:
1.11 millert 744: struct charclass {
745: const char *cc_name;
746: int cc_namelen;
1.12 millert 747: int (*cc_func)(int);
1.11 millert 748: } charclasses[] = {
1.12 millert 749: { "alnum", 5, isalnum },
750: { "alpha", 5, isalpha },
751: { "blank", 5, isblank },
752: { "cntrl", 5, iscntrl },
753: { "digit", 5, isdigit },
754: { "graph", 5, isgraph },
755: { "lower", 5, islower },
756: { "print", 5, isprint },
757: { "punct", 5, ispunct },
758: { "space", 5, isspace },
759: { "upper", 5, isupper },
760: { "xdigit", 6, isxdigit },
1.11 millert 761: { NULL, 0, NULL },
762: };
763:
764:
1.1 tholo 765: int relex(void) /* lexical analyzer for reparse */
766: {
1.5 kstailey 767: int c, n;
1.1 tholo 768: int cflag;
1.10 millert 769: static uschar *buf = 0;
1.5 kstailey 770: static int bufsz = 100;
1.10 millert 771: uschar *bp;
1.11 millert 772: struct charclass *cc;
1.12 millert 773: int i;
1.1 tholo 774:
775: switch (c = *prestr++) {
776: case '|': return OR;
777: case '*': return STAR;
778: case '+': return PLUS;
779: case '?': return QUEST;
780: case '.': return DOT;
781: case '\0': prestr--; return '\0';
782: case '^':
783: case '$':
784: case '(':
785: case ')':
786: return c;
787: case '\\':
1.10 millert 788: rlxval = quoted((char **) &prestr);
1.1 tholo 789: return CHAR;
790: default:
791: rlxval = c;
792: return CHAR;
793: case '[':
1.10 millert 794: if (buf == 0 && (buf = (uschar *) malloc(bufsz)) == NULL)
1.8 millert 795: FATAL("out of space in reg expr %.10s..", lastre);
1.5 kstailey 796: bp = buf;
1.1 tholo 797: if (*prestr == '^') {
798: cflag = 1;
799: prestr++;
800: }
801: else
802: cflag = 0;
1.11 millert 803: n = 2 * strlen((const char *) prestr)+1;
1.15 ! millert 804: if (!adjbuf((char **) &buf, &bufsz, n, n, (char **) &bp, "relex1"))
1.8 millert 805: FATAL("out of space for reg expr %.10s...", lastre);
1.1 tholo 806: for (; ; ) {
807: if ((c = *prestr++) == '\\') {
1.5 kstailey 808: *bp++ = '\\';
1.1 tholo 809: if ((c = *prestr++) == '\0')
1.8 millert 810: FATAL("nonterminated character class %.20s...", lastre);
1.5 kstailey 811: *bp++ = c;
1.10 millert 812: /* } else if (c == '\n') { */
813: /* FATAL("newline in character class %.20s...", lastre); */
1.11 millert 814: } else if (c == '[' && *prestr == ':') {
815: /* POSIX char class names, Dag-Erling Smorgrav, des@ofug.org */
816: for (cc = charclasses; cc->cc_name; cc++)
817: if (strncmp((const char *) prestr + 1, (const char *) cc->cc_name, cc->cc_namelen) == 0)
818: break;
819: if (cc->cc_name != NULL && prestr[1 + cc->cc_namelen] == ':' &&
820: prestr[2 + cc->cc_namelen] == ']') {
821: prestr += cc->cc_namelen + 3;
1.12 millert 822: for (i = 0; i < NCHARS; i++) {
1.15 ! millert 823: if (!adjbuf((char **) &buf, &bufsz, bp-buf+1, 100, (char **) &bp, "relex2"))
1.12 millert 824: FATAL("out of space for reg expr %.10s...", lastre);
825: if (cc->cc_func(i)) {
826: *bp++ = i;
827: n++;
828: }
829: }
1.11 millert 830: } else
831: *bp++ = c;
1.1 tholo 832: } else if (c == '\0') {
1.8 millert 833: FATAL("nonterminated character class %.20s", lastre);
1.5 kstailey 834: } else if (bp == buf) { /* 1st char is special */
835: *bp++ = c;
1.1 tholo 836: } else if (c == ']') {
1.5 kstailey 837: *bp++ = 0;
1.10 millert 838: rlxstr = (uschar *) tostring((char *) buf);
1.1 tholo 839: if (cflag == 0)
840: return CCL;
841: else
842: return NCCL;
843: } else
1.5 kstailey 844: *bp++ = c;
1.1 tholo 845: }
846: }
847: }
848:
849: int cgoto(fa *f, int s, int c)
850: {
851: int i, j, k;
1.4 millert 852: int *p, *q;
1.1 tholo 853:
1.12 millert 854: assert(c == HAT || c < NCHARS);
1.1 tholo 855: while (f->accept >= maxsetvec) { /* guessing here! */
856: maxsetvec *= 4;
857: setvec = (int *) realloc(setvec, maxsetvec * sizeof(int));
858: tmpset = (int *) realloc(tmpset, maxsetvec * sizeof(int));
1.7 millert 859: if (setvec == 0 || tmpset == 0)
1.1 tholo 860: overflo("out of space in cgoto()");
861: }
862: for (i = 0; i <= f->accept; i++)
863: setvec[i] = 0;
864: setcnt = 0;
865: /* compute positions of gototab[s,c] into setvec */
866: p = f->posns[s];
867: for (i = 1; i <= *p; i++) {
868: if ((k = f->re[p[i]].ltype) != FINAL) {
1.7 millert 869: if ((k == CHAR && c == ptoi(f->re[p[i]].lval.np))
1.1 tholo 870: || (k == DOT && c != 0 && c != HAT)
871: || (k == ALL && c != 0)
1.15 ! millert 872: || (k == EMPTYRE && c != 0)
1.10 millert 873: || (k == CCL && member(c, (char *) f->re[p[i]].lval.up))
874: || (k == NCCL && !member(c, (char *) f->re[p[i]].lval.up) && c != 0 && c != HAT)) {
1.1 tholo 875: q = f->re[p[i]].lfollow;
876: for (j = 1; j <= *q; j++) {
877: if (q[j] >= maxsetvec) {
878: maxsetvec *= 4;
879: setvec = (int *) realloc(setvec, maxsetvec * sizeof(int));
880: tmpset = (int *) realloc(setvec, maxsetvec * sizeof(int));
881: if (setvec == 0 || tmpset == 0)
882: overflo("cgoto overflow");
883: }
884: if (setvec[q[j]] == 0) {
885: setcnt++;
886: setvec[q[j]] = 1;
887: }
888: }
889: }
890: }
891: }
892: /* determine if setvec is a previous state */
893: tmpset[0] = setcnt;
894: j = 1;
895: for (i = f->accept; i >= 0; i--)
896: if (setvec[i]) {
897: tmpset[j++] = i;
898: }
899: /* tmpset == previous state? */
900: for (i = 1; i <= f->curstat; i++) {
901: p = f->posns[i];
902: if ((k = tmpset[0]) != p[0])
903: goto different;
904: for (j = 1; j <= k; j++)
905: if (tmpset[j] != p[j])
906: goto different;
907: /* setvec is state i */
908: f->gototab[s][c] = i;
909: return i;
910: different:;
911: }
912:
913: /* add tmpset to current set of states */
914: if (f->curstat >= NSTATES-1) {
915: f->curstat = 2;
916: f->reset = 1;
917: for (i = 2; i < NSTATES; i++)
918: xfree(f->posns[i]);
919: } else
920: ++(f->curstat);
921: for (i = 0; i < NCHARS; i++)
922: f->gototab[f->curstat][i] = 0;
923: xfree(f->posns[f->curstat]);
1.13 pvalchev 924: if ((p = (int *) calloc(setcnt+1, sizeof(int))) == NULL)
1.1 tholo 925: overflo("out of space in cgoto");
926:
927: f->posns[f->curstat] = p;
928: f->gototab[s][c] = f->curstat;
929: for (i = 0; i <= setcnt; i++)
930: p[i] = tmpset[i];
931: if (setvec[f->accept])
932: f->out[f->curstat] = 1;
933: else
934: f->out[f->curstat] = 0;
935: return f->curstat;
936: }
937:
938:
939: void freefa(fa *f) /* free a finite automaton */
940: {
941: int i;
942:
943: if (f == NULL)
944: return;
945: for (i = 0; i <= f->curstat; i++)
946: xfree(f->posns[i]);
947: for (i = 0; i <= f->accept; i++) {
948: xfree(f->re[i].lfollow);
949: if (f->re[i].ltype == CCL || f->re[i].ltype == NCCL)
950: xfree((f->re[i].lval.np));
951: }
952: xfree(f->restr);
953: xfree(f);
954: }
![[BACK]](/icons/back.gif){kind=icon}
Return to b.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / awk