![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to machine.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / twig|
Return to machine.c CVS log | Up to [Research Unix] / researchv10no / cmd / twig |
1.1 root 1: #include "common.h"
2: #include "code.h"
3: #include "sym.h"
4: #include "machine.h"
5:
6: int gen_table2; /* generate type two tables */
7: struct machine_node *machine = NULL;
8: static int depth;
9:
10: static struct machine_node *
11: get_state()
12: {
13: struct machine_node *mp = (struct machine_node *)
14: malloc (sizeof (struct machine_node));
15: assert (mp!=NULL);
16: mp->inp.value = -1;
17: mp->nst = NULL;
18: mp->link = NULL;
19: mp->fail = NULL;
20: mp->match = NULL;
21: return(mp);
22: }
23:
24: add_match(s, tp, depth)
25: struct machine_node *s;
26: LabelData *tp;
27: int depth;
28: {
29: struct match *mp = (struct match *) malloc (sizeof (struct match));
30:
31: assert (mp!=NULL);
32: mp->next = s->match;
33: mp->depth = depth;
34: mp->tree = tp;
35: s->match = mp;
36: }
37:
38: /*
39: * Build a trie from the path strings. Failure transition are added later.
40: */
41: cgotofn(tp)
42: LabelData *tp;
43: {
44: struct machine_input inp;
45: int ret;
46: register struct machine_node *s;
47: register int quit = 0;
48:
49: if (machine==NULL) {
50: /* first time thru */
51: machine = get_state();
52: }
53: s = machine;
54: depth = -1;
55:
56: assert (tp->tree!=NULL);
57: path_setup (tp->tree);
58:
59: for(;;) {
60: ret = path_getsym(&inp);
61:
62: /* no more paths */
63: if (ret == EOF)
64: break;
65:
66: if (ret == NULL) {
67: /*
68: * the end of the path. Add a match to the
69: * accepting state.
70: */
71: assert ((depth&01)==0); /* make sure it's even */
72: add_match(s, tp, depth >> 1);
73: s = machine;
74: depth = -1;
75: ntrees++;
76: continue;
77: }
78:
79: while (!MI_EQUAL(s->inp, inp)) {
80: if (!MI_DEFINED(s->inp.value) || s->link == NULL) {
81: if (MI_DEFINED(s->inp.value)) {
82: /*
83: * The trie must be split here
84: */
85: s->link = get_state();
86: s = s->link;
87: }
88: /*
89: * Fill in the state
90: */
91: s->inp = inp;
92: s->nst = get_state();
93: s = s->nst;
94: depth++;
95: break;
96: } else s = s->link;
97: }
98: if (MI_EQUAL(s->inp, inp)) {
99: s = s->nst;
100: depth++;
101: }
102: }
103: }
104:
105: /* print out the machine for debugging */
106: machine_print(mp)
107: struct machine_node *mp;
108: {
109: register struct machine_node *mp2;
110: struct machine_node *fail;
111: struct match *match, *p;
112:
113: if (mp==NULL)
114: return;
115: printf("%x %d:", mp, mp->index);
116: if((fail = mp->fail))
117: printf("\tfail %x", fail);
118: if((match = mp->match)) {
119: printf("\taccept ");
120: for(p = match; p!=NULL; p = p->next) {
121: LabelData *tp = p->tree;
122: printf("%s ", (tp->label)->name);
123: }
124: }
125: putchar('\n');
126: for(mp2=mp; mp2!=NULL; mp2 = mp2->link) {
127: if (MI_DEFINED(mp2->inp.value)) {
128: if (MI_BRANCH(mp->inp.value))
129: printf(" %d -> ", mp2->inp.value);
130: else
131: printf(" [%s] -> ", (mp2->inp.sym)->name);
132: printf("%x", mp2->nst);
133: }
134: assert(mp2->fail==fail);
135: assert(mp2->match==match);
136: }
137: if(MI_DEFINED(mp->inp.value))
138: putchar('\n');
139: for (mp2 = mp; mp2!=NULL; mp2=mp2->link) {
140: machine_print(mp2->nst);
141: }
142: }
143:
144: /*
145: * This routine augments the machine with failure transition.
146: * The trie is examined in breadth first order.
147: * See Aho, Corasick Comm ACM 18:6 for details
148: */
149: cfail()
150: {
151: struct machine_node **stack, **stack2;
152: struct machine_node **stackTop, **stack2Top, **temp;
153: int stackCnt, stack2Cnt;
154: struct machine_node *state;
155: struct machine_input sym;
156: register struct machine_node *s, *q;
157:
158: /* allocate stacks */
159: stackTop = stack = (struct machine_node **) malloc
160: (ntrees*sizeof (struct machine_node *));
161: stack2 = stack2Top = (struct machine_node **) malloc
162: (ntrees*sizeof (struct machine_node *));
163: stackCnt = stack2Cnt = 0;
164: s = machine;
165: do {
166: if (MI_DEFINED(s->inp.value)) {
167: assert(++stackCnt <= ntrees);
168: *stackTop++ = s->nst;
169: }
170: s = s->link;
171: } while (s != NULL);
172:
173: for(;;) {
174: if (stackCnt == 0) {
175: /* swap stacks */
176: if (stack2Cnt == 0)
177: break;
178: stackCnt = stack2Cnt; stack2Cnt = 0;
179: stackTop = stack2Top;
180: temp = stack; stack = stack2; stack2 = temp;
181: stack2Top = stack2;
182: }
183: stackCnt--;
184: s = *--stackTop;
185: do {
186: int startstate = 0;
187: sym = s->inp;
188: if (MI_DEFINED(sym.value)) { /* g(s,c) != 0 */
189: assert (++stack2Cnt <= ntrees);
190: *stack2Top++ = (q=s->nst);
191: state = s->fail; /* state = f(s) */
192: for(;;) {
193: if (state == 0) {
194: state = machine;
195: startstate++;
196: }
197: if (MI_EQUAL(state->inp, sym)) {
198: struct match *mp = NULL;
199:
200: /* append any accepting matches */
201: for(mp=(state->nst)->match;mp;mp=mp->next)
202: add_match(q,mp->tree, mp->depth);
203: mp = q->match;
204:
205: do {
206: /* f(q) = g(state,sym)
207: * for all q links */
208: q->fail = state->nst;
209: q->match = mp;
210: } while ((q = q->link) != 0);
211: break;
212: }
213: else if (state->link != 0)
214: state = state->link;
215: else {
216: state = state->fail;
217: if (state==NULL&&startstate)
218: break;
219: }
220: }
221: }
222: s = s->link;
223: } while (s!=NULL);
224: }
225: }
226:
227: /*
228: * Called from the YACC rule pattern_spec
229: */
230: void
231: machine_build()
232: {
233: cfail();
234: (void) MachineNumber(machine, 0);
235: if(debug_flag&DB_MACH) {
236: fputs("\n-------\n", stderr);
237: machine_print(machine);
238: }
239: }
240:
241: struct match *acceptTable[MAXACCEPTS];
242: struct match **acceptTableTop = acceptTable;
243: static short int *arityTable;
244: int nextAcceptIndex = 0;
245:
246: /*
247: * This is the first pass of the process to generate the
248: * flattened machine used in the walker. Called from machine_build
249: */
250: int
251: MachineNumber(mach, index)
252: struct machine_node *mach;
253: int index;
254: {
255: struct machine_node *mp;
256:
257: for(mp=mach; mp!=NULL; mp = mp->link)
258: if(MI_DEFINED(mp->inp.value))
259: index = MachineNumber(mp->nst, index);
260:
261: mach->index = index;
262: if (mach->match!=NULL) index += 2;
263: if(mach->link!=NULL || mach->nst!=NULL) {
264: index += 2;
265: for(mp = mach; mp!=NULL; mp = mp->link)
266: if(mp->nst!=NULL)
267: index += 2;
268: }
269:
270: if (mach->fail!=NULL)
271: index += 2;
272: index++;
273: return(index);
274: }
275:
276: /*
277: * Build the flattened out machine used in the walker.
278: * See machine.h for description
279: */
280: MachineGen()
281: {
282: struct match **atp, *ap;
283: short int *sp;
284:
285: oreset();
286: fputs("short int mtTable[] = {\n", outfile);
287: machineGen2(machine);
288: fputs("};\n", outfile);
289:
290: fputs("short int mtAccept[] = {\n", outfile);
291:
292: oreset();
293: for(atp = acceptTable; atp < acceptTableTop; atp++) {
294: for(ap = *atp; ap!=NULL; ap = ap->next) {
295: register LabelData *tree = ap->tree;
296:
297: /* if you change any of the code below you must change
298: * the increment added to nextAcceptIndex in
299: * machineGen2
300: */
301: oputint(tree->treeIndex);
302: oputint(ap->depth);
303: }
304: oputint(-1);
305: }
306: fprintf(outfile, "};\nshort int mtStart = %d;\n", machine->index);
307: }
308:
309: machineGen2(mach)
310: struct machine_node *mach;
311: {
312: struct machine_node *mp;
313: struct match *ap;
314:
315: if (mach==NULL)
316: return;
317:
318: for(mp=mach; mp!=NULL; mp = mp->link)
319: if(MI_DEFINED(mp->inp.value))
320: machineGen2(mp->nst);
321:
322: assert(mach->index == ointcnt());
323: if (mach->match!=NULL) {
324: *acceptTableTop++ = mach->match;
325: oputint(ACCEPT); oputint(nextAcceptIndex);
326: for(ap = mach->match; ap!=NULL; ap = ap->next)
327: nextAcceptIndex += 2;
328: nextAcceptIndex++;
329: }
330: if(mach->link!=NULL || mach->nst!=NULL) {
331: if(MI_BRANCH(mp->inp.value)&&gen_table2) {
332: oputint (TABLE2);
333: for(mp = mach; mp!=NULL; mp = mp->link) {
334: if(mp->nst!=NULL) {
335: oputoct(mp->inp.value);
336: oputint((mp->nst)->index);
337: }
338: }
339: } else {
340: oputint (TABLE);
341: for(mp = mach; mp!=NULL; mp = mp->link) {
342: if(mp->nst!=NULL) {
343: oputoct(mp->inp.value);
344: oputint((mp->nst)->index);
345: }
346: }
347: }
348: oputint(-1);
349: }
350:
351: /* A failure transition or a -1 terminate every state */
352: if (mach->fail!=NULL) {
353: oputint(FAIL); oputint((mach->fail)->index);
354: }
355: oputint(-1);
356: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.