#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define	MAX_ENDS 10

#define	S_SPLIT 256
#define	S_MATCH 257

/* Operators, ordered by ascending precedence */
typedef enum ops {
	OP_START,	/* Sentinel, implicit */
	OP_END,		/* Implicit */
	OP_CHAR,
	OP_RPAR,
	OP_LPAR,
	OP_OR,
	OP_CONCAT,	/* Implicit */
	OP_STAR,
} optype_t;

struct state {
	int c;
	struct state *next;
	struct state *next2;
};

struct expr {
	struct state *start;
	struct state **ptrs[MAX_ENDS];
	int nptrs;
};

int tokval;
struct expr exprstack[10];
struct expr *exprp = exprstack;
optype_t opstack[10];
optype_t *opp = opstack;
int need_concat;

static struct state *
new_state(int c, struct state *next, struct state *next2)
{
	struct state *s;

	s = malloc(sizeof(struct state));
	s->c = c;
	s->next = next;
	s->next2 = next2;

	return (s);
}

void
patch(struct expr *e, struct state *s)
{
	int i;

	for (i = 0; i < e->nptrs; i++)
		*e->ptrs[i] = s;
}

optype_t
next_token(char **s)
{
	char c;

	c = *(*s)++;

	switch (c) {
	case '\0':
		return (OP_END);
	case '(':
		return (OP_LPAR);	
	case ')':
		return (OP_RPAR);
	case '*':
		return (OP_STAR);
	case '|':
		return (OP_OR);
	case '\\':
		tokval = *(*s)++;
		return (OP_CHAR);
	default:
		tokval = c;
		return (OP_CHAR);
	}
}

void
push_expr(struct state *start, struct state **ptr)
{
	struct expr *e;

	e = exprp++;
	e->start = start;
	*e->ptrs = ptr;
	e->nptrs = 1;
}

void
push_expr_arr(struct state *start, struct state **ptrs[], int n)
{
	struct expr *e;

	e = exprp++;
	e->start = start;
	e->nptrs = n;
	memcpy(e->ptrs, ptrs, n * sizeof(struct state *));
}

struct expr *
pop_expr()
{
	return (--exprp);
}

void
push_op(optype_t op)
{
	*opp++ = op;
}

optype_t
pop_op()
{
	*opp = OP_START;
	return (*--opp);
}

void
evalopsuntil(optype_t op)
{
	struct state *new;
	struct expr *e1, *e2;
	optype_t cur;
	int i;

	while (*(opp-1) >= op) {
		cur = pop_op();
		if (cur == OP_STAR) {
			e1 = pop_expr();
			new = new_state(S_SPLIT, e1->start, NULL);
			patch(e1, new);
			push_expr(new, &new->next2);
		} else if (cur == OP_CONCAT) {
			e2 = pop_expr();
			e1 = pop_expr();
			patch(e1, e2->start);
			push_expr_arr(e1->start, e2->ptrs, e2->nptrs);
		} else if (cur == OP_OR) {
			e2 = pop_expr();
			e1 = pop_expr();
			new = new_state(S_SPLIT, e1->start, e2->start);
			/* XXX overflow */
			for (i = 0; i < e2->nptrs; i++)
				e1->ptrs[e1->nptrs + i] = e2->ptrs[i];
			push_expr_arr(new, e1->ptrs, e1->nptrs + e2->nptrs);
		} else if (cur == OP_START)
			break;
	}
}

void
operator(optype_t op)
{
	if (*(opp - 1) >= op) {
		evalopsuntil(op);
		if (op != OP_RPAR)
			push_op(op);
	} else
		push_op(op);

	if (op == OP_RPAR && need_concat)
		operator(OP_CONCAT);

	if (op == OP_STAR || op == OP_RPAR)
		need_concat = 1;
	else
		need_concat = 0;
}

struct state *
compile(char *s)
{
	struct state *new, *start;
	struct expr *e;
	int op;

	need_concat = 0;
	start = NULL;
	opp = opstack;
	exprp = exprstack;
	push_op(OP_START);

	while (1) {
		op = next_token(&s);
		if (op == OP_END)
			break;
		if (op == OP_CHAR) {
			if (need_concat)
				operator(OP_CONCAT);

			new = new_state(tokval, NULL, NULL);
			push_expr(new, &new->next);

			need_concat = 1;
		} else
			operator(op);
	}

	evalopsuntil(OP_START);
	e = pop_expr();
	new = new_state(S_MATCH, NULL, NULL);
	patch(e, new);

	return (e->start);
}

int
main(void)
{
	compile("a(b|c)*d");
	compile("abcd");
	compile("a(b|c)d");
	compile("a(bb)*a");
	compile("a(bc)d");
	compile("ab*cd");
	compile("a(bc)*d");
	compile("a(b|c)d");
	compile("a(bc|de)fg");

	return (0);
}