2 * Copyright (c) 1989 The Regents of the University of California.
5 * This code is derived from software contributed to Berkeley by
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 4. Neither the name of the University nor the names of its contributors
17 * may be used to endorse or promote products derived from this software
18 * without specific prior written permission.
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 static char sccsid[] = "@(#)output.c 5.7 (Berkeley) 5/24/93";
39 #include <sys/cdefs.h>
40 __FBSDID("$FreeBSD$");
53 static short *state_count;
63 static int default_goto(int);
64 static void free_itemsets(void);
65 static void free_reductions(void);
66 static void free_shifts(void);
67 static void goto_actions(void);
68 static int is_C_identifier(char *);
69 static int matching_vector(int);
70 static void output_actions(void);
71 static void output_base(void);
72 static void output_check(void);
73 static void output_debug(void);
74 static void output_defines(void);
75 static void output_prefix(void);
76 static void output_rule_data(void);
77 static void output_semantic_actions(void);
78 static void output_stored_text(void);
79 static void output_stype(void);
80 static void output_table(void);
81 static void output_trailing_text(void);
82 static void output_yydefred(void);
83 static void pack_table(void);
84 static int pack_vector(int);
85 static void save_column(int, int);
86 static void sort_actions(void);
87 static void token_actions(void);
88 static int increase_maxtable(int);
90 static const char line_format[] = "#line %d \"%s\"\n";
100 output_stored_text();
108 if (rflag) write_section(tables);
109 write_section(header);
110 output_trailing_text();
112 output_semantic_actions();
113 write_section(trailer);
120 if (symbol_prefix == NULL)
121 symbol_prefix = "yy";
125 fprintf(code_file, "#define yyparse %sparse\n", symbol_prefix);
127 fprintf(code_file, "#define yylex %slex\n", symbol_prefix);
129 fprintf(code_file, "#define yyerror %serror\n", symbol_prefix);
131 fprintf(code_file, "#define yychar %schar\n", symbol_prefix);
133 fprintf(code_file, "#define yyval %sval\n", symbol_prefix);
135 fprintf(code_file, "#define yylval %slval\n", symbol_prefix);
137 fprintf(code_file, "#define yydebug %sdebug\n", symbol_prefix);
139 fprintf(code_file, "#define yynerrs %snerrs\n", symbol_prefix);
141 fprintf(code_file, "#define yyerrflag %serrflag\n", symbol_prefix);
143 fprintf(code_file, "#define yyss %sss\n", symbol_prefix);
145 fprintf(code_file, "#define yyssp %sssp\n", symbol_prefix);
147 fprintf(code_file, "#define yyvs %svs\n", symbol_prefix);
149 fprintf(code_file, "#define yyvsp %svsp\n", symbol_prefix);
151 fprintf(code_file, "#define yylhs %slhs\n", symbol_prefix);
153 fprintf(code_file, "#define yylen %slen\n", symbol_prefix);
155 fprintf(code_file, "#define yydefred %sdefred\n", symbol_prefix);
157 fprintf(code_file, "#define yydgoto %sdgoto\n", symbol_prefix);
159 fprintf(code_file, "#define yysindex %ssindex\n", symbol_prefix);
161 fprintf(code_file, "#define yyrindex %srindex\n", symbol_prefix);
163 fprintf(code_file, "#define yygindex %sgindex\n", symbol_prefix);
165 fprintf(code_file, "#define yytable %stable\n", symbol_prefix);
167 fprintf(code_file, "#define yycheck %scheck\n", symbol_prefix);
169 fprintf(code_file, "#define yyname %sname\n", symbol_prefix);
171 fprintf(code_file, "#define yyrule %srule\n", symbol_prefix);
173 fprintf(code_file, "#define yysslim %ssslim\n", symbol_prefix);
175 fprintf(code_file, "#define yystacksize %sstacksize\n", symbol_prefix);
178 fprintf(code_file, "#define YYPREFIX \"%s\"\n", symbol_prefix);
183 output_rule_data(void)
189 fprintf(output_file, "const short %slhs[] = {%42d,", symbol_prefix,
190 symbol_value[start_symbol]);
193 for (i = 3; i < nrules; i++)
197 if (!rflag) ++outline;
198 putc('\n', output_file);
204 fprintf(output_file, "%5d,", symbol_value[rlhs[i]]);
206 if (!rflag) outline += 2;
207 fprintf(output_file, "\n};\n");
209 fprintf(output_file, "const short %slen[] = {%42d,", symbol_prefix, 2);
212 for (i = 3; i < nrules; i++)
216 if (!rflag) ++outline;
217 putc('\n', output_file);
223 fprintf(output_file, "%5d,", rrhs[i + 1] - rrhs[i] - 1);
225 if (!rflag) outline += 2;
226 fprintf(output_file, "\n};\n");
231 output_yydefred(void)
235 fprintf(output_file, "const short %sdefred[] = {%39d,", symbol_prefix,
236 (defred[0] ? defred[0] - 2 : 0));
239 for (i = 1; i < nstates; i++)
245 if (!rflag) ++outline;
246 putc('\n', output_file);
250 fprintf(output_file, "%5d,", (defred[i] ? defred[i] - 2 : 0));
253 if (!rflag) outline += 2;
254 fprintf(output_file, "\n};\n");
261 nvectors = 2*nstates + nvars;
263 froms = NEW2(nvectors, short *);
264 tos = NEW2(nvectors, short *);
265 tally = NEW2(nvectors, short);
266 width = NEW2(nvectors, short);
272 free(accessing_symbol);
275 free(goto_map + ntokens);
291 int shiftcount, reducecount;
293 short *actionrow, *r, *s;
296 actionrow = NEW2(2*ntokens, short);
297 for (i = 0; i < nstates; ++i)
301 for (j = 0; j < 2*ntokens; ++j)
306 for (p = parser[i]; p; p = p->next)
308 if (p->suppressed == 0)
310 if (p->action_code == SHIFT)
313 actionrow[p->symbol] = p->number;
315 else if (p->action_code == REDUCE && p->number != defred[i])
318 actionrow[p->symbol + ntokens] = p->number;
323 tally[i] = shiftcount;
324 tally[nstates+i] = reducecount;
326 width[nstates+i] = 0;
329 froms[i] = r = NEW2(shiftcount, short);
330 tos[i] = s = NEW2(shiftcount, short);
333 for (j = 0; j < ntokens; ++j)
337 if (min > symbol_value[j])
338 min = symbol_value[j];
339 if (max < symbol_value[j])
340 max = symbol_value[j];
341 *r++ = symbol_value[j];
345 width[i] = max - min + 1;
349 froms[nstates+i] = r = NEW2(reducecount, short);
350 tos[nstates+i] = s = NEW2(reducecount, short);
353 for (j = 0; j < ntokens; ++j)
355 if (actionrow[ntokens+j])
357 if (min > symbol_value[j])
358 min = symbol_value[j];
359 if (max < symbol_value[j])
360 max = symbol_value[j];
361 *r++ = symbol_value[j];
362 *s++ = actionrow[ntokens+j] - 2;
365 width[nstates+i] = max - min + 1;
377 state_count = NEW2(nstates, short);
379 k = default_goto(start_symbol + 1);
380 fprintf(output_file, "const short %sdgoto[] = {%40d,", symbol_prefix, k);
381 save_column(start_symbol + 1, k);
384 for (i = start_symbol + 2; i < nsyms; i++)
388 if (!rflag) ++outline;
389 putc('\n', output_file);
396 fprintf(output_file, "%5d,", k);
400 if (!rflag) outline += 2;
401 fprintf(output_file, "\n};\n");
406 default_goto(int symbol)
414 m = goto_map[symbol];
415 n = goto_map[symbol + 1];
417 if (m == n) return (0);
419 for (i = 0; i < nstates; i++)
422 for (i = m; i < n; i++)
423 state_count[to_state[i]]++;
427 for (i = 0; i < nstates; i++)
429 if (state_count[i] > max)
431 max = state_count[i];
436 return (default_state);
442 save_column(int symbol, int default_state)
453 m = goto_map[symbol];
454 n = goto_map[symbol + 1];
457 for (i = m; i < n; i++)
459 if (to_state[i] != default_state)
462 if (count == 0) return;
464 symno = symbol_value[symbol] + 2*nstates;
466 froms[symno] = sp1 = sp = NEW2(count, short);
467 tos[symno] = sp2 = NEW2(count, short);
469 for (i = m; i < n; i++)
471 if (to_state[i] != default_state)
473 *sp1++ = from_state[i];
474 *sp2++ = to_state[i];
478 tally[symno] = count;
479 width[symno] = sp1[-1] - sp[0] + 1;
491 order = NEW2(nvectors, short);
494 for (i = 0; i < nvectors; i++)
502 while (j >= 0 && (width[order[j]] < w))
505 while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
508 for (k = nentries - 1; k > j; k--)
509 order[k + 1] = order[k];
525 base = NEW2(nvectors, short);
526 pos = NEW2(nentries, short);
529 table = NEW2(maxtable, short);
530 check = NEW2(maxtable, short);
535 for (i = 0; i < maxtable; i++)
538 for (i = 0; i < nentries; i++)
540 state = matching_vector(i);
543 place = pack_vector(i);
548 base[order[i]] = place;
551 for (i = 0; i < nvectors; i++)
565 /* The function matching_vector determines if the vector specified by */
566 /* the input parameter matches a previously considered vector. The */
567 /* test at the start of the function checks if the vector represents */
568 /* a row of shifts over terminal symbols or a row of reductions, or a */
569 /* column of shifts over a nonterminal symbol. Berkeley Yacc does not */
570 /* check if a column of shifts over a nonterminal symbols matches a */
571 /* previously considered vector. Because of the nature of LR parsing */
572 /* tables, no two columns can match. Therefore, the only possible */
573 /* match would be between a row and a column. Such matches are */
574 /* unlikely. Therefore, to save time, no attempt is made to see if a */
575 /* column matches a previously considered vector. */
577 /* Matching_vector is poorly designed. The test could easily be made */
578 /* faster. Also, it depends on the vectors being in a specific */
582 matching_vector(int vector)
599 for (prev = vector - 1; prev >= 0; prev--)
602 if (width[j] != w || tally[j] != t)
606 for (k = 0; match && k < t; k++)
608 if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
622 pack_vector(int vector)
639 j = lowzero - from[0];
640 for (k = 1; k < t; ++k)
641 if (lowzero - from[k] > j)
642 j = lowzero - from[k];
648 for (k = 0; ok && k < t; k++)
654 fatal("maximum table size exceeded");
655 maxtable = increase_maxtable(loc);
658 if (check[loc] != -1)
661 for (k = 0; ok && k < vector; k++)
668 for (k = 0; k < t; k++)
672 check[loc] = from[k];
673 if (loc > high) high = loc;
676 while (check[lowzero] != -1)
678 if (lowzero >= maxtable)
680 if (lowzero >= MAXTABLE)
682 fatal("maximum table size exceeded in check\n");
685 maxtable = increase_maxtable(loc);
703 fprintf(output_file, "const short %ssindex[] = {%39d,", symbol_prefix,
707 for (i = 1; i < nstates; i++)
711 if (!rflag) ++outline;
712 putc('\n', output_file);
718 fprintf(output_file, "%5d,", base[i]);
721 if (!rflag) outline += 2;
722 fprintf(output_file, "\n};\nconst short %srindex[] = {%39d,", symbol_prefix,
726 for (i = nstates + 1; i < 2*nstates; i++)
730 if (!rflag) ++outline;
731 putc('\n', output_file);
737 fprintf(output_file, "%5d,", base[i]);
740 if (!rflag) outline += 2;
741 fprintf(output_file, "\n};\nconst short %sgindex[] = {%39d,", symbol_prefix,
745 for (i = 2*nstates + 1; i < nvectors - 1; i++)
749 if (!rflag) ++outline;
750 putc('\n', output_file);
756 fprintf(output_file, "%5d,", base[i]);
759 if (!rflag) outline += 2;
760 fprintf(output_file, "\n};\n");
773 fprintf(code_file, "#define YYTABLESIZE %d\n", high);
774 fprintf(output_file, "const short %stable[] = {%40d,", symbol_prefix,
778 for (i = 1; i <= high; i++)
782 if (!rflag) ++outline;
783 putc('\n', output_file);
789 fprintf(output_file, "%5d,", table[i]);
792 if (!rflag) outline += 2;
793 fprintf(output_file, "\n};\n");
805 fprintf(output_file, "const short %scheck[] = {%40d,", symbol_prefix,
809 for (i = 1; i <= high; i++)
813 if (!rflag) ++outline;
814 putc('\n', output_file);
820 fprintf(output_file, "%5d,", check[i]);
823 if (!rflag) outline += 2;
824 fprintf(output_file, "\n};\n");
830 is_C_identifier(char *name)
840 if (!isalpha(c) && c != '_' && c != '$')
842 while ((c = *++s) != '"')
844 if (!isalnum(c) && c != '_' && c != '$')
850 if (!isalpha(c) && c != '_' && c != '$')
854 if (!isalnum(c) && c != '_' && c != '$')
868 fprintf(code_file, "#define YYERRCODE %d\n", symbol_value[1]);
872 fprintf(defines_file, "#ifndef YYERRCODE\n");
873 fprintf(defines_file, "#define YYERRCODE %d\n", symbol_value[1]);
874 fprintf(defines_file, "#endif\n\n");
876 for (i = 2; i < ntokens; ++i)
879 if (is_C_identifier(s))
881 fprintf(code_file, "#define ");
882 if (dflag) fprintf(defines_file, "#define ");
886 while ((c = *++s) != '"')
889 if (dflag) putc(c, defines_file);
897 if (dflag) putc(c, defines_file);
902 fprintf(code_file, " %d\n", symbol_value[i]);
903 if (dflag) fprintf(defines_file, " %d\n", symbol_value[i]);
907 if (dflag && unionized)
910 union_file = fopen(union_file_name, "r");
911 if (union_file == NULL) open_error(union_file_name);
912 while ((c = getc(union_file)) != EOF)
913 putc(c, defines_file);
914 fprintf(defines_file, " YYSTYPE;\nextern YYSTYPE %slval;\n",
921 output_stored_text(void)
927 text_file = fopen(text_file_name, "r");
928 if (text_file == NULL)
929 open_error(text_file_name);
931 if ((c = getc(in)) == EOF)
937 while ((c = getc(in)) != EOF)
944 fprintf(out, line_format, ++outline + 1, code_file_name);
953 static char eof[] = "end-of-file";
956 fprintf(code_file, "#define YYFINAL %d\n", final_state);
958 fprintf(code_file, "#ifndef YYDEBUG\n#define YYDEBUG %d\n#endif\n",
961 fprintf(output_file, "#ifndef YYDEBUG\n#define YYDEBUG %d\n#endif\n",
965 for (i = 2; i < ntokens; ++i)
966 if (symbol_value[i] > max)
967 max = symbol_value[i];
969 fprintf(code_file, "#define YYMAXTOKEN %d\n", max);
971 symnam = malloc((max+1)*sizeof(char *));
972 if (symnam == 0) no_space();
974 /* Note that it is not necessary to initialize the element */
976 for (i = 0; i < max; ++i)
978 for (i = ntokens - 1; i >= 2; --i)
979 symnam[symbol_value[i]] = symbol_name[i];
982 if (!rflag) ++outline;
983 fprintf(output_file, "#if YYDEBUG\n");
984 fprintf(output_file, "const char * const %sname[] = {", symbol_prefix);
986 for (i = 0; i <= max; ++i)
1006 if (!rflag) ++outline;
1007 putc('\n', output_file);
1010 fprintf(output_file, "\"\\\"");
1016 fprintf(output_file, "\\\\");
1018 fprintf(output_file, "\\\\");
1020 putc(*s, output_file);
1023 putc(*s, output_file);
1025 fprintf(output_file, "\\\"\",");
1027 else if (s[0] == '\'')
1034 if (!rflag) ++outline;
1035 putc('\n', output_file);
1038 fprintf(output_file, "\"'\\\"'\",");
1043 while (*++s != '\'')
1056 if (!rflag) ++outline;
1057 putc('\n', output_file);
1060 fprintf(output_file, "\"'");
1062 while (*++s != '\'')
1066 fprintf(output_file, "\\\\");
1068 fprintf(output_file, "\\\\");
1070 putc(*s, output_file);
1073 putc(*s, output_file);
1075 fprintf(output_file, "'\",");
1084 if (!rflag) ++outline;
1085 putc('\n', output_file);
1088 putc('"', output_file);
1089 do { putc(*s, output_file); } while (*++s);
1090 fprintf(output_file, "\",");
1098 if (!rflag) ++outline;
1099 putc('\n', output_file);
1102 fprintf(output_file, "0,");
1105 if (!rflag) outline += 2;
1106 fprintf(output_file, "\n};\n");
1109 if (!rflag) ++outline;
1110 fprintf(output_file, "const char * const %srule[] = {\n", symbol_prefix);
1111 for (i = 2; i < nrules; ++i)
1113 fprintf(output_file, "\"%s :", symbol_name[rlhs[i]]);
1114 for (j = rrhs[i]; ritem[j] > 0; ++j)
1116 s = symbol_name[ritem[j]];
1119 fprintf(output_file, " \\\"");
1125 fprintf(output_file, "\\\\\\\\");
1127 fprintf(output_file, "\\\\%c", s[1]);
1131 putc(*s, output_file);
1133 fprintf(output_file, "\\\"");
1135 else if (s[0] == '\'')
1138 fprintf(output_file, " '\\\"'");
1139 else if (s[1] == '\\')
1142 fprintf(output_file, " '\\\\\\\\");
1144 fprintf(output_file, " '\\\\%c", s[2]);
1146 while (*++s != '\'')
1147 putc(*s, output_file);
1148 putc('\'', output_file);
1151 fprintf(output_file, " '%c'", s[1]);
1154 fprintf(output_file, " %s", s);
1156 if (!rflag) ++outline;
1157 fprintf(output_file, "\",\n");
1160 if (!rflag) outline += 2;
1161 fprintf(output_file, "};\n#endif\n");
1168 if (!unionized && ntags == 0)
1171 fprintf(code_file, "#ifndef YYSTYPE\ntypedef int YYSTYPE;\n#endif\n");
1177 output_trailing_text(void)
1191 if ((c = getc(in)) == EOF)
1196 fprintf(out, line_format, lineno, input_file_name);
1208 fprintf(out, line_format, lineno, input_file_name);
1210 do { putc(c, out); } while ((c = *++cptr) != '\n');
1216 while ((c = getc(in)) != EOF)
1230 fprintf(out, line_format, ++outline + 1, code_file_name);
1235 output_semantic_actions(void)
1240 fclose(action_file);
1241 action_file = fopen(action_file_name, "r");
1242 if (action_file == NULL)
1243 open_error(action_file_name);
1245 if ((c = getc(action_file)) == EOF)
1253 while ((c = getc(action_file)) != EOF)
1268 fprintf(out, line_format, ++outline + 1, code_file_name);
1278 for (cp = first_state; cp; cp = next)
1292 for (sp = first_shift; sp; sp = next)
1302 free_reductions(void)
1304 reductions *rp, *next;
1306 free(reduction_table);
1307 for (rp = first_reduction; rp; rp = next)
1317 * inputs - loc location in table
1318 * output - size increased to
1319 * side effects - table is increase by at least 200 short words
1323 increase_maxtable(int loc)
1330 do { newmax += 200; } while (newmax <= loc);
1331 table = realloc(table, newmax*sizeof(short));
1332 if (table == 0) no_space();
1333 check = realloc(check, newmax*sizeof(short));
1334 if (check == 0) no_space();
1335 for (l = maxtable; l < newmax; ++l)