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