NFA를 DFA로 바꾸어주는 프로그램(C++)

소개글

NFA를 DFA로 바꾸어주는 프로그램(C++)에 대한 보고서 자료입니다.

본문내용

get_ep_states(i, eclosure[i], nfa, n_sym);
printf(" state %d : [%s]\n", i, eclosure[i]);
} printf("\n");
}
/*
Epsilon closure of 'states' is 'epstates'.
*/
void e_closure(char *epstates, char *states, char eclosure[][STATES+1])
{
int i;
strcpy(epstates, states);
for (i = 0; i < strlen(states); i++)
string_merge(epstates, eclosure[states[i]-'0']);
}
/*
Convert NFA table to DFA table.
Method:
0. state-name이 스트링이므로 StateName 테이블 이용
'n' -- StateName[]에 등록된 state 개수
1. DFA table의 entry 개수를 1로 초기화 및 StateName에 추가
2. StateName[i]의 각 symbol들에 대해 nextstate 계산
3. nextstate가 스트링이므로 StateName의 index를 DFA에 넣음
Return value: number of DFA states.
*/
int nfa_to_dfa(char *nfa[][SYMBOLS], int n_nfa,
int n_sym, int dfa[][SYMBOLS])
{
int i = 0; /* current index of DFA */
int n = 1; /* number of DFA states */
char nextstate[STATES+1];
char temp[STATES+1]; /* epsilon closure */
int j;
init_Eclosure(Eclosure, nfa, n_nfa, n_sym);
e_closure(temp, "0", Eclosure);
strcpy(StateName[0], temp); /* initialize start state */
printf("Epsilon-NFA to DFA conversion\n");
for (i = 0; i < n; i++) { /* for each DFA state */
for (j = 0; j < n_sym; j++) { /* for each input symbol */
get_next_state_NFA(nextstate, StateName[i], nfa, j);
e_closure(temp, nextstate, Eclosure);
dfa[i][j] = state_index(temp, StateName, &n);
printf(" state %d(%4s) : %d --> state %2d(%4s)\n",
i, StateName[i], j, dfa[i][j], temp);
dfa[i][j] += 'A'; /* 0/1/2/... --> 'A/B/C/...' */
}
}
return n; /* number of DFA states */
}
/*
NFA의 final state가 하나라도 포함된 모든 state가 DFA의 final state임.
*/
void get_DFA_finals(
char *dfinals, /* DFA final states */
char *nfinals, /* NFA final states */
char stnt[][STATES+1], /* state-name table */
int n_dfa) /* number of DFA states */
{
int i, j, k=0, n=strlen(nfinals);
for (i = 0; i < n_dfa; i++) {
for (j = 0; j < n; j++) {
if (strchr(stnt[i], nfinals[j])) {
dfinals[k++] = i+'A';
break;
}
}
}
dfinals[k] = '\0';
}
void main()
{
load_NFA_table();
print_nfa_table(NFAtab, N_NFA_states, N_symbols, NFA_finals);
N_DFA_states = nfa_to_dfa(NFAtab, N_NFA_states, N_symbols, DFAtab);
get_DFA_finals(DFA_finals, NFA_finals, StateName, N_DFA_states);
print_dfa_table(DFAtab, N_DFA_states, N_symbols, DFA_finals);
}

키워드

NFA,   DFA,   컴파일러,   소스,   C++