컴파일러3장20번연습문제

소개글

컴파일러3장20번연습문제에 대한 보고서 자료입니다.

본문내용

' */
strcpy(stnt[n2++], newstates[i]);
}
}
sort(stnt, n2); /* sort equiv. classes */
return n2; /* number of NEW states(equiv. classes) */
}
// Equiv. classes are segmented and get NEW equiv. classes.
int set_new_equiv_class(char stnt[][STATES+1], int n, int newdfa[][SYMBOLS], int n_sym, int n_dfa) {
int i, j, k;
for (i = 0; i < n; i++) {
for (j = 0; j < n_sym; j++) {
k = newdfa[i][j]-'A'; /* index of equiv. vector */
if (k >= n) /* equiv. class 'i' should be segmented */
return split_equiv_class(stnt, i, k, n, n_dfa);
}
}
return n;
}
// State-minimization of DFA: 'dfa' --> 'newdfa'
int optimize_DFA(int dfa[][SYMBOLS], int n_dfa, int n_sym, char *finals, char stnt[][STATES+1], int newdfa[][SYMBOLS]) {
int n; /* number of new DFA states */
int n2; /* 'n' + */
n = init_equiv_class(stnt, n_dfa, finals);
while (1) {
n2 = get_optimized_DFA(stnt, n, dfa, n_sym, newdfa);
if (n != n2)
n = set_new_equiv_class(stnt, n, newdfa, n_sym, n_dfa);
else break; /* equiv. class segmentation ended!!! */
}
return n; /* number of DFA states */
}
// Check if 't' is a subset of 's'.
int is_subset(char *s, char *t) {
int i;
for (i = 0; *t; i++)
if (!strchr(s, *t++)) return 0;
return 1;
}
// New finals states of reduced DFA.
void get_NEW_finals(char *newfinals, char *oldfinals, char stnt[][STATES+1], int n) {
int i;
for (i = 0; i < n; i++)
if (is_subset(oldfinals, stnt[i])) *newfinals++ = i+'A';
*newfinals++ = '\0';
}
// ======================== 메인 프로그램 ===========================
void main() {
int i,j,flag;
char ch; /* input symbol */
int cur_state; /* start state */
// Regular Expression을 입력 받아 epsilon-NFA로 변환
read_RE();
RE_to_eNFA();
print_nfa_table(NFAtab, N_NFA_states, N_symbols, NFA_finals);
// epsilon-NFA를 DFA로 변환
N_DFA_states = nfa_to_dfa(NFAtab, N_NFA_states, N_symbols, DFAtab);
get_DFA_finals(DFA_finals, NFA_finals, StateName, N_DFA_states);
// Trap state 추가 및 Symbol에 대한 null state를 모두 Trap state로 적용
for (i = 0; i < N_DFA_states; i++)
for (j = 0; j < N_symbols; j++)
if(DFAtab[i][j]=='@') DFAtab[i][j]='A'+N_DFA_states;
for (i = 0; i < N_symbols; i++) // trap state 생성 및 초기화
DFAtab[N_DFA_states][i]='A'+N_DFA_states;
N_DFA_states++;
// DFA 상태수 최소화
N_optDFA_states = optimize_DFA(DFAtab, N_DFA_states, N_symbols, DFA_finals, StateName, OptDFA);
get_NEW_finals(NEW_finals, DFA_finals, StateName, N_optDFA_states);
print_dfa_table(OptDFA, N_optDFA_states, N_symbols, NEW_finals);
// 입력 스트링을 받고 인식하는 부분
printf("\n");
while(1) {
flag=0;
cur_state=0;
j=0;
printf("Enter Input-string (Exit = quit): ");
gets(Input_String);
ch=Input_String[j];
if(!strcmp(Input_String,"quit")) break;
while (j<=(int)(strlen(Input_String)-1)) {
if((i=Symb_num(ch)) == (-1)) { // 잘못된 symbol이면 루프 종료
cur_state = N_optDFA_states-1; // 현재 state를 trap state로 지정.
break;
}
cur_state = OptDFA[cur_state][i]-'A';
ch = Input_String[++j];
}
for(i=0;i<(int)strlen(NEW_finals);i++)
if (cur_state == NEW_finals[i]-'A') flag=1;
if (flag) puts("Accept");
else puts("Reject");
}
}
□ 실행 결과

키워드

컴파일러,   연습문제,   20번,   3장