/[dtapublic]/sf_code/esrgpcpj/shared/tcl_base/regc_nfa.c
ViewVC logotype

Contents of /sf_code/esrgpcpj/shared/tcl_base/regc_nfa.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 25 - (show annotations) (download)
Sat Oct 8 06:43:03 2016 UTC (7 years, 5 months ago) by dashley
File MIME type: text/plain
File size: 38178 byte(s)
Initial commit.
1 /* $Header: /cvsroot/esrg/sfesrg/esrgpcpj/shared/tcl_base/regc_nfa.c,v 1.1.1.1 2001/06/13 04:32:10 dtashley Exp $ */
2
3 /*
4 * NFA utilities.
5 * This file is #included by regcomp.c.
6 *
7 * Copyright (c) 1998, 1999 Henry Spencer. All rights reserved.
8 *
9 * Development of this software was funded, in part, by Cray Research Inc.,
10 * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
11 * Corporation, none of whom are responsible for the results. The author
12 * thanks all of them.
13 *
14 * Redistribution and use in source and binary forms -- with or without
15 * modification -- are permitted for any purpose, provided that
16 * redistributions in source form retain this entire copyright notice and
17 * indicate the origin and nature of any modifications.
18 *
19 * I'd appreciate being given credit for this package in the documentation
20 * of software which uses it, but that is not a requirement.
21 *
22 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
23 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
24 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
25 * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
26 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
27 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
28 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
29 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
30 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
31 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 *
33 *
34 *
35 * One or two things that technically ought to be in here
36 * are actually in color.c, thanks to some incestuous relationships in
37 * the color chains.
38 */
39
40 #define NISERR() VISERR(nfa->v)
41 #define NERR(e) VERR(nfa->v, (e))
42
43
44 /*
45 - newnfa - set up an NFA
46 ^ static struct nfa *newnfa(struct vars *, struct colormap *, struct nfa *);
47 */
48 static struct nfa * /* the NFA, or NULL */
49 newnfa(v, cm, parent)
50 struct vars *v;
51 struct colormap *cm;
52 struct nfa *parent; /* NULL if primary NFA */
53 {
54 struct nfa *nfa;
55
56 nfa = (struct nfa *)MALLOC(sizeof(struct nfa));
57 if (nfa == NULL)
58 return NULL;
59
60 nfa->states = NULL;
61 nfa->slast = NULL;
62 nfa->free = NULL;
63 nfa->nstates = 0;
64 nfa->cm = cm;
65 nfa->v = v;
66 nfa->bos[0] = nfa->bos[1] = COLORLESS;
67 nfa->eos[0] = nfa->eos[1] = COLORLESS;
68 nfa->post = newfstate(nfa, '@'); /* number 0 */
69 nfa->pre = newfstate(nfa, '>'); /* number 1 */
70 nfa->parent = parent;
71
72 nfa->init = newstate(nfa); /* may become invalid later */
73 nfa->final = newstate(nfa);
74 if (ISERR()) {
75 freenfa(nfa);
76 return NULL;
77 }
78 rainbow(nfa, nfa->cm, PLAIN, COLORLESS, nfa->pre, nfa->init);
79 newarc(nfa, '^', 1, nfa->pre, nfa->init);
80 newarc(nfa, '^', 0, nfa->pre, nfa->init);
81 rainbow(nfa, nfa->cm, PLAIN, COLORLESS, nfa->final, nfa->post);
82 newarc(nfa, '$', 1, nfa->final, nfa->post);
83 newarc(nfa, '$', 0, nfa->final, nfa->post);
84
85 if (ISERR()) {
86 freenfa(nfa);
87 return NULL;
88 }
89 return nfa;
90 }
91
92 /*
93 - freenfa - free an entire NFA
94 ^ static VOID freenfa(struct nfa *);
95 */
96 static VOID
97 freenfa(nfa)
98 struct nfa *nfa;
99 {
100 struct state *s;
101
102 while ((s = nfa->states) != NULL) {
103 s->nins = s->nouts = 0; /* don't worry about arcs */
104 freestate(nfa, s);
105 }
106 while ((s = nfa->free) != NULL) {
107 nfa->free = s->next;
108 destroystate(nfa, s);
109 }
110
111 nfa->slast = NULL;
112 nfa->nstates = -1;
113 nfa->pre = NULL;
114 nfa->post = NULL;
115 FREE(nfa);
116 }
117
118 /*
119 - newstate - allocate an NFA state, with zero flag value
120 ^ static struct state *newstate(struct nfa *);
121 */
122 static struct state * /* NULL on error */
123 newstate(nfa)
124 struct nfa *nfa;
125 {
126 struct state *s;
127
128 if (nfa->free != NULL) {
129 s = nfa->free;
130 nfa->free = s->next;
131 } else {
132 s = (struct state *)MALLOC(sizeof(struct state));
133 if (s == NULL) {
134 NERR(REG_ESPACE);
135 return NULL;
136 }
137 s->oas.next = NULL;
138 s->free = NULL;
139 s->noas = 0;
140 }
141
142 assert(nfa->nstates >= 0);
143 s->no = nfa->nstates++;
144 s->flag = 0;
145 if (nfa->states == NULL)
146 nfa->states = s;
147 s->nins = 0;
148 s->ins = NULL;
149 s->nouts = 0;
150 s->outs = NULL;
151 s->tmp = NULL;
152 s->next = NULL;
153 if (nfa->slast != NULL) {
154 assert(nfa->slast->next == NULL);
155 nfa->slast->next = s;
156 }
157 s->prev = nfa->slast;
158 nfa->slast = s;
159 return s;
160 }
161
162 /*
163 - newfstate - allocate an NFA state with a specified flag value
164 ^ static struct state *newfstate(struct nfa *, int flag);
165 */
166 static struct state * /* NULL on error */
167 newfstate(nfa, flag)
168 struct nfa *nfa;
169 int flag;
170 {
171 struct state *s;
172
173 s = newstate(nfa);
174 if (s != NULL)
175 s->flag = (char)flag;
176 return s;
177 }
178
179 /*
180 - dropstate - delete a state's inarcs and outarcs and free it
181 ^ static VOID dropstate(struct nfa *, struct state *);
182 */
183 static VOID
184 dropstate(nfa, s)
185 struct nfa *nfa;
186 struct state *s;
187 {
188 struct arc *a;
189
190 while ((a = s->ins) != NULL)
191 freearc(nfa, a);
192 while ((a = s->outs) != NULL)
193 freearc(nfa, a);
194 freestate(nfa, s);
195 }
196
197 /*
198 - freestate - free a state, which has no in-arcs or out-arcs
199 ^ static VOID freestate(struct nfa *, struct state *);
200 */
201 static VOID
202 freestate(nfa, s)
203 struct nfa *nfa;
204 struct state *s;
205 {
206 assert(s != NULL);
207 assert(s->nins == 0 && s->nouts == 0);
208
209 s->no = FREESTATE;
210 s->flag = 0;
211 if (s->next != NULL)
212 s->next->prev = s->prev;
213 else {
214 assert(s == nfa->slast);
215 nfa->slast = s->prev;
216 }
217 if (s->prev != NULL)
218 s->prev->next = s->next;
219 else {
220 assert(s == nfa->states);
221 nfa->states = s->next;
222 }
223 s->prev = NULL;
224 s->next = nfa->free; /* don't delete it, put it on the free list */
225 nfa->free = s;
226 }
227
228 /*
229 - destroystate - really get rid of an already-freed state
230 ^ static VOID destroystate(struct nfa *, struct state *);
231 */
232 static VOID
233 destroystate(nfa, s)
234 struct nfa *nfa;
235 struct state *s;
236 {
237 struct arcbatch *ab;
238 struct arcbatch *abnext;
239
240 assert(s->no == FREESTATE);
241 for (ab = s->oas.next; ab != NULL; ab = abnext) {
242 abnext = ab->next;
243 FREE(ab);
244 }
245 s->ins = NULL;
246 s->outs = NULL;
247 s->next = NULL;
248 FREE(s);
249 }
250
251 /*
252 - newarc - set up a new arc within an NFA
253 ^ static VOID newarc(struct nfa *, int, pcolor, struct state *,
254 ^ struct state *);
255 */
256 static VOID
257 newarc(nfa, t, co, from, to)
258 struct nfa *nfa;
259 int t;
260 pcolor co;
261 struct state *from;
262 struct state *to;
263 {
264 struct arc *a;
265
266 assert(from != NULL && to != NULL);
267
268 /* check for duplicates */
269 for (a = from->outs; a != NULL; a = a->outchain)
270 if (a->to == to && a->co == co && a->type == t)
271 return;
272
273 a = allocarc(nfa, from);
274 if (NISERR())
275 return;
276 assert(a != NULL);
277
278 a->type = t;
279 a->co = (color)co;
280 a->to = to;
281 a->from = from;
282
283 /*
284 * Put the new arc on the beginning, not the end, of the chains.
285 * Not only is this easier, it has the very useful side effect that
286 * deleting the most-recently-added arc is the cheapest case rather
287 * than the most expensive one.
288 */
289 a->inchain = to->ins;
290 to->ins = a;
291 a->outchain = from->outs;
292 from->outs = a;
293
294 from->nouts++;
295 to->nins++;
296
297 if (COLORED(a) && nfa->parent == NULL)
298 colorchain(nfa->cm, a);
299
300 return;
301 }
302
303 /*
304 - allocarc - allocate a new out-arc within a state
305 ^ static struct arc *allocarc(struct nfa *, struct state *);
306 */
307 static struct arc * /* NULL for failure */
308 allocarc(nfa, s)
309 struct nfa *nfa;
310 struct state *s;
311 {
312 struct arc *a;
313 struct arcbatch *new;
314 int i;
315
316 /* shortcut */
317 if (s->free == NULL && s->noas < ABSIZE) {
318 a = &s->oas.a[s->noas];
319 s->noas++;
320 return a;
321 }
322
323 /* if none at hand, get more */
324 if (s->free == NULL) {
325 new = (struct arcbatch *)MALLOC(sizeof(struct arcbatch));
326 if (new == NULL) {
327 NERR(REG_ESPACE);
328 return NULL;
329 }
330 new->next = s->oas.next;
331 s->oas.next = new;
332
333 for (i = 0; i < ABSIZE; i++) {
334 new->a[i].type = 0;
335 new->a[i].freechain = &new->a[i+1];
336 }
337 new->a[ABSIZE-1].freechain = NULL;
338 s->free = &new->a[0];
339 }
340 assert(s->free != NULL);
341
342 a = s->free;
343 s->free = a->freechain;
344 return a;
345 }
346
347 /*
348 - freearc - free an arc
349 ^ static VOID freearc(struct nfa *, struct arc *);
350 */
351 static VOID
352 freearc(nfa, victim)
353 struct nfa *nfa;
354 struct arc *victim;
355 {
356 struct state *from = victim->from;
357 struct state *to = victim->to;
358 struct arc *a;
359
360 assert(victim->type != 0);
361
362 /* take it off color chain if necessary */
363 if (COLORED(victim) && nfa->parent == NULL)
364 uncolorchain(nfa->cm, victim);
365
366 /* take it off source's out-chain */
367 assert(from != NULL);
368 assert(from->outs != NULL);
369 a = from->outs;
370 if (a == victim) /* simple case: first in chain */
371 from->outs = victim->outchain;
372 else {
373 for (; a != NULL && a->outchain != victim; a = a->outchain)
374 continue;
375 assert(a != NULL);
376 a->outchain = victim->outchain;
377 }
378 from->nouts--;
379
380 /* take it off target's in-chain */
381 assert(to != NULL);
382 assert(to->ins != NULL);
383 a = to->ins;
384 if (a == victim) /* simple case: first in chain */
385 to->ins = victim->inchain;
386 else {
387 for (; a != NULL && a->inchain != victim; a = a->inchain)
388 continue;
389 assert(a != NULL);
390 a->inchain = victim->inchain;
391 }
392 to->nins--;
393
394 /* clean up and place on free list */
395 victim->type = 0;
396 victim->from = NULL; /* precautions... */
397 victim->to = NULL;
398 victim->inchain = NULL;
399 victim->outchain = NULL;
400 victim->freechain = from->free;
401 from->free = victim;
402 }
403
404 /*
405 - findarc - find arc, if any, from given source with given type and color
406 * If there is more than one such arc, the result is random.
407 ^ static struct arc *findarc(struct state *, int, pcolor);
408 */
409 static struct arc *
410 findarc(s, type, co)
411 struct state *s;
412 int type;
413 pcolor co;
414 {
415 struct arc *a;
416
417 for (a = s->outs; a != NULL; a = a->outchain)
418 if (a->type == type && a->co == co)
419 return a;
420 return NULL;
421 }
422
423 /*
424 - cparc - allocate a new arc within an NFA, copying details from old one
425 ^ static VOID cparc(struct nfa *, struct arc *, struct state *,
426 ^ struct state *);
427 */
428 static VOID
429 cparc(nfa, oa, from, to)
430 struct nfa *nfa;
431 struct arc *oa;
432 struct state *from;
433 struct state *to;
434 {
435 newarc(nfa, oa->type, oa->co, from, to);
436 }
437
438 /*
439 - moveins - move all in arcs of a state to another state
440 * You might think this could be done better by just updating the
441 * existing arcs, and you would be right if it weren't for the desire
442 * for duplicate suppression, which makes it easier to just make new
443 * ones to exploit the suppression built into newarc.
444 ^ static VOID moveins(struct nfa *, struct state *, struct state *);
445 */
446 static VOID
447 moveins(nfa, old, new)
448 struct nfa *nfa;
449 struct state *old;
450 struct state *new;
451 {
452 struct arc *a;
453
454 assert(old != new);
455
456 while ((a = old->ins) != NULL) {
457 cparc(nfa, a, a->from, new);
458 freearc(nfa, a);
459 }
460 assert(old->nins == 0);
461 assert(old->ins == NULL);
462 }
463
464 /*
465 - copyins - copy all in arcs of a state to another state
466 ^ static VOID copyins(struct nfa *, struct state *, struct state *);
467 */
468 static VOID
469 copyins(nfa, old, new)
470 struct nfa *nfa;
471 struct state *old;
472 struct state *new;
473 {
474 struct arc *a;
475
476 assert(old != new);
477
478 for (a = old->ins; a != NULL; a = a->inchain)
479 cparc(nfa, a, a->from, new);
480 }
481
482 /*
483 - moveouts - move all out arcs of a state to another state
484 ^ static VOID moveouts(struct nfa *, struct state *, struct state *);
485 */
486 static VOID
487 moveouts(nfa, old, new)
488 struct nfa *nfa;
489 struct state *old;
490 struct state *new;
491 {
492 struct arc *a;
493
494 assert(old != new);
495
496 while ((a = old->outs) != NULL) {
497 cparc(nfa, a, new, a->to);
498 freearc(nfa, a);
499 }
500 }
501
502 /*
503 - copyouts - copy all out arcs of a state to another state
504 ^ static VOID copyouts(struct nfa *, struct state *, struct state *);
505 */
506 static VOID
507 copyouts(nfa, old, new)
508 struct nfa *nfa;
509 struct state *old;
510 struct state *new;
511 {
512 struct arc *a;
513
514 assert(old != new);
515
516 for (a = old->outs; a != NULL; a = a->outchain)
517 cparc(nfa, a, new, a->to);
518 }
519
520 /*
521 - cloneouts - copy out arcs of a state to another state pair, modifying type
522 ^ static VOID cloneouts(struct nfa *, struct state *, struct state *,
523 ^ struct state *, int);
524 */
525 static VOID
526 cloneouts(nfa, old, from, to, type)
527 struct nfa *nfa;
528 struct state *old;
529 struct state *from;
530 struct state *to;
531 int type;
532 {
533 struct arc *a;
534
535 assert(old != from);
536
537 for (a = old->outs; a != NULL; a = a->outchain)
538 newarc(nfa, type, a->co, from, to);
539 }
540
541 /*
542 - delsub - delete a sub-NFA, updating subre pointers if necessary
543 * This uses a recursive traversal of the sub-NFA, marking already-seen
544 * states using their tmp pointer.
545 ^ static VOID delsub(struct nfa *, struct state *, struct state *);
546 */
547 static VOID
548 delsub(nfa, lp, rp)
549 struct nfa *nfa;
550 struct state *lp; /* the sub-NFA goes from here... */
551 struct state *rp; /* ...to here, *not* inclusive */
552 {
553 assert(lp != rp);
554
555 rp->tmp = rp; /* mark end */
556
557 deltraverse(nfa, lp, lp);
558 assert(lp->nouts == 0 && rp->nins == 0); /* did the job */
559 assert(lp->no != FREESTATE && rp->no != FREESTATE); /* no more */
560
561 rp->tmp = NULL; /* unmark end */
562 lp->tmp = NULL; /* and begin, marked by deltraverse */
563 }
564
565 /*
566 - deltraverse - the recursive heart of delsub
567 * This routine's basic job is to destroy all out-arcs of the state.
568 ^ static VOID deltraverse(struct nfa *, struct state *, struct state *);
569 */
570 static VOID
571 deltraverse(nfa, leftend, s)
572 struct nfa *nfa;
573 struct state *leftend;
574 struct state *s;
575 {
576 struct arc *a;
577 struct state *to;
578
579 if (s->nouts == 0)
580 return; /* nothing to do */
581 if (s->tmp != NULL)
582 return; /* already in progress */
583
584 s->tmp = s; /* mark as in progress */
585
586 while ((a = s->outs) != NULL) {
587 to = a->to;
588 deltraverse(nfa, leftend, to);
589 assert(to->nouts == 0 || to->tmp != NULL);
590 freearc(nfa, a);
591 if (to->nins == 0 && to->tmp == NULL) {
592 assert(to->nouts == 0);
593 freestate(nfa, to);
594 }
595 }
596
597 assert(s->no != FREESTATE); /* we're still here */
598 assert(s == leftend || s->nins != 0); /* and still reachable */
599 assert(s->nouts == 0); /* but have no outarcs */
600
601 s->tmp = NULL; /* we're done here */
602 }
603
604 /*
605 - dupnfa - duplicate sub-NFA
606 * Another recursive traversal, this time using tmp to point to duplicates
607 * as well as mark already-seen states. (You knew there was a reason why
608 * it's a state pointer, didn't you? :-))
609 ^ static VOID dupnfa(struct nfa *, struct state *, struct state *,
610 ^ struct state *, struct state *);
611 */
612 static VOID
613 dupnfa(nfa, start, stop, from, to)
614 struct nfa *nfa;
615 struct state *start; /* duplicate of subNFA starting here */
616 struct state *stop; /* and stopping here */
617 struct state *from; /* stringing duplicate from here */
618 struct state *to; /* to here */
619 {
620 if (start == stop) {
621 newarc(nfa, EMPTY, 0, from, to);
622 return;
623 }
624
625 stop->tmp = to;
626 duptraverse(nfa, start, from);
627 /* done, except for clearing out the tmp pointers */
628
629 stop->tmp = NULL;
630 cleartraverse(nfa, start);
631 }
632
633 /*
634 - duptraverse - recursive heart of dupnfa
635 ^ static VOID duptraverse(struct nfa *, struct state *, struct state *);
636 */
637 static VOID
638 duptraverse(nfa, s, stmp)
639 struct nfa *nfa;
640 struct state *s;
641 struct state *stmp; /* s's duplicate, or NULL */
642 {
643 struct arc *a;
644
645 if (s->tmp != NULL)
646 return; /* already done */
647
648 s->tmp = (stmp == NULL) ? newstate(nfa) : stmp;
649 if (s->tmp == NULL) {
650 assert(NISERR());
651 return;
652 }
653
654 for (a = s->outs; a != NULL && !NISERR(); a = a->outchain) {
655 duptraverse(nfa, a->to, (struct state *)NULL);
656 assert(a->to->tmp != NULL);
657 cparc(nfa, a, s->tmp, a->to->tmp);
658 }
659 }
660
661 /*
662 - cleartraverse - recursive cleanup for algorithms that leave tmp ptrs set
663 ^ static VOID cleartraverse(struct nfa *, struct state *);
664 */
665 static VOID
666 cleartraverse(nfa, s)
667 struct nfa *nfa;
668 struct state *s;
669 {
670 struct arc *a;
671
672 if (s->tmp == NULL)
673 return;
674 s->tmp = NULL;
675
676 for (a = s->outs; a != NULL; a = a->outchain)
677 cleartraverse(nfa, a->to);
678 }
679
680 /*
681 - specialcolors - fill in special colors for an NFA
682 ^ static VOID specialcolors(struct nfa *);
683 */
684 static VOID
685 specialcolors(nfa)
686 struct nfa *nfa;
687 {
688 /* false colors for BOS, BOL, EOS, EOL */
689 if (nfa->parent == NULL) {
690 nfa->bos[0] = pseudocolor(nfa->cm);
691 nfa->bos[1] = pseudocolor(nfa->cm);
692 nfa->eos[0] = pseudocolor(nfa->cm);
693 nfa->eos[1] = pseudocolor(nfa->cm);
694 } else {
695 assert(nfa->parent->bos[0] != COLORLESS);
696 nfa->bos[0] = nfa->parent->bos[0];
697 assert(nfa->parent->bos[1] != COLORLESS);
698 nfa->bos[1] = nfa->parent->bos[1];
699 assert(nfa->parent->eos[0] != COLORLESS);
700 nfa->eos[0] = nfa->parent->eos[0];
701 assert(nfa->parent->eos[1] != COLORLESS);
702 nfa->eos[1] = nfa->parent->eos[1];
703 }
704 }
705
706 /*
707 - optimize - optimize an NFA
708 ^ static long optimize(struct nfa *, FILE *);
709 */
710 static long /* re_info bits */
711 optimize(nfa, f)
712 struct nfa *nfa;
713 FILE *f; /* for debug output; NULL none */
714 {
715 int verbose = (f != NULL) ? 1 : 0;
716
717 if (verbose)
718 fprintf(f, "\ninitial cleanup:\n");
719 cleanup(nfa); /* may simplify situation */
720 if (verbose)
721 dumpnfa(nfa, f);
722 if (verbose)
723 fprintf(f, "\nempties:\n");
724 fixempties(nfa, f); /* get rid of EMPTY arcs */
725 if (verbose)
726 fprintf(f, "\nconstraints:\n");
727 pullback(nfa, f); /* pull back constraints backward */
728 pushfwd(nfa, f); /* push fwd constraints forward */
729 if (verbose)
730 fprintf(f, "\nfinal cleanup:\n");
731 cleanup(nfa); /* final tidying */
732 return analyze(nfa); /* and analysis */
733 }
734
735 /*
736 - pullback - pull back constraints backward to (with luck) eliminate them
737 ^ static VOID pullback(struct nfa *, FILE *);
738 */
739 static VOID
740 pullback(nfa, f)
741 struct nfa *nfa;
742 FILE *f; /* for debug output; NULL none */
743 {
744 struct state *s;
745 struct state *nexts;
746 struct arc *a;
747 struct arc *nexta;
748 int progress;
749
750 /* find and pull until there are no more */
751 do {
752 progress = 0;
753 for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
754 nexts = s->next;
755 for (a = s->outs; a != NULL && !NISERR(); a = nexta) {
756 nexta = a->outchain;
757 if (a->type == '^' || a->type == BEHIND)
758 if (pull(nfa, a))
759 progress = 1;
760 assert(nexta == NULL || s->no != FREESTATE);
761 }
762 }
763 if (progress && f != NULL)
764 dumpnfa(nfa, f);
765 } while (progress && !NISERR());
766 if (NISERR())
767 return;
768
769 for (a = nfa->pre->outs; a != NULL; a = nexta) {
770 nexta = a->outchain;
771 if (a->type == '^') {
772 assert(a->co == 0 || a->co == 1);
773 newarc(nfa, PLAIN, nfa->bos[a->co], a->from, a->to);
774 freearc(nfa, a);
775 }
776 }
777 }
778
779 /*
780 - pull - pull a back constraint backward past its source state
781 * A significant property of this function is that it deletes at most
782 * one state -- the constraint's from state -- and only if the constraint
783 * was that state's last outarc.
784 ^ static int pull(struct nfa *, struct arc *);
785 */
786 static int /* 0 couldn't, 1 could */
787 pull(nfa, con)
788 struct nfa *nfa;
789 struct arc *con;
790 {
791 struct state *from = con->from;
792 struct state *to = con->to;
793 struct arc *a;
794 struct arc *nexta;
795 struct state *s;
796
797 if (from == to) { /* circular constraint is pointless */
798 freearc(nfa, con);
799 return 1;
800 }
801 if (from->flag) /* can't pull back beyond start */
802 return 0;
803 if (from->nins == 0) { /* unreachable */
804 freearc(nfa, con);
805 return 1;
806 }
807
808 /* first, clone from state if necessary to avoid other outarcs */
809 if (from->nouts > 1) {
810 s = newstate(nfa);
811 if (NISERR())
812 return 0;
813 assert(to != from); /* con is not an inarc */
814 copyins(nfa, from, s); /* duplicate inarcs */
815 cparc(nfa, con, s, to); /* move constraint arc */
816 freearc(nfa, con);
817 from = s;
818 con = from->outs;
819 }
820 assert(from->nouts == 1);
821
822 /* propagate the constraint into the from state's inarcs */
823 for (a = from->ins; a != NULL; a = nexta) {
824 nexta = a->inchain;
825 switch (combine(con, a)) {
826 case INCOMPATIBLE: /* destroy the arc */
827 freearc(nfa, a);
828 break;
829 case SATISFIED: /* no action needed */
830 break;
831 case COMPATIBLE: /* swap the two arcs, more or less */
832 s = newstate(nfa);
833 if (NISERR())
834 return 0;
835 cparc(nfa, a, s, to); /* anticipate move */
836 cparc(nfa, con, a->from, s);
837 if (NISERR())
838 return 0;
839 freearc(nfa, a);
840 break;
841 default:
842 assert(NOTREACHED);
843 break;
844 }
845 }
846
847 /* remaining inarcs, if any, incorporate the constraint */
848 moveins(nfa, from, to);
849 dropstate(nfa, from); /* will free the constraint */
850 return 1;
851 }
852
853 /*
854 - pushfwd - push forward constraints forward to (with luck) eliminate them
855 ^ static VOID pushfwd(struct nfa *, FILE *);
856 */
857 static VOID
858 pushfwd(nfa, f)
859 struct nfa *nfa;
860 FILE *f; /* for debug output; NULL none */
861 {
862 struct state *s;
863 struct state *nexts;
864 struct arc *a;
865 struct arc *nexta;
866 int progress;
867
868 /* find and push until there are no more */
869 do {
870 progress = 0;
871 for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
872 nexts = s->next;
873 for (a = s->ins; a != NULL && !NISERR(); a = nexta) {
874 nexta = a->inchain;
875 if (a->type == '$' || a->type == AHEAD)
876 if (push(nfa, a))
877 progress = 1;
878 assert(nexta == NULL || s->no != FREESTATE);
879 }
880 }
881 if (progress && f != NULL)
882 dumpnfa(nfa, f);
883 } while (progress && !NISERR());
884 if (NISERR())
885 return;
886
887 for (a = nfa->post->ins; a != NULL; a = nexta) {
888 nexta = a->inchain;
889 if (a->type == '$') {
890 assert(a->co == 0 || a->co == 1);
891 newarc(nfa, PLAIN, nfa->eos[a->co], a->from, a->to);
892 freearc(nfa, a);
893 }
894 }
895 }
896
897 /*
898 - push - push a forward constraint forward past its destination state
899 * A significant property of this function is that it deletes at most
900 * one state -- the constraint's to state -- and only if the constraint
901 * was that state's last inarc.
902 ^ static int push(struct nfa *, struct arc *);
903 */
904 static int /* 0 couldn't, 1 could */
905 push(nfa, con)
906 struct nfa *nfa;
907 struct arc *con;
908 {
909 struct state *from = con->from;
910 struct state *to = con->to;
911 struct arc *a;
912 struct arc *nexta;
913 struct state *s;
914
915 if (to == from) { /* circular constraint is pointless */
916 freearc(nfa, con);
917 return 1;
918 }
919 if (to->flag) /* can't push forward beyond end */
920 return 0;
921 if (to->nouts == 0) { /* dead end */
922 freearc(nfa, con);
923 return 1;
924 }
925
926 /* first, clone to state if necessary to avoid other inarcs */
927 if (to->nins > 1) {
928 s = newstate(nfa);
929 if (NISERR())
930 return 0;
931 copyouts(nfa, to, s); /* duplicate outarcs */
932 cparc(nfa, con, from, s); /* move constraint */
933 freearc(nfa, con);
934 to = s;
935 con = to->ins;
936 }
937 assert(to->nins == 1);
938
939 /* propagate the constraint into the to state's outarcs */
940 for (a = to->outs; a != NULL; a = nexta) {
941 nexta = a->outchain;
942 switch (combine(con, a)) {
943 case INCOMPATIBLE: /* destroy the arc */
944 freearc(nfa, a);
945 break;
946 case SATISFIED: /* no action needed */
947 break;
948 case COMPATIBLE: /* swap the two arcs, more or less */
949 s = newstate(nfa);
950 if (NISERR())
951 return 0;
952 cparc(nfa, con, s, a->to); /* anticipate move */
953 cparc(nfa, a, from, s);
954 if (NISERR())
955 return 0;
956 freearc(nfa, a);
957 break;
958 default:
959 assert(NOTREACHED);
960 break;
961 }
962 }
963
964 /* remaining outarcs, if any, incorporate the constraint */
965 moveouts(nfa, to, from);
966 dropstate(nfa, to); /* will free the constraint */
967 return 1;
968 }
969
970 /*
971 - combine - constraint lands on an arc, what happens?
972 ^ #def INCOMPATIBLE 1 // destroys arc
973 ^ #def SATISFIED 2 // constraint satisfied
974 ^ #def COMPATIBLE 3 // compatible but not satisfied yet
975 ^ static int combine(struct arc *, struct arc *);
976 */
977 static int
978 combine(con, a)
979 struct arc *con;
980 struct arc *a;
981 {
982 # define CA(ct,at) (((ct)<<CHAR_BIT) | (at))
983
984 switch (CA(con->type, a->type)) {
985 case CA('^', PLAIN): /* newlines are handled separately */
986 case CA('$', PLAIN):
987 return INCOMPATIBLE;
988 break;
989 case CA(AHEAD, PLAIN): /* color constraints meet colors */
990 case CA(BEHIND, PLAIN):
991 if (con->co == a->co)
992 return SATISFIED;
993 return INCOMPATIBLE;
994 break;
995 case CA('^', '^'): /* collision, similar constraints */
996 case CA('$', '$'):
997 case CA(AHEAD, AHEAD):
998 case CA(BEHIND, BEHIND):
999 if (con->co == a->co) /* true duplication */
1000 return SATISFIED;
1001 return INCOMPATIBLE;
1002 break;
1003 case CA('^', BEHIND): /* collision, dissimilar constraints */
1004 case CA(BEHIND, '^'):
1005 case CA('$', AHEAD):
1006 case CA(AHEAD, '$'):
1007 return INCOMPATIBLE;
1008 break;
1009 case CA('^', '$'): /* constraints passing each other */
1010 case CA('^', AHEAD):
1011 case CA(BEHIND, '$'):
1012 case CA(BEHIND, AHEAD):
1013 case CA('$', '^'):
1014 case CA('$', BEHIND):
1015 case CA(AHEAD, '^'):
1016 case CA(AHEAD, BEHIND):
1017 case CA('^', LACON):
1018 case CA(BEHIND, LACON):
1019 case CA('$', LACON):
1020 case CA(AHEAD, LACON):
1021 return COMPATIBLE;
1022 break;
1023 }
1024 assert(NOTREACHED);
1025 return INCOMPATIBLE; /* for benefit of blind compilers */
1026 }
1027
1028 /*
1029 - fixempties - get rid of EMPTY arcs
1030 ^ static VOID fixempties(struct nfa *, FILE *);
1031 */
1032 static VOID
1033 fixempties(nfa, f)
1034 struct nfa *nfa;
1035 FILE *f; /* for debug output; NULL none */
1036 {
1037 struct state *s;
1038 struct state *nexts;
1039 struct arc *a;
1040 struct arc *nexta;
1041 int progress;
1042
1043 /* find and eliminate empties until there are no more */
1044 do {
1045 progress = 0;
1046 for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
1047 nexts = s->next;
1048 for (a = s->outs; a != NULL && !NISERR(); a = nexta) {
1049 nexta = a->outchain;
1050 if (a->type == EMPTY && unempty(nfa, a))
1051 progress = 1;
1052 assert(nexta == NULL || s->no != FREESTATE);
1053 }
1054 }
1055 if (progress && f != NULL)
1056 dumpnfa(nfa, f);
1057 } while (progress && !NISERR());
1058 }
1059
1060 /*
1061 - unempty - optimize out an EMPTY arc, if possible
1062 * Actually, as it stands this function always succeeds, but the return
1063 * value is kept with an eye on possible future changes.
1064 ^ static int unempty(struct nfa *, struct arc *);
1065 */
1066 static int /* 0 couldn't, 1 could */
1067 unempty(nfa, a)
1068 struct nfa *nfa;
1069 struct arc *a;
1070 {
1071 struct state *from = a->from;
1072 struct state *to = a->to;
1073 int usefrom; /* work on from, as opposed to to? */
1074
1075 assert(a->type == EMPTY);
1076 assert(from != nfa->pre && to != nfa->post);
1077
1078 if (from == to) { /* vacuous loop */
1079 freearc(nfa, a);
1080 return 1;
1081 }
1082
1083 /* decide which end to work on */
1084 usefrom = 1; /* default: attack from */
1085 if (from->nouts > to->nins)
1086 usefrom = 0;
1087 else if (from->nouts == to->nins) {
1088 /* decide on secondary issue: move/copy fewest arcs */
1089 if (from->nins > to->nouts)
1090 usefrom = 0;
1091 }
1092
1093 freearc(nfa, a);
1094 if (usefrom) {
1095 if (from->nouts == 0) {
1096 /* was the state's only outarc */
1097 moveins(nfa, from, to);
1098 freestate(nfa, from);
1099 } else
1100 copyins(nfa, from, to);
1101 } else {
1102 if (to->nins == 0) {
1103 /* was the state's only inarc */
1104 moveouts(nfa, to, from);
1105 freestate(nfa, to);
1106 } else
1107 copyouts(nfa, to, from);
1108 }
1109
1110 return 1;
1111 }
1112
1113 /*
1114 - cleanup - clean up NFA after optimizations
1115 ^ static VOID cleanup(struct nfa *);
1116 */
1117 static VOID
1118 cleanup(nfa)
1119 struct nfa *nfa;
1120 {
1121 struct state *s;
1122 struct state *nexts;
1123 int n;
1124
1125 /* clear out unreachable or dead-end states */
1126 /* use pre to mark reachable, then post to mark can-reach-post */
1127 markreachable(nfa, nfa->pre, (struct state *)NULL, nfa->pre);
1128 markcanreach(nfa, nfa->post, nfa->pre, nfa->post);
1129 for (s = nfa->states; s != NULL; s = nexts) {
1130 nexts = s->next;
1131 if (s->tmp != nfa->post && !s->flag)
1132 dropstate(nfa, s);
1133 }
1134 assert(nfa->post->nins == 0 || nfa->post->tmp == nfa->post);
1135 cleartraverse(nfa, nfa->pre);
1136 assert(nfa->post->nins == 0 || nfa->post->tmp == NULL);
1137 /* the nins==0 (final unreachable) case will be caught later */
1138
1139 /* renumber surviving states */
1140 n = 0;
1141 for (s = nfa->states; s != NULL; s = s->next)
1142 s->no = n++;
1143 nfa->nstates = n;
1144 }
1145
1146 /*
1147 - markreachable - recursive marking of reachable states
1148 ^ static VOID markreachable(struct nfa *, struct state *, struct state *,
1149 ^ struct state *);
1150 */
1151 static VOID
1152 markreachable(nfa, s, okay, mark)
1153 struct nfa *nfa;
1154 struct state *s;
1155 struct state *okay; /* consider only states with this mark */
1156 struct state *mark; /* the value to mark with */
1157 {
1158 struct arc *a;
1159
1160 if (s->tmp != okay)
1161 return;
1162 s->tmp = mark;
1163
1164 for (a = s->outs; a != NULL; a = a->outchain)
1165 markreachable(nfa, a->to, okay, mark);
1166 }
1167
1168 /*
1169 - markcanreach - recursive marking of states which can reach here
1170 ^ static VOID markcanreach(struct nfa *, struct state *, struct state *,
1171 ^ struct state *);
1172 */
1173 static VOID
1174 markcanreach(nfa, s, okay, mark)
1175 struct nfa *nfa;
1176 struct state *s;
1177 struct state *okay; /* consider only states with this mark */
1178 struct state *mark; /* the value to mark with */
1179 {
1180 struct arc *a;
1181
1182 if (s->tmp != okay)
1183 return;
1184 s->tmp = mark;
1185
1186 for (a = s->ins; a != NULL; a = a->inchain)
1187 markcanreach(nfa, a->from, okay, mark);
1188 }
1189
1190 /*
1191 - analyze - ascertain potentially-useful facts about an optimized NFA
1192 ^ static long analyze(struct nfa *);
1193 */
1194 static long /* re_info bits to be ORed in */
1195 analyze(nfa)
1196 struct nfa *nfa;
1197 {
1198 struct arc *a;
1199 struct arc *aa;
1200
1201 if (nfa->pre->outs == NULL)
1202 return REG_UIMPOSSIBLE;
1203 for (a = nfa->pre->outs; a != NULL; a = a->outchain)
1204 for (aa = a->to->outs; aa != NULL; aa = aa->outchain)
1205 if (aa->to == nfa->post)
1206 return REG_UEMPTYMATCH;
1207 return 0;
1208 }
1209
1210 /*
1211 - compact - compact an NFA
1212 ^ static VOID compact(struct nfa *, struct cnfa *);
1213 */
1214 static VOID
1215 compact(nfa, cnfa)
1216 struct nfa *nfa;
1217 struct cnfa *cnfa;
1218 {
1219 struct state *s;
1220 struct arc *a;
1221 size_t nstates;
1222 size_t narcs;
1223 struct carc *ca;
1224 struct carc *first;
1225
1226 assert (!NISERR());
1227
1228 nstates = 0;
1229 narcs = 0;
1230 for (s = nfa->states; s != NULL; s = s->next) {
1231 nstates++;
1232 narcs += 1 + s->nouts + 1;
1233 /* 1 as a fake for flags, nouts for arcs, 1 as endmarker */
1234 }
1235
1236 cnfa->states = (struct carc **)MALLOC(nstates * sizeof(struct carc *));
1237 cnfa->arcs = (struct carc *)MALLOC(narcs * sizeof(struct carc));
1238 if (cnfa->states == NULL || cnfa->arcs == NULL) {
1239 if (cnfa->states != NULL)
1240 FREE(cnfa->states);
1241 if (cnfa->arcs != NULL)
1242 FREE(cnfa->arcs);
1243 NERR(REG_ESPACE);
1244 return;
1245 }
1246 cnfa->nstates = nstates;
1247 cnfa->pre = nfa->pre->no;
1248 cnfa->post = nfa->post->no;
1249 cnfa->bos[0] = nfa->bos[0];
1250 cnfa->bos[1] = nfa->bos[1];
1251 cnfa->eos[0] = nfa->eos[0];
1252 cnfa->eos[1] = nfa->eos[1];
1253 cnfa->ncolors = maxcolor(nfa->cm) + 1;
1254 cnfa->flags = 0;
1255
1256 ca = cnfa->arcs;
1257 for (s = nfa->states; s != NULL; s = s->next) {
1258 assert((size_t)s->no < nstates);
1259 cnfa->states[s->no] = ca;
1260 ca->co = 0; /* clear and skip flags "arc" */
1261 ca++;
1262 first = ca;
1263 for (a = s->outs; a != NULL; a = a->outchain)
1264 switch (a->type) {
1265 case PLAIN:
1266 ca->co = a->co;
1267 ca->to = a->to->no;
1268 ca++;
1269 break;
1270 case LACON:
1271 assert(s->no != cnfa->pre);
1272 ca->co = (color)(cnfa->ncolors + a->co);
1273 ca->to = a->to->no;
1274 ca++;
1275 cnfa->flags |= HASLACONS;
1276 break;
1277 default:
1278 assert(NOTREACHED);
1279 break;
1280 }
1281 carcsort(first, ca-1);
1282 ca->co = COLORLESS;
1283 ca->to = 0;
1284 ca++;
1285 }
1286 assert(ca == &cnfa->arcs[narcs]);
1287 assert(cnfa->nstates != 0);
1288
1289 /* mark no-progress states */
1290 for (a = nfa->pre->outs; a != NULL; a = a->outchain)
1291 cnfa->states[a->to->no]->co = 1;
1292 cnfa->states[nfa->pre->no]->co = 1;
1293 }
1294
1295 /*
1296 - carcsort - sort compacted-NFA arcs by color
1297 * Really dumb algorithm, but if the list is long enough for that to matter,
1298 * you're in real trouble anyway.
1299 ^ static VOID carcsort(struct carc *, struct carc *);
1300 */
1301 static VOID
1302 carcsort(first, last)
1303 struct carc *first;
1304 struct carc *last;
1305 {
1306 struct carc *p;
1307 struct carc *q;
1308 struct carc tmp;
1309
1310 if (last - first <= 1)
1311 return;
1312
1313 for (p = first; p <= last; p++)
1314 for (q = p; q <= last; q++)
1315 if (p->co > q->co ||
1316 (p->co == q->co && p->to > q->to)) {
1317 assert(p != q);
1318 tmp = *p;
1319 *p = *q;
1320 *q = tmp;
1321 }
1322 }
1323
1324 /*
1325 - freecnfa - free a compacted NFA
1326 ^ static VOID freecnfa(struct cnfa *);
1327 */
1328 static VOID
1329 freecnfa(cnfa)
1330 struct cnfa *cnfa;
1331 {
1332 assert(cnfa->nstates != 0); /* not empty already */
1333 cnfa->nstates = 0;
1334 FREE(cnfa->states);
1335 FREE(cnfa->arcs);
1336 }
1337
1338 /*
1339 - dumpnfa - dump an NFA in human-readable form
1340 ^ static VOID dumpnfa(struct nfa *, FILE *);
1341 */
1342 static VOID
1343 dumpnfa(nfa, f)
1344 struct nfa *nfa;
1345 FILE *f;
1346 {
1347 #ifdef REG_DEBUG
1348 struct state *s;
1349
1350 fprintf(f, "pre %d, post %d", nfa->pre->no, nfa->post->no);
1351 if (nfa->bos[0] != COLORLESS)
1352 fprintf(f, ", bos [%ld]", (long)nfa->bos[0]);
1353 if (nfa->bos[1] != COLORLESS)
1354 fprintf(f, ", bol [%ld]", (long)nfa->bos[1]);
1355 if (nfa->eos[0] != COLORLESS)
1356 fprintf(f, ", eos [%ld]", (long)nfa->eos[0]);
1357 if (nfa->eos[1] != COLORLESS)
1358 fprintf(f, ", eol [%ld]", (long)nfa->eos[1]);
1359 fprintf(f, "\n");
1360 for (s = nfa->states; s != NULL; s = s->next)
1361 dumpstate(s, f);
1362 if (nfa->parent == NULL)
1363 dumpcolors(nfa->cm, f);
1364 fflush(f);
1365 #endif
1366 }
1367
1368 #ifdef REG_DEBUG /* subordinates of dumpnfa */
1369 /*
1370 ^ #ifdef REG_DEBUG
1371 */
1372
1373 /*
1374 - dumpstate - dump an NFA state in human-readable form
1375 ^ static VOID dumpstate(struct state *, FILE *);
1376 */
1377 static VOID
1378 dumpstate(s, f)
1379 struct state *s;
1380 FILE *f;
1381 {
1382 struct arc *a;
1383
1384 fprintf(f, "%d%s%c", s->no, (s->tmp != NULL) ? "T" : "",
1385 (s->flag) ? s->flag : '.');
1386 if (s->prev != NULL && s->prev->next != s)
1387 fprintf(f, "\tstate chain bad\n");
1388 if (s->nouts == 0)
1389 fprintf(f, "\tno out arcs\n");
1390 else
1391 dumparcs(s, f);
1392 fflush(f);
1393 for (a = s->ins; a != NULL; a = a->inchain) {
1394 if (a->to != s)
1395 fprintf(f, "\tlink from %d to %d on %d's in-chain\n",
1396 a->from->no, a->to->no, s->no);
1397 }
1398 }
1399
1400 /*
1401 - dumparcs - dump out-arcs in human-readable form
1402 ^ static VOID dumparcs(struct state *, FILE *);
1403 */
1404 static VOID
1405 dumparcs(s, f)
1406 struct state *s;
1407 FILE *f;
1408 {
1409 int pos;
1410
1411 assert(s->nouts > 0);
1412 /* printing arcs in reverse order is usually clearer */
1413 pos = dumprarcs(s->outs, s, f, 1);
1414 if (pos != 1)
1415 fprintf(f, "\n");
1416 }
1417
1418 /*
1419 - dumprarcs - dump remaining outarcs, recursively, in reverse order
1420 ^ static int dumprarcs(struct arc *, struct state *, FILE *, int);
1421 */
1422 static int /* resulting print position */
1423 dumprarcs(a, s, f, pos)
1424 struct arc *a;
1425 struct state *s;
1426 FILE *f;
1427 int pos; /* initial print position */
1428 {
1429 if (a->outchain != NULL)
1430 pos = dumprarcs(a->outchain, s, f, pos);
1431 dumparc(a, s, f);
1432 if (pos == 5) {
1433 fprintf(f, "\n");
1434 pos = 1;
1435 } else
1436 pos++;
1437 return pos;
1438 }
1439
1440 /*
1441 - dumparc - dump one outarc in readable form, including prefixing tab
1442 ^ static VOID dumparc(struct arc *, struct state *, FILE *);
1443 */
1444 static VOID
1445 dumparc(a, s, f)
1446 struct arc *a;
1447 struct state *s;
1448 FILE *f;
1449 {
1450 struct arc *aa;
1451 struct arcbatch *ab;
1452
1453 fprintf(f, "\t");
1454 switch (a->type) {
1455 case PLAIN:
1456 fprintf(f, "[%ld]", (long)a->co);
1457 break;
1458 case AHEAD:
1459 fprintf(f, ">%ld>", (long)a->co);
1460 break;
1461 case BEHIND:
1462 fprintf(f, "<%ld<", (long)a->co);
1463 break;
1464 case LACON:
1465 fprintf(f, ":%ld:", (long)a->co);
1466 break;
1467 case '^':
1468 case '$':
1469 fprintf(f, "%c%d", a->type, (int)a->co);
1470 break;
1471 case EMPTY:
1472 break;
1473 default:
1474 fprintf(f, "0x%x/0%lo", a->type, (long)a->co);
1475 break;
1476 }
1477 if (a->from != s)
1478 fprintf(f, "?%d?", a->from->no);
1479 for (ab = &a->from->oas; ab != NULL; ab = ab->next) {
1480 for (aa = &ab->a[0]; aa < &ab->a[ABSIZE]; aa++)
1481 if (aa == a)
1482 break; /* NOTE BREAK OUT */
1483 if (aa < &ab->a[ABSIZE]) /* propagate break */
1484 break; /* NOTE BREAK OUT */
1485 }
1486 if (ab == NULL)
1487 fprintf(f, "?!?"); /* not in allocated space */
1488 fprintf(f, "->");
1489 if (a->to == NULL) {
1490 fprintf(f, "NULL");
1491 return;
1492 }
1493 fprintf(f, "%d", a->to->no);
1494 for (aa = a->to->ins; aa != NULL; aa = aa->inchain)
1495 if (aa == a)
1496 break; /* NOTE BREAK OUT */
1497 if (aa == NULL)
1498 fprintf(f, "?!?"); /* missing from in-chain */
1499 }
1500
1501 /*
1502 ^ #endif
1503 */
1504 #endif /* ifdef REG_DEBUG */
1505
1506 /*
1507 - dumpcnfa - dump a compacted NFA in human-readable form
1508 ^ static VOID dumpcnfa(struct cnfa *, FILE *);
1509 */
1510 static VOID
1511 dumpcnfa(cnfa, f)
1512 struct cnfa *cnfa;
1513 FILE *f;
1514 {
1515 #ifdef REG_DEBUG
1516 int st;
1517
1518 fprintf(f, "pre %d, post %d", cnfa->pre, cnfa->post);
1519 if (cnfa->bos[0] != COLORLESS)
1520 fprintf(f, ", bos [%ld]", (long)cnfa->bos[0]);
1521 if (cnfa->bos[1] != COLORLESS)
1522 fprintf(f, ", bol [%ld]", (long)cnfa->bos[1]);
1523 if (cnfa->eos[0] != COLORLESS)
1524 fprintf(f, ", eos [%ld]", (long)cnfa->eos[0]);
1525 if (cnfa->eos[1] != COLORLESS)
1526 fprintf(f, ", eol [%ld]", (long)cnfa->eos[1]);
1527 if (cnfa->flags&HASLACONS)
1528 fprintf(f, ", haslacons");
1529 fprintf(f, "\n");
1530 for (st = 0; st < cnfa->nstates; st++)
1531 dumpcstate(st, cnfa->states[st], cnfa, f);
1532 fflush(f);
1533 #endif
1534 }
1535
1536 #ifdef REG_DEBUG /* subordinates of dumpcnfa */
1537 /*
1538 ^ #ifdef REG_DEBUG
1539 */
1540
1541 /*
1542 - dumpcstate - dump a compacted-NFA state in human-readable form
1543 ^ static VOID dumpcstate(int, struct carc *, struct cnfa *, FILE *);
1544 */
1545 static VOID
1546 dumpcstate(st, ca, cnfa, f)
1547 int st;
1548 struct carc *ca;
1549 struct cnfa *cnfa;
1550 FILE *f;
1551 {
1552 int i;
1553 int pos;
1554
1555 fprintf(f, "%d%s", st, (ca[0].co) ? ":" : ".");
1556 pos = 1;
1557 for (i = 1; ca[i].co != COLORLESS; i++) {
1558 if (ca[i].co < cnfa->ncolors)
1559 fprintf(f, "\t[%ld]->%d", (long)ca[i].co, ca[i].to);
1560 else
1561 fprintf(f, "\t:%ld:->%d", (long)ca[i].co-cnfa->ncolors,
1562 ca[i].to);
1563 if (pos == 5) {
1564 fprintf(f, "\n");
1565 pos = 1;
1566 } else
1567 pos++;
1568 }
1569 if (i == 1 || pos != 1)
1570 fprintf(f, "\n");
1571 fflush(f);
1572 }
1573
1574 /*
1575 ^ #endif
1576 */
1577 #endif /* ifdef REG_DEBUG */
1578
1579 /* $History: regc_nfa.c $
1580 *
1581 * ***************** Version 1 *****************
1582 * User: Dtashley Date: 1/02/01 Time: 12:04a
1583 * Created in $/IjuScripter, IjuConsole/Source/Tcl Base
1584 * Initial check-in.
1585 */
1586
1587 /* End of REGC_NFA.C */

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25