typedef enum regtype {
    regchar, regcharset, regdot, regempty, regbol, regeol,
    regconcat, regalternate, regoptional, regstar, regplus,
} Regtype;

typedef unsigned long u_long;
typedef u_long Set[8];

typedef struct regexp Regexp;
typedef struct machine Machine;
typedef struct state State;
typedef struct transition Transition;

#define alloc(type) ((type *) malloc(sizeof(type)))
#define LAMBDA -1
#define MAXSTATES 256

struct regexp {
    Regtype regtype;
    union {
	Regexp *arg;
	Regexp *pair[2];
	char ch;
	Set chset;
    } data;
};

struct machine {
    Regexp *regexp;
    int numStates;
    State *states[MAXSTATES];
};

struct state {
    Machine *machine;
    

Regexp *RegexpParse(char **);

/*
 * Sets
 */

void SetClear(Set set)
{
    bzero(set, sizeof(set));
}

void SetAdd(Set set, int state)
{
    set[state>>5] |= (1<<(state & 31));
}

int InSet(Set set, int state)
{
    return set[state>>5] & (1<<(state & 31));
}


/***********************************************************************
 * Regexp read and print
 */

void RPcharset (char **c, Set s)
{
    int invert = 0;
    char ch, ch2;

    SetClear(s);
    (*c)++;
    if (**c == '^') {
	invert = 1;
	(*c)++;
    }
    if (**c == '-') {
	SetAdd(s, **c);
	(*c)++;
    }
    if (**c == ']') {
	SetAdd(s, **c);
	(*c)++;
    }
    while ((ch = **c) && (ch != ']')) {
	(*c)++;
	if (**c == '-') {
	    (*c)++;
	    ch2 = **c;
	    if (!ch2) return;
	    (*c)++;
	    while (ch != ch2) 
		SetAdd(s, ch++);
	}
	SetAdd(s, ch);
    }
    if (**c) (*c)++;

    if (invert) {
	int n;
	Set s2;

	bcopy (s, s2, sizeof(s));
	SetClear(s);
	for (n = 0; n <= 255; n++)
	    if (!InSet(s2, n))
		SetAdd(s, n);
    }
}

void RPchar (char **c, char *char_ret)
{
    if (**c == '\\')
	(*c)++;
    if (*char_ret = **c)
	(*c)++;
}
	

Regexp *RP3(char **c)
{
    Regexp *unit = alloc(Regexp);
    Regexp *post;
    
    switch (**c) {

      case '[':
	unit->regtype = regcharset;
	RPcharset(c, unit->data.chset);
	break;

      case '(':
	(*c)++;
	free(unit);			/* oops */
	unit = RegexpParse(c);
	if (**c == ')')
	    (*c)++;
	else
	    ;				/* maybe signal an error?  nah. */
	break;
	
      case '^':
      case '$':
      case '.':
      case ')':
      case 0:
	if ((unit->regtype = (**c == '^' ? regbol :
			      **c == '$' ? regeol :
			      **c == '.' ? regdot :
			      regempty)) != regempty)
	    (*c)++;
	break;
	
      default:
	RPchar(c, &unit->data.ch);
	break;
    }
    switch (**c) {
      case '*':
      case '+':
      case '?':
	post = alloc(Regexp);
	post->regtype = (**c == '*' ? regstar :
			 **c == '+' ? regplus :
			 regoptional);
	post->data.arg = unit;
	(*c)++;
	return post;
    }
    return unit;
}

Regexp *RP2(char **c)
{
    Regexp *first = RP3(c);
    if (**c && (**c != '|') && (**c != ')')) {
	Regexp *second = RP2(c);
	Regexp *concat = alloc(Regexp);
	concat->regtype = regconcat;
	concat->data.pair[0] = first;
	concat->data.pair[1] = second;
	return concat;
    } else
	return first;
}

Regexp *RP1(char **c)
{
    Regexp *first = RP2(c);
    if (**c == '|') {
	(*c)++;
	Regexp *second = RP1(c);
	Regexp *alt = alloc(Regexp);
	alt->regtype = regalternate;
	alt->data.pair[0] = first;
	alt->data.pair[1] = second;
	return alt;
    } else
	return first;
}

    
Regexp *RegexpParse(char **c)
{
    return RP1(c);
}


void RegexpPrint (Regexp *r)
{
    int c;

    switch (r->regtype) {
      case regchar:
	putchar(r->data.ch); break;
      case regcharset:
	putchar('[');
	for (c = 0; c <= 255; c++)
	    if (InSet(r->data.chset, c))
		if (c >= 32 && c <= 126)
		    putchar(c);
		else
		    printf ("'%d", c);
	putchar(']');
	break;
      case regdot:
	printf ("dot"); break;
      case regempty:
	printf ("nil"); break;
      case regbol:
	printf ("bol"); break;
      case regeol:
	printf ("eol"); break;
      case regconcat:
      case regalternate:
	printf ("(");
	RegexpPrint (r->data.pair[0]);
	if (r->regtype == regalternate)
	    printf (" | ");
	RegexpPrint (r->data.pair[1]);
	printf (")");
	break;
      case regoptional:
      case regstar:
      case regplus:
	RegexpPrint (r->data.arg);
	printf (r->regtype == regoptional ? "?" :
		r->regtype == regplus ? "+" : "*");
        break;
    }
}
	

/***********************************************************************
 * Stuff for machines
 */

Machine *RegexpCompile(Regexp *r)
{
    

main()
{
    char rtext[200];
    char *c;
    Regexp *regexp;
    Machine *machine;
    
    while (1) {
	printf ("\nEnter regexp: ");
	if (!gets(rtext)) exit(0);
	c = rtext;
	regexp = RegexpParse(&c);
	RegexpPrint(regexp);
	printf ("\n");
	machine = RegexpCompile(regexp);
	MachinePrint(machine);
    }
}