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