/* the functions in this file take a syntax tree for a regular   expression and produce a DFA using the McNaughton-Yamada   construction.						*/#include <stdio.h>#include "re.h"extern char *strncpy(), *strcat(), *strcpy();extern int  strlen();#define TRUE	1extern char *malloc();extern Pset pset_union(); extern int pos_cnt;extern Re_node parse();Re_lit_array lpos; /*  extend_re() extends the RE by adding a ".*(" at the front and a "("    at the back.						   	*/char *extend_re(s)char *s;{    char *s1;    s1 = malloc((unsigned) strlen(s)+4+1);    return strcat(strcat(strcpy(s1, ".*("), s), ")");}/* mk_followpos() takes a syntax tree for a regular expression and   traverses it once, computing the followpos function at each node   and returns a pointer to an array whose ith element is a pointer   to a list of position nodes, representing the positions in   followpos(i).							*/void mk_followpos_1(e, fpos)Re_node e;Pset_array fpos;{    Pset pos;    int i;    switch (Op(e)) {	case EOS: break;	case OPSTAR:	    pos = Lastpos(e);	    while (pos != NULL) {		i = pos->posnum;		(*fpos)[i] = pset_union(Firstpos(e), (*fpos)[i]);		pos = pos->nextpos;	    }	    mk_followpos_1(Child(e), fpos);	    break;	case OPCAT:	    pos = Lastpos(Lchild(e));	    while (pos != NULL) {		i = pos->posnum;		(*fpos)[i] = pset_union(Firstpos(Rchild(e)), (*fpos)[i]);		pos = pos->nextpos;	    }	    mk_followpos_1(Lchild(e), fpos);	    mk_followpos_1(Rchild(e), fpos);	    break;	case OPOPT:	    mk_followpos_1(Child(e), fpos);	    break;	case OPALT:	    mk_followpos_1(Lchild(e), fpos);	    mk_followpos_1(Rchild(e), fpos);	    break;	case LITERAL:	    break;	default: printf("mk_followpos: unknown node type %d\n", Op(e));    }    return;}Pset_array mk_followpos(tree, npos)Re_node tree;int npos;{    int i;    Pset_array fpos;    if (tree == NULL || npos < 0) return NULL;    fpos = (Pset_array) malloc((unsigned) (npos+1)*sizeof(Pset));    if (fpos == NULL) return NULL;    for (i = 0; i <= npos; i++) (*fpos)[i] = NULL;    mk_followpos_1(tree, fpos);    return fpos;}/* mk_poslist() sets a static array whose i_th element is a pointer to   the RE-literal at position i.  It returns 1 if everything is OK,  0   otherwise.								*//* init performs initialization actions; it returns -1 in case of error,   0 if everything goes OK.						*/int init(s, table)char *s; int table[32][32];{    Pset_array fpos;    Re_node e;    Pset l;    int i, j;    if ((e = parse(extend_re(s))) == NULL) return -1;    if ((fpos = mk_followpos(e, pos_cnt)) == NULL) return -1;    for (i = 0; i <= pos_cnt; i += 1) {#ifdef Debug	printf("followpos[%d] = ", i);#endif        l = (*fpos)[i];        j = 0;        for ( ; l != NULL; l = l->nextpos)  {#ifdef Debug            printf("%d ", l->posnum);#endif            table[i][j] = l->posnum;            j++;        } #ifdef Debug        printf("\n");#endif    }#ifdef Debug    for (i=0; i <= pos_cnt; i += 1)  {       j = 0;       while (table[i][j] != 0) {          printf(" %d ", table[i][j]);          j++;      }      printf("\n");   }#endif    return (pos_cnt);}