1 /* file fsaio.c - 11. 10. 94.
2 * 9/1/98. Change generator type from char to `gen'.
3 * 1.5.96. - adjusted kbm_type_names, srec_read and srec_print to deal with
4 * srec type "list of Integers".
5 * This file contains io-routines for manipulating finite state automata
6 * They can deal with both deterministic and non-deterministic automata,
7 * but the functions in fsa.c currently only deal with dfa's.
8 *
9 * 13.9.95. - wrote in code to handle srec type "list of words"
10 * 5.12.94. - changes for sparse storage type with some dense rows.
11 * 17.11.94. Added parts to do with labeled srec type.
12 */
13
14 #define MAXWORDLEN 65535
15
16 #include <stdlib.h>
17 #include "defs.h"
18 #include "fsa.h"
19 #include "externals.h"
20
21 char *kbm_type_names[] = {"simple", "identifiers", "words",
22 "list of words", "list of integers", "strings",
23 "labeled", "product"};
24 char *kbm_flag_names[] = {"DFA", "NFA", "MIDFA", "minimized",
25 "BFS", "accessible", "trim", "RWS"};
26 static gen *wbuffer; /* used only for calls of read_word - this can
27 * be allocated temporarily.
28 */
29
30 /* Functions defined in this file: */
31
32
33 /* Print the set record *srptr. Follows corresponding GAP routine.
34 * Currently, rather arbitrarily, identifiers and strings names are
35 * printed in dense format, and words and lists of words in sparse format.
36 */
srec_print(FILE * wfile,srec * srptr,char * name,int offset,char * endstring)37 void srec_print(FILE *wfile, srec *srptr, char *name, int offset,
38 char *endstring)
39
40 {
41 int ct, j, l;
42 srec sr;
43 boolean first;
44
45 sr = *srptr;
46 *kbm_buffer = '\0';
47 if (stringlen(name) == 0)
48 add_to_buffer(0, "rec(");
49 else {
50 add_to_buffer(12 + offset, name);
51 add_to_buffer(0, " := rec(");
52 }
53
54 printbuffer(wfile);
55 add_to_buffer(16 + offset, "type");
56 sprintf(kbm_buffer + stringlen(kbm_buffer), " := \"%s\",",
57 kbm_type_names[sr.type]);
58 printbuffer(wfile);
59
60 add_to_buffer(16 + offset, "size");
61 sprintf(kbm_buffer + stringlen(kbm_buffer), " := %d", sr.size);
62 if (sr.type != SIMPLE)
63 add_to_buffer(0, ",");
64 printbuffer(wfile);
65
66 if (sr.type == PRODUCT) {
67 add_to_buffer(16 + offset, "arity");
68 sprintf(kbm_buffer + stringlen(kbm_buffer), " := %d,", sr.arity);
69 printbuffer(wfile);
70
71 add_to_buffer(16 + offset, "padding");
72 sprintf(kbm_buffer + stringlen(kbm_buffer), " := %c,", sr.padding);
73 printbuffer(wfile);
74
75 srec_print(wfile, sr.base, "base", offset + 4, " ");
76 }
77
78 else if (sr.type == IDENTIFIERS) {
79 add_to_buffer(16 + offset, "format");
80 sprintf(kbm_buffer + stringlen(kbm_buffer), " := \"dense\",");
81 printbuffer(wfile);
82
83 add_to_buffer(16 + offset, "names");
84 sprintf(kbm_buffer + stringlen(kbm_buffer), " := [");
85 ct = 1;
86 while (ct <= sr.size) {
87 if (ct == 1 || stringlen(kbm_buffer) + stringlen(sr.names[ct]) <= 76) {
88 if (ct > 1)
89 add_to_buffer(0, ",");
90 sprintf(kbm_buffer + stringlen(kbm_buffer), "%s", sr.names[ct]);
91 }
92 else {
93 add_to_buffer(0, ",");
94 printbuffer(wfile);
95 add_to_buffer(21 + offset, "");
96 sprintf(kbm_buffer + stringlen(kbm_buffer), "%s", sr.names[ct]);
97 }
98 ct++;
99 }
100 add_to_buffer(0, "]");
101 printbuffer(wfile);
102 }
103
104 else if (sr.type == STRINGS) {
105 add_to_buffer(16 + offset, "format");
106 sprintf(kbm_buffer + stringlen(kbm_buffer), " := \"dense\",");
107 printbuffer(wfile);
108
109 add_to_buffer(16 + offset, "names");
110 sprintf(kbm_buffer + stringlen(kbm_buffer), " := [");
111 ct = 1;
112 while (ct <= sr.size) {
113 if (ct == 1 ||
114 stringlen(kbm_buffer) + stringlen(sr.names[ct]) + 2 <= 76) {
115 if (ct > 1)
116 add_to_buffer(0, ",");
117 sprintf(kbm_buffer + stringlen(kbm_buffer), "\"%s\"", sr.names[ct]);
118 }
119 else {
120 add_to_buffer(0, ",");
121 printbuffer(wfile);
122 add_to_buffer(21 + offset, "");
123 sprintf(kbm_buffer + stringlen(kbm_buffer), "\"%s\"", sr.names[ct]);
124 }
125 ct++;
126 }
127 add_to_buffer(0, "]");
128 printbuffer(wfile);
129 }
130
131 else if (sr.type == WORDS || sr.type == LISTOFWORDS) {
132 add_to_buffer(16 + offset, "alphabet");
133 sprintf(kbm_buffer + stringlen(kbm_buffer), " := [");
134 ct = 1;
135 while (ct <= sr.alphabet_size) {
136 if (ct == 1 || stringlen(kbm_buffer) + stringlen(sr.alphabet[ct]) <= 76) {
137 if (ct > 1)
138 add_to_buffer(0, ",");
139 sprintf(kbm_buffer + stringlen(kbm_buffer), "%s", sr.alphabet[ct]);
140 }
141 else {
142 add_to_buffer(0, ",");
143 printbuffer(wfile);
144 add_to_buffer(21 + offset, "");
145 sprintf(kbm_buffer + stringlen(kbm_buffer), "%s", sr.alphabet[ct]);
146 }
147 ct++;
148 }
149 add_to_buffer(0, "],");
150 printbuffer(wfile);
151
152 add_to_buffer(16 + offset, "format");
153 sprintf(kbm_buffer + stringlen(kbm_buffer), " := \"sparse\",");
154 printbuffer(wfile);
155
156 add_to_buffer(16 + offset, "names");
157 sprintf(kbm_buffer + stringlen(kbm_buffer), " := [");
158 printbuffer(wfile);
159 for (ct = 1; ct <= sr.size; ct++) {
160 /* If the set is large, we will format less nicely, to save space. */
161 if (sr.size > 128)
162 add_to_buffer(0, "\t");
163 else
164 add_to_buffer(12 + offset, "");
165 sprintf(kbm_buffer + stringlen(kbm_buffer), "[%d,", ct);
166 if (sr.type == WORDS)
167 add_word_to_buffer(wfile, sr.words[ct], sr.alphabet);
168 else {
169 add_to_buffer(0, "[");
170 j = 0;
171 while (sr.wordslist[ct][j]) {
172 if (j > 0)
173 add_to_buffer(0, ",");
174 if (stringlen(kbm_buffer) > 68) {
175 printbuffer(wfile);
176 if (sr.size > 128)
177 add_to_buffer(0, "\t ");
178 else
179 add_to_buffer(18 + offset, "");
180 }
181 add_word_to_buffer(wfile, sr.wordslist[ct][j], sr.alphabet);
182 j++;
183 }
184 add_to_buffer(0, "]");
185 }
186 if (ct == sr.size)
187 add_to_buffer(0, "]");
188 else
189 add_to_buffer(0, "],");
190 printbuffer(wfile);
191 }
192 add_to_buffer(11 + offset, "]");
193 printbuffer(wfile);
194 }
195
196 else if (sr.type == LISTOFINTS) {
197 add_to_buffer(16 + offset, "format");
198 sprintf(kbm_buffer + stringlen(kbm_buffer), " := \"sparse\",");
199 printbuffer(wfile);
200
201 add_to_buffer(16 + offset, "names");
202 sprintf(kbm_buffer + stringlen(kbm_buffer), " := [");
203 printbuffer(wfile);
204 for (ct = 1; ct <= sr.size; ct++) {
205 /* If the set is large, we will format less nicely, to save space. */
206 if (sr.size > 128)
207 add_to_buffer(0, "\t");
208 else
209 add_to_buffer(12 + offset, "");
210 sprintf(kbm_buffer + stringlen(kbm_buffer), "[%d,", ct);
211 add_to_buffer(0, "[");
212 l = sr.intlist[ct][0];
213 for (j = 1; j <= l; j++) {
214 if (j > 1)
215 add_to_buffer(0, ",");
216 if (stringlen(kbm_buffer) > 74) {
217 printbuffer(wfile);
218 if (sr.size > 128)
219 add_to_buffer(0, "\t ");
220 else
221 add_to_buffer(18 + offset, "");
222 }
223 sprintf(kbm_buffer + stringlen(kbm_buffer), "%d", sr.intlist[ct][j]);
224 }
225 add_to_buffer(0, "]");
226 if (ct == sr.size)
227 add_to_buffer(0, "]");
228 else
229 add_to_buffer(0, "],");
230 printbuffer(wfile);
231 }
232 add_to_buffer(11 + offset, "]");
233 printbuffer(wfile);
234 }
235
236 else if (sr.type == LABELED) {
237 srec_print(wfile, sr.labels, "labels", offset + 4, ",");
238
239 add_to_buffer(16 + offset, "format");
240 sprintf(kbm_buffer + stringlen(kbm_buffer), " := \"sparse\",");
241 printbuffer(wfile);
242
243 add_to_buffer(16 + offset, "setToLabels");
244 sprintf(kbm_buffer + stringlen(kbm_buffer), " := [");
245 printbuffer(wfile);
246 first = TRUE;
247 for (ct = 1; ct <= sr.size; ct++)
248 if (sr.setToLabels[ct] != 0) {
249 if (first)
250 first = FALSE;
251 else {
252 strcat(kbm_buffer, ",");
253 printbuffer(wfile);
254 }
255 if (sr.size <= 128)
256 add_to_buffer(21 + offset, "");
257 else
258 add_to_buffer(0, "\t");
259 sprintf(kbm_buffer + stringlen(kbm_buffer), "[%d,%d]", ct,
260 sr.setToLabels[ct]);
261 }
262 printbuffer(wfile);
263 add_to_buffer(21 + offset, "]");
264 printbuffer(wfile);
265 }
266
267 if (stringlen(name) == 0)
268 add_to_buffer(0, ")");
269 else
270 add_to_buffer(12 + offset, ")");
271 add_to_buffer(0, endstring);
272 printbuffer(wfile);
273 }
274
275 /* Print the table record *tableptr. */
table_print(FILE * wfile,table_struc * tableptr,char * name,int offset,char * endstring,int ns,int ne)276 void table_print(FILE *wfile, table_struc *tableptr, char *name, int offset,
277 char *endstring, int ns, int ne)
278
279 {
280 int **table, ct, g, i, k, nl, dr, *ptr, *ptre;
281 boolean dense, densepf, first, firstg;
282
283 table = tableptr->table_data_ptr;
284 dense = tableptr->table_type == DENSE;
285 densepf = tableptr->printing_format == DENSE;
286 dr = tableptr->denserows;
287
288 *kbm_buffer = '\0';
289 if (stringlen(name) == 0)
290 add_to_buffer(0, "rec(");
291 else {
292 add_to_buffer(12 + offset, name);
293 add_to_buffer(0, " := rec(");
294 }
295
296 printbuffer(wfile);
297
298 /* Calculate number of nonzero transitions - this ought to be stored in
299 * tableptr->numTransitions, but we won't rely on that (unless the table
300 * is stored externally).
301 */
302
303 add_to_buffer(offset + 16, "format");
304 if (densepf)
305 sprintf(kbm_buffer + stringlen(kbm_buffer), " := \"dense deterministic\",");
306 else
307 sprintf(kbm_buffer + stringlen(kbm_buffer), " := \"sparse\",");
308 printbuffer(wfile);
309
310 if (tableptr->filename == 0) {
311 if (dense) {
312 ct = 0;
313 for (g = 1; g <= ne; g++)
314 for (i = 1; i <= ns; i++)
315 if (target(dense, table, g, i, dr) != 0)
316 ct++;
317 }
318 else {
319 ct = 0;
320 for (g = 1; g <= ne; g++)
321 for (i = 1; i <= dr; i++)
322 if (target(dense, table, g, i, dr) != 0)
323 ct++;
324 if (dr < ns)
325 ct += (table[ns + 1] - table[dr + 1]) / 2;
326 }
327 tableptr->numTransitions = ct;
328 }
329
330 add_to_buffer(offset + 16, "numTransitions");
331 sprintf(kbm_buffer + stringlen(kbm_buffer), " := %d,",
332 tableptr->numTransitions);
333 printbuffer(wfile);
334
335 if (tableptr->filename) {
336 add_to_buffer(offset + 16, "filename");
337 sprintf(kbm_buffer + stringlen(kbm_buffer), " := \"%s\"",
338 tableptr->filename);
339 printbuffer(wfile);
340 if (stringlen(name) == 0)
341 add_to_buffer(0, ")");
342 else
343 add_to_buffer(12 + offset, ")");
344 add_to_buffer(0, endstring);
345 printbuffer(wfile);
346 return;
347 }
348
349 add_to_buffer(offset + 16, "transitions");
350 sprintf(kbm_buffer + stringlen(kbm_buffer), " := [");
351 if (ns == 0 || ns > 128)
352 printbuffer(wfile);
353 first = TRUE;
354 for (i = 1; i <= ns; i++) {
355 if (!first && ns <= 128)
356 add_to_buffer(offset + 21, "");
357 sprintf(kbm_buffer + stringlen(kbm_buffer), "[");
358 first = FALSE;
359 if (!dense && !densepf && i > dr) {
360 /* In this case we can print directly */
361 ptr = table[i];
362 ptre = table[i + 1];
363 firstg = TRUE;
364 while (ptr < ptre) {
365 if (!firstg)
366 sprintf(kbm_buffer + stringlen(kbm_buffer), ",");
367 firstg = FALSE;
368 g = *(ptr++);
369 k = *(ptr++);
370 nl = int_len(k) + 3 + int_len((int)g);
371 if (stringlen(kbm_buffer) + nl >= 76) {
372 printbuffer(wfile);
373 /* If the state-set is large, we format less nicely to save space. */
374 if (ns <= 128)
375 add_to_buffer(offset + 22, "");
376 else
377 add_to_buffer(0, " ");
378 }
379 sprintf(kbm_buffer + stringlen(kbm_buffer), "[%d,%d]", g, k);
380 }
381 }
382 else {
383 firstg = TRUE;
384 for (g = 1; g <= ne; g++) {
385 k = target(dense, table, g, i, dr);
386 if (densepf || k != 0) {
387 if (!firstg)
388 sprintf(kbm_buffer + stringlen(kbm_buffer), ",");
389 firstg = FALSE;
390 nl = densepf ? int_len(k) : int_len(k) + 3 + int_len((int)g);
391 if (stringlen(kbm_buffer) + nl >= 76) {
392 printbuffer(wfile);
393 if (ns <= 128)
394 add_to_buffer(offset + 22, "");
395 else
396 add_to_buffer(0, " ");
397 }
398 if (densepf)
399 sprintf(kbm_buffer + stringlen(kbm_buffer), "%d", k);
400 else
401 sprintf(kbm_buffer + stringlen(kbm_buffer), "[%d,%d]", g, k);
402 }
403 }
404 }
405 if (i < ns)
406 sprintf(kbm_buffer + stringlen(kbm_buffer), "],");
407 else
408 sprintf(kbm_buffer + stringlen(kbm_buffer), "] ");
409 if (tableptr->comment_state_numbers)
410 sprintf(kbm_buffer + stringlen(kbm_buffer), "#%d", i);
411 printbuffer(wfile);
412 }
413 add_to_buffer(offset + 20, "");
414 sprintf(kbm_buffer + stringlen(kbm_buffer), "]");
415 printbuffer(wfile);
416
417 if (stringlen(name) == 0)
418 add_to_buffer(0, ")");
419 else
420 add_to_buffer(12 + offset, ")");
421 add_to_buffer(0, endstring);
422 printbuffer(wfile);
423 }
424
fsa_print(FILE * wfile,fsa * fsaptr,char * name)425 void fsa_print(FILE *wfile, fsa *fsaptr, char *name)
426 {
427 int i, ns, ne;
428 boolean first;
429
430 if (kbm_print_level >= 3)
431 printf(" #Calling fsa_print.\n");
432 ns = fsaptr->states->size;
433 ne = fsaptr->alphabet->size;
434
435 *kbm_buffer = '\0';
436 if (stringlen(name) == 0)
437 add_to_buffer(0, "rec(");
438 else {
439 sprintf(kbm_buffer, "%s := rec(", name);
440 }
441 printbuffer(wfile);
442
443 add_to_buffer(16, "isFSA");
444 sprintf(kbm_buffer + stringlen(kbm_buffer), " := true,");
445 printbuffer(wfile);
446
447 srec_print(wfile, fsaptr->alphabet, "alphabet", 4, ",");
448
449 srec_print(wfile, fsaptr->states, "states", 4, ",");
450
451 add_to_buffer(16, "flags");
452 sprintf(kbm_buffer + stringlen(kbm_buffer), " := [");
453 first = TRUE;
454 for (i = 0; i < num_kbm_flag_strings; i++)
455 if (fsaptr->flags[i]) {
456 if (!first)
457 sprintf(kbm_buffer + stringlen(kbm_buffer), ",");
458 first = FALSE;
459 sprintf(kbm_buffer + stringlen(kbm_buffer), "\"%s\"", kbm_flag_names[i]);
460 }
461 sprintf(kbm_buffer + stringlen(kbm_buffer), "],");
462 printbuffer(wfile);
463
464 add_to_buffer(16, "initial");
465 sprintf(kbm_buffer + stringlen(kbm_buffer), " := [");
466 if (ns > 1 && ns == fsaptr->num_initial)
467 sprintf(kbm_buffer + stringlen(kbm_buffer), "1..%d", fsaptr->states->size);
468 else {
469 for (i = 1; i <= fsaptr->num_initial; i++) {
470 if (i > 1)
471 sprintf(kbm_buffer + stringlen(kbm_buffer), ",");
472 if (stringlen(kbm_buffer) + int_len(fsaptr->initial[i]) > 76) {
473 printbuffer(wfile);
474 add_to_buffer(21, "");
475 }
476 sprintf(kbm_buffer + stringlen(kbm_buffer), "%d", fsaptr->initial[i]);
477 }
478 }
479 sprintf(kbm_buffer + stringlen(kbm_buffer), "],");
480 printbuffer(wfile);
481
482 add_to_buffer(16, "accepting");
483 sprintf(kbm_buffer + stringlen(kbm_buffer), " := [");
484 if (ns > 1 && ns == fsaptr->num_accepting)
485 sprintf(kbm_buffer + stringlen(kbm_buffer), "1..%d", fsaptr->states->size);
486 else {
487 for (i = 1; i <= fsaptr->num_accepting; i++) {
488 if (i > 1)
489 sprintf(kbm_buffer + stringlen(kbm_buffer), ",");
490 if (stringlen(kbm_buffer) + int_len(fsaptr->accepting[i]) > 76) {
491 printbuffer(wfile);
492 add_to_buffer(21, "");
493 }
494 sprintf(kbm_buffer + stringlen(kbm_buffer), "%d", fsaptr->accepting[i]);
495 }
496 }
497 sprintf(kbm_buffer + stringlen(kbm_buffer), "],");
498 printbuffer(wfile);
499
500 /* If the fsa is not known to be deterministic (or (25.7.95.) possibly
501 * multiple start-state deterministic), we will print it sparsely
502 */
503 if (!fsaptr->flags[DFA] && !fsaptr->flags[MIDFA])
504 fsaptr->table->printing_format = SPARSE;
505 table_print(wfile, fsaptr->table, "table", 4, "", ns, ne);
506
507 sprintf(kbm_buffer, ");");
508 printbuffer(wfile);
509 }
510
511 /* Read the set record *srptr from rfile, assigning space as required.
512 * If maxsize is larger than srptr->size, and space is allocated for
513 * names or labels, then space is allocated for maxsize of these.
514 * This allows for possible later expansion.
515 */
srec_read(FILE * rfile,srec * srptr,int maxsize)516 void srec_read(FILE *rfile, srec *srptr, int maxsize)
517
518 {
519 int delim, i, j, k, l, ct, n;
520 boolean typeset, sizeset, baseset, arityset, paddingset, namesset, formatset,
521 labelsset, alphabetset, setToLabelsset, nonempty;
522 int *buf1, *buf2, *swapbuf, bufsize; /* for reading lists of integers */
523 gen *wbp;
524 storage_type st = DENSE;
525 read_ident(rfile, kbm_buffer, &delim, FALSE);
526 if (delim != '(' || strcmp(kbm_buffer, "rec") != 0) {
527 fprintf(stderr, "#Input error: \"rec(\" expected\n");
528 exit(1);
529 }
530
531 /* main loop reading the fields of the record follows. */
532 typeset = FALSE;
533 sizeset = FALSE;
534 baseset = FALSE;
535 arityset = FALSE;
536 paddingset = FALSE;
537 namesset = FALSE;
538 formatset = FALSE;
539 labelsset = FALSE;
540 alphabetset = FALSE;
541 setToLabelsset = FALSE;
542 do {
543 read_ident(rfile, kbm_buffer, &delim, FALSE);
544 if (delim != ':') {
545 fprintf(stderr, "#Input error: bad record field assignment\n");
546 exit(1);
547 }
548 check_next_char(rfile, '=');
549 if (strcmp(kbm_buffer, "type") == 0) {
550 typeset = TRUE;
551 read_string(rfile, kbm_buffer, &delim);
552 if (strcmp(kbm_buffer, "simple") == 0)
553 srptr->type = SIMPLE;
554 else if (strcmp(kbm_buffer, "identifiers") == 0)
555 srptr->type = IDENTIFIERS;
556 else if (strcmp(kbm_buffer, "group generators") == 0) {
557 /* put in for compatability with a variant (by Paul Sanders).
558 * Here the "names" field becomes "generatorOrder", and the
559 * format field is omitted, with dense format assumed.
560 */
561 formatset = TRUE;
562 st = DENSE;
563 srptr->type = IDENTIFIERS;
564 }
565 else if (strcmp(kbm_buffer, "words") == 0)
566 srptr->type = WORDS;
567 else if (strcmp(kbm_buffer, "list of words") == 0)
568 srptr->type = LISTOFWORDS;
569 else if (strcmp(kbm_buffer, "list of integers") == 0)
570 srptr->type = LISTOFINTS;
571 else if (strcmp(kbm_buffer, "strings") == 0)
572 srptr->type = STRINGS;
573 else if (strcmp(kbm_buffer, "product") == 0)
574 srptr->type = PRODUCT;
575 else if (strcmp(kbm_buffer, "labeled") == 0 ||
576 strcmp(kbm_buffer, "labelled") == 0)
577 srptr->type = LABELED;
578 else {
579 fprintf(stderr, "Error: unknown set-record type %s.\n", kbm_buffer);
580 exit(1);
581 }
582 }
583 else if (strcmp(kbm_buffer, "size") == 0) {
584 sizeset = TRUE;
585 read_int(rfile, &(srptr->size), &delim);
586 }
587 else if (strcmp(kbm_buffer, "arity") == 0) {
588 arityset = TRUE;
589 if (!typeset || srptr->type != PRODUCT) {
590 fprintf(stderr, "Error: arity field only used for product type.\n");
591 exit(1);
592 }
593 read_int(rfile, &(srptr->arity), &delim);
594 }
595 else if (strcmp(kbm_buffer, "padding") == 0) {
596 paddingset = TRUE;
597 if (!typeset || srptr->type != PRODUCT) {
598 fprintf(stderr, "Error: padding field only used for product type.\n");
599 exit(1);
600 }
601 read_ident(rfile, kbm_buffer, &delim, FALSE);
602 srptr->padding = kbm_buffer[0];
603 }
604 else if (strcmp(kbm_buffer, "base") == 0) {
605 baseset = TRUE;
606 if (!typeset || srptr->type != PRODUCT) {
607 fprintf(stderr, "Error: base field only used for product type.\n");
608 exit(1);
609 }
610 tmalloc(srptr->base, srec, 1);
611 srec_read(rfile, srptr->base, 0);
612 read_delim(rfile, &delim);
613 }
614 else if (strcmp(kbm_buffer, "format") == 0) {
615 formatset = TRUE;
616 if (srptr->type != IDENTIFIERS && srptr->type != WORDS &&
617 srptr->type != LISTOFWORDS && srptr->type != LISTOFINTS &&
618 srptr->type != STRINGS && srptr->type != LABELED) {
619 fprintf(stderr,
620 "Error: set-record type doesn't require format field.\n");
621 exit(1);
622 }
623 read_string(rfile, kbm_buffer, &delim);
624 if (strcmp(kbm_buffer, "dense") == 0)
625 st = DENSE;
626 else if (strcmp(kbm_buffer, "sparse") == 0)
627 st = SPARSE;
628 else {
629 fprintf(stderr, "Error: unknown storage type %s.\n", kbm_buffer);
630 exit(1);
631 }
632 }
633 else if (strcmp(kbm_buffer, "alphabet") == 0) {
634 alphabetset = TRUE;
635 if (srptr->type != WORDS && srptr->type != LISTOFWORDS) {
636 fprintf(stderr,
637 "Error: set-record type doesn't require alphabet field.\n");
638 exit(1);
639 }
640 check_next_char(rfile, '[');
641 i = 0;
642 do {
643 read_ident(rfile, kbm_buffer, &delim, TRUE);
644 if (stringlen(kbm_buffer) > 0) {
645 i++;
646 if (i > MAXGEN) {
647 fprintf(stderr, "Error: alphabet is too large.\n");
648 exit(1);
649 }
650 tmalloc(srptr->alphabet[i], char, stringlen(kbm_buffer) + 1);
651 strcpy(srptr->alphabet[i], kbm_buffer);
652 }
653 } while (delim != ']');
654 srptr->alphabet_size = i;
655 check_next_char(rfile, ',');
656 }
657 else if (strcmp(kbm_buffer, "names") == 0 ||
658 strcmp(kbm_buffer, "generatorOrder") == 0) {
659 if (!typeset || !sizeset || !formatset) {
660 fprintf(stderr,
661 "Error: type, size and format fields must precede names.\n");
662 exit(1);
663 }
664 if (srptr->type != IDENTIFIERS && srptr->type != WORDS &&
665 srptr->type != STRINGS && srptr->type != LISTOFWORDS &&
666 srptr->type != LISTOFINTS) {
667 fprintf(stderr,
668 "Error: set-record type doesn't require names field.\n");
669 exit(1);
670 }
671 namesset = TRUE;
672 check_next_char(rfile, '[');
673 if (maxsize < srptr->size)
674 maxsize = srptr->size;
675 maxsize++; /* hack (can't remember why) */
676 if (srptr->type == LISTOFWORDS)
677 tmalloc(srptr->wordslist, gen **,
678 maxsize + 1) else if (srptr->type == LISTOFINTS)
679 tmalloc(srptr->intlist, int *,
680 maxsize + 1) else if (srptr->type == WORDS)
681 tmalloc(srptr->words, gen *, maxsize + 1) else tmalloc(
682 srptr->names, char *, maxsize + 1);
683 if (srptr->type == WORDS || srptr->type == LISTOFWORDS) {
684 if (!alphabetset) {
685 fprintf(stderr, "Error: alphabet field must precede names.\n");
686 exit(1);
687 }
688 /* We now have to work out the algorithm for converting words to
689 * generator numbers, based on the alphabet names - similar to that in
690 * rwsio.c
691 */
692 process_names(srptr->alphabet, srptr->alphabet_size);
693 /* Finally allocate some space temporarily to read the words into. */
694 tmalloc(wbuffer, gen, MAXWORDLEN + 1);
695 }
696 if (st == DENSE) {
697 if (srptr->size == 0)
698 read_delim(rfile, &delim);
699 for (i = 1; i <= srptr->size; i++) {
700 if (srptr->type == IDENTIFIERS) {
701 read_ident(rfile, kbm_buffer, &delim, TRUE);
702 tmalloc(srptr->names[i], char, stringlen(kbm_buffer) + 1);
703 strcpy(srptr->names[i], kbm_buffer);
704 }
705 else if (srptr->type == STRINGS) {
706 read_string(rfile, kbm_buffer, &delim);
707 tmalloc(srptr->names[i], char, stringlen(kbm_buffer) + 1);
708 strcpy(srptr->names[i], kbm_buffer);
709 }
710 else if (srptr->type == WORDS) {
711 read_word(rfile, wbuffer, wbuffer + MAXWORDLEN, &delim,
712 srptr->alphabet, srptr->alphabet_size, TRUE);
713 tmalloc(srptr->words[i], gen, genstrlen(wbuffer) + 1);
714 genstrcpy(srptr->words[i], wbuffer);
715 }
716 else if (srptr->type == LISTOFWORDS) {
717 check_next_char(rfile, '[');
718 l = 0;
719 wbp = wbuffer;
720 do {
721 nonempty = read_word(rfile, wbp, wbuffer + MAXWORDLEN, &delim,
722 srptr->alphabet, srptr->alphabet_size, TRUE);
723 if (nonempty || l > 0 || delim != ']')
724 l++;
725 wbp += (genstrlen(wbp) + 1);
726 } while (delim != ']');
727 tmalloc(srptr->wordslist[i], gen *, l + 1);
728 wbp = wbuffer;
729 for (j = 0; j < l; j++) {
730 tmalloc(srptr->wordslist[i][j], gen, genstrlen(wbp) + 1);
731 genstrcpy(srptr->wordslist[i][j], wbp);
732 wbp += (genstrlen(wbp) + 1);
733 }
734 srptr->wordslist[i][l] = 0;
735 if (i < srptr->size)
736 check_next_char(rfile, ',');
737 else
738 check_next_char(rfile, ']');
739 }
740 else if (srptr->type == LISTOFINTS) {
741 check_next_char(rfile, '[');
742 ct = 0;
743 bufsize = 1024;
744 tmalloc(buf1, int, bufsize);
745 do {
746 if (!read_int(rfile, &j, &delim))
747 break; /* should only happen if list is empty */
748 ct++;
749 if (ct >= bufsize) {
750 bufsize *= 2;
751 tmalloc(buf2, int, bufsize);
752 for (k = 1; k < ct; k++)
753 buf2[k] = buf1[k];
754 tfree(buf1);
755 swapbuf = buf1;
756 buf1 = buf2;
757 buf2 = swapbuf;
758 }
759 buf1[ct] = j;
760 } while (delim != ']');
761 tmalloc(srptr->intlist[i], int, ct + 1);
762 for (j = 1; j <= ct; j++)
763 srptr->intlist[i][j] = buf1[j];
764 srptr->intlist[i][0] = ct;
765 if (i < srptr->size)
766 check_next_char(rfile, ',');
767 else
768 check_next_char(rfile, ']');
769 tfree(buf1);
770 }
771 }
772 }
773 else {
774 read_delim(rfile, &delim);
775 while (delim != ']') {
776 read_int(rfile, &i, &delim);
777 if (i <= 0 || i > srptr->size) {
778 fprintf(stderr, "Error: name-number out of range.\n");
779 exit(1);
780 }
781 if (srptr->type == IDENTIFIERS) {
782 read_ident(rfile, kbm_buffer, &delim, TRUE);
783 tmalloc(srptr->names[i], char, stringlen(kbm_buffer) + 1);
784 strcpy(srptr->names[i], kbm_buffer);
785 }
786 else if (srptr->type == STRINGS) {
787 read_string(rfile, kbm_buffer, &delim);
788 tmalloc(srptr->names[i], char, stringlen(kbm_buffer) + 1);
789 strcpy(srptr->names[i], kbm_buffer);
790 }
791 else if (srptr->type == WORDS) {
792 read_word(rfile, wbuffer, wbuffer + MAXWORDLEN, &delim,
793 srptr->alphabet, srptr->alphabet_size, TRUE);
794 tmalloc(srptr->words[i], gen, genstrlen(wbuffer) + 1);
795 genstrcpy(srptr->words[i], wbuffer);
796 }
797 else if (srptr->type == LISTOFWORDS) {
798 check_next_char(rfile, '[');
799 l = 0;
800 wbp = wbuffer;
801 do {
802 nonempty = read_word(rfile, wbp, wbuffer + MAXWORDLEN, &delim,
803 srptr->alphabet, srptr->alphabet_size, TRUE);
804 if (nonempty || l > 0 || delim != ']')
805 l++;
806 wbp += (genstrlen(wbp) + 1);
807 } while (delim != ']');
808 tmalloc(srptr->wordslist[i], gen *, l + 1);
809 wbp = wbuffer;
810 for (j = 0; j < l; j++) {
811 tmalloc(srptr->wordslist[i][j], gen, genstrlen(wbp) + 1);
812 genstrcpy(srptr->wordslist[i][j], wbp);
813 wbp += (genstrlen(wbp) + 1);
814 }
815 srptr->wordslist[i][l] = 0;
816 check_next_char(rfile, ']');
817 }
818 else if (srptr->type == LISTOFINTS) {
819 check_next_char(rfile, '[');
820 ct = 0;
821 bufsize = 1024;
822 tmalloc(buf1, int, bufsize);
823 do {
824 if (!read_int(rfile, &j, &delim))
825 break; /* should only happen if list is empty */
826 ct++;
827 if (ct >= bufsize) {
828 bufsize *= 2;
829 tmalloc(buf2, int, bufsize);
830 for (k = 1; k < ct; k++)
831 buf2[k] = buf1[k];
832 tfree(buf1);
833 swapbuf = buf1;
834 buf1 = buf2;
835 buf2 = swapbuf;
836 }
837 buf1[ct] = j;
838 } while (delim != ']');
839 tmalloc(srptr->intlist[i], int, ct + 1);
840 for (j = 1; j <= ct; j++)
841 srptr->intlist[i][j] = buf1[j];
842 srptr->intlist[i][0] = ct;
843 check_next_char(rfile, ']');
844 tfree(buf1);
845 }
846 read_delim(rfile, &delim);
847 if (delim == ',')
848 read_delim(rfile, &delim);
849 }
850 }
851 read_delim(rfile, &delim);
852 /* don't forget to de-allocate space for reading words if necessary */
853 if (srptr->type == WORDS || srptr->type == LISTOFWORDS)
854 tfree(wbuffer);
855 }
856 else if (strcmp(kbm_buffer, "labels") == 0) {
857 labelsset = TRUE;
858 if (!typeset || (srptr->type != LABELED)) {
859 fprintf(stderr, "Error: labels field only used for labeled type.\n");
860 exit(1);
861 }
862 tmalloc(srptr->labels, srec, 1);
863 srec_read(rfile, srptr->labels, 0);
864 read_delim(rfile, &delim);
865 if (srptr->labels->size > MAXUSHORT) {
866 fprintf(stderr, "Error: label-set can have size at most 65535.\n");
867 exit(1);
868 }
869 }
870 else if (strcmp(kbm_buffer, "setToLabels") == 0) {
871 setToLabelsset = TRUE;
872 if (!typeset || (srptr->type != LABELED)) {
873 fprintf(stderr,
874 "Error: setToLabels field only used for labeled type.\n");
875 exit(1);
876 }
877 if (!labelsset) {
878 fprintf(stderr, "Error: labels field must precede setToLabels.\n");
879 exit(1);
880 }
881 if (!formatset) {
882 fprintf(stderr, "Error: format field must precede setToLabels.\n");
883 exit(1);
884 }
885 check_next_char(rfile, '[');
886 if (maxsize < srptr->size)
887 maxsize = srptr->size;
888 tmalloc(srptr->setToLabels, setToLabelsType, maxsize + 1);
889 for (i = 0; i <= srptr->size; i++)
890 srptr->setToLabels[i] = 0;
891 if (st == DENSE) {
892 for (i = 1; i <= srptr->size; i++) {
893 read_int(rfile, &n, &delim);
894 if (n < 0 || n > srptr->labels->size) {
895 fprintf(stderr, "Error: label out of range.\n");
896 exit(1);
897 }
898 srptr->setToLabels[i] = n;
899 if (delim == ']')
900 break;
901 }
902 }
903 else {
904 read_delim(rfile, &delim);
905 while (delim != ']') {
906 read_int(rfile, &i, &delim);
907 if (i <= 0 || i > srptr->size) {
908 fprintf(stderr, "Error: label-number out of range.\n");
909 exit(1);
910 }
911 read_int(rfile, &n, &delim);
912 if (n < 0 || n > srptr->labels->size) {
913 fprintf(stderr, "Error: label out of range.\n");
914 exit(1);
915 }
916 srptr->setToLabels[i] = n;
917 read_delim(rfile, &delim);
918 if (delim == ',')
919 read_delim(rfile, &delim);
920 }
921 }
922 read_delim(rfile, &delim);
923 }
924 else {
925 printf("#Warning: Unknown field name %s.\n", kbm_buffer);
926 skip_gap_expression(rfile, &delim);
927 }
928 } while (delim != ')');
929
930 if (!typeset || !sizeset) {
931 fprintf(stderr, "Error: type and size fields must be set.\n");
932 exit(1);
933 }
934 if (srptr->type == IDENTIFIERS || srptr->type == WORDS ||
935 srptr->type == STRINGS || srptr->type == LISTOFWORDS ||
936 srptr->type == LISTOFINTS) {
937 if (!namesset) {
938 fprintf(stderr, "Error: set-record type requires names field.\n");
939 exit(1);
940 }
941 }
942 if (srptr->type == PRODUCT) {
943 if (!arityset || !paddingset || !baseset) {
944 fprintf(
945 stderr,
946 "Error: set-record type require arity, padding and base fields.\n");
947 exit(1);
948 }
949 /* The size of the set-record should be (n+1)^r or (n+1)^r-1, where
950 * n is the size of the base set, and r the arity.
951 */
952 n = srptr->base->size + 1;
953 for (i = 1; i < srptr->arity; i++)
954 n *= (srptr->base->size + 1);
955 if (srptr->size != n && srptr->size != n - 1) {
956 fprintf(stderr, "Error: set-record size wrong for product type.\n");
957 exit(1);
958 }
959 }
960 if (srptr->type == LABELED) {
961 if (!setToLabelsset) {
962 fprintf(stderr, "Error: set-record type require setToLabels field.\n");
963 exit(1);
964 }
965 }
966 }
967
968 /* Read the table_struc *tableptr from rfile, assigning space as required.
969 * dr is the number of rows stored densely if storage_type=SPARSE.
970 * ns and ne are the sizes of the state-set and alphabet-set.
971 * maxstates is the maximum number of states that we allocate space for
972 * in dense-storage mode.
973 * nondet is true if fsa-table is not known to be deterministic.
974 */
table_read(FILE * rfile,table_struc * tableptr,storage_type table_storage_type,int dr,int ns,int maxstates,int ne,boolean nondet)975 void table_read(FILE *rfile, table_struc *tableptr,
976 storage_type table_storage_type, int dr, int ns, int maxstates,
977 int ne, boolean nondet)
978 {
979 int delim, i, j, k, ntleft = 0, dt = 0;
980 boolean filenameset, numTransitionsset, transitionsset;
981 int **table, *sparseptr = 0;
982
983 numTransitionsset = FALSE;
984 transitionsset = FALSE;
985 filenameset = FALSE;
986
987 read_ident(rfile, kbm_buffer, &delim, FALSE);
988 if (delim != '(' || strcmp(kbm_buffer, "rec") != 0) {
989 fprintf(stderr, "#Input error: \"rec(\" expected\n");
990 exit(1);
991 }
992
993 /* main loop reading the fields of the record follows. */
994 do {
995 read_ident(rfile, kbm_buffer, &delim, FALSE);
996 if (delim != ':') {
997 fprintf(stderr, "#Input error: bad record field assignment\n");
998 exit(1);
999 }
1000 check_next_char(rfile, '=');
1001 if (strcmp(kbm_buffer, "filename") == 0) {
1002 /* In this case, the transition table (and possibly other info) is stored
1003 * externally in the file "filename"
1004 */
1005 if (transitionsset) {
1006 fprintf(stderr, "#Input error - filename and transitions fields are "
1007 "both present.\n");
1008 exit(1);
1009 }
1010 filenameset = TRUE;
1011 read_string(rfile, kbm_buffer, &delim);
1012 tmalloc(tableptr->filename, char, stringlen(kbm_buffer) + 1);
1013 strcpy(tableptr->filename, kbm_buffer);
1014 }
1015 else if (strcmp(kbm_buffer, "format") == 0) {
1016 read_string(rfile, kbm_buffer, &delim);
1017 if (strcmp(kbm_buffer, "dense deterministic") == 0)
1018 tableptr->printing_format = DENSE;
1019 else if (strcmp(kbm_buffer, "sparse") == 0)
1020 tableptr->printing_format = SPARSE;
1021 else {
1022 fprintf(stderr, "Error: invalid format value %s\n", kbm_buffer);
1023 exit(1);
1024 }
1025 }
1026 else if (strcmp(kbm_buffer, "numTransitions") == 0) {
1027 numTransitionsset = TRUE;
1028 read_int(rfile, &(tableptr->numTransitions), &delim);
1029 }
1030 else if (strcmp(kbm_buffer, "defaultTarget") == 0) {
1031 read_int(rfile, &dt, &delim);
1032 if (dt != 0)
1033 /* Our code doesn't currently cope with this, so we will enforce
1034 * storage-type dense in this case.
1035 */
1036 table_storage_type = DENSE;
1037 }
1038 else if (strcmp(kbm_buffer, "transitions") == 0) {
1039 if (filenameset) {
1040 fprintf(stderr, "#Input error - filename and transitions fields are "
1041 "both present.\n");
1042 exit(1);
1043 }
1044 transitionsset = TRUE;
1045 if (!numTransitionsset) {
1046 /* In this case, we have currently to use dense storage */
1047 if (nondet) {
1048 fprintf(stderr, "Error: In a non-deterministic trnasition table\n");
1049 fprintf(stderr, "you must include the 'numTransitions' field,\n");
1050 exit(1);
1051 }
1052 table_storage_type = DENSE;
1053 }
1054 tableptr->table_type = table_storage_type;
1055 if (table_storage_type == SPARSE) {
1056 if (dr > ns)
1057 dr = ns;
1058 tableptr->denserows = dr;
1059 }
1060 tableptr->maxstates = maxstates;
1061 /* assign space according to storage type */
1062 if (table_storage_type == DENSE) {
1063 fsa_table_init(tableptr, maxstates, ne);
1064 table = tableptr->table_data_ptr;
1065 }
1066 else {
1067 tmalloc(tableptr->table_data_ptr, int *, ns + 2);
1068 table = tableptr->table_data_ptr;
1069 if (dr > 0) {
1070 /* Here we have to read in the data in two separate chunks. */
1071 tmalloc(table[0], int, dr *ne);
1072 for (i = 1; i <= dr; i++)
1073 table[i] = table[0] + (i - 1) * ne - 1;
1074 ntleft = tableptr->numTransitions;
1075 }
1076 else {
1077 tmalloc(table[0], int, 2 * tableptr->numTransitions + 1);
1078 sparseptr = table[0];
1079 }
1080 }
1081 /* Now read the transitions */
1082 check_next_char(rfile, '[');
1083 for (i = 1; i <= ns; i++) {
1084 check_next_char(rfile, '[');
1085 if (table_storage_type == SPARSE) {
1086 if (dr > 0 && i == dr + 1) { /* allocate remaining storage */
1087 tmalloc(table[i], int, 2 * ntleft + 1);
1088 sparseptr = table[i];
1089 }
1090 else if (i > dr)
1091 table[i] = sparseptr;
1092 }
1093 if (tableptr->printing_format == DENSE) {
1094 if (ne == 0)
1095 read_delim(rfile, &delim);
1096 else
1097 for (j = 1; j <= ne; j++) {
1098 read_int(rfile, &k, &delim);
1099 if (table_storage_type == DENSE)
1100 table[j][i] = k;
1101 else if (i <= dr) {
1102 table[i][j] = k;
1103 if (k != 0)
1104 ntleft--;
1105 }
1106 else if (k != 0) {
1107 *(sparseptr++) = j;
1108 *(sparseptr++) = k;
1109 }
1110 if (k > ns) {
1111 fprintf(stderr,
1112 "Error: transition target out of range in table.\n");
1113 exit(1);
1114 }
1115 }
1116 if (delim != ']') {
1117 fprintf(stderr, "Error: format error in table.\n");
1118 exit(1);
1119 }
1120 }
1121 else {
1122 if (table_storage_type == DENSE)
1123 for (j = 1; j <= ne; j++)
1124 table[j][i] = dt; /* in case there is a default target */
1125 else if (i <= dr)
1126 for (j = 1; j <= ne; j++)
1127 table[i][j] = 0;
1128 read_delim(rfile, &delim);
1129 while (delim != ']') {
1130 read_int(rfile, &j, &delim);
1131 read_int(rfile, &k, &delim);
1132 if (table_storage_type == DENSE)
1133 table[j][i] = k;
1134 else if (i <= dr) {
1135 table[i][j] = k;
1136 if (k != 0)
1137 ntleft--;
1138 }
1139 else if (k != 0) {
1140 *(sparseptr++) = j;
1141 *(sparseptr++) = k;
1142 }
1143 if (k > ns) {
1144 fprintf(stderr,
1145 "Error: transition target out of range in table.\n");
1146 exit(1);
1147 }
1148 read_delim(rfile, &delim);
1149 if (delim == ',')
1150 read_delim(rfile, &delim);
1151 }
1152 }
1153 read_delim(rfile, &delim);
1154 }
1155 if (ns == 0)
1156 read_delim(rfile, &delim);
1157 if (table_storage_type == SPARSE && (ns > dr || ns == 0))
1158 /* Set extra pointer to show end of data */
1159 table[ns + 1] = sparseptr;
1160 read_delim(rfile, &delim);
1161 }
1162 else {
1163 printf("#Warning: Unknown field name %s.\n", kbm_buffer);
1164 skip_gap_expression(rfile, &delim);
1165 }
1166 } while (delim != ')');
1167
1168 if (!transitionsset && !filenameset) {
1169 fprintf(stderr, "transitions and filename fields are not set.\n");
1170 exit(1);
1171 }
1172 if (filenameset)
1173 /* In this case, the storage_type has to be as specified by the format field
1174 */
1175 tableptr->table_type = tableptr->printing_format;
1176 }
1177
1178 /* Read the fsa *fsaptr from rfile, assigning space as required.
1179 * If maxstates is greater than the actual number of states, then
1180 * space will be assigned for maxstates states, to allow more states
1181 * to be added later (this only makes sense with dense storage_type).
1182 * If assignment is true, an assignment to an fsa is read.
1183 * The name is returned in *name, which is assumed to have enough space.
1184 */
fsa_read(FILE * rfile,fsa * fsaptr,storage_type table_storage_type,int dr,int maxstates,boolean assignment,char * name)1185 void fsa_read(FILE *rfile, fsa *fsaptr, storage_type table_storage_type, int dr,
1186 int maxstates, boolean assignment, char *name)
1187 {
1188 int delim, i, j, k, ct, ns = 0, ne = 0, *ia, *buf1, *buf2, *swapbuf, bufsize;
1189 boolean isFSAset, statesset, alphabetset, initialset, acceptingset, flagsset,
1190 tableset, in, compressed;
1191
1192 if (kbm_print_level >= 3)
1193 printf(" #Calling fsa_read.\n");
1194 isFSAset = FALSE;
1195 isFSAset = FALSE;
1196 statesset = FALSE;
1197 alphabetset = FALSE;
1198 initialset = FALSE;
1199 acceptingset = FALSE;
1200 flagsset = FALSE;
1201 tableset = FALSE;
1202
1203 fsa_init(fsaptr);
1204
1205 if (assignment) {
1206 read_ident(rfile, kbm_buffer, &delim, FALSE);
1207 if (delim != ':') {
1208 fprintf(stderr, "#Input error: file must contain a record assignment\n");
1209 exit(1);
1210 }
1211 strcpy(name, kbm_buffer);
1212 check_next_char(rfile, '=');
1213 }
1214
1215 read_ident(rfile, kbm_buffer, &delim, FALSE);
1216 if (delim != '(' || strcmp(kbm_buffer, "rec") != 0) {
1217 fprintf(stderr, "#Input error: \"rec(\" expected\n");
1218 exit(1);
1219 }
1220
1221 /* main loop reading the fields of the record follows. */
1222 do {
1223 read_ident(rfile, kbm_buffer, &delim, FALSE);
1224 if (delim != ':') {
1225 fprintf(stderr, "#Input error: bad record field assignment\n");
1226 exit(1);
1227 }
1228 check_next_char(rfile, '=');
1229 if (strcmp(kbm_buffer, "isFSA") == 0) {
1230 isFSAset = TRUE;
1231 read_ident(rfile, kbm_buffer, &delim, FALSE);
1232 if (strcmp(kbm_buffer, "true") != 0) {
1233 fprintf(stderr, "#Input error: isFSA field must equal \"true\"\n");
1234 exit(1);
1235 }
1236 }
1237 else if (strcmp(kbm_buffer, "states") == 0) {
1238 statesset = TRUE;
1239 srec_read(rfile, fsaptr->states, maxstates);
1240 ns = fsaptr->states->size;
1241 read_delim(rfile, &delim);
1242 }
1243 else if (strcmp(kbm_buffer, "alphabet") == 0) {
1244 alphabetset = TRUE;
1245 srec_read(rfile, fsaptr->alphabet, 0);
1246 ne = fsaptr->alphabet->size;
1247 read_delim(rfile, &delim);
1248 }
1249 else if (strcmp(kbm_buffer, "flags") == 0) {
1250 flagsset = TRUE;
1251 check_next_char(rfile, '[');
1252 do {
1253 read_string(rfile, kbm_buffer, &delim);
1254 for (i = 0; i < num_kbm_flag_strings; i++)
1255 if (strcmp(kbm_buffer, kbm_flag_names[i]) == 0)
1256 fsaptr->flags[(kbm_flag_strings)i] = TRUE;
1257 } while (delim != ']');
1258 read_delim(rfile, &delim);
1259 /* If the fsa is not known to be deterministic (or (25.7.95.) possibly
1260 * multiple start-state deterministic), then we should store is in
1261 * sparse format
1262 */
1263 if (!fsaptr->flags[DFA] && !fsaptr->flags[MIDFA]) {
1264 table_storage_type = SPARSE;
1265 dr = 0;
1266 }
1267 }
1268 else if (strcmp(kbm_buffer, "initial") == 0 ||
1269 strcmp(kbm_buffer, "accepting") == 0) {
1270 /* We'll handle these together since they are so similar. */
1271 compressed = FALSE;
1272 bufsize = 1024;
1273 in = strcmp(kbm_buffer, "initial") == 0;
1274 if (!statesset) {
1275 fprintf(
1276 stderr,
1277 "Error: states field must precede initial and accepting fields.\n");
1278 exit(1);
1279 }
1280 ct = 0;
1281 tmalloc(buf1, int, bufsize);
1282 /* We don't know how long the list will be in advance */
1283 check_next_char(rfile, '[');
1284 do {
1285 read_int(rfile, &i, &delim);
1286 if (i < 0 || i > ns) {
1287 fprintf(stderr,
1288 "Invalid state number in initial or accepting list.\n");
1289 exit(1);
1290 }
1291 if (i > 0) {
1292 ct++;
1293 if (delim == '.') {
1294 compressed = TRUE;
1295 if (ct != 1) {
1296 fprintf(stderr,
1297 "Error in format of initial or accepting field.\n");
1298 exit(1);
1299 }
1300 check_next_char(rfile, '.');
1301 read_int(rfile, &j, &delim);
1302 if (j >= i && j <= ns) {
1303 if (delim != ']') {
1304 fprintf(stderr,
1305 "Error in format of initial or accepting field.\n");
1306 exit(1);
1307 }
1308 ct = j - i + 1;
1309 if (ct == 1 || ct != ns || in) {
1310 /* if ct = ns, we don't store the list of accept states. */
1311 tmalloc(ia, int, ct + 1);
1312 if (in)
1313 fsaptr->initial = ia;
1314 else
1315 fsaptr->accepting = ia;
1316 for (k = 1; k <= ct; k++)
1317 ia[k] = k + i - 1;
1318 }
1319 }
1320 else {
1321 fprintf(stderr,
1322 "Error in format of initial or accepting field.\n");
1323 exit(1);
1324 }
1325 }
1326 else {
1327 compressed = FALSE;
1328 if (ct >= bufsize) {
1329 bufsize *= 2;
1330 tmalloc(buf2, int, bufsize);
1331 for (j = 1; j < ct; j++)
1332 buf2[j] = buf1[j];
1333 tfree(buf1);
1334 swapbuf = buf1;
1335 buf1 = buf2;
1336 buf2 = swapbuf;
1337 }
1338 buf1[ct] = i;
1339 }
1340 } /* if (i>0) */
1341 } while (delim != ']');
1342 if (!compressed) {
1343 tmalloc(ia, int, ct + 1);
1344 if (in)
1345 fsaptr->initial = ia;
1346 else
1347 fsaptr->accepting = ia;
1348 for (i = 1; i <= ct; i++)
1349 ia[i] = buf1[i];
1350 }
1351 tfree(buf1);
1352 if (in) {
1353 initialset = TRUE;
1354 fsaptr->num_initial = ct;
1355 }
1356 else {
1357 acceptingset = TRUE;
1358 fsaptr->num_accepting = ct;
1359 }
1360 read_delim(rfile, &delim);
1361 }
1362 else if (strcmp(kbm_buffer, "table") == 0) {
1363 if (!statesset) {
1364 fprintf(stderr, "Error: states field must precede table fields.\n");
1365 exit(1);
1366 }
1367 if (!alphabetset) {
1368 fprintf(stderr, "Error: alphabet field must precede table fields.\n");
1369 exit(1);
1370 }
1371 tableset = TRUE;
1372 if (fsaptr->alphabet->type == PRODUCT)
1373 k = fsaptr->alphabet->base->size;
1374 else
1375 k = -1;
1376 if (maxstates < ns)
1377 maxstates = ns;
1378 if (!fsaptr->flags[DFA] && !fsaptr->flags[MIDFA])
1379 table_read(rfile, fsaptr->table, table_storage_type, dr, ns, maxstates,
1380 ne, TRUE);
1381 else
1382 table_read(rfile, fsaptr->table, table_storage_type, dr, ns, maxstates,
1383 ne, FALSE);
1384 read_delim(rfile, &delim);
1385 }
1386 else {
1387 printf("#Warning: Unknown field name %s.\n", kbm_buffer);
1388 skip_gap_expression(rfile, &delim);
1389 }
1390 } while (delim != ')');
1391
1392 if (!isFSAset || !statesset || !alphabetset || !initialset || !acceptingset ||
1393 !flagsset || !tableset) {
1394 fprintf(stderr, "One of the compulsory fsa-fields is not set.\n");
1395 exit(1);
1396 }
1397 if (assignment)
1398 read_delim(rfile, &delim);
1399 }
1400
1401 /* Read the transition-table of the fsa *fsaptr which is stored in the
1402 * file with *file in unformatted form.
1403 * *file should be opened and closed externally to the function.
1404 * This is used by the functions in fsalogic.c
1405 */
compressed_transitions_read(fsa * fsaptr,FILE * rfile)1406 void compressed_transitions_read(fsa *fsaptr, FILE *rfile)
1407 {
1408 int ns, ne, nt, **table, *tab_ptr, len, i, j;
1409
1410 ns = fsaptr->states->size;
1411 ne = fsaptr->alphabet->size;
1412 nt = fsaptr->table->numTransitions;
1413
1414 if (fsaptr->table->table_type == DENSE) {
1415 /* it is a pity that the table was output in transposed form! */
1416 fsa_table_init(fsaptr->table, ns, ne);
1417 table = fsaptr->table->table_data_ptr;
1418 for (i = 1; i <= ns; i++)
1419 for (j = 1; j <= ne; j++) {
1420 size_t s = fread((void *)(table[j] + i), sizeof(int), (size_t)1, rfile);
1421 (void)s; // HACK to silence compiler warning
1422 }
1423 }
1424 else {
1425 tmalloc(fsaptr->table->table_data_ptr, int *, ns + 2);
1426 tmalloc(fsaptr->table->table_data_ptr[0], int, 2 * nt + 1);
1427 tab_ptr = fsaptr->table->table_data_ptr[0];
1428 table = fsaptr->table->table_data_ptr;
1429 for (i = 1; i <= ns; i++) {
1430 table[i] = tab_ptr;
1431 fread((void *)&len, sizeof(int), (size_t)1, rfile);
1432 if (len > 0)
1433 fread((void *)tab_ptr, sizeof(int), (size_t)len, rfile);
1434 tab_ptr += len;
1435 }
1436 table[ns + 1] = tab_ptr;
1437 }
1438 }
1439