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 * 3. All advertising materials mentioning features or use of this software
17 * must display the following acknowledgement:
18 * This product includes software developed by the University of
19 * California, Berkeley and its contributors.
20 * 4. Neither the name of the University nor the names of its contributors
21 * may be used to endorse or promote products derived from this software
22 * without specific prior written permission.
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
39 static char sccsid[] = "@(#)output.c 5.7 (Berkeley) 5/24/93";
43 #include <sys/cdefs.h>
44 __FBSDID("$FreeBSD$");
57 static short *state_count;
67 static int default_goto(int);
68 static void free_itemsets(void);
69 static void free_reductions(void);
70 static void free_shifts(void);
71 static void goto_actions(void);
72 static int is_C_identifier(char *);
73 static int matching_vector(int);
74 static void output_actions(void);
75 static void output_base(void);
76 static void output_check(void);
77 static void output_debug(void);
78 static void output_defines(void);
79 static void output_prefix(void);
80 static void output_rule_data(void);
81 static void output_semantic_actions(void);
82 static void output_stored_text(void);
83 static void output_stype(void);
84 static void output_table(void);
85 static void output_trailing_text(void);
86 static void output_yydefred(void);
87 static void pack_table(void);
88 static int pack_vector(int);
89 static void save_column(int, int);
90 static void sort_actions(void);
91 static void token_actions(void);
92 static int increase_maxtable(int);
94 static const char line_format[] = "#line %d \"%s\"\n";
104 output_stored_text();
112 if (rflag) write_section(tables);
113 write_section(header);
114 output_trailing_text();
116 output_semantic_actions();
117 write_section(trailer);
124 if (symbol_prefix == NULL)
125 symbol_prefix = "yy";
129 fprintf(code_file, "#define yyparse %sparse\n", symbol_prefix);
131 fprintf(code_file, "#define yylex %slex\n", symbol_prefix);
133 fprintf(code_file, "#define yyerror %serror\n", symbol_prefix);
135 fprintf(code_file, "#define yychar %schar\n", symbol_prefix);
137 fprintf(code_file, "#define yyval %sval\n", symbol_prefix);
139 fprintf(code_file, "#define yylval %slval\n", symbol_prefix);
141 fprintf(code_file, "#define yydebug %sdebug\n", symbol_prefix);
143 fprintf(code_file, "#define yynerrs %snerrs\n", symbol_prefix);
145 fprintf(code_file, "#define yyerrflag %serrflag\n", symbol_prefix);
147 fprintf(code_file, "#define yyss %sss\n", symbol_prefix);
149 fprintf(code_file, "#define yyssp %sssp\n", symbol_prefix);
151 fprintf(code_file, "#define yyvs %svs\n", symbol_prefix);
153 fprintf(code_file, "#define yyvsp %svsp\n", symbol_prefix);
155 fprintf(code_file, "#define yylhs %slhs\n", symbol_prefix);
157 fprintf(code_file, "#define yylen %slen\n", symbol_prefix);
159 fprintf(code_file, "#define yydefred %sdefred\n", symbol_prefix);
161 fprintf(code_file, "#define yydgoto %sdgoto\n", symbol_prefix);
163 fprintf(code_file, "#define yysindex %ssindex\n", symbol_prefix);
165 fprintf(code_file, "#define yyrindex %srindex\n", symbol_prefix);
167 fprintf(code_file, "#define yygindex %sgindex\n", symbol_prefix);
169 fprintf(code_file, "#define yytable %stable\n", symbol_prefix);
171 fprintf(code_file, "#define yycheck %scheck\n", symbol_prefix);
173 fprintf(code_file, "#define yyname %sname\n", symbol_prefix);
175 fprintf(code_file, "#define yyrule %srule\n", symbol_prefix);
177 fprintf(code_file, "#define yysslim %ssslim\n", symbol_prefix);
179 fprintf(code_file, "#define yystacksize %sstacksize\n", symbol_prefix);
182 fprintf(code_file, "#define YYPREFIX \"%s\"\n", symbol_prefix);
193 fprintf(output_file, "const short %slhs[] = {%42d,", symbol_prefix,
194 symbol_value[start_symbol]);
197 for (i = 3; i < nrules; i++)
201 if (!rflag) ++outline;
202 putc('\n', output_file);
208 fprintf(output_file, "%5d,", symbol_value[rlhs[i]]);
210 if (!rflag) outline += 2;
211 fprintf(output_file, "\n};\n");
213 fprintf(output_file, "const short %slen[] = {%42d,", symbol_prefix, 2);
216 for (i = 3; i < nrules; i++)
220 if (!rflag) ++outline;
221 putc('\n', output_file);
227 fprintf(output_file, "%5d,", rrhs[i + 1] - rrhs[i] - 1);
229 if (!rflag) outline += 2;
230 fprintf(output_file, "\n};\n");
239 fprintf(output_file, "const short %sdefred[] = {%39d,", symbol_prefix,
240 (defred[0] ? defred[0] - 2 : 0));
243 for (i = 1; i < nstates; i++)
249 if (!rflag) ++outline;
250 putc('\n', output_file);
254 fprintf(output_file, "%5d,", (defred[i] ? defred[i] - 2 : 0));
257 if (!rflag) outline += 2;
258 fprintf(output_file, "\n};\n");
265 nvectors = 2*nstates + nvars;
267 froms = NEW2(nvectors, short *);
268 tos = NEW2(nvectors, short *);
269 tally = NEW2(nvectors, short);
270 width = NEW2(nvectors, short);
276 FREE(accessing_symbol);
279 FREE(goto_map + ntokens);
295 int shiftcount, reducecount;
297 short *actionrow, *r, *s;
300 actionrow = NEW2(2*ntokens, short);
301 for (i = 0; i < nstates; ++i)
305 for (j = 0; j < 2*ntokens; ++j)
310 for (p = parser[i]; p; p = p->next)
312 if (p->suppressed == 0)
314 if (p->action_code == SHIFT)
317 actionrow[p->symbol] = p->number;
319 else if (p->action_code == REDUCE && p->number != defred[i])
322 actionrow[p->symbol + ntokens] = p->number;
327 tally[i] = shiftcount;
328 tally[nstates+i] = reducecount;
330 width[nstates+i] = 0;
333 froms[i] = r = NEW2(shiftcount, short);
334 tos[i] = s = NEW2(shiftcount, short);
337 for (j = 0; j < ntokens; ++j)
341 if (min > symbol_value[j])
342 min = symbol_value[j];
343 if (max < symbol_value[j])
344 max = symbol_value[j];
345 *r++ = symbol_value[j];
349 width[i] = max - min + 1;
353 froms[nstates+i] = r = NEW2(reducecount, short);
354 tos[nstates+i] = s = NEW2(reducecount, short);
357 for (j = 0; j < ntokens; ++j)
359 if (actionrow[ntokens+j])
361 if (min > symbol_value[j])
362 min = symbol_value[j];
363 if (max < symbol_value[j])
364 max = symbol_value[j];
365 *r++ = symbol_value[j];
366 *s++ = actionrow[ntokens+j] - 2;
369 width[nstates+i] = max - min + 1;
381 state_count = NEW2(nstates, short);
383 k = default_goto(start_symbol + 1);
384 fprintf(output_file, "const short %sdgoto[] = {%40d,", symbol_prefix, k);
385 save_column(start_symbol + 1, k);
388 for (i = start_symbol + 2; i < nsyms; i++)
392 if (!rflag) ++outline;
393 putc('\n', output_file);
400 fprintf(output_file, "%5d,", k);
404 if (!rflag) outline += 2;
405 fprintf(output_file, "\n};\n");
419 m = goto_map[symbol];
420 n = goto_map[symbol + 1];
422 if (m == n) return (0);
424 for (i = 0; i < nstates; i++)
427 for (i = m; i < n; i++)
428 state_count[to_state[i]]++;
432 for (i = 0; i < nstates; i++)
434 if (state_count[i] > max)
436 max = state_count[i];
441 return (default_state);
447 save_column(symbol, default_state)
460 m = goto_map[symbol];
461 n = goto_map[symbol + 1];
464 for (i = m; i < n; i++)
466 if (to_state[i] != default_state)
469 if (count == 0) return;
471 symno = symbol_value[symbol] + 2*nstates;
473 froms[symno] = sp1 = sp = NEW2(count, short);
474 tos[symno] = sp2 = NEW2(count, short);
476 for (i = m; i < n; i++)
478 if (to_state[i] != default_state)
480 *sp1++ = from_state[i];
481 *sp2++ = to_state[i];
485 tally[symno] = count;
486 width[symno] = sp1[-1] - sp[0] + 1;
498 order = NEW2(nvectors, short);
501 for (i = 0; i < nvectors; i++)
509 while (j >= 0 && (width[order[j]] < w))
512 while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
515 for (k = nentries - 1; k > j; k--)
516 order[k + 1] = order[k];
532 base = NEW2(nvectors, short);
533 pos = NEW2(nentries, short);
536 table = NEW2(maxtable, short);
537 check = NEW2(maxtable, short);
542 for (i = 0; i < maxtable; i++)
545 for (i = 0; i < nentries; i++)
547 state = matching_vector(i);
550 place = pack_vector(i);
555 base[order[i]] = place;
558 for (i = 0; i < nvectors; i++)
572 /* The function matching_vector determines if the vector specified by */
573 /* the input parameter matches a previously considered vector. The */
574 /* test at the start of the function checks if the vector represents */
575 /* a row of shifts over terminal symbols or a row of reductions, or a */
576 /* column of shifts over a nonterminal symbol. Berkeley Yacc does not */
577 /* check if a column of shifts over a nonterminal symbols matches a */
578 /* previously considered vector. Because of the nature of LR parsing */
579 /* tables, no two columns can match. Therefore, the only possible */
580 /* match would be between a row and a column. Such matches are */
581 /* unlikely. Therefore, to save time, no attempt is made to see if a */
582 /* column matches a previously considered vector. */
584 /* Matching_vector is poorly designed. The test could easily be made */
585 /* faster. Also, it depends on the vectors being in a specific */
589 matching_vector(vector)
607 for (prev = vector - 1; prev >= 0; prev--)
610 if (width[j] != w || tally[j] != t)
614 for (k = 0; match && k < t; k++)
616 if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
648 j = lowzero - from[0];
649 for (k = 1; k < t; ++k)
650 if (lowzero - from[k] > j)
651 j = lowzero - from[k];
657 for (k = 0; ok && k < t; k++)
663 fatal("maximum table size exceeded");
664 maxtable = increase_maxtable(loc);
667 if (check[loc] != -1)
670 for (k = 0; ok && k < vector; k++)
677 for (k = 0; k < t; k++)
681 check[loc] = from[k];
682 if (loc > high) high = loc;
685 while (check[lowzero] != -1)
687 if (lowzero >= maxtable)
689 if (lowzero >= MAXTABLE)
691 fatal("maximum table size exceeded in check\n");
694 maxtable = increase_maxtable(loc);
712 fprintf(output_file, "const short %ssindex[] = {%39d,", symbol_prefix,
716 for (i = 1; i < nstates; i++)
720 if (!rflag) ++outline;
721 putc('\n', output_file);
727 fprintf(output_file, "%5d,", base[i]);
730 if (!rflag) outline += 2;
731 fprintf(output_file, "\n};\nconst short %srindex[] = {%39d,", symbol_prefix,
735 for (i = nstates + 1; i < 2*nstates; i++)
739 if (!rflag) ++outline;
740 putc('\n', output_file);
746 fprintf(output_file, "%5d,", base[i]);
749 if (!rflag) outline += 2;
750 fprintf(output_file, "\n};\nconst short %sgindex[] = {%39d,", symbol_prefix,
754 for (i = 2*nstates + 1; i < nvectors - 1; i++)
758 if (!rflag) ++outline;
759 putc('\n', output_file);
765 fprintf(output_file, "%5d,", base[i]);
768 if (!rflag) outline += 2;
769 fprintf(output_file, "\n};\n");
782 fprintf(code_file, "#define YYTABLESIZE %d\n", high);
783 fprintf(output_file, "const short %stable[] = {%40d,", symbol_prefix,
787 for (i = 1; i <= high; i++)
791 if (!rflag) ++outline;
792 putc('\n', output_file);
798 fprintf(output_file, "%5d,", table[i]);
801 if (!rflag) outline += 2;
802 fprintf(output_file, "\n};\n");
814 fprintf(output_file, "const short %scheck[] = {%40d,", symbol_prefix,
818 for (i = 1; i <= high; i++)
822 if (!rflag) ++outline;
823 putc('\n', output_file);
829 fprintf(output_file, "%5d,", check[i]);
832 if (!rflag) outline += 2;
833 fprintf(output_file, "\n};\n");
839 is_C_identifier(name)
850 if (!isalpha(c) && c != '_' && c != '$')
852 while ((c = *++s) != '"')
854 if (!isalnum(c) && c != '_' && c != '$')
860 if (!isalpha(c) && c != '_' && c != '$')
864 if (!isalnum(c) && c != '_' && c != '$')
878 fprintf(code_file, "#define YYERRCODE %d\n", symbol_value[1]);
882 fprintf(defines_file, "#ifndef YYERRCODE\n");
883 fprintf(defines_file, "#define YYERRCODE %d\n", symbol_value[1]);
884 fprintf(defines_file, "#endif\n\n");
886 for (i = 2; i < ntokens; ++i)
889 if (is_C_identifier(s))
891 fprintf(code_file, "#define ");
892 if (dflag) fprintf(defines_file, "#define ");
896 while ((c = *++s) != '"')
899 if (dflag) putc(c, defines_file);
907 if (dflag) putc(c, defines_file);
912 fprintf(code_file, " %d\n", symbol_value[i]);
913 if (dflag) fprintf(defines_file, " %d\n", symbol_value[i]);
917 if (dflag && unionized)
920 union_file = fopen(union_file_name, "r");
921 if (union_file == NULL) open_error(union_file_name);
922 while ((c = getc(union_file)) != EOF)
923 putc(c, defines_file);
924 fprintf(defines_file, " YYSTYPE;\nextern YYSTYPE %slval;\n",
937 text_file = fopen(text_file_name, "r");
938 if (text_file == NULL)
939 open_error(text_file_name);
941 if ((c = getc(in)) == EOF)
947 while ((c = getc(in)) != EOF)
954 fprintf(out, line_format, ++outline + 1, code_file_name);
963 static char eof[] = "end-of-file";
966 fprintf(code_file, "#define YYFINAL %d\n", final_state);
968 fprintf(code_file, "#ifndef YYDEBUG\n#define YYDEBUG %d\n#endif\n",
971 fprintf(output_file, "#ifndef YYDEBUG\n#define YYDEBUG %d\n#endif\n",
975 for (i = 2; i < ntokens; ++i)
976 if (symbol_value[i] > max)
977 max = symbol_value[i];
979 fprintf(code_file, "#define YYMAXTOKEN %d\n", max);
981 symnam = (char **) MALLOC((max+1)*sizeof(char *));
982 if (symnam == 0) no_space();
984 /* Note that it is not necessary to initialize the element */
986 for (i = 0; i < max; ++i)
988 for (i = ntokens - 1; i >= 2; --i)
989 symnam[symbol_value[i]] = symbol_name[i];
992 if (!rflag) ++outline;
993 fprintf(output_file, "#if YYDEBUG\n");
994 fprintf(output_file, "const char * const %sname[] = {", symbol_prefix);
996 for (i = 0; i <= max; ++i)
1016 if (!rflag) ++outline;
1017 putc('\n', output_file);
1020 fprintf(output_file, "\"\\\"");
1026 fprintf(output_file, "\\\\");
1028 fprintf(output_file, "\\\\");
1030 putc(*s, output_file);
1033 putc(*s, output_file);
1035 fprintf(output_file, "\\\"\",");
1037 else if (s[0] == '\'')
1044 if (!rflag) ++outline;
1045 putc('\n', output_file);
1048 fprintf(output_file, "\"'\\\"'\",");
1053 while (*++s != '\'')
1066 if (!rflag) ++outline;
1067 putc('\n', output_file);
1070 fprintf(output_file, "\"'");
1072 while (*++s != '\'')
1076 fprintf(output_file, "\\\\");
1078 fprintf(output_file, "\\\\");
1080 putc(*s, output_file);
1083 putc(*s, output_file);
1085 fprintf(output_file, "'\",");
1094 if (!rflag) ++outline;
1095 putc('\n', output_file);
1098 putc('"', output_file);
1099 do { putc(*s, output_file); } while (*++s);
1100 fprintf(output_file, "\",");
1108 if (!rflag) ++outline;
1109 putc('\n', output_file);
1112 fprintf(output_file, "0,");
1115 if (!rflag) outline += 2;
1116 fprintf(output_file, "\n};\n");
1119 if (!rflag) ++outline;
1120 fprintf(output_file, "const char * const %srule[] = {\n", symbol_prefix);
1121 for (i = 2; i < nrules; ++i)
1123 fprintf(output_file, "\"%s :", symbol_name[rlhs[i]]);
1124 for (j = rrhs[i]; ritem[j] > 0; ++j)
1126 s = symbol_name[ritem[j]];
1129 fprintf(output_file, " \\\"");
1135 fprintf(output_file, "\\\\\\\\");
1137 fprintf(output_file, "\\\\%c", s[1]);
1141 putc(*s, output_file);
1143 fprintf(output_file, "\\\"");
1145 else if (s[0] == '\'')
1148 fprintf(output_file, " '\\\"'");
1149 else if (s[1] == '\\')
1152 fprintf(output_file, " '\\\\\\\\");
1154 fprintf(output_file, " '\\\\%c", s[2]);
1156 while (*++s != '\'')
1157 putc(*s, output_file);
1158 putc('\'', output_file);
1161 fprintf(output_file, " '%c'", s[1]);
1164 fprintf(output_file, " %s", s);
1166 if (!rflag) ++outline;
1167 fprintf(output_file, "\",\n");
1170 if (!rflag) outline += 2;
1171 fprintf(output_file, "};\n#endif\n");
1178 if (!unionized && ntags == 0)
1181 fprintf(code_file, "#ifndef YYSTYPE\ntypedef int YYSTYPE;\n#endif\n");
1187 output_trailing_text()
1201 if ((c = getc(in)) == EOF)
1206 fprintf(out, line_format, lineno, input_file_name);
1218 fprintf(out, line_format, lineno, input_file_name);
1220 do { putc(c, out); } while ((c = *++cptr) != '\n');
1226 while ((c = getc(in)) != EOF)
1240 fprintf(out, line_format, ++outline + 1, code_file_name);
1245 output_semantic_actions()
1250 fclose(action_file);
1251 action_file = fopen(action_file_name, "r");
1252 if (action_file == NULL)
1253 open_error(action_file_name);
1255 if ((c = getc(action_file)) == EOF)
1263 while ((c = getc(action_file)) != EOF)
1278 fprintf(out, line_format, ++outline + 1, code_file_name);
1288 for (cp = first_state; cp; cp = next)
1302 for (sp = first_shift; sp; sp = next)
1314 reductions *rp, *next;
1316 FREE(reduction_table);
1317 for (rp = first_reduction; rp; rp = next)
1327 * inputs - loc location in table
1328 * output - size increased to
1329 * side effects - table is increase by at least 200 short words
1333 increase_maxtable(int loc)
1340 do { newmax += 200; } while (newmax <= loc);
1341 table = (short *) REALLOC(table, newmax*sizeof(short));
1342 if (table == 0) no_space();
1343 check = (short *) REALLOC(check, newmax*sizeof(short));
1344 if (check == 0) no_space();
1345 for (l = maxtable; l < newmax; ++l)