extern struct fa
*cgotofn();
#define left(v) v->narg[0]
#define right(v) v->narg[1]
#define parent(v) v->nnext
#define LEAF case CCL: case NCCL: case CHAR: case DOT:
#define UNARY case FINAL: case STAR: case PLUS: case QUEST:
/* encoding in tree nodes:
leaf (CCL, NCCL, CHAR, DOT): left is index, right contains value or pointer to value
unary (FINAL, STAR, PLUS, QUEST): left is child, right is null
binary (CAT, OR): left and right are children
parent contains pointer to parent
struct fa
*makedfa(p
) /* returns dfa for tree pointed to by p */
p1
= op2(CAT
, op2(STAR
, op2(DOT
, (node
*) 0, (node
*) 0), (node
*) 0), p
);
/* put DOT STAR in front of reg. exp. */
p1
= op2(FINAL
, p1
, (node
*) 0); /* install FINAL node */
penter(p1
); /* enter parent pointers and leaf indices */
point
[line
] = p1
; /* FINAL node */
setvec
[0] = 1; /* for initial DOT STAR */
cfoll(p1
); /* set up follow sets */
freetr(p1
); /* add this when alloc works */
penter(p
) /* set up parent pointers and leaf indices */
error(FATAL
, "unknown type %d in penter\n", type(p
));
freetr(p
) /* free parse tree and follow sets */
xfree(foll
[(int) left(p
)]);
error(FATAL
, "unknown type %d in freetr", type(p
));
while ((c
= *p
++) != 0) {
if (c
== '-' && i
> 0 && chars
[i
-1] != 0) {
dprintf("cclenter: in = |%s|, out = |%s|\n", op
, chars
, NULL
);
error(FATAL
, "regular expression too long\n");
cfoll(v
) /* enter follow set of each leaf of vertex v into foll[leaf] */
if (notin(foll
, ( (int) left(v
))-1, &prev
)) {
foll
[(int) left(v
)] = add(setcnt
);
foll
[ (int) left(v
)] = foll
[prev
];
error(FATAL
, "unknown type %d in cfoll", type(v
));
first(p
) /* collects initially active leaves of p into setvec */
register node
*p
; /* returns 0 or 1 depending on whether p matches empty string */
if (setvec
[(int) left(p
)] != 1) {
setvec
[(int) left(p
)] = 1;
if (type(p
) == CCL
&& (*(char *) right(p
)) == '\0')
return(0); /* empty CCL */
if (first(left(p
)) == 0) return(0);
if (first(left(p
)) == 0 && first(right(p
)) == 0) return(0);
if (first(left(p
)) == 0 || b
== 0) return(0);
error(FATAL
, "unknown type %d in first\n", type(p
));
node
*v
; /* collects leaves that can follow v into setvec */
case CAT
: if (v
== left(p
)) { /* v is left child of p */
if (first(right(p
)) == 0) {
else /* v is right child */
case FINAL
: if (setvec
[line
] != 1) {
member(c
, s
) /* is c in s? */
notin(array
, n
, prev
) /* is setvec in array[0] thru array[n]? */
for (j
=0; j
< setcnt
; j
++)
if (setvec
[*(++ptr
)] != 1) goto nxt
;
int *add(n
) { /* remember setvec */
if ((p
= ptr
= (int *) malloc((n
+1)*sizeof(int))) == NULL
)
dprintf("add(%d)\n", n
, NULL
, NULL
);
for (i
=1; i
<= line
; i
++)
dprintf(" ptr = %o, *ptr = %d, i = %d\n", ptr
, *ptr
, i
);
dprintf("\n", NULL
, NULL
, NULL
);
int j
, n
, s
, ind
, numtrans
;
struct fa
*where
[NSTATES
];
for (i
=0; i
<=line
; i
++) index
[i
] = iposns
[i
] = setvec
[i
] = 0;
for (i
=0; i
<NCHARS
; i
++) isyms
[i
] = symbol
[i
] = 0;
/* compute initial positions and symbols of state 0 */
ptr
= state
[0] = foll
[0];
for (i
=0; i
<spinit
; i
++) {
dprintf("i = %d, spinit = %d, curpos = %d\n", i
, spinit
, curpos
);
for (k
=1; k
<NCHARS
; k
++) {
for (p
= (char *) right(cp
); *p
; p
++) {
for (k
=1; k
<NCHARS
; k
++) {
if (k
!= HAT
&& !member(k
, (char *) right(cp
))) {
dprintf("s = %d\n", s
, NULL
, NULL
);
if (*(state
[s
] + *state
[s
]) == line
) { /* s final? */
if (iposns
[curpos
] != 1 && index
[curpos
] != 1) {
sposns
[spmax
++] = curpos
;
if (isyms
[k
] == 0 && symbol
[k
] == 0) {
for (k
=1; k
<NCHARS
; k
++) {
if (isyms
[k
] == 0 && symbol
[k
] == 0) {
for (p
= (char *) right(cp
); *p
; p
++) {
if (isyms
[*p
] == 0 && symbol
[*p
] == 0) {
for (k
=1; k
<NCHARS
; k
++) {
if (k
!= HAT
&& !member(k
, (char *) right(cp
))) {
if (isyms
[k
] == 0 && symbol
[k
] == 0) {
for (j
=0; j
<ssmax
; j
++) { /* nextstate(s, ssyms[j]) */
for (k
=0; k
<=line
; k
++) setvec
[k
] = 0;
for (i
=0; i
<spmax
; i
++) {
if ((k
= type(cp
)) != FINAL
)
if (k
== CHAR
&& c
== (int) right(cp
)
|| k
== CCL
&& member(c
, (char *) right(cp
))
|| k
== NCCL
&& !member(c
, (char *) right(cp
))) {
if (setvec
[*(++ptr
)] != 1
if (notin(state
, n
, &prev
)) {
dprintf("cgotofn: notin; state = %d, n = %d\n", state
, n
, NULL
);
state
[++n
] = add(setcnt
);
dprintf(" delta(%d,%o) = %d", s
,c
,n
);
dprintf(", ind = %d\n", ind
+1, NULL
, NULL
);
dprintf(" delta(%d,%o) = %d", s
,c
,prev
);
dprintf(", ind = %d\n", ind
+1, NULL
, NULL
);
if ((pfa
= (struct fa
*) malloc((numtrans
+ 1) * sizeof(struct fa
))) == NULL
)
pfa
->cch
= -1; /* s is a final state */
for (i
=1, pfa
+= 1; i
<=numtrans
; i
++, pfa
++) {
pfa
->st
= (struct fa
*) fatab
[2*i
];
xfree(state
[i
]); /* free state[i] */
dprintf("state %d: (%o)\n", i
, pfa
, NULL
);
dprintf(" numtrans = %d, default = %o\n", pfa
->cch
, pfa
->st
, NULL
);
for (k
=1; k
<=pfa
->cch
; k
++) {
(pfa
+k
)->st
= where
[ (int) (pfa
+k
)->st
];
dprintf(" char = %o, nextstate = %o\n",(pfa
+k
)->cch
, (pfa
+k
)->st
, NULL
);
if ((num
= pfa
->cch
) < 0)
for (pfa
+= num
; num
; num
--, pfa
--)
if (pfa
->cch
== 1) { /* fast test for first character, if possible */
adv
: if ((count
= pfa
->cch
) < 0) return(1);
for (pfa
+= count
; count
; count
--, pfa
--)
if ((count
= pfa
->cch
) < 0) return(1);