跳至內容

用戶:Antigng-bot/regex/NFARuntime

維基百科,自由的百科全書
#include <stdlib.h>
#include "mem.h"
#include "struct.h"
#include "regexFrontEnd.h"
#include "NFARuntime.h"
int nodecount=0;
struct _NFAType *NFARes=NULL;
static int nodeInsertEdge(struct _NFANode *node,unsigned int ch,struct _NFANode *target)
{
	struct hashlist *edges=node->edgetable;
	struct _NodeEdgeList *p;
	if(int_hashquery(edges,ch,(void **)&p))
	{
		struct _NodeEdgeList *q=(struct _NodeEdgeList *)s_calloc(sizeof(struct _NodeEdgeList),1);
		q->edge=target;
		q->next=p->next;
		p->next=q;
		return 1;
	}
	else
	{
		struct _NodeCharList *q=(struct _NodeCharList *)s_calloc(sizeof(struct _NodeCharList),1);
		p=(struct _NodeEdgeList *)s_calloc(sizeof(struct _NodeEdgeList),1);
		p->next=0;
		p->edge=target;
		int_hashadd(edges,ch,p);
		q->ch=ch;
		q->next=node->validchar;
		node->validchar=q;
		return 0;
	}
}
struct _NFAType *doConcatenation(struct _NFAType *arg1,struct _NFAType *arg2)
{
	struct _NFANode *end1=arg1->end,*begin2=arg2->begin;
	end1->edgetable=begin2->edgetable;
	end1->validchar=begin2->validchar;
	arg1->end=arg2->end;
	s_free(begin2);
	s_free(arg2);
	nodecount--;
	return arg1;
}
struct _NFAType *doChoice(struct _NFAType *arg1,struct _NFAType *arg2)
{
	struct _NFANode *begin_new=(struct _NFANode *)s_calloc(sizeof(struct _NFANode),1);
	struct _NFANode *end_new=(struct _NFANode *)s_calloc(sizeof(struct _NFANode),1);
	begin_new->edgetable=hashini();
	nodeInsertEdge(begin_new,0,arg1->begin);
	nodeInsertEdge(begin_new,0,arg2->begin);
	arg1->begin=begin_new;
	arg1->end->edgetable=hashini();
	nodeInsertEdge(arg1->end,0,end_new);
	arg2->end->edgetable=hashini();
	nodeInsertEdge(arg2->end,0,end_new);
	arg1->end=end_new;
	s_free(arg2);
	nodecount+=2;
	return arg1;
}
struct _NFAType *doKleenStar(struct _NFAType *arg)
{
	struct _NFANode *end=arg->end,*begin=arg->begin;
	end->edgetable=begin->edgetable;
	end->validchar=begin->validchar;
	begin->edgetable=hashini();
	begin->validchar=0;
	nodeInsertEdge(begin,0,end);
	arg->end=(struct _NFANode *)s_calloc(sizeof(struct _NFANode),1);
	nodeInsertEdge(end,0,arg->end);
	nodecount++;
	return arg;
}
struct _NFAType *doPositiveClosure(struct _NFAType *arg)
{
	struct _NFANode *end=arg->end,*begin=arg->begin;
	end->edgetable=hashini();
	nodeInsertEdge(end,0,begin);
	arg->begin=(struct _NFANode *)s_calloc(sizeof(struct _NFANode),1);
	arg->begin->edgetable=hashini();
	nodeInsertEdge(arg->begin,0,begin);
	arg->end=(struct _NFANode *)s_calloc(sizeof(struct _NFANode),1);
	nodeInsertEdge(end,0,arg->end);
	nodecount+=2;
	return arg;
}
struct _NFAType *doQuestion(struct _NFAType *arg)
{
	struct _NFANode *end=arg->end,*begin=arg->begin;
	nodeInsertEdge(begin,0,end);
	return arg;
}
struct _NFAType *buildNFAFromChar(unsigned int ch)
{
	struct _NFAType *arg=(struct _NFAType *)s_calloc(sizeof(struct _NFAType),1);
	arg->begin=(struct _NFANode *)s_calloc(sizeof(struct _NFANode),1);
	arg->begin->edgetable=hashini();
	arg->end=(struct _NFANode *)s_calloc(sizeof(struct _NFANode),1);
	nodeInsertEdge(arg->begin,ch,arg->end);
	nodecount+=2;
	return arg;
}

struct _NFAType *buildNFAFromGen(unsigned int ch)
{
	unsigned int pch=0;
	struct _NFAType *arg=(struct _NFAType *)s_calloc(sizeof(struct _NFAType),1);
	arg->begin=(struct _NFANode *)s_calloc(sizeof(struct _NFANode),1);
	arg->begin->edgetable=hashini();
	arg->end=(struct _NFANode *)s_calloc(sizeof(struct _NFANode),1);
	switch(ch)
	{
	case 'd':
		for(pch='0';pch<='9';pch++)
		{
			nodeInsertEdge(arg->begin,pch,arg->end);
		}
		break;
	case 'a':
		for(pch='A';pch<='Z';pch++)
		{
			nodeInsertEdge(arg->begin,pch,arg->end);
		}
		for(pch='a';pch<='z';pch++)
		{
			nodeInsertEdge(arg->begin,pch,arg->end);
		}
		break;
	case 's':
		nodeInsertEdge(arg->begin,' ',arg->end);
		nodeInsertEdge(arg->begin,'\f',arg->end);
		nodeInsertEdge(arg->begin,'\n',arg->end);
		nodeInsertEdge(arg->begin,'\r',arg->end);
		nodeInsertEdge(arg->begin,'\t',arg->end);
		nodeInsertEdge(arg->begin,'\v',arg->end);
		break;
	}
	nodecount+=2;
	return arg;
}
struct _NFAType *buildNFAFromRange(struct _rangeValue range)
{
	unsigned int ch=0;
	int count=0;
	struct _NFAType *arg=(struct _NFAType *)s_calloc(sizeof(struct _NFAType),1);
	arg->begin=(struct _NFANode *)s_calloc(sizeof(struct _NFANode),1);
	arg->begin->edgetable=hashini();
	arg->end=(struct _NFANode *)s_calloc(sizeof(struct _NFANode),1);
	for(count=0;count<range.count;count++)
	{
		for(ch=range.pairs[count].start;ch<=range.pairs[count].end;ch++)
		{
			nodeInsertEdge(arg->begin,ch,arg->end);
		}
	}
	nodecount+=2;
	return arg;
}