rnd.h

正则表达式转换为NFA再转换为DFA

//RND.h   

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

#define Max_alphabet 20
#define Max_regexp 50
#define Max_StateTransition 20
#define Max_State 200
#define FileAlphabetPath "alphabet.txt"
#define FileRegexpPath "regexp.txt" 
#define FileOutputPath "Report.txt"


//转换弧类型定义
typedef struct TRANS
{
    int dest;//目的状态点
    char sign;//转换变量
    struct TRANS* next;//指向下一个转换弧
} Trans;

//状态类型定义
typedef struct STATE
{
    int id ;    //状态编号
    int numOfTrans;    //从该节点出去的转换弧计数
    Trans *trans;//用单链表保存所有的转换弧
} State ,*PState;

//NFA类型定义
typedef struct NFANODE
{
    PState *NodeTable;//[Max_State]; //存放所有状态的数组
    int numOfStates;//总的状态数
    int numOfTrans;//总的转换弧条数
    PState pStart;//NFA的start state
    PState pFinal;//NFA的final state
} NFA;

//DFA类型定义
typedef struct DFANODE
{
    int **DStates;//DFA状态表
    int **Dtrans;//DFA转移表
    int *AcceptSet;//DFA的接受状态集合
    int numofDStates;//DFA的状态计数
    int numOfDTrans;//DFA的转移计数
} DFA;

// 定义链式字符栈结点
typedef struct  CHARSTACK
{      
    char data;
    struct CHARSTACK *next;
} SNode ,*PSNode;

// 定义链式Nfa栈（状态栈）结点
typedef struct  STATESTACK
{      
    PState data;
    struct STATESTACK *next;
} Nfa_SNode ,*PNfa_SNode;



//全局变量
char Alphabet[Max_alphabet];
char Operator[3]={'|','*','+'};
int NumOfSymbol;
char Regexp[Max_regexp];
char Postfix[Max_regexp];
PSNode SymbStack;
PNfa_SNode StateStack;
NFA *Nfa;
DFA Dfa;
FILE *fpout;

int Readalphabet(void);//读入字母表
int Readregexp(void);//读入正则表达式

void Init_SymbStack(void);//字符栈初始化
int  IsEmpty_SymbStack(void);// 判断字符栈是否为空
void Push_SymbStack(char x);// 字符栈数据入栈
char Pop_SymbStack(void);// 字符栈数据出栈
char GetTop_SymbStack(void);// 获取字符栈栈顶数据
void Destory_SymbStack(void);// 字符栈的析构函数

void Init_StateStack(void);//状态栈初始化
//int  IsEmpty_StateStack(void);// 判断状态栈是否为空
void Push_StateStack(PState x);// 状态栈数据入栈
PState Pop_StateStack(void);// 状态栈数据出栈
void Destory_StateStack(void);// 状态栈的析构函数

int LexScan(char *x);//正则式的合法性检测
int IsInArray(char x, char *charArray);//在charArray[]中查找x，成功返回1，失败返回0，用于合法性检测
void AddConcatenation();//正则式加入连接符“+” （代表concatenation运算符）
void REtoPostfix(void);//将正则式转为后缀表达式
void Init_Nfa(void);//Nfa的初始化
void ConstructNFA(void);//用Thompson算法构造NFA
void NewState(PState x);//申请新的状态点
void AddTrans(PState s1,PState s2,char x);//添加转换弧
void OutputNFA();//输出NFA
void BubbleSort(int *array);// 对状态集进行排序，方便比较数组，使输出形式更好看。
int CompArray(int *t1, int *t2);//比较两个一维数组是否含有完全相同的元素
int* TransX(int *T, char x);// 对状态集T中包含的某个NFA状态求 x 转换的状态集合
int* Closures(int *T);//对状态集T中包含的某个NFA状态S求ε闭包
void ConstructDFA();//采用子集构造法构造DFA
void OutputDFATable();//输出DFA表格
void OutputDFA();//输出DFA的各种状态概要，并调用void OutputDFATable()输出DFA
void OutputSet_Array(int* array);//输出数组 共计27个字符位
int Optimize();//去掉只有入度没有出度的非接受状态
int Simplify();//将DFA最简化__最大等价状态集法


