![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to b.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / awk|
Return to b.c CVS log | Up to [Research Unix] / researchv10no / cmd / awk |
1.1 root 1: /*
2: Copyright (c) 1989 AT&T
3: All Rights Reserved
4:
5: THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T.
6:
7: The copyright notice above does not evidence any
8: actual or intended publication of such source code.
9: */
10:
11: #define DEBUG
12:
13: #include <ctype.h>
14: #include <stdio.h>
15: #include <string.h>
16: #include <stdlib.h>
17: #include "awk.h"
18: #include "y.tab.h"
19:
20: #define HAT (NCHARS-1) /* matches ^ in regular expr */
21: /* NCHARS is 2**n */
22: #define MAXLIN 512
23:
24: #define type(v) (v)->nobj
25: #define left(v) (v)->narg[0]
26: #define right(v) (v)->narg[1]
27: #define parent(v) (v)->nnext
28:
29: #define LEAF case CCL: case NCCL: case CHAR: case DOT: case FINAL: case ALL:
30: #define UNARY case STAR: case PLUS: case QUEST:
31:
32: /* encoding in tree Nodes:
33: leaf (CCL, NCCL, CHAR, DOT, FINAL, ALL):
34: left is index, right contains value or pointer to value
35: unary (STAR, PLUS, QUEST): left is child, right is null
36: binary (CAT, OR): left and right are children
37: parent contains pointer to parent
38: */
39:
40:
41: uchar chars[MAXLIN];
42: int setvec[MAXLIN];
43: int tmpset[MAXLIN];
44: Node *point[MAXLIN];
45:
46: int rtok; /* next token in current re */
47: int rlxval;
48: uchar *rlxstr;
49: uchar *prestr; /* current position in current re */
50: uchar *lastre; /* origin of last re */
51:
52: static int setcnt;
53: static int poscnt;
54:
55: uchar *patbeg;
56: int patlen;
57:
58: #define NFA 20 /* cache this many dynamic fa's */
59: fa *fatab[NFA];
60: int nfatab = 0; /* entries in fatab */
61:
62: fa *makedfa(uchar *s, int anchor) /* returns dfa for reg expr s */
63: {
64: int i, use, nuse;
65: fa *pfa;
66:
67: if (compile_time) /* a constant for sure */
68: return mkdfa(s, anchor);
69: for (i = 0; i < nfatab; i++) /* is it there already? */
70: if (fatab[i]->anchor == anchor && strcmp(fatab[i]->restr,s) == 0) {
71: fatab[i]->use++;
72: return fatab[i];
73: }
74: pfa = mkdfa(s, anchor);
75: if (nfatab < NFA) { /* room for another */
76: fatab[nfatab] = pfa;
77: fatab[nfatab]->use = 1;
78: nfatab++;
79: return pfa;
80: }
81: use = fatab[0]->use; /* replace least-recently used */
82: nuse = 0;
83: for (i = 1; i < nfatab; i++)
84: if (fatab[i]->use < use) {
85: use = fatab[i]->use;
86: nuse = i;
87: }
88: freefa(fatab[nuse]);
89: fatab[nuse] = pfa;
90: pfa->use = 1;
91: return pfa;
92: }
93:
94: fa *mkdfa(uchar *s, int anchor) /* does the real work of making a dfa */
95: /* anchor = 1 for anchored matches, else 0 */
96: {
97: Node *p, *p1;
98: fa *f;
99:
100: p = reparse(s);
101: p1 = op2(CAT, op2(STAR, op2(ALL, NIL, NIL), NIL), p);
102: /* put ALL STAR in front of reg. exp. */
103: p1 = op2(CAT, p1, op2(FINAL, NIL, NIL));
104: /* put FINAL after reg. exp. */
105:
106: poscnt = 0;
107: penter(p1); /* enter parent pointers and leaf indices */
108: if ((f = (fa *) calloc(1, sizeof(fa) + poscnt*sizeof(rrow))) == NULL)
109: overflo("out of space for fa");
110: f->accept = poscnt-1; /* penter has computed number of positions in re */
111: cfoll(f, p1); /* set up follow sets */
112: freetr(p1);
113: if ((f->posns[0] = (int *) calloc(1, *(f->re[0].lfollow)*sizeof(int))) == NULL)
114: overflo("out of space in makedfa");
115: if ((f->posns[1] = (int *) calloc(1, sizeof(int))) == NULL)
116: overflo("out of space in makedfa");
117: *f->posns[1] = 0;
118: f->initstat = makeinit(f, anchor);
119: f->anchor = anchor;
120: f->restr = tostring(s);
121: return f;
122: }
123:
124: int makeinit(fa *f, int anchor)
125: {
126: register int i, k;
127:
128: f->curstat = 2;
129: f->out[2] = 0;
130: f->reset = 0;
131: k = *(f->re[0].lfollow);
132: xfree(f->posns[2]);
133: if ((f->posns[2] = (int *) calloc(1, (k+1)*sizeof(int))) == NULL)
134: overflo("out of space in makeinit");
135: for (i=0; i<=k; i++) {
136: (f->posns[2])[i] = (f->re[0].lfollow)[i];
137: }
138: if ((f->posns[2])[1] == f->accept)
139: f->out[2] = 1;
140: for (i=0; i<NCHARS; i++)
141: f->gototab[2][i] = 0;
142: f->curstat = cgoto(f, 2, HAT);
143: if (anchor) {
144: *f->posns[2] = k-1; /* leave out position 0 */
145: for (i=0; i<k; i++) {
146: (f->posns[0])[i] = (f->posns[2])[i];
147: }
148:
149: f->out[0] = f->out[2];
150: if (f->curstat != 2)
151: --(*f->posns[f->curstat]);
152: }
153: return f->curstat;
154: }
155:
156: void penter(Node *p) /* set up parent pointers and leaf indices */
157: {
158: switch(type(p)) {
159: LEAF
160: left(p) = (Node *) poscnt;
161: if (poscnt >= MAXLIN)
162: overflo("leaf index overflow in penter");
163: point[poscnt++] = p;
164: break;
165: UNARY
166: penter(left(p));
167: parent(left(p)) = p;
168: break;
169: case CAT:
170: case OR:
171: penter(left(p));
172: penter(right(p));
173: parent(left(p)) = p;
174: parent(right(p)) = p;
175: break;
176: default: /* can't happen */
177: ERROR "unknown type %d in penter", type(p) FATAL;
178: break;
179: }
180: }
181:
182: void freetr(Node *p) /* free parse tree */
183: {
184: switch (type(p)) {
185: LEAF
186: xfree(p);
187: break;
188: UNARY
189: freetr(left(p));
190: xfree(p);
191: break;
192: case CAT:
193: case OR:
194: freetr(left(p));
195: freetr(right(p));
196: xfree(p);
197: break;
198: default: /* can't happen */
199: ERROR "unknown type %d in freetr", type(p) FATAL;
200: break;
201: }
202: }
203:
204: /* in the parsing of regular expressions, metacharacters like . have */
205: /* to be seen literally; \056 is not a metacharacter. */
206:
207: hexstr(char **pp) /* find and eval hex string at pp, return new p */
208: {
209: char *p;
210: int n = 0;
211:
212: for (p = *pp; isxdigit(*p); p++) {
213: if (isdigit(*p))
214: n = 16 * n + *p - '0';
215: else if (*p >= 'a' && *p <= 'f')
216: n = 16 * n + *p - 'a' + 10;
217: else if (*p >= 'A' && *p <= 'F')
218: n = 16 * n + *p - 'A' + 10;
219: }
220: *pp = p;
221: return n;
222: }
223:
224: #define isoctdigit(c) ((c) >= '0' && (c) <= '8') /* multiple use of arg */
225:
226: quoted(char **pp) /* pick up next thing after a \\ */
227: /* and increment *pp */
228: {
229: char *p = *pp;
230: int c;
231:
232: if ((c = *p++) == 't')
233: c = '\t';
234: else if (c == 'n')
235: c = '\n';
236: else if (c == 'f')
237: c = '\f';
238: else if (c == 'r')
239: c = '\r';
240: else if (c == 'b')
241: c = '\b';
242: else if (c == '\\')
243: c = '\\';
244: else if (c == 'x') { /* hexadecimal goo follows */
245: c = hexstr(&p);
246: } else if (isoctdigit(c)) { /* \d \dd \ddd */
247: int n = c - '0';
248: if (isoctdigit(*p)) {
249: n = 8 * n + *p++ - '0';
250: if (isoctdigit(*p))
251: n = 8 * n + *p++ - '0';
252: }
253: c = n;
254: } /* else */
255: /* c = c; */
256: *pp = p;
257: return c;
258: }
259:
260: uchar *cclenter(uchar *p)
261: {
262: register int i, c, c2;
263: uchar *op;
264:
265: op = p;
266: i = 0;
267: while ((c = *p++) != 0) {
268: if (c == '\\') {
269: c = quoted(&p);
270: } else if (c == '-' && i > 0 && chars[i-1] != 0) {
271: if (*p != 0) {
272: c = chars[i-1];
273: c2 = *p++;
274: if (c2 == '\\')
275: c2 = quoted(&p);
276: while (c < c2) {
277: if (i >= MAXLIN-1)
278: overflo("character class too big");
279: chars[i++] = ++c;
280: }
281: continue;
282: }
283: }
284: if (i >= MAXLIN-1)
285: overflo("character class too big");
286: chars[i++] = c;
287: }
288: chars[i++] = '\0';
289: dprintf( ("cclenter: in = |%s|, out = |%s|\n", op, chars) );
290: xfree(op);
291: return(tostring(chars));
292: }
293:
294: void overflo(uchar *s)
295: {
296: ERROR "regular expression too big: %s", s FATAL;
297: }
298:
299: void cfoll(fa *f, Node *v) /* enter follow set of each leaf of vertex v into lfollow[leaf] */
300: {
301: register int i;
302: register int *p;
303:
304: switch(type(v)) {
305: LEAF
306: f->re[(int) left(v)].ltype = type(v);
307: f->re[(int) left(v)].lval = (long) right(v); /* assumes ptr & long fit */
308: for (i=0; i<=f->accept; i++)
309: setvec[i] = 0;
310: setcnt = 0;
311: follow(v); /* computes setvec and setcnt */
312: if ((p = (int *) calloc(1, (setcnt+1)*sizeof(int))) == NULL)
313: overflo("out of space building follow set");
314: f->re[(int) left(v)].lfollow = p;
315: *p = setcnt;
316: for (i = f->accept; i >= 0; i--)
317: if (setvec[i] == 1) *++p = i;
318: break;
319: UNARY
320: cfoll(f,left(v));
321: break;
322: case CAT:
323: case OR:
324: cfoll(f,left(v));
325: cfoll(f,right(v));
326: break;
327: default: /* can't happen */
328: ERROR "unknown type %d in cfoll", type(v) FATAL;
329: }
330: }
331:
332: first(Node *p) /* collects initially active leaves of p into setvec */
333: /* returns 0 or 1 depending on whether p matches empty string */
334: {
335: register int b;
336:
337: switch(type(p)) {
338: LEAF
339: if (setvec[(int) left(p)] != 1) {
340: setvec[(int) left(p)] = 1;
341: setcnt++;
342: }
343: if (type(p) == CCL && (*(uchar *) right(p)) == '\0')
344: return(0); /* empty CCL */
345: else return(1);
346: case PLUS:
347: if (first(left(p)) == 0) return(0);
348: return(1);
349: case STAR:
350: case QUEST:
351: first(left(p));
352: return(0);
353: case CAT:
354: if (first(left(p)) == 0 && first(right(p)) == 0) return(0);
355: return(1);
356: case OR:
357: b = first(right(p));
358: if (first(left(p)) == 0 || b == 0) return(0);
359: return(1);
360: }
361: ERROR "unknown type %d in first", type(p) FATAL; /* can't happen */
362: return(-1);
363: }
364:
365: void follow(Node *v) /* collects leaves that can follow v into setvec */
366: {
367: Node *p;
368:
369: if (type(v) == FINAL)
370: return;
371: p = parent(v);
372: switch (type(p)) {
373: case STAR:
374: case PLUS:
375: first(v);
376: follow(p);
377: return;
378:
379: case OR:
380: case QUEST:
381: follow(p);
382: return;
383:
384: case CAT:
385: if (v == left(p)) { /* v is left child of p */
386: if (first(right(p)) == 0) {
387: follow(p);
388: return;
389: }
390: }
391: else /* v is right child */
392: follow(p);
393: return;
394: }
395: }
396:
397: member(int c, uchar *s) /* is c in s? */
398: {
399: while (*s)
400: if (c == *s++)
401: return(1);
402: return(0);
403: }
404:
405:
406: match(fa *f, uchar *p)
407: {
408: register int s, ns;
409:
410: s = f->reset?makeinit(f,0):f->initstat;
411: if (f->out[s])
412: return(1);
413: do {
414: if (ns=f->gototab[s][*p])
415: s=ns;
416: else
417: s=cgoto(f,s,*p);
418: if (f->out[s])
419: return(1);
420: } while (*p++ != 0);
421: return(0);
422: }
423:
424: pmatch(fa *f, uchar *p)
425: {
426: register int s, ns;
427: register uchar *q;
428: int i, k;
429:
430: s = f->reset?makeinit(f,1):f->initstat;
431: patbeg = p;
432: patlen = -1;
433: do {
434: q = p;
435: do {
436: if (f->out[s]) /* final state */
437: patlen = q-p;
438: if (ns=f->gototab[s][*q])
439: s=ns;
440: else
441: s=cgoto(f,s,*q);
442: if (s==1) /* no transition */
443: if (patlen >= 0) {
444: patbeg = p;
445: return(1);
446: }
447: else
448: goto nextin; /* no match */
449: } while (*q++ != 0);
450: if (f->out[s])
451: patlen = q-p-1; /* don't count $ */
452: if (patlen >= 0) {
453: patbeg = p;
454: return(1);
455: }
456: nextin:
457: s = 2;
458: if (f->reset) {
459: for (i=2; i<=f->curstat; i++)
460: xfree(f->posns[i]);
461: k = *f->posns[0];
462: if ((f->posns[2] = (int *) calloc(1, (k+1)*sizeof(int))) == NULL)
463: overflo("out of space in pmatch");
464: for (i=0; i<=k; i++)
465: (f->posns[2])[i] = (f->posns[0])[i];
466: f->initstat = f->curstat = 2;
467: f->out[2] = f->out[0];
468: for (i=0; i<NCHARS; i++)
469: f->gototab[2][i] = 0;
470: }
471: } while (*p++ != 0);
472: return (0);
473: }
474:
475: nematch(fa *f, uchar *p)
476: {
477: register int s, ns;
478: register uchar *q;
479: int i, k;
480:
481: s = f->reset?makeinit(f,1):f->initstat;
482: patlen = -1;
483: while (*p) {
484: q = p;
485: do {
486: if (f->out[s]) /* final state */
487: patlen = q-p;
488: if (ns=f->gototab[s][*q])
489: s=ns;
490: else
491: s=cgoto(f,s,*q);
492: if (s==1) /* no transition */
493: if (patlen > 0) {
494: patbeg = p;
495: return(1);
496: }
497: else
498: goto nnextin; /* no nonempty match */
499: } while (*q++ != 0);
500: if (f->out[s])
501: patlen = q-p-1; /* don't count $ */
502: if (patlen > 0 ) {
503: patbeg = p;
504: return(1);
505: }
506: nnextin:
507: s = 2;
508: if (f->reset) {
509: for (i=2; i<=f->curstat; i++)
510: xfree(f->posns[i]);
511: k = *f->posns[0];
512: if ((f->posns[2] = (int *) calloc(1, (k+1)*sizeof(int))) == NULL)
513: overflo("out of state space");
514: for (i=0; i<=k; i++)
515: (f->posns[2])[i] = (f->posns[0])[i];
516: f->initstat = f->curstat = 2;
517: f->out[2] = f->out[0];
518: for (i=0; i<NCHARS; i++)
519: f->gototab[2][i] = 0;
520: }
521: p++;
522: }
523: return (0);
524: }
525:
526: Node *reparse(uchar *p)
527: {
528: /* parses regular expression pointed to by p */
529: /* uses relex() to scan regular expression */
530: Node *np;
531:
532: dprintf( ("reparse <%s>\n", p) );
533: lastre = prestr = p; /* prestr points to string to be parsed */
534: rtok = relex();
535: if (rtok == '\0')
536: ERROR "empty regular expression" FATAL;
537: np = regexp();
538: if (rtok != '\0')
539: ERROR "syntax error in regular expression %s at %s", lastre, prestr FATAL;
540: return(np);
541: }
542:
543: Node *regexp(void)
544: {
545: return (alt(concat(primary())));
546: }
547:
548: Node *primary(void)
549: {
550: Node *np;
551:
552: switch (rtok) {
553: case CHAR:
554: np = op2(CHAR, NIL, (Node *) rlxval);
555: rtok = relex();
556: return (unary(np));
557: case ALL:
558: rtok = relex();
559: return (unary(op2(ALL, NIL, NIL)));
560: case DOT:
561: rtok = relex();
562: return (unary(op2(DOT, NIL, NIL)));
563: case CCL:
564: np = op2(CCL, NIL, (Node*) cclenter(rlxstr));
565: rtok = relex();
566: return (unary(np));
567: case NCCL:
568: np = op2(NCCL, NIL, (Node *) cclenter(rlxstr));
569: rtok = relex();
570: return (unary(np));
571: case '^':
572: rtok = relex();
573: return (unary(op2(CHAR, NIL, (Node *) HAT)));
574: case '$':
575: rtok = relex();
576: return (unary(op2(CHAR, NIL, NIL)));
577: case '(':
578: rtok = relex();
579: if (rtok == ')') { /* special pleading for () */
580: rtok = relex();
581: return unary(op2(CCL, NIL, (Node *) tostring("")));
582: }
583: np = regexp();
584: if (rtok == ')') {
585: rtok = relex();
586: return (unary(np));
587: }
588: else
589: ERROR "syntax error in regular expression %s at %s", lastre, prestr FATAL;
590: default:
591: ERROR "illegal primary in regular expression %s at %s", lastre, prestr FATAL;
592: }
593: return 0; /*NOTREACHED*/
594: }
595:
596: Node *concat(Node *np)
597: {
598: switch (rtok) {
599: case CHAR: case DOT: case ALL: case CCL: case NCCL: case '$': case '(':
600: return (concat(op2(CAT, np, primary())));
601: }
602: return (np);
603: }
604:
605: Node *alt(Node *np)
606: {
607: if (rtok == OR) {
608: rtok = relex();
609: return (alt(op2(OR, np, concat(primary()))));
610: }
611: return (np);
612: }
613:
614: Node *unary(Node *np)
615: {
616: switch (rtok) {
617: case STAR:
618: rtok = relex();
619: return (unary(op2(STAR, np, NIL)));
620: case PLUS:
621: rtok = relex();
622: return (unary(op2(PLUS, np, NIL)));
623: case QUEST:
624: rtok = relex();
625: return (unary(op2(QUEST, np, NIL)));
626: default:
627: return (np);
628: }
629: }
630:
631: relex(void) /* lexical analyzer for reparse */
632: {
633: register int c;
634: uchar cbuf[MAXLIN];
635: int clen, cflag;
636:
637: switch (c = *prestr++) {
638: case '|': return OR;
639: case '*': return STAR;
640: case '+': return PLUS;
641: case '?': return QUEST;
642: case '.': return DOT;
643: case '\0': prestr--; return '\0';
644: case '^':
645: case '$':
646: case '(':
647: case ')':
648: return c;
649: case '\\':
650: rlxval = quoted(&prestr);
651: return CHAR;
652: default:
653: rlxval = c;
654: return CHAR;
655: case '[':
656: clen = 0;
657: if (*prestr == '^') {
658: cflag = 1;
659: prestr++;
660: }
661: else
662: cflag = 0;
663: for ( ; clen < MAXLIN-1; ) {
664: if ((c = *prestr++) == '\\') {
665: cbuf[clen++] = '\\';
666: if ((c = *prestr++) == '\0')
667: ERROR "nonterminated character class %.20s...", lastre FATAL;
668: cbuf[clen++] = c;
669: } else if (c == ']') {
670: cbuf[clen] = 0;
671: rlxstr = tostring(cbuf);
672: if (cflag == 0)
673: return CCL;
674: else
675: return NCCL;
676: } else if (c == '\n') {
677: ERROR "newline in character class %.20s...", lastre FATAL;
678: } else if (c == '\0') {
679: ERROR "nonterminated character class %.20s", lastre FATAL;
680: } else
681: cbuf[clen++] = c;
682: }
683: if (clen >= MAXLIN-1)
684: ERROR "character class %.20s... too long", cbuf FATAL;
685: }
686: /* can't happen */
687: return 0;
688: }
689:
690: int cgoto(fa *f, int s, int c)
691: {
692: register int i, j, k;
693: register int *p, *q;
694:
695: for (i=0; i<=f->accept; i++)
696: setvec[i] = 0;
697: setcnt = 0;
698: /* compute positions of gototab[s,c] into setvec */
699: p = f->posns[s];
700: for (i=1; i<=*p; i++) {
701: if ((k = f->re[p[i]].ltype) != FINAL) {
702: if (k == CHAR && c == f->re[p[i]].lval
703: || k == DOT && c != 0 && c != HAT
704: || k == ALL && c != 0
705: || k == CCL && member(c, (uchar *) f->re[p[i]].lval)
706: || k == NCCL && !member(c, (uchar *) f->re[p[i]].lval) && c != 0 && c != HAT) {
707: q = f->re[p[i]].lfollow;
708: for (j=1; j<=*q; j++) {
709: if (setvec[q[j]] == 0) {
710: setcnt++;
711: setvec[q[j]] = 1;
712: }
713: }
714: }
715: }
716: }
717: /* determine if setvec is a previous state */
718: tmpset[0] = setcnt;
719: j = 1;
720: for (i = f->accept; i >= 0; i--)
721: if (setvec[i]) {
722: tmpset[j++] = i;
723: }
724: /* tmpset == previous state? */
725: for (i=1; i<= f->curstat; i++) {
726: p = f->posns[i];
727: if ((k = tmpset[0]) != p[0])
728: goto different;
729: for (j = 1; j <= k; j++)
730: if (tmpset[j] != p[j])
731: goto different;
732: /* setvec is state i */
733: f->gototab[s][c] = i;
734: return i;
735: different:;
736: }
737:
738: /* add tmpset to current set of states */
739: if (f->curstat >= NSTATES-1) {
740: f->curstat = 2;
741: f->reset = 1;
742: for (i=2; i<NSTATES; i++)
743: xfree(f->posns[i]);
744: }
745: else
746: ++(f->curstat);
747: for (i=0; i<NCHARS; i++)
748: f->gototab[f->curstat][i] = 0;
749: xfree(f->posns[f->curstat]);
750: if ((p = (int *) calloc(1, (setcnt+1)*sizeof(int))) == NULL)
751: overflo("out of space in cgoto");
752:
753: f->posns[f->curstat] = p;
754: f->gototab[s][c] = f->curstat;
755: for (i = 0; i <= setcnt; i++)
756: p[i] = tmpset[i];
757: if (setvec[f->accept])
758: f->out[f->curstat] = 1;
759: else
760: f->out[f->curstat] = 0;
761: return f->curstat;
762: }
763:
764:
765: void freefa(fa *f)
766: {
767:
768: register int i;
769:
770: if (f == NULL)
771: return;
772: for (i=0; i<=f->curstat; i++)
773: xfree(f->posns[i]);
774: for (i=0; i<=f->accept; i++) {
775: xfree(f->re[i].lfollow);
776: if (f->re[i].ltype == CCL || f->re[i].ltype == NCCL)
777: xfree(f->re[i].lval);
778: }
779: xfree(f->restr);
780: xfree(f);
781: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.