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