my-nfa.c

这是我自己写的将正则表达式的parser

#include <stdio.h>
#include <unistd.h>

struct frame {
	int n_pair;
};

struct state {
	int c;
	struct state *out;
	struct state *out1;
	int lastlist;
};

typedef struct state state_t;

struct frame f[100] = {0};
struct frame *pf;

char *postfix(char *regex)
{
	int n_pair = 0;
	static char buf[1024];
	char *dst = buf;
	pf = f;

	if (strlen(regex) * 2 >= 1024) {
		printf("too long regex.\n");
		exit(0);
	}

	while (*regex) {
		switch (*regex) {
			default:
				if (n_pair > 1) {
					*dst = '.';
					dst++;
					n_pair = 1;
				}
				*dst++ = *regex++;
				n_pair ++;
				break;
			case '(':
				if (n_pair > 1) {
					*dst = '.';
					dst++;
					n_pair = 1;
				}
				pf->n_pair = n_pair;
				printf("( n_pair = %d\n", pf->n_pair);
				pf++;
				regex++;
				n_pair = 0;
				break;
			case ')':
				pf--;
				if (n_pair > 1) {
					printf("1111\n");
					*dst++ = '.';
				}
				if (pf->n_pair > 0) {
					printf("222\n");
					*dst++ = '.';
				}
				n_pair = 1;
				regex++;
				break;
			case '?':
			case '+':
			case '*':
				*dst++ = *regex++;
#if 0
				if (n_pair > 0) {
					*dst++ = '.';
				}
				n_pair --;
#endif
				break;
		}
	}

	if (n_pair > 1) {
		printf("33333\n");
		*dst++ = '.';
	}
	*dst = '\0';
	printf("the postfix string is %s\n", buf);

	return buf;
}

struct out_list {
	struct state **s;
	struct out_list *next;
};

typedef struct out_list out_list_t;

struct frag {
	struct state *start;
	struct out_list *out;
};

typedef struct frag frag_t;

struct state *state(int c, struct state *out, struct state *out1)
{
	struct state *s;

	s = malloc(sizeof(struct state));
	memset(s, 0, sizeof(*s));
	s->c = c;
	s->out = out;
	s->out1 = out1;

	return s;
}

struct frag *_frag(struct state *start, out_list_t *out)
{
	struct frag *f;
	out_list_t *o;

	f = malloc(sizeof(struct frag));
	memset(f, 0, sizeof(*f));
	f->start = start;
	f->out = out;
#if 0
	/*
	 * only the header for the out list, can't hold any data in it.
	 */
	f->out = malloc(sizeof(struct out_list));
	memset(f->out, 0, sizeof(out_list_t));

	/*
	 * actually data block.
	 */
	o = malloc(sizeof(struct out_list));
	o->s = out;
	o->next = NULL;
	f->out->next = o;
#endif

	return f;
}

void patch(struct frag *e1, struct state *s)
{
	out_list_t *o;

	o = e1->out->next;
	while (o) {
		printf("^^^^^^patch with e1->start->c = %c, o = %p\n", e1->start->c, o);
		*o->s = s;
		printf("^^^^^^o->s = %p, e1->start->out = %p\n", *o->s, e1->start->out);
		o = o->next;
	}
	return;
}

struct state matchstate = {
	258,
	NULL,
	NULL
};

struct frag *frag[100];
struct frag **frag_p = frag;

struct frag *pop()
{
	frag_p --;
	return *frag_p;
}

void push(struct frag *f)
{
	*frag_p = f;
	frag_p ++;
}

void dump_state(state_t *s)
{
static int a = 0;
	a++;
	printf("dump_state  %d: ch = %c, \n", a, s->c);
	if (s->out) {
		dump_state(s->out);
	}
	a--;
}

void dump_f(frag_t *f)
{
	out_list_t *o;
	state_t *s;
	o = f->out->next;
	printf("*********dump_f***************\n");
	while (o) {
		printf("the f->out is %p\n", o->s);
		dump_state(o->s);
		o = o->next;
	}
	printf("*********end***************\n");
}

void dump_out_list(out_list_t *header)
{
	out_list_t *p;
	printf("###########begin dump_out_list#####################\n");
	p = header->next;
	while (p) {
		printf("p->state = %p\n", *p->s);
		p = p->next;
	}
	printf("###########end dump_out_list#####################\n");
	return;
}

