1118 实验三 有限自动机的构造与识别

#include<stdio.h>

#include <ctype.h>

#define ok 1

#define error 0

#define MAXREGLUARLONG 40

#define MAXSTATELONG 40

#define MAXCAHRSLONG 40

typedef int state;

int iCurrentState=0; //初态以1开始

int iPreState=0;

int iLastForkState=0;

int iForkState=0;

int iMaxState=0;

char cRegluarSting[MAXREGLUARLONG]; //输入的正规式字符串

char cCharSet[MAXCAHRSLONG]; //字符集

int iStateMatrix[MAXSTATELONG][MAXCAHRSLONG]; //状态转换矩阵

state vStoreRegluarSting()//把字符串读入一个缓冲区中

{

scanf("%s",cRegluarSting);

return ok;

}

state vPreProcessRegluarSting()

//对字符串进行预处理,去掉字符串里面的对分析不产生影响

int i=0;

while(cRegluarSting[i]!='\0')

{

if(cRegluarSting[i]=='*')

{

int j=i+1;

while(cRegluarSting[j-1]!='\0')

{

cRegluarSting[j-1]=cRegluarSting[j++];

}

}

i++;

}

void vConstructStateMatrix(char cChar,int istate)//构造状态转换矩阵

int i;

for(i=0;cCharSet[i]!='\0';i++)

if(cChar==cCharSet[i])

break;

cCharSet[i]=cChar;

iStateMatrix[iPreState][i]=istate;

void vAanalyseRegluarSting()//对字符串进行从左到右的分析与处理

for(i=0;cRegluarSting[i]!=0;i++)

if(cRegluarSting[i]=='(') //NFA出现开始分叉情况

int iTheFirstl=0;

int iCharNumBeforl=0;

iForkState=iCurrentState;

while(cRegluarSting[i]!=')')

{

i++;

if(isalpha(cRegluarSting[i]))

{

if(cRegluarSting[i+1]==')')

iCurrentState=iLastForkState;

else

iCurrentState++;

iCharNumBeforl++; vConstructStateMatrix(cRegluarSting[i],iCurrentState);

iPreState=iCurrentState;

if(iCurrentState>iMaxState)

iMaxState=iCurrentState;

}

if(cRegluarSting[i]=='|')

{

iPreState=iForkState;

if(iTheFirstl==0)

{

iLastForkState=iCurrentState;

iTheFirstl++;

}

if(iCharNumBeforl==1&&cRegluarSting[i+2]=='|')

iCurrentState=iForkState;

iCharNumBeforl=0;

}

if(cRegluarSting[i]==')')

iPreState=iForkState=iLastForkState;

iCurrentState=iMaxState;

else

iCurrentState++; vConstructStateMatrix(cRegluarSting[i],iCurrentState);

iPreState=iCurrentState;

if(iCurrentState>iMaxState)

iMaxState=iCurrentState;

}

void vPrintfStateProjectFunction()

{

int icCharSetPointer;

int iPreStatePointer;

for

(iPreStatePointer=0;iPreStatePointer<MAXSTATELONG;iPreStatePointer++)

for(icCharSetPointer=0;icCharSetPointer<MAXSTATELONG;icCharSetPointer++)

if(iStateMatrix[iPreStatePointer][icCharSetPointer]>0) printf("&(%d,%c)=%d\n",iPreStatePointer,cCharSet[icCharSetPointer],iStateMatrix[iPreStatePointer][icCharSetPointer]);

void vPrintfNfa()//输出NFA

int iStateNumble;

printf("NFA的形式为:(S,$,&,S0,F)\n\n以下为NFA的具体集合内容:\n\n");

printf("字符集$为:{");

while(cCharSet[i]!=0)

if(cCharSet[i+1]==0)

printf("%c",cCharSet[i++]);

printf("%c,",cCharSet[i++]);

printf("}\n");

printf("\n状态集S为:{");

for (i=0;i<=iMaxState;i++) {

if(i==iMaxState)

printf("%d",i);

printf("%d,",i);

printf("}\n\n");

vPrintfStateProjectFunction();

printf("\n初态集S0为:{0}\n\n");

printf("终态集F为:{%d}",iMaxState);

void main()

vStoreRegluarSting();

vPreProcessRegluarSting();

vAanalyseRegluarSting();

vPrintfNfa();