#include "dfanfa.h"
/*定义全局变量*/
static BOOL *NFA_alreadyOn; //记录NFA状态是否被添加情况
static char *GlobalPost_Expr; //后缀表达式
static int GlobalExpr_Index; //记录后缀表达式长度
/*----------------------------------------------------------------------------*/
/* 判断当前字符是否在字符集中*/
/*----------------------------------------------------------------------------*/
static BOOL in_symbols(char ch,char *symbols,int len)
{
int i;
for(i=0;i<len;++i)
{
if(symbols[i]==ch)
return TRUE;
}
return FALSE;
}
/*----------------------------------------------------------------------------*/
/* 销毁NFA*/
/*----------------------------------------------------------------------------*/
void destroy_NFA(NFA *nfa)
{
if(nfa->states!=NULL)
{
free(nfa->states);
nfa->states=NULL;
nfa->states_len=0;
}
if(nfa->symbols!=NULL)
{
free(nfa->symbols);
nfa->symbols=NULL;
nfa->symbols_len=0;
}
if(nfa->finals!=NULL)
{
free(nfa->finals);
nfa->finals=NULL;
nfa->finals_len=0;
}
if(nfa->matrix!=NULL)
{
free(nfa->matrix);
nfa->matrix=NULL;
}
if(nfa!=NULL)
{
free(nfa);
nfa=NULL;
}
}
/*----------------------------------------------------------------------------*/
/*添加状态 ,令 alreadyOn[state]为 TRUE，表示添加状态state */
/*----------------------------------------------------------------------------*/
void NFA_addState(NFA *nfa,NFAstate state)
{
NFAstate *T,t;
NFA_alreadyOn[state]=TRUE;
if(nfa->symbols_index[Ee]==-1)
return;
T=nfa->matrix[state][nfa->symbols_index[Ee]];
while((t=*T++)!=NOSTATE)
{
if(!NFA_alreadyOn[t])
NFA_addState(nfa,t);
}
}
/*----------------------------------------------------------------------------*/
/* 判断state是否在NFA状态集states中
state为NFA状态
p_states状态集
len为状态数*/
/*----------------------------------------------------------------------------*/
int in_NFAstates(NFAstate state,NFAstate *states,int len)
{
int i;
for(i=0;i<len;++i)
{
if(states[i]==state)
return i;
}
return NOSTATE;
}
/*----------------------------------------------------------------------------*/
/* 模拟NFA，如果字符串能到达终结状态返回TRUE
expr为输入字符串 */
/*----------------------------------------------------------------------------*/
BOOL NFA_execute(NFA *nfa,char *expr)
{
NFAstate *newstate,*oldstate,*temp;
NFAstate s0=nfa->start;
int i,states=nfa->states_len,index=0;
char ch;
NFA_alreadyOn=(BOOL*)malloc(nfa->states_len*sizeof(BOOL));
memset(NFA_alreadyOn,FALSE,nfa->states_len*sizeof(BOOL));
if(*expr==0)
{
NFA_addState(nfa,nfa->start);
for(i=nfa->start;i<nfa->states_len;++i)//结果保存到newstate
{
if(NFA_alreadyOn[i])
{
if(in_NFAstates(i,nfa->finals,nfa->finals_len)!=NOSTATE)
{
free(NFA_alreadyOn);
return TRUE;
}
}
}
free(NFA_alreadyOn);
return FALSE;
}
newstate=(NFAstate *)malloc(states*sizeof(NFAstate));
oldstate=(NFAstate *)malloc(states*sizeof(NFAstate));
memset(newstate,NOSTATE,states*sizeof(NFAstate));
memset(oldstate,NOSTATE,states*sizeof(NFAstate));
NFA_addState(nfa,nfa->start);
for(i=nfa->start;i<nfa->states_len;++i)
{
if(NFA_alreadyOn[i])
{
newstate[index++]=i;
NFA_alreadyOn[i]=FALSE;
}
}
while((ch=*expr++) !='\0')
{
if(!in_symbols(ch,nfa->symbols,nfa->symbols_len))
{
return FALSE;
}
for(i=0;i<index;++i)
{
oldstate[i]=newstate[i];
newstate[i]=NOSTATE;
}
for(i=0;i<index;++i)
{
temp=(nfa->matrix) [oldstate[i]][nfa->symbols_index[ch]];
while(*temp!=NOSTATE)
NFA_addState(nfa,*temp++);
}
for(i=0,index=0;i<states;++i)
{
if(NFA_alreadyOn[i])
{
newstate[index++]=i;
NFA_alreadyOn[i]=FALSE;
}
}
}
for(i=0;i<nfa->states_len;++i)
{
if(in_NFAstates(newstate[i],nfa->finals,nfa->finals_len)!=NOSTATE)
{
free(newstate);
free(oldstate);
return TRUE;
}
}
free(newstate);
free(oldstate);
free(NFA_alreadyOn);
return FALSE;
}
/*----------------------------------------------------------------------------*/
/* 销毁DFA*/
/*----------------------------------------------------------------------------*/
void destroy_DFA(DFA *dfa)
{
if(dfa->states!=NULL)
{
free(dfa->states);
dfa->states=NULL;
dfa->states_len=0;
}
if(dfa->symbols!=NULL)
{
free(dfa->symbols);
dfa->symbols=NULL;
dfa->symbols_len=0;
}
if(dfa->finals!=NULL)
{
free(dfa->finals);
dfa->finals=NULL;
dfa->finals_len=0;
}
if(dfa->matrix!=NULL)
{
free(dfa->matrix);
dfa->matrix=NULL;
}
if(dfa!=NULL)
{
free(dfa);
dfa=NULL;
}
}
/*----------------------------------------------------------------------------*/
/* 判断state是否在DFA状态集states中
state为DFA状态
states状态集
states_len为状态数*/
/*----------------------------------------------------------------------------*/
int in_DFAstates(DFAstate state,DFAstate *states,int states_len)
{
int i;
for(i=0;i<states_len;++i)
{
if(states[i]==state)
return i;
}
return NOSTATE;
}
/*----------------------------------------------------------------------------*/
/* 模拟DFA，如果字符串能到达终结状态返回TRUE
expr为输入字符串 */
/*----------------------------------------------------------------------------*/
BOOL DFA_execute(DFA *dfa,char *expr)
{
DFAstate state=dfa->start;
char ch;
DFAMatrixItem state_index=0;
if((state_index=in_DFAstates(state,dfa->states,dfa->states_len))==NOSTATE)
return FALSE;
while((ch=*expr++) !='\0')
{
if(!in_symbols(ch,dfa->symbols,dfa->symbols_len))
return FALSE;
if(dfa->symbols_index[ch]==-1)
return FALSE;
state_index=(dfa->matrix)[state_index][dfa->symbols_index[ch]];
if(state_index==NOSTATE)
return FALSE;
}
state=dfa->states[state_index];
if(in_DFAstates(state,dfa->finals,dfa->finals_len)!=NOSTATE)
return TRUE;
else
return FALSE;
}
/*----------------------------------------------------------------------------*/
/* 判断DFA dnstate状态是否在 Dnstates数组里
dnstate为一个DNFAstate状态
Dnstates 为DNFAstate状态集合
dfalen 为 Dnstates数组长度 */
/*----------------------------------------------------------------------------*/
DFAstate in_DNFAstates(DNFAstate *dnstate,DNFAstate *Dnstates,int states_len)
{
int i,j=0;
for(i=0;i<states_len;++i)
{
if(dnstate->len==Dnstates[i].len)
{
for(j=0;j<dnstate->len;++j)
if(dnstate->NFAstates[j]!=Dnstates[i].NFAstates[j])
break;
}
else
continue;
if(j==dnstate->len)
return i;
}
return NOSTATE;
}
/*--------------------------------------------------------------