/*______________________________读入字母表______________________________*/ 
//将字母表读入到全局变量中，成功返回1，失败返回0。                            
int Readalphabet()
{
    FILE *fp;
    int i=0;
    char temp;

    printf(" ___________________________Initialization__________________________\n");
    fprintf(fpout," ___________________________Initialization__________________________\n");
    fp=fopen(FileAlphabetPath,"r");
    if (fp==NULL)
        return 0;
    printf(" The alphabet is: ");
    fprintf(fpout," The alphabet is: ");
    while( !feof(fp) )
    {
       temp=fgetc(fp);
        if((temp!=',')&&(temp!=' ')&&(temp!=10)&&(temp!=13)&&(temp!=-1))//10 换行 13回车 
        {
            Alphabet[i]=temp;
            i++;
        }
    }
    NumOfSymbol=i;//记住实际的symbol的个数
    for (i=0;i<NumOfSymbol-1;i++)
    {
        printf("%c,",Alphabet[i]);
        fprintf(fpout,"%c,",Alphabet[i]);
    }
    printf("%c\n",Alphabet[i]);
    fprintf(fpout,"%c\n",Alphabet[i]);

    printf(" The total number of symbols is: %d\n",NumOfSymbol);
    fprintf(fpout," The total number of symbols is: %d\n",NumOfSymbol);
    fclose(fp);
    return 1;
}                                                                           

/*____________________________读入正则表达式____________________________*/ 
//将正则表达式读入到全局变量中，成功返回1，失败返回0。
int Readregexp()
{
    FILE *fp;

    fp=fopen(FileRegexpPath,"r");
    if (fp==NULL)
        return 0;
    fscanf(fp,"%s",Regexp);
    printf(" The regular express is: %s\n",Regexp);
    fprintf(fpout," The regular express is: %s\n",Regexp);
    fclose(fp);
    return 1;
}





/*____________________________正则式合法性验证____________________________*/ 
//词法扫描，正则式合法性验证
int LexScan(char *x)
{
 int i;
 for(i=0;x[i]!='\0';i++)
 {
  if(x[i]=='(')
   Push_SymbStack(x[i]);
  else if (x[i]==')')
  {
   if(Pop_SymbStack()=='$')
    return 0;
  }
  else 
  {
   if(IsInArray(x[i], Alphabet)==0)
    if(IsInArray(x[i], Operator)==0)
     return 0;
  }
 }
 if(!IsEmpty_SymbStack)
 {
  printf("\nNumber of \"(\" and \")\" is not march!\n");
  fprintf(fpout,"\nNumber of \"(\" and \")\" is not march!\n");
  return 0;
 }
 return 1;
}
//在charArray[]中查找x，成功返回1，失败返回0
int IsInArray(char x, char *charArray)
{
 int i,flag;
 flag=0;
 for(i=0 ; charArray[i] != '\0' ; i++)
 { if(charArray[i]==x)
   return 1;
 }
 return 0;
}
/*____________________________栈操作实现____________________________*/ 
void Init_SymbStack()//字符栈初始化
{
 SymbStack=(PSNode) malloc(sizeof(SNode));
 SymbStack->data=0;
 SymbStack->next=NULL;
}
void Init_StateStack()//状态栈初始化
{
 StateStack=(PNfa_SNode) malloc(sizeof(Nfa_SNode));
 StateStack->data=NULL;
 StateStack->next=NULL; 
}

void Push_SymbStack(char x)// 字符栈数据入栈
{
 PSNode temp=(PSNode) malloc(sizeof(SNode));
 temp->data=x;
 temp->next=SymbStack;
 SymbStack=temp;
}

void Push_StateStack(PState x)// 状态栈数据入栈
{
 PNfa_SNode temp=(PNfa_SNode) malloc(sizeof(Nfa_SNode));
 temp->data=x;
 temp->next=StateStack;
 StateStack=temp;
}
int  IsEmpty_SymbStack(void)// 判断字符栈是否为空，空返回1，非空返回0。
{
 if (! SymbStack)
  return 1;
 else return 0;
}
int  IsEmpty_StateStack(void);// 判断状态栈是否为空
char Pop_SymbStack(void)// 字符栈数据出栈
{
 if (! IsEmpty_SymbStack())
 {
  char x;
     PSNode temp=SymbStack;
  SymbStack=SymbStack->next;
  x=temp->data;
  free(temp);
  return x;
 }
 else
 {
  printf("The stack is empty!\n");
  return '$';
 }
}
PState Pop_StateStack(void)// 状态栈数据出栈
{
 if (StateStack)
 {
  PState x;
     PNfa_SNode temp=StateStack;
  StateStack=StateStack->next;
  x=temp->data;
  free(temp);
  return x;
 }
 else
 {
  printf("The stack is empty!\n");
  getchar();
  exit(1);
 }
}
char GetTop_SymbStack(void)// 取字符栈栈顶数据
{
 if (! IsEmpty_SymbStack())
 {
  return SymbStack->data;
 }
 else
 {
  printf("The stack is empty!\n");
  return '$';
 }
}

void Destory_SymbStack()// 字符栈析构函数
{
 PSNode temp=(PSNode) malloc(sizeof(SNode));
 while (SymbStack)
 {
  temp=SymbStack;
  SymbStack=SymbStack->next;
  free(temp);
 }
}
void Destory_StateStack(void)// 状态栈的析构函数
{
 PNfa_SNode temp=(PNfa_SNode) malloc(sizeof(Nfa_SNode));
 while (StateStack)
 {
  temp=StateStack;
  StateStack=StateStack->next;
  free(temp);  
 }
}
 

 

 




