1 /**************************************************************************/
2 /* */
3 /* OCaml */
4 /* */
5 /* Xavier Leroy, projet Cristal, INRIA Rocquencourt */
6 /* */
7 /* Copyright 1996 Institut National de Recherche en Informatique et */
8 /* en Automatique. */
9 /* */
10 /* All rights reserved. This file is distributed under the terms of */
11 /* the GNU Lesser General Public License version 2.1, with the */
12 /* special exception on linking described in the file LICENSE. */
13 /* */
14 /**************************************************************************/
15
16 /* Based on public-domain code from Berkeley Yacc */
17
18 #include "defs.h"
19
20 static int nvectors;
21 static int nentries;
22 static short **froms;
23 static short **tos;
24 static short *tally;
25 static short *width;
26 static short *state_count;
27 static short *order;
28 static short *base;
29 static short *pos;
30 static int maxtable;
31 static short *table;
32 static short *check;
33 static int lowzero;
34 static int high;
35
36
37 void free_itemsets (void);
38 void free_shifts (void);
39 void free_reductions (void);
40 void output_stored_text (void);
41 void output_transl (void);
42 void output_rule_data (void);
43 void output_yydefred (void);
44 void output_actions (void);
45 void output_debug (void);
46 void output_trailing_text (void);
47 void output_semantic_actions (void);
48 void output_entries (void);
49 void token_actions (void);
50 void goto_actions (void);
51 void sort_actions (void);
52 void pack_table (void);
53 void output_base (void);
54 void output_table (void);
55 void output_check (void);
56 int default_goto (int symbol);
57 void save_column (int symbol, int default_state);
58 int matching_vector (int vector);
59 int pack_vector (int vector);
60
61
output(void)62 void output(void)
63 {
64 extern char *header[], *define_tables[];
65
66 free_itemsets();
67 free_shifts();
68 free_reductions();
69 write_section(header);
70 output_stored_text();
71 output_transl();
72 output_rule_data();
73 output_yydefred();
74 output_actions();
75 output_debug();
76 free_parser();
77 if (sflag){
78 if (!rflag) ++outline;
79 fprintf(output_file,
80 "let yyact = Array.new %d (fun _ -> (failwith \"parser\" : Obj.t))\n",
81 ntotalrules);
82 }else{
83 if (!rflag) outline += 2;
84 fprintf(output_file,
85 "let yyact = [|\n (fun _ -> failwith \"parser\")\n");
86 }
87 output_semantic_actions();
88 if (!sflag){
89 if (!rflag) ++outline;
90 fprintf(output_file, "|]\n");
91 }
92 write_section(define_tables);
93 output_entries();
94 output_trailing_text();
95 }
96
97
output_char(unsigned int n)98 static void output_char(unsigned int n)
99 {
100 n = n & 0xFF;
101 putc('\\', output_file);
102 putc('0' + n / 100, output_file);
103 putc('0' + (n / 10) % 10, output_file);
104 putc('0' + n % 10, output_file);
105 }
106
output_short(int n)107 static void output_short(int n)
108 {
109 output_char(n);
110 output_char(n >> 8);
111 }
112
output_rule_data(void)113 void output_rule_data(void)
114 {
115 register int i;
116 register int j;
117
118
119 fprintf(output_file, "let yylhs = \"");
120 output_short(symbol_value[start_symbol]);
121
122 j = 8;
123 for (i = 3; i < nrules; i++)
124 {
125 if (j >= 8)
126 {
127 if (!rflag) ++outline;
128 fprintf(output_file, "\\\n");
129 j = 1;
130 }
131 else
132 ++j;
133
134 output_short(symbol_value[rlhs[i]]);
135 }
136 if (!rflag) outline += 2;
137 fprintf(output_file, "\"\n\n");
138
139 fprintf(output_file, "let yylen = \"");
140 output_short(2);
141
142 j = 8;
143 for (i = 3; i < nrules; i++)
144 {
145 if (j >= 8)
146 {
147 if (!rflag) ++outline;
148 fprintf(output_file, "\\\n");
149 j = 1;
150 }
151 else
152 j++;
153
154 output_short(rrhs[i + 1] - rrhs[i] - 1);
155 }
156 if (!rflag) outline += 2;
157 fprintf(output_file, "\"\n\n");
158 }
159
160
output_yydefred(void)161 void output_yydefred(void)
162 {
163 register int i, j;
164
165 fprintf(output_file, "let yydefred = \"");
166 output_short(defred[0] ? defred[0] - 2 : 0);
167
168 j = 8;
169 for (i = 1; i < nstates; i++)
170 {
171 if (j < 8)
172 ++j;
173 else
174 {
175 if (!rflag) ++outline;
176 fprintf(output_file, "\\\n");
177 j = 1;
178 }
179
180 output_short(defred[i] ? defred[i] - 2 : 0);
181 }
182
183 if (!rflag) outline += 2;
184 fprintf(output_file, "\"\n\n");
185 }
186
187
output_actions(void)188 void output_actions(void)
189 {
190 nvectors = 2*nstates + nvars;
191
192 froms = NEW2(nvectors, short *);
193 tos = NEW2(nvectors, short *);
194 tally = NEW2(nvectors, short);
195 width = NEW2(nvectors, short);
196
197 token_actions();
198 FREE(lookaheads);
199 FREE(LA);
200 FREE(LAruleno);
201 FREE(accessing_symbol);
202
203 goto_actions();
204 FREE(goto_map + ntokens);
205 FREE(from_state);
206 FREE(to_state);
207
208 sort_actions();
209 pack_table();
210 output_base();
211 output_table();
212 output_check();
213 }
214
215
token_actions(void)216 void token_actions(void)
217 {
218 register int i, j;
219 register int shiftcount, reducecount;
220 register int max, min;
221 register short *actionrow, *r, *s;
222 register action *p;
223
224 actionrow = NEW2(2*ntokens, short);
225 for (i = 0; i < nstates; ++i)
226 {
227 if (parser[i])
228 {
229 for (j = 0; j < 2*ntokens; ++j)
230 actionrow[j] = 0;
231
232 shiftcount = 0;
233 reducecount = 0;
234 for (p = parser[i]; p; p = p->next)
235 {
236 if (p->suppressed == 0)
237 {
238 if (p->action_code == SHIFT)
239 {
240 ++shiftcount;
241 actionrow[p->symbol] = p->number;
242 }
243 else if (p->action_code == REDUCE && p->number != defred[i])
244 {
245 ++reducecount;
246 actionrow[p->symbol + ntokens] = p->number;
247 }
248 }
249 }
250
251 tally[i] = shiftcount;
252 tally[nstates+i] = reducecount;
253 width[i] = 0;
254 width[nstates+i] = 0;
255 if (shiftcount > 0)
256 {
257 froms[i] = r = NEW2(shiftcount, short);
258 tos[i] = s = NEW2(shiftcount, short);
259 min = MAXSHORT;
260 max = 0;
261 for (j = 0; j < ntokens; ++j)
262 {
263 if (actionrow[j])
264 {
265 if (min > symbol_value[j])
266 min = symbol_value[j];
267 if (max < symbol_value[j])
268 max = symbol_value[j];
269 *r++ = symbol_value[j];
270 *s++ = actionrow[j];
271 }
272 }
273 width[i] = max - min + 1;
274 }
275 if (reducecount > 0)
276 {
277 froms[nstates+i] = r = NEW2(reducecount, short);
278 tos[nstates+i] = s = NEW2(reducecount, short);
279 min = MAXSHORT;
280 max = 0;
281 for (j = 0; j < ntokens; ++j)
282 {
283 if (actionrow[ntokens+j])
284 {
285 if (min > symbol_value[j])
286 min = symbol_value[j];
287 if (max < symbol_value[j])
288 max = symbol_value[j];
289 *r++ = symbol_value[j];
290 *s++ = actionrow[ntokens+j] - 2;
291 }
292 }
293 width[nstates+i] = max - min + 1;
294 }
295 }
296 }
297 FREE(actionrow);
298 }
299
goto_actions(void)300 void goto_actions(void)
301 {
302 register int i, j, k;
303
304 state_count = NEW2(nstates, short);
305
306 k = default_goto(start_symbol + 1);
307 fprintf(output_file, "let yydgoto = \"");
308 output_short(k);
309
310 save_column(start_symbol + 1, k);
311
312 j = 8;
313 for (i = start_symbol + 2; i < nsyms; i++)
314 {
315 if (j >= 8)
316 {
317 if (!rflag) ++outline;
318 fprintf(output_file, "\\\n");
319 j = 1;
320 }
321 else
322 ++j;
323
324 k = default_goto(i);
325 output_short(k);
326 save_column(i, k);
327 }
328
329 if (!rflag) outline += 2;
330 fprintf(output_file, "\"\n\n");
331 FREE(state_count);
332 }
333
334 int
default_goto(int symbol)335 default_goto(int symbol)
336 {
337 register int i;
338 register int m;
339 register int n;
340 register int default_state;
341 register int max;
342
343 m = goto_map[symbol];
344 n = goto_map[symbol + 1];
345
346 if (m == n) return (0);
347
348 for (i = 0; i < nstates; i++)
349 state_count[i] = 0;
350
351 for (i = m; i < n; i++)
352 state_count[to_state[i]]++;
353
354 max = 0;
355 default_state = 0;
356 for (i = 0; i < nstates; i++)
357 {
358 if (state_count[i] > max)
359 {
360 max = state_count[i];
361 default_state = i;
362 }
363 }
364
365 return (default_state);
366 }
367
368
369
save_column(int symbol,int default_state)370 void save_column(int symbol, int default_state)
371 {
372 register int i;
373 register int m;
374 register int n;
375 register short *sp;
376 register short *sp1;
377 register short *sp2;
378 register int count;
379 register int symno;
380
381 m = goto_map[symbol];
382 n = goto_map[symbol + 1];
383
384 count = 0;
385 for (i = m; i < n; i++)
386 {
387 if (to_state[i] != default_state)
388 ++count;
389 }
390 if (count == 0) return;
391
392 symno = symbol_value[symbol] + 2*nstates;
393
394 froms[symno] = sp1 = sp = NEW2(count, short);
395 tos[symno] = sp2 = NEW2(count, short);
396
397 for (i = m; i < n; i++)
398 {
399 if (to_state[i] != default_state)
400 {
401 *sp1++ = from_state[i];
402 *sp2++ = to_state[i];
403 }
404 }
405
406 tally[symno] = count;
407 width[symno] = sp1[-1] - sp[0] + 1;
408 }
409
sort_actions(void)410 void sort_actions(void)
411 {
412 register int i;
413 register int j;
414 register int k;
415 register int t;
416 register int w;
417
418 order = NEW2(nvectors, short);
419 nentries = 0;
420
421 for (i = 0; i < nvectors; i++)
422 {
423 if (tally[i] > 0)
424 {
425 t = tally[i];
426 w = width[i];
427 j = nentries - 1;
428
429 while (j >= 0 && (width[order[j]] < w))
430 j--;
431
432 while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
433 j--;
434
435 for (k = nentries - 1; k > j; k--)
436 order[k + 1] = order[k];
437
438 order[j + 1] = i;
439 nentries++;
440 }
441 }
442 }
443
444
pack_table(void)445 void pack_table(void)
446 {
447 register int i;
448 register int place;
449 register int state;
450
451 base = NEW2(nvectors, short);
452 pos = NEW2(nentries, short);
453
454 maxtable = 1000;
455 table = NEW2(maxtable, short);
456 check = NEW2(maxtable, short);
457
458 lowzero = 0;
459 high = 0;
460
461 for (i = 0; i < maxtable; i++)
462 check[i] = -1;
463
464 for (i = 0; i < nentries; i++)
465 {
466 state = matching_vector(i);
467
468 if (state < 0)
469 place = pack_vector(i);
470 else
471 place = base[state];
472
473 pos[i] = place;
474 base[order[i]] = place;
475 }
476
477 for (i = 0; i < nvectors; i++)
478 {
479 if (froms[i])
480 FREE(froms[i]);
481 if (tos[i])
482 FREE(tos[i]);
483 }
484
485 FREE(froms);
486 FREE(tos);
487 FREE(pos);
488 }
489
490
491 /* The function matching_vector determines if the vector specified by */
492 /* the input parameter matches a previously considered vector. The */
493 /* test at the start of the function checks if the vector represents */
494 /* a row of shifts over terminal symbols or a row of reductions, or a */
495 /* column of shifts over a nonterminal symbol. Berkeley Yacc does not */
496 /* check if a column of shifts over a nonterminal symbols matches a */
497 /* previously considered vector. Because of the nature of LR parsing */
498 /* tables, no two columns can match. Therefore, the only possible */
499 /* match would be between a row and a column. Such matches are */
500 /* unlikely. Therefore, to save time, no attempt is made to see if a */
501 /* column matches a previously considered vector. */
502 /* */
503 /* Matching_vector is poorly designed. The test could easily be made */
504 /* faster. Also, it depends on the vectors being in a specific */
505 /* order. */
506
507 int
matching_vector(int vector)508 matching_vector(int vector)
509 {
510 register int i;
511 register int j;
512 register int k;
513 register int t;
514 register int w;
515 register int match;
516 register int prev;
517
518 i = order[vector];
519 if (i >= 2*nstates)
520 return (-1);
521
522 t = tally[i];
523 w = width[i];
524
525 for (prev = vector - 1; prev >= 0; prev--)
526 {
527 j = order[prev];
528 if (width[j] != w || tally[j] != t)
529 return (-1);
530
531 match = 1;
532 for (k = 0; match && k < t; k++)
533 {
534 if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
535 match = 0;
536 }
537
538 if (match)
539 return (j);
540 }
541
542 return (-1);
543 }
544
545
546
547 int
pack_vector(int vector)548 pack_vector(int vector)
549 {
550 register int i, j, k, l;
551 register int t;
552 register int loc;
553 register int ok;
554 register short *from;
555 register short *to;
556 int newmax;
557
558 i = order[vector];
559 t = tally[i];
560 assert(t);
561
562 from = froms[i];
563 to = tos[i];
564
565 j = lowzero - from[0];
566 for (k = 1; k < t; ++k)
567 if (lowzero - from[k] > j)
568 j = lowzero - from[k];
569 for (;; ++j)
570 {
571 if (j == 0)
572 continue;
573 ok = 1;
574 for (k = 0; ok && k < t; k++)
575 {
576 loc = j + from[k];
577 if (loc >= maxtable)
578 {
579 if (loc >= MAXTABLE)
580 fatal("maximum table size exceeded");
581
582 newmax = maxtable;
583 do { newmax += 200; } while (newmax <= loc);
584 table = (short *) REALLOC(table, newmax*sizeof(short));
585 if (table == 0) no_space();
586 check = (short *) REALLOC(check, newmax*sizeof(short));
587 if (check == 0) no_space();
588 for (l = maxtable; l < newmax; ++l)
589 {
590 table[l] = 0;
591 check[l] = -1;
592 }
593 maxtable = newmax;
594 }
595
596 if (check[loc] != -1)
597 ok = 0;
598 }
599 for (k = 0; ok && k < vector; k++)
600 {
601 if (pos[k] == j)
602 ok = 0;
603 }
604 if (ok)
605 {
606 for (k = 0; k < t; k++)
607 {
608 loc = j + from[k];
609 table[loc] = to[k];
610 check[loc] = from[k];
611 if (loc > high) high = loc;
612 }
613
614 while (lowzero < maxtable && check[lowzero] != -1)
615 ++lowzero;
616
617 return (j);
618 }
619 }
620 }
621
622
623
output_base(void)624 void output_base(void)
625 {
626 register int i, j;
627
628 fprintf(output_file, "let yysindex = \"");
629 output_short(base[0]);
630
631 j = 8;
632 for (i = 1; i < nstates; i++)
633 {
634 if (j >= 8)
635 {
636 if (!rflag) ++outline;
637 fprintf(output_file, "\\\n");
638 j = 1;
639 }
640 else
641 ++j;
642
643 output_short(base[i]);
644 }
645
646 if (!rflag) outline += 2;
647 fprintf(output_file, "\"\n\n");
648
649 fprintf(output_file, "let yyrindex = \"");
650 output_short(base[nstates]);
651
652 j = 8;
653 for (i = nstates + 1; i < 2*nstates; i++)
654 {
655 if (j >= 8)
656 {
657 if (!rflag) ++outline;
658 fprintf(output_file, "\\\n");
659 j = 1;
660 }
661 else
662 ++j;
663
664 output_short(base[i]);
665 }
666
667 if (!rflag) outline += 2;
668 fprintf(output_file, "\"\n\n");
669
670 fprintf(output_file, "let yygindex = \"");
671 output_short(base[2*nstates]);
672
673 j = 8;
674 for (i = 2*nstates + 1; i < nvectors - 1; i++)
675 {
676 if (j >= 8)
677 {
678 if (!rflag) ++outline;
679 fprintf(output_file, "\\\n");
680 j = 1;
681 }
682 else
683 ++j;
684
685 output_short(base[i]);
686 }
687
688 if (!rflag) outline += 2;
689 fprintf(output_file, "\"\n\n");
690 FREE(base);
691 }
692
693
694
output_table(void)695 void output_table(void)
696 {
697 register int i;
698 register int j;
699
700 ++outline;
701 fprintf(code_file, "let yytablesize = %d\n", high);
702 fprintf(output_file, "let yytable = \"");
703 output_short(table[0]);
704
705 j = 8;
706 for (i = 1; i <= high; i++)
707 {
708 if (j >= 8)
709 {
710 if (!rflag) ++outline;
711 fprintf(output_file, "\\\n");
712 j = 1;
713 }
714 else
715 ++j;
716
717 output_short(table[i]);
718 }
719
720 if (!rflag) outline += 2;
721 fprintf(output_file, "\"\n\n");
722 FREE(table);
723 }
724
725
726
output_check(void)727 void output_check(void)
728 {
729 register int i;
730 register int j;
731
732 fprintf(output_file, "let yycheck = \"");
733 output_short(check[0]);
734
735 j = 8;
736 for (i = 1; i <= high; i++)
737 {
738 if (j >= 8)
739 {
740 if (!rflag) ++outline;
741 fprintf(output_file, "\\\n");
742 j = 1;
743 }
744 else
745 ++j;
746
747 output_short(check[i]);
748 }
749
750 if (!rflag) outline += 2;
751 fprintf(output_file, "\"\n\n");
752 FREE(check);
753 }
754
755
output_transl(void)756 void output_transl(void)
757 {
758 int i;
759
760 ++outline;
761 fprintf(code_file, "let yytransl_const = [|\n");
762 for (i = 0; i < ntokens; i++) {
763 if (symbol_true_token[i] && symbol_tag[i] == NULL) {
764 ++outline;
765 fprintf(code_file, " %3d (* %s *);\n", symbol_value[i], symbol_name[i]);
766 }
767 }
768 outline += 2;
769 fprintf(code_file, " 0|]\n\n");
770 ++outline;
771 fprintf(code_file, "let yytransl_block = [|\n");
772 for (i = 0; i < ntokens; i++) {
773 if (symbol_true_token[i] && symbol_tag[i] != NULL) {
774 ++outline;
775 fprintf(code_file, " %3d (* %s *);\n", symbol_value[i], symbol_name[i]);
776 }
777 }
778 outline += 2;
779 fprintf(code_file, " 0|]\n\n");
780 }
781
output_stored_text(void)782 void output_stored_text(void)
783 {
784 register int c;
785 register FILE *in, *out;
786
787 fclose(text_file);
788 text_file = fopen(text_file_name, "r");
789 if (text_file == NULL)
790 open_error(text_file_name);
791 in = text_file;
792 if ((c = getc(in)) == EOF)
793 return;
794 out = code_file;
795 if (c == '\n')
796 ++outline;
797 putc(c, out);
798 while ((c = getc(in)) != EOF)
799 {
800 if (c == '\n')
801 ++outline;
802 putc(c, out);
803 }
804 if (!lflag)
805 fprintf(out, line_format, ++outline + 1, code_file_name);
806 }
807
808
output_debug(void)809 void output_debug(void)
810 {
811 int i;
812
813 ++outline;
814 fprintf(code_file, "let yynames_const = \"\\\n");
815 for (i = 0; i < ntokens; i++) {
816 if (symbol_true_token[i] && symbol_tag[i] == NULL) {
817 ++outline;
818 fprintf(code_file, " %s\\000\\\n", symbol_name[i]);
819 }
820 }
821 outline += 2;
822 fprintf(code_file, " \"\n\n");
823 ++outline;
824 fprintf(code_file, "let yynames_block = \"\\\n");
825 for (i = 0; i < ntokens; i++) {
826 if (symbol_true_token[i] && symbol_tag[i] != NULL) {
827 ++outline;
828 fprintf(code_file, " %s\\000\\\n", symbol_name[i]);
829 }
830 }
831 outline += 2;
832 fprintf(code_file, " \"\n\n");
833 }
834
output_trailing_text(void)835 void output_trailing_text(void)
836 {
837 register int c, last;
838 register FILE *in, *out;
839
840 if (line == 0)
841 return;
842
843 in = input_file;
844 out = code_file;
845
846 ++outline;
847 fprintf (out, ";;\n");
848
849 c = *cptr;
850 if (c == '\n')
851 {
852 ++lineno;
853 if ((c = getc(in)) == EOF)
854 return;
855 if (!lflag)
856 {
857 ++outline;
858 fprintf(out, line_format, lineno, input_file_name);
859 }
860 if (c == '\n')
861 ++outline;
862 putc(c, out);
863 last = c;
864 }
865 else
866 {
867 if (!lflag)
868 {
869 ++outline;
870 fprintf(out, line_format, lineno, input_file_name);
871 }
872 do { putc(c, out); } while ((c = *++cptr) != '\n');
873 ++outline;
874 putc('\n', out);
875 last = '\n';
876 }
877
878
879 while ((c = getc(in)) != EOF)
880 {
881 if (c == '\n')
882 ++outline;
883 putc(c, out);
884 last = c;
885 }
886
887 if (last != '\n')
888 {
889 ++outline;
890 putc('\n', out);
891 }
892 if (!lflag)
893 fprintf(out, line_format, ++outline + 1, code_file_name);
894 }
895
896
copy_file(FILE ** file,char * file_name)897 void copy_file(FILE **file, char *file_name)
898 {
899 register int c, last;
900 register FILE *out = code_file;
901 int state = 0;
902
903 fclose(*file);
904 *file = fopen(file_name, "r");
905 if (*file == NULL)
906 open_error(file_name);
907
908 last = '\n';
909
910 while ((c = getc(*file)) != EOF)
911 {
912 switch (c){
913 case '\n': state = 1; break;
914 case '#': state = (state == 1) ? 2 : 0; break;
915 case ' ': state = (state == 2) ? 3 : 0; break;
916 case '0':
917 if (state == 3){
918 fprintf (out, "%d \"%s", outline+2, code_file_name);
919 c = '"';
920 }
921 state = 0;
922 break;
923 default: state = 0; break;
924 }
925 if (c == '\n') ++outline;
926 putc(c, out);
927 last = c;
928 }
929
930 if (last != '\n')
931 {
932 ++outline;
933 putc('\n', out);
934 }
935
936 }
937
output_semantic_actions(void)938 void output_semantic_actions(void)
939 {
940 copy_file (&action_file, action_file_name);
941 }
942
output_entries(void)943 void output_entries(void)
944 {
945 copy_file (&entry_file, entry_file_name);
946 }
947
free_itemsets(void)948 void free_itemsets(void)
949 {
950 register core *cp, *next;
951
952 FREE(state_table);
953 for (cp = first_state; cp; cp = next)
954 {
955 next = cp->next;
956 FREE(cp);
957 }
958 }
959
960
free_shifts(void)961 void free_shifts(void)
962 {
963 register shifts *sp, *next;
964
965 FREE(shift_table);
966 for (sp = first_shift; sp; sp = next)
967 {
968 next = sp->next;
969 FREE(sp);
970 }
971 }
972
973
974
free_reductions(void)975 void free_reductions(void)
976 {
977 register reductions *rp, *next;
978
979 FREE(reduction_table);
980 for (rp = first_reduction; rp; rp = next)
981 {
982 next = rp->next;
983 FREE(rp);
984 }
985 }
986