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();