// 定义运算符的优先级
int Precedence(char symbol)
{
    int p;
    switch (symbol)
    {
    case '|': p=1; break;
    case '+': p=2; break;
    case '*': p=3; break;
    default:  p=0; break;
    }
    return p;
}
/*____________________________正则式加"+"运算符_____________________________*/ 
//加入连接符 concatenation
void AddConcatenation()
{
 int i=0, j, len=strlen(Regexp);
 while (Regexp[i+1] != '\0')
 {
  if (((Regexp[i] != '(' && Regexp[i] != '+' && Regexp[i] != '|') 
   || Regexp[i]==')' || Regexp[i]=='*')
   && (Regexp[i+1] != ')' && Regexp[i+1] != '+' && Regexp[i+1] != '|' && Regexp[i+1] != '*'))
  {
   for (j=len; j>i+1; j--)
    Regexp[j]=Regexp[j-1];
   Regexp[i+1]='+';
   len++;
   Regexp[len]='\0';
   i++;
  }
  i++;
 }
}
/*____________________________正则式转后缀表达式_____________________________*/ 
// 将正则式转为后缀表达式
void REtoPostfix()
{
 int i=0, j=0;
 char curr, ctop;
 Init_SymbStack();
 curr=Regexp[i];
 while (curr != '\0')
 {
  if (curr=='(')
  {
   Push_SymbStack(curr);
   curr=Regexp[++i];
  }
  else if (curr==')')
  {
   while (GetTop_SymbStack() != '(')
   {
    Postfix[j++]=Pop_SymbStack();
   }
            Pop_SymbStack();
   curr=Regexp[++i];
  }
  else if ( (curr=='+') || (curr=='|') || (curr=='*') )
  {
      ctop=GetTop_SymbStack();
      while (Precedence(ctop) >= Precedence(curr))
   {
       Postfix[j++]=ctop;
       Pop_SymbStack();
       ctop=GetTop_SymbStack();
   }
   Push_SymbStack(curr);
   curr=Regexp[++i];
  }
  else
  {
   Postfix[j++]=curr;
   curr=Regexp[++i];
  }
 }
 curr=Pop_SymbStack();
 while ( (curr=='+') || (curr=='|') || (curr=='*'))
 {
  Postfix[j++]=curr;
  curr=Pop_SymbStack();
 }
 Postfix[j]='\0';
 Destory_SymbStack();
 printf("\nThe postfix is: %s\n",Postfix);
}

/*____________________________用Thompson算法构造NFA____________________________*/
void ConstructNFA()
{
 int i=0;
 char curr=Postfix[i];
 PState s1,s2,s3,s4,s5,s6;
 Init_StateStack();
 while(curr!='\0')
 {
  if(curr=='+')//对+运算进行处理
  {
   s4=Pop_StateStack();
   s3=Pop_StateStack();
   s2=Pop_StateStack();
   s1=Pop_StateStack();
   AddTrans(s2,s3,'~');
   Push_StateStack(s1);
   Push_StateStack(s4);
  }
  else if(curr=='|')//对|运算进行处理
  {
   s4=Pop_StateStack();
   s3=Pop_StateStack();
   s2=Pop_StateStack();
   s1=Pop_StateStack();
   s5=(PState)malloc(sizeof(State));
   NewState(s5);
   s6=(PState)malloc(sizeof(State));
   NewState(s6);
   AddTrans(s5,s1,'~');
   AddTrans(s5,s3,'~');
   AddTrans(s2,s6,'~');
   AddTrans(s4,s6,'~');
   Push_StateStack(s5);
   Push_StateStack(s6);
  }
  else if(curr=='*')//对*运算进行处理
  {
   s2=Pop_StateStack();
   s1=Pop_StateStack();
   s3=(PState)malloc(sizeof(State));
   NewState(s3);
   s4=(PState)malloc(sizeof(State));
   NewState(s4);
   AddTrans(s3,s1,'~');
   AddTrans(s2,s4,'~');   
   AddTrans(s2,s1,'~');
   AddTrans(s3,s4,'~');
   Push_StateStack(s3);
   Push_StateStack(s4);
  }
  else//对symbol进行处理 
  {
   s1=(PState)malloc(sizeof(State));
   NewState(s1);
   s2=(PState)malloc(sizeof(State));
   NewState(s2);
   AddTrans(s1,s2,curr);
   Push_StateStack(s1);
   Push_StateStack(s2);
  }
  curr=Postfix[++i];
 }
 Nfa->pFinal=Pop_StateStack();