不确定的有限状态自动机

/** *author: liu.yang *mail: yl_cquc@163.com *date: 2008.4 */ #include <stdio.h> #include <stdlib.h> #include "NFA.h" NFA* ConstructNFA(Grammar *gm) { NFA * nfa=(NFA*)malloc(sizeof(NFA)); if(!nfa) return NULL; nfa->nonTerminal = (char*)malloc(strlen(gm->nonTerminal)+1); nfa->terminal = (char*)malloc(strlen(gm->terminal)+1); nfa->start = (char*)malloc(strlen(gm->start)+1); nfa->terminalState = (char*)malloc(1+1); if((!nfa->nonTerminal)&&(!nfa->terminal)&&(!nfa->start)&&(!nfa->terminal)) return NULL; char* strTerminal=charToString(chTerminal); /*malloc here ,remmber to free*/ if(!strTerminal) return NULL; strcpy(nfa->terminalState,strTerminal); strcpy(nfa->nonTerminal,gm->nonTerminal); stradd(nfa->nonTerminal,strTerminal); strcpy(nfa->terminal,gm->terminal); strcpy(nfa->start,gm->start); nfa->stateNum = strlen(gm->nonTerminal)+1; nfa->alphabetNum=strlen(gm->terminal); nfa->stateConvertTable=(char**)malloc((nfa->stateNum)*(nfa->alphabetNum)*sizeof(char*)); int i=0,j=0; /** *initial stateConvertTable */ for(i=0;i<nfa->stateNum;i++) { for(j=0;j<nfa->alphabetNum;j++) { *(nfa->stateConvertTable+i*(nfa->alphabetNum)+j) = (char*)malloc(nfa->stateNum+1); strcpy(*(nfa->stateConvertTable+i*(nfa->alphabetNum)+j),""); } } /* printf("nfa->stateNum=%d\n",nfa->stateNum); printf("nfa->alphabetNum=%d\n",nfa->alphabetNum); for(i=0;i<nfa->stateNum;i++) { for(j=0;j<nfa->alphabetNum;j++) { printf("%s ",(*(nfa->stateConvertTable+i*(nfa->alphabetNum)+j))); } printf("\n"); } */ /** *create stateConverTable */ ST *st=ConstructST(gm->production,','); if(!st) return NULL; char* temp; char* strFront; char* strRear; char* str1; int rowNum=0,colNum=0; while((temp=HaveMoreTokens(st))!=NULL) { strFront = temp; strRear = (char*)malloc(strlen(temp)); if(!strRear) return NULL; strcpy(strRear,temp+3); str1=charToString(charAt(strRear,1)); /*malloc here ,remmber to free*/ if(!str1) return NULL; rowNum = indexOf(nfa->nonTerminal,*strFront); /* printf("temp=%s\n",temp); // printf("nonTerminal=%s\n",nfa->nonTerminal); // printf("*strFront=%c\n",*strFront); // printf("rowNum=%d\n",rowNum); printf("strlen(strRear)=%d\n",strlen(strRear)); */ if(strlen(strRear)==2) { colNum=indexOf(nfa->terminal,charAt(strRear,0)); if(!charContains((*(nfa->stateConvertTable+rowNum*(nfa->alphabetNum))+colNum),charAt(strRear,1))) stradd(*(nfa->stateConvertTable+rowNum*(nfa->alphabetNum)+colNum),str1); } else if(strlen(strRear)==1) { colNum=indexOf(nfa->terminal,charAt(strRear,0)); if(!charContains((*(nfa->stateConvertTable+rowNum*(nfa->alphabetNum)+colNum)),chTerminal)) { stradd(*(nfa->stateConvertTable+rowNum*(nfa->alphabetNum)+colNum),strTerminal); } } FREE(str1); FREE(strRear); FREE(temp); } FREE(strTerminal); printf(" "); for(j=0;j<nfa->alphabetNum;j++) printf(" %c ",*(nfa->terminal+j)); printf("\n"); for(i=0;i<nfa->stateNum;i++) { printf("\n %4c",*(nfa->nonTerminal+i)); for(j=0;j<nfa->alphabetNum;j++) { if(strlen((*(nfa->stateConvertTable+i*(nfa->alphabetNum)+j)))==0) strcpy((*(nfa->stateConvertTable+i*(nfa->alphabetNum)+j)),"$"); printf(" %4s",(*(nfa->stateConvertTable+i*(nfa->alphabetNum)+j))); } printf("\n"); } return nfa; } void DestroyNFA(NFA **nfa) { FREE((*nfa)->nonTerminal); FREE((*nfa)->terminal); FREE((*nfa)->start); int i=0; for(i=0;i<(((*nfa)->stateNum)*((*nfa)->alphabetNum));i++) { FREE(*((*nfa)->stateConvertTable+i)); } FREE(*nfa); }