void dump_frag()
{
	struct frag **t;

	printf("-------------------------------\n");
	t = frag_p;
	while (t > frag) {
		t--;
		printf("frag start = %p\n", (*t)->start);
		printf("start state char = %c\n", (*t)->start->c);
		dump_out_list((*t)->out);
	}
	printf("-------------------------------\n");
}

/*
 * FIXME: take care of append for strange using of the header.!!!!
 */
out_list_t *mklist(state_t **s)
{
	out_list_t *o;

	o = malloc(sizeof(out_list_t));

	o->next = malloc(sizeof(out_list_t));

	o->next->next = NULL;
	o->next->s = s;

	return o;
}

struct state *nfa(char *post)
{
	struct state *s;
	struct frag *e1, *e2;


	while (*post) {
		switch (*post) {
			case '.':
				e2 = pop();
				e1 = pop();
				patch(e1, e2->start);
				push(_frag(e1->start, e2->out));
				printf("post = %c\n", *post);
				post++;
				dump_frag();
				break;
			default:
				s = state(*post, NULL, NULL);
				printf("post = %c, state->out = %p, state->out1 = %p, state = %p\n", 
						*post, s->out, s->out1, s);
				push(_frag(s, mklist(&s->out)));
				post++;
				dump_frag();
				break;

		}
	}
	
	e1 = pop();
	printf("after pop()\n");
	dump_f(e1);
	if (frag_p != frag) {
		printf("error occured.\n");
		exit(0);
	}

	patch(e1, &matchstate);
	dump_f(e1);

	printf("############leave nfa#############\n");
	return e1->start;
}

struct out_list nlist = {NULL, NULL};
struct out_list clist = {NULL, NULL};

int listid = 10;
void add_to_nlist(struct state *s)
{
	struct out_list *p;

	struct out_list *p1;

	printf("add_to_nlist state = %p\n", s);
	if (!s || s->lastlist == listid) {
		return;
	}
	p1 = malloc(sizeof(struct out_list));
	p1->next = NULL;
	p1->s = s;
	p = &nlist;
	while (p->next) {
		p = p->next;
	}

	p->next = p1;
	s->lastlist = listid;

	return;
}

void dump_nlist(void)
{
	printf("-------------begin dump_nlist--------------\n");
	out_list_t *p;

	p = &nlist;

	while (p->next) {
		p = p->next;
		printf("nlist state: %p, char = %c.\n", p, ((state_t *)(p->s))->c);
	}
	printf("-------------leave dump_nlist--------------\n");
}

void add_to_clist(struct state *s)
{
	struct out_list *p;

	struct out_list *p1;

	if (s->lastlist == listid) {
		printf("888888888888 return from clist with same listid.\n");
		return;
	}
	p1 = malloc(sizeof(struct out_list));
	p1->next = NULL;
	p1->s = s;
	printf("add_to_clist:%p\n", s);
	p = &clist;
	while (p->next) {
		p = p->next;
	}

	p->next = p1;
	s->lastlist = listid;

	return;
}

void dump_clist(void)
{
	printf("-------------begin dump_clist--------------\n");
	out_list_t *p;

	p = &clist;

	while (p->next) {
		p = p->next;
		printf("clist state: %p, char = %c.\n", p, ((state_t *)(p->s))->c);
	}
	printf("-------------leave dump_clist--------------\n");
}

int step(char ch)
{
	struct out_list *p;
	p = clist.next;

	printf("###########enter step##############\n");
	nlist.next = NULL;
	listid ++;
	while (p) {
		if (((state_t *)(p->s))->c == ch) {
			add_to_nlist(((state_t *)(p->s))->out);
		}
		p = p->next;
	}
	dump_nlist();
	printf("###########leave step##############\n");
}

int match(struct state *start, char *str)
{
	struct out_list t;
	add_to_clist(start);
	while (*str) {
		dump_clist();
		step(*str);
		t = clist; clist = nlist;nlist = t;
		str++;
	}

	struct out_list *p;

	p = clist.next;
	while (p) {
		if ((*p->s) == &matchstate) {
			printf("match.\n");
			return 1;
		}
		p = p->next;
	}
	printf("don't match.\n");
	return -1;
}

int main(int argc, char **argv)
{
	char *post;
	struct state *start;
	if (argc != 3) {
		printf("usage: program regex string.\n");
		exit(0);
	}

	post = postfix(argv[1]);

	start = nfa(post);

	match(start, argv[2]);

	return 0;
}