00001
00018
00019
00020
00021
00022
00023
00024
00025 #include <sent/stddefs.h>
00026 #include <sent/dfa.h>
00027
00028 static char buf[MAXLINELEN];
00029
00035 void
00036 dfa_state_init(DFA_INFO *dinfo)
00037 {
00038 int i;
00039 dinfo->maxstatenum = DFA_STATESTEP;
00040 dinfo->st = (DFA_STATE *)mymalloc(sizeof(DFA_STATE) * dinfo->maxstatenum);
00041 for (i=0;i<dinfo->maxstatenum;i++) {
00042 dinfo->st[i].number = i;
00043 dinfo->st[i].status = 0;
00044 dinfo->st[i].arc = NULL;
00045 }
00046 dinfo->state_num = dinfo->arc_num = dinfo->term_num = 0;
00047 dinfo->sp_id = WORD_INVALID;
00048 }
00049
00056 void
00057 dfa_state_expand(DFA_INFO *dinfo, int needed)
00058 {
00059 int oldnum, i;
00060 oldnum = dinfo->maxstatenum;
00061 dinfo->maxstatenum += DFA_STATESTEP;
00062 if (dinfo->maxstatenum < needed) dinfo->maxstatenum = needed;
00063 dinfo->st = (DFA_STATE *)myrealloc(dinfo->st, sizeof(DFA_STATE) * dinfo->maxstatenum);
00064 for (i=oldnum;i<dinfo->maxstatenum;i++) {
00065 dinfo->st[i].number = i;
00066 dinfo->st[i].status = 0;
00067 dinfo->st[i].arc = NULL;
00068 }
00069 }
00070
00079 boolean
00080 rddfa(FILE *fp, DFA_INFO *dinfo)
00081 {
00082 int state_max, arc_num, terminal_max;
00083
00084
00085 dfa_state_init(dinfo);
00086 state_max = 0;
00087 arc_num = 0;
00088 terminal_max = 0;
00089
00090 while (getl(buf, MAXLINELEN, fp) != NULL) {
00091 if (rddfa_line(buf, dinfo, &state_max, &arc_num, &terminal_max) == FALSE) {
00092 break;
00093 }
00094 }
00095 dinfo->state_num = state_max + 1;
00096 dinfo->arc_num = arc_num;
00097 dinfo->term_num = terminal_max + 1;
00098 return(TRUE);
00099 }
00100
00109 boolean
00110 rddfa_fp(FILE *fp, DFA_INFO *dinfo)
00111 {
00112 int state_max, arc_num, terminal_max;
00113
00114
00115 dfa_state_init(dinfo);
00116 state_max = 0;
00117 arc_num = 0;
00118 terminal_max = 0;
00119
00120 while(getl_fp(buf, MAXLINELEN, fp) != NULL) {
00121 if (rddfa_line(buf, dinfo, &state_max, &arc_num, &terminal_max) == FALSE) {
00122 break;
00123 }
00124 }
00125 dinfo->state_num = state_max + 1;
00126 dinfo->arc_num = arc_num;
00127 dinfo->term_num = terminal_max + 1;
00128 return(TRUE);
00129 }
00130
00142 boolean
00143 rddfa_line(char *line, DFA_INFO *dinfo, int *state_max, int *arc_num, int *terminal_max)
00144 {
00145 DFA_ARC *newarc;
00146 int state, terminal, next_state;
00147 unsigned int status;
00148 char *p;
00149
00150 if (strmatch(buf, "DFAEND")) return(FALSE);
00151
00152 if ((p = strtok(line, DELM)) == NULL) {
00153 jlog("Error: rddfa: failed to parse, corrupted or invalid data?\n");
00154 return FALSE;
00155 }
00156 state = atoi(p);
00157 if ((p = strtok(NULL, DELM)) == NULL) {
00158 jlog("Error: rddfa: failed to parse, corrupted or invalid data?\n");
00159 return FALSE;
00160 }
00161 terminal = atoi(p);
00162 if ((p = strtok(NULL, DELM)) == NULL) {
00163 jlog("Error: rddfa: failed to parse, corrupted or invalid data?\n");
00164 return FALSE;
00165 }
00166 next_state = atoi(p);
00167 if ((p = strtok(NULL, DELM)) == NULL) {
00168 jlog("Error: rddfa: failed to parse, corrupted or invalid data?\n");
00169 return FALSE;
00170 }
00171 sscanf(p, "%x", &status);
00172
00173 if (state >= dinfo->maxstatenum) {
00174 dfa_state_expand(dinfo, state+1);
00175 }
00176 if (next_state >= dinfo->maxstatenum) {
00177 dfa_state_expand(dinfo, next_state+1);
00178 }
00179
00180
00181 if (status & ACCEPT_S) {
00182 dinfo->st[state].status |= ACCEPT_S;
00183 }
00184
00185 if (state == 0) {
00186 dinfo->st[state].status |= INITIAL_S;
00187 }
00188
00189
00190 if (terminal > 0 || next_state > 0) {
00191
00192 newarc = (DFA_ARC *)mymalloc(sizeof(DFA_ARC));
00193 newarc->label = terminal;
00194 newarc->to_state = next_state;
00195 newarc->next = dinfo->st[state].arc;
00196 dinfo->st[state].arc = newarc;
00197 (*arc_num)++;
00198 }
00199
00200 if (*state_max < state) *state_max = state;
00201 if (*terminal_max < terminal) *terminal_max = terminal;
00202
00203 return(TRUE);
00204 }
00205
00206
00207
00208
00217 void
00218 dfa_append(DFA_INFO *dst, DFA_INFO *src, int soffset, int coffset)
00219 {
00220 DFA_ARC *arc, *newarc;
00221 int s, state, terminal, next_state;
00222 unsigned int status;
00223
00224 for (s = 0; s < src->state_num; s++) {
00225 state = s + soffset;
00226 status = src->st[s].status;
00227 if (state >= dst->maxstatenum) {
00228 dfa_state_expand(dst, state+1);
00229 }
00230
00231 if (status & ACCEPT_S) {
00232 dst->st[state].status |= ACCEPT_S;
00233 }
00234
00235 if (s == 0) {
00236 dst->st[state].status |= INITIAL_S;
00237 }
00238 for (arc = src->st[s].arc; arc; arc = arc->next) {
00239 terminal = arc->label + coffset;
00240 next_state = arc->to_state + soffset;
00241
00242 if (next_state >= dst->maxstatenum) {
00243 dfa_state_expand(dst, next_state+1);
00244 }
00245
00246 newarc = (DFA_ARC *)mymalloc(sizeof(DFA_ARC));
00247 newarc->label = terminal;
00248 newarc->to_state = next_state;
00249 newarc->next = dst->st[state].arc;
00250 dst->st[state].arc = newarc;
00251
00252 dst->arc_num++;
00253 if (dst->term_num < terminal + 1) dst->term_num = terminal + 1;
00254 }
00255 if (dst->state_num < state + 1) dst->state_num = state + 1;
00256 }
00257 }