00001
00017
00018
00019
00020
00021
00022
00023
00024 #include <sent/stddefs.h>
00025 #include <sent/dfa.h>
00026
00027 static char buf[MAXLINELEN];
00028
00034 void
00035 dfa_state_init(DFA_INFO *dinfo)
00036 {
00037 int i;
00038 dinfo->maxstatenum = DFA_STATESTEP;
00039 dinfo->st = (DFA_STATE *)mymalloc(sizeof(DFA_STATE) * dinfo->maxstatenum);
00040 for (i=0;i<dinfo->maxstatenum;i++) {
00041 dinfo->st[i].number = i;
00042 dinfo->st[i].status = 0;
00043 dinfo->st[i].arc = NULL;
00044 }
00045 dinfo->state_num = dinfo->arc_num = dinfo->term_num = 0;
00046 dinfo->sp_id = WORD_INVALID;
00047 }
00048
00055 void
00056 dfa_state_expand(DFA_INFO *dinfo, int needed)
00057 {
00058 int oldnum, i;
00059 oldnum = dinfo->maxstatenum;
00060 dinfo->maxstatenum += DFA_STATESTEP;
00061 if (dinfo->maxstatenum < needed) dinfo->maxstatenum = needed;
00062 dinfo->st = (DFA_STATE *)myrealloc(dinfo->st, sizeof(DFA_STATE) * dinfo->maxstatenum);
00063 for (i=oldnum;i<dinfo->maxstatenum;i++) {
00064 dinfo->st[i].number = i;
00065 dinfo->st[i].status = 0;
00066 dinfo->st[i].arc = NULL;
00067 }
00068 }
00069
00078 boolean
00079 rddfa(FILE *fp, DFA_INFO *dinfo)
00080 {
00081 int state_max, arc_num, terminal_max;
00082
00083
00084 dfa_state_init(dinfo);
00085 state_max = 0;
00086 arc_num = 0;
00087 terminal_max = 0;
00088
00089 while (getl(buf, MAXLINELEN, fp) != NULL) {
00090 if (rddfa_line(buf, dinfo, &state_max, &arc_num, &terminal_max) == FALSE) {
00091 break;
00092 }
00093 }
00094 dinfo->state_num = state_max + 1;
00095 dinfo->arc_num = arc_num;
00096 dinfo->term_num = terminal_max + 1;
00097 return(TRUE);
00098 }
00099
00108 boolean
00109 rddfa_fd(int fd, DFA_INFO *dinfo)
00110 {
00111 int state_max, arc_num, terminal_max;
00112
00113
00114 dfa_state_init(dinfo);
00115 state_max = 0;
00116 arc_num = 0;
00117 terminal_max = 0;
00118
00119 while(getl_fd(buf, MAXLINELEN, fd) != NULL) {
00120 if (rddfa_line(buf, dinfo, &state_max, &arc_num, &terminal_max) == FALSE) {
00121 break;
00122 }
00123 }
00124 dinfo->state_num = state_max + 1;
00125 dinfo->arc_num = arc_num;
00126 dinfo->term_num = terminal_max + 1;
00127 return(TRUE);
00128 }
00129
00138 boolean
00139 rddfa_sd(int sd, DFA_INFO *dinfo)
00140 {
00141 int state_max, arc_num, terminal_max;
00142
00143
00144 dfa_state_init(dinfo);
00145 state_max = 0;
00146 arc_num = 0;
00147 terminal_max = 0;
00148
00149 while(getl_sd(buf, MAXLINELEN, sd) != NULL) {
00150 if (rddfa_line(buf, dinfo, &state_max, &arc_num, &terminal_max) == FALSE) {
00151 break;
00152 }
00153 }
00154 dinfo->state_num = state_max + 1;
00155 dinfo->arc_num = arc_num;
00156 dinfo->term_num = terminal_max + 1;
00157 return(TRUE);
00158 }
00159
00171 boolean
00172 rddfa_line(char *line, DFA_INFO *dinfo, int *state_max, int *arc_num, int *terminal_max)
00173 {
00174 DFA_ARC *newarc;
00175 int state, terminal, next_state;
00176 unsigned int status;
00177
00178 if (strmatch(buf, "DFAEND")) return(FALSE);
00179
00180 state = atoi(first_token(line));
00181 terminal = atoi(next_token());
00182 next_state = atoi(next_token());
00183 sscanf(next_token(), "%x", &status);
00184
00185 if (state >= dinfo->maxstatenum) {
00186 dfa_state_expand(dinfo, state+1);
00187 }
00188 if (next_state >= dinfo->maxstatenum) {
00189 dfa_state_expand(dinfo, next_state+1);
00190 }
00191
00192
00193 if (status & ACCEPT_S) {
00194 dinfo->st[state].status |= ACCEPT_S;
00195 }
00196
00197 if (state == 0) {
00198 dinfo->st[state].status |= INITIAL_S;
00199 }
00200
00201
00202 if (terminal > 0 || next_state > 0) {
00203
00204 newarc = (DFA_ARC *)mymalloc(sizeof(DFA_ARC));
00205 newarc->label = terminal;
00206 newarc->to_state = next_state;
00207 newarc->next = dinfo->st[state].arc;
00208 dinfo->st[state].arc = newarc;
00209 (*arc_num)++;
00210 }
00211
00212 if (*state_max < state) *state_max = state;
00213 if (*terminal_max < terminal) *terminal_max = terminal;
00214
00215 return(TRUE);
00216 }
00217
00218
00219
00220
00229 void
00230 dfa_append(DFA_INFO *dst, DFA_INFO *src, int soffset, int coffset)
00231 {
00232 DFA_ARC *arc, *newarc;
00233 int s, state, terminal, next_state;
00234 unsigned int status;
00235
00236 for (s = 0; s < src->state_num; s++) {
00237 state = s + soffset;
00238 status = src->st[s].status;
00239 if (state >= dst->maxstatenum) {
00240 dfa_state_expand(dst, state+1);
00241 }
00242
00243 if (status & ACCEPT_S) {
00244 dst->st[state].status |= ACCEPT_S;
00245 }
00246
00247 if (s == 0) {
00248 dst->st[state].status |= INITIAL_S;
00249 }
00250 for (arc = src->st[s].arc; arc; arc = arc->next) {
00251 terminal = arc->label + coffset;
00252 next_state = arc->to_state + soffset;
00253
00254 if (next_state >= dst->maxstatenum) {
00255 dfa_state_expand(dst, next_state+1);
00256 }
00257
00258 newarc = (DFA_ARC *)mymalloc(sizeof(DFA_ARC));
00259 newarc->label = terminal;
00260 newarc->to_state = next_state;
00261 newarc->next = dst->st[state].arc;
00262 dst->st[state].arc = newarc;
00263
00264 dst->arc_num++;
00265 if (dst->term_num < terminal + 1) dst->term_num = terminal + 1;
00266 }
00267 if (dst->state_num < state + 1) dst->state_num = state + 1;
00268 }
00269 }