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