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 */ |