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
36 * $FreeBSD: src/usr.bin/yacc/output.c,v 1.13.2.3 2001/10/05 03:03:14 obrien Exp $
37 * $DragonFly: src/usr.bin/yacc/output.c,v 1.5 2005/01/05 15:26:05 joerg Exp $
39 * @(#)output.c 5.7 (Berkeley) 5/24/93
46 static int default_goto(int);
47 static void free_itemsets(void);
48 static void free_reductions(void);
49 static void free_shifts(void);
50 static void goto_actions(void);
51 static int is_C_identifier(char *);
52 static int matching_vector(int);
53 static void output_actions(void);
54 static void output_base(void);
55 static void output_check(void);
56 static void output_debug(void);
57 static void output_defines(void);
58 static void output_prefix(void);
59 static void output_rule_data(void);
60 static void output_semantic_actions(void);
61 static void output_stored_text(void);
62 static void output_stype(void);
63 static void output_table(void);
64 static void output_trailing_text(void);
65 static void output_yydefred(void);
66 static void pack_table(void);
67 static int pack_vector(int);
68 static void save_column(int, int);
69 static void sort_actions(void);
70 static void token_actions(void);
71 static int increase_maxtable(int);
73 static const char line_format[] = "#line %d \"%s\"\n";
80 static short *state_count;
106 if (rflag) write_section(tables);
107 write_section(header);
108 output_trailing_text();
110 output_semantic_actions();
111 write_section(trailer);
118 if (symbol_prefix == NULL)
119 symbol_prefix = "yy";
123 fprintf(code_file, "#define yyparse %sparse\n", symbol_prefix);
125 fprintf(code_file, "#define yylex %slex\n", symbol_prefix);
127 fprintf(code_file, "#define yyerror %serror\n", symbol_prefix);
129 fprintf(code_file, "#define yychar %schar\n", symbol_prefix);
131 fprintf(code_file, "#define yyval %sval\n", symbol_prefix);
133 fprintf(code_file, "#define yylval %slval\n", symbol_prefix);
135 fprintf(code_file, "#define yydebug %sdebug\n", symbol_prefix);
137 fprintf(code_file, "#define yynerrs %snerrs\n", symbol_prefix);
139 fprintf(code_file, "#define yyerrflag %serrflag\n", symbol_prefix);
141 fprintf(code_file, "#define yyss %sss\n", symbol_prefix);
143 fprintf(code_file, "#define yyssp %sssp\n", symbol_prefix);
145 fprintf(code_file, "#define yyvs %svs\n", symbol_prefix);
147 fprintf(code_file, "#define yyvsp %svsp\n", symbol_prefix);
149 fprintf(code_file, "#define yylhs %slhs\n", symbol_prefix);
151 fprintf(code_file, "#define yylen %slen\n", symbol_prefix);
153 fprintf(code_file, "#define yydefred %sdefred\n", symbol_prefix);
155 fprintf(code_file, "#define yydgoto %sdgoto\n", symbol_prefix);
157 fprintf(code_file, "#define yysindex %ssindex\n", symbol_prefix);
159 fprintf(code_file, "#define yyrindex %srindex\n", symbol_prefix);
161 fprintf(code_file, "#define yygindex %sgindex\n", symbol_prefix);
163 fprintf(code_file, "#define yytable %stable\n", symbol_prefix);
165 fprintf(code_file, "#define yycheck %scheck\n", symbol_prefix);
167 fprintf(code_file, "#define yyname %sname\n", symbol_prefix);
169 fprintf(code_file, "#define yyrule %srule\n", symbol_prefix);
171 fprintf(code_file, "#define yysslim %ssslim\n", symbol_prefix);
173 fprintf(code_file, "#define yystacksize %sstacksize\n", symbol_prefix);
176 fprintf(code_file, "#define YYPREFIX \"%s\"\n", symbol_prefix);
181 output_rule_data(void)
187 fprintf(output_file, "const short %slhs[] = {%42d,", symbol_prefix,
188 symbol_value[start_symbol]);
191 for (i = 3; i < nrules; i++)
195 if (!rflag) ++outline;
196 putc('\n', output_file);
202 fprintf(output_file, "%5d,", symbol_value[rlhs[i]]);
204 if (!rflag) outline += 2;
205 fprintf(output_file, "\n};\n");
207 fprintf(output_file, "const short %slen[] = {%42d,", symbol_prefix, 2);
210 for (i = 3; i < nrules; i++)
214 if (!rflag) ++outline;
215 putc('\n', output_file);
221 fprintf(output_file, "%5d,", rrhs[i + 1] - rrhs[i] - 1);
223 if (!rflag) outline += 2;
224 fprintf(output_file, "\n};\n");
229 output_yydefred(void)
233 fprintf(output_file, "const short %sdefred[] = {%39d,", symbol_prefix,
234 (defred[0] ? defred[0] - 2 : 0));
237 for (i = 1; i < nstates; i++)
243 if (!rflag) ++outline;
244 putc('\n', output_file);
248 fprintf(output_file, "%5d,", (defred[i] ? defred[i] - 2 : 0));
251 if (!rflag) outline += 2;
252 fprintf(output_file, "\n};\n");
259 nvectors = 2*nstates + nvars;
261 froms = NEW2(nvectors, short *);
262 tos = NEW2(nvectors, short *);
263 tally = NEW2(nvectors, short);
264 width = NEW2(nvectors, short);
270 FREE(accessing_symbol);
273 FREE(goto_map + ntokens);
289 int shiftcount, reducecount;
291 short *actionrow, *r, *s;
294 actionrow = NEW2(2*ntokens, short);
295 for (i = 0; i < nstates; ++i)
299 for (j = 0; j < 2*ntokens; ++j)
304 for (p = parser[i]; p; p = p->next)
306 if (p->suppressed == 0)
308 if (p->action_code == SHIFT)
311 actionrow[p->symbol] = p->number;
313 else if (p->action_code == REDUCE && p->number != defred[i])
316 actionrow[p->symbol + ntokens] = p->number;
321 tally[i] = shiftcount;
322 tally[nstates+i] = reducecount;
324 width[nstates+i] = 0;
327 froms[i] = r = NEW2(shiftcount, short);
328 tos[i] = s = NEW2(shiftcount, short);
331 for (j = 0; j < ntokens; ++j)
335 if (min > symbol_value[j])
336 min = symbol_value[j];
337 if (max < symbol_value[j])
338 max = symbol_value[j];
339 *r++ = symbol_value[j];
343 width[i] = max - min + 1;
347 froms[nstates+i] = r = NEW2(reducecount, short);
348 tos[nstates+i] = s = NEW2(reducecount, short);
351 for (j = 0; j < ntokens; ++j)
353 if (actionrow[ntokens+j])
355 if (min > symbol_value[j])
356 min = symbol_value[j];
357 if (max < symbol_value[j])
358 max = symbol_value[j];
359 *r++ = symbol_value[j];
360 *s++ = actionrow[ntokens+j] - 2;
363 width[nstates+i] = max - min + 1;
375 state_count = NEW2(nstates, short);
377 k = default_goto(start_symbol + 1);
378 fprintf(output_file, "const short %sdgoto[] = {%40d,", symbol_prefix, k);
379 save_column(start_symbol + 1, k);
382 for (i = start_symbol + 2; i < nsyms; i++)
386 if (!rflag) ++outline;
387 putc('\n', output_file);
394 fprintf(output_file, "%5d,", k);
398 if (!rflag) outline += 2;
399 fprintf(output_file, "\n};\n");
404 default_goto(int symbol)
412 m = goto_map[symbol];
413 n = goto_map[symbol + 1];
415 if (m == n) return (0);
417 for (i = 0; i < nstates; i++)
420 for (i = m; i < n; i++)
421 state_count[to_state[i]]++;
425 for (i = 0; i < nstates; i++)
427 if (state_count[i] > max)
429 max = state_count[i];
434 return (default_state);
440 save_column(int symbol, int default_state)
451 m = goto_map[symbol];
452 n = goto_map[symbol + 1];
455 for (i = m; i < n; i++)
457 if (to_state[i] != default_state)
460 if (count == 0) return;
462 symno = symbol_value[symbol] + 2*nstates;
464 froms[symno] = sp1 = sp = NEW2(count, short);
465 tos[symno] = sp2 = NEW2(count, short);
467 for (i = m; i < n; i++)
469 if (to_state[i] != default_state)
471 *sp1++ = from_state[i];
472 *sp2++ = to_state[i];
476 tally[symno] = count;
477 width[symno] = sp1[-1] - sp[0] + 1;
489 order = NEW2(nvectors, short);
492 for (i = 0; i < nvectors; i++)
500 while (j >= 0 && (width[order[j]] < w))
503 while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
506 for (k = nentries - 1; k > j; k--)
507 order[k + 1] = order[k];
523 base = NEW2(nvectors, short);
524 pos = NEW2(nentries, short);
527 table = NEW2(maxtable, short);
528 check = NEW2(maxtable, short);
533 for (i = 0; i < maxtable; i++)
536 for (i = 0; i < nentries; i++)
538 state = matching_vector(i);
541 place = pack_vector(i);
546 base[order[i]] = place;
549 for (i = 0; i < nvectors; i++)
563 /* The function matching_vector determines if the vector specified by */
564 /* the input parameter matches a previously considered vector. The */
565 /* test at the start of the function checks if the vector represents */
566 /* a row of shifts over terminal symbols or a row of reductions, or a */
567 /* column of shifts over a nonterminal symbol. Berkeley Yacc does not */
568 /* check if a column of shifts over a nonterminal symbols matches a */
569 /* previously considered vector. Because of the nature of LR parsing */
570 /* tables, no two columns can match. Therefore, the only possible */
571 /* match would be between a row and a column. Such matches are */
572 /* unlikely. Therefore, to save time, no attempt is made to see if a */
573 /* column matches a previously considered vector. */
575 /* Matching_vector is poorly designed. The test could easily be made */
576 /* faster. Also, it depends on the vectors being in a specific */
580 matching_vector(int vector)
597 for (prev = vector - 1; prev >= 0; prev--)
600 if (width[j] != w || tally[j] != t)
604 for (k = 0; match && k < t; k++)
606 if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
620 pack_vector(int vector)
636 j = lowzero - from[0];
637 for (k = 1; k < t; ++k)
638 if (lowzero - from[k] > j)
639 j = lowzero - from[k];
645 for (k = 0; ok && k < t; k++)
651 fatal("maximum table size exceeded");
652 maxtable = increase_maxtable(loc);
655 if (check[loc] != -1)
658 for (k = 0; ok && k < vector; k++)
665 for (k = 0; k < t; k++)
669 check[loc] = from[k];
670 if (loc > high) high = loc;
673 while (check[lowzero] != -1)
675 if (lowzero >= maxtable)
677 if (lowzero >= MAXTABLE)
679 fatal("maximum table size exceeded in check\n");
682 maxtable = increase_maxtable(loc);
700 fprintf(output_file, "const short %ssindex[] = {%39d,", symbol_prefix,
704 for (i = 1; i < nstates; i++)
708 if (!rflag) ++outline;
709 putc('\n', output_file);
715 fprintf(output_file, "%5d,", base[i]);
718 if (!rflag) outline += 2;
719 fprintf(output_file, "\n};\nconst short %srindex[] = {%39d,", symbol_prefix,
723 for (i = nstates + 1; i < 2*nstates; i++)
727 if (!rflag) ++outline;
728 putc('\n', output_file);
734 fprintf(output_file, "%5d,", base[i]);
737 if (!rflag) outline += 2;
738 fprintf(output_file, "\n};\nconst short %sgindex[] = {%39d,", symbol_prefix,
742 for (i = 2*nstates + 1; i < nvectors - 1; i++)
746 if (!rflag) ++outline;
747 putc('\n', output_file);
753 fprintf(output_file, "%5d,", base[i]);
756 if (!rflag) outline += 2;
757 fprintf(output_file, "\n};\n");
770 fprintf(code_file, "#define YYTABLESIZE %d\n", high);
771 fprintf(output_file, "const short %stable[] = {%40d,", symbol_prefix,
775 for (i = 1; i <= high; i++)
779 if (!rflag) ++outline;
780 putc('\n', output_file);
786 fprintf(output_file, "%5d,", table[i]);
789 if (!rflag) outline += 2;
790 fprintf(output_file, "\n};\n");
802 fprintf(output_file, "const short %scheck[] = {%40d,", symbol_prefix,
806 for (i = 1; i <= high; i++)
810 if (!rflag) ++outline;
811 putc('\n', output_file);
817 fprintf(output_file, "%5d,", check[i]);
820 if (!rflag) outline += 2;
821 fprintf(output_file, "\n};\n");
827 is_C_identifier(char *name)
837 if (!isalpha(c) && c != '_' && c != '$')
839 while ((c = *++s) != '"')
841 if (!isalnum(c) && c != '_' && c != '$')
847 if (!isalpha(c) && c != '_' && c != '$')
851 if (!isalnum(c) && c != '_' && c != '$')
865 fprintf(code_file, "#define YYERRCODE %d\n", symbol_value[1]);
869 fprintf(defines_file, "#ifndef YYERRCODE\n");
870 fprintf(defines_file, "#define YYERRCODE %d\n", symbol_value[1]);
871 fprintf(defines_file, "#endif\n\n");
873 for (i = 2; i < ntokens; ++i)
876 if (is_C_identifier(s))
878 fprintf(code_file, "#define ");
879 if (dflag) fprintf(defines_file, "#define ");
883 while ((c = *++s) != '"')
886 if (dflag) putc(c, defines_file);
894 if (dflag) putc(c, defines_file);
899 fprintf(code_file, " %d\n", symbol_value[i]);
900 if (dflag) fprintf(defines_file, " %d\n", symbol_value[i]);
904 if (dflag && unionized)
907 union_file = fopen(union_file_name, "r");
908 if (union_file == NULL) open_error(union_file_name);
909 while ((c = getc(union_file)) != EOF)
910 putc(c, defines_file);
911 fprintf(defines_file, " YYSTYPE;\nextern YYSTYPE %slval;\n",
918 output_stored_text(void)
924 text_file = fopen(text_file_name, "r");
925 if (text_file == NULL)
926 open_error(text_file_name);
928 if ((c = getc(in)) == EOF)
934 while ((c = getc(in)) != EOF)
941 fprintf(out, line_format, ++outline + 1, code_file_name);
949 const char **symnam, *s;
952 fprintf(code_file, "#define YYFINAL %d\n", final_state);
954 fprintf(code_file, "#ifndef YYDEBUG\n#define YYDEBUG %d\n#endif\n",
957 fprintf(output_file, "#ifndef YYDEBUG\n#define YYDEBUG %d\n#endif\n",
961 for (i = 2; i < ntokens; ++i)
962 if (symbol_value[i] > max)
963 max = symbol_value[i];
965 fprintf(code_file, "#define YYMAXTOKEN %d\n", max);
967 symnam = MALLOC((max+1)*sizeof(char *));
968 if (symnam == 0) no_space();
970 /* Note that it is not necessary to initialize the element */
972 for (i = 0; i < max; ++i)
974 for (i = ntokens - 1; i >= 2; --i)
975 symnam[symbol_value[i]] = symbol_name[i];
976 symnam[0] = "end-of-file";
978 if (!rflag) ++outline;
979 fprintf(output_file, "#if YYDEBUG\n");
980 fprintf(output_file, "const char * const %sname[] = {", symbol_prefix);
982 for (i = 0; i <= max; ++i)
1002 if (!rflag) ++outline;
1003 putc('\n', output_file);
1006 fprintf(output_file, "\"\\\"");
1012 fprintf(output_file, "\\\\");
1014 fprintf(output_file, "\\\\");
1016 putc(*s, output_file);
1019 putc(*s, output_file);
1021 fprintf(output_file, "\\\"\",");
1023 else if (s[0] == '\'')
1030 if (!rflag) ++outline;
1031 putc('\n', output_file);
1034 fprintf(output_file, "\"'\\\"'\",");
1039 while (*++s != '\'')
1052 if (!rflag) ++outline;
1053 putc('\n', output_file);
1056 fprintf(output_file, "\"'");
1058 while (*++s != '\'')
1062 fprintf(output_file, "\\\\");
1064 fprintf(output_file, "\\\\");
1066 putc(*s, output_file);
1069 putc(*s, output_file);
1071 fprintf(output_file, "'\",");
1080 if (!rflag) ++outline;
1081 putc('\n', output_file);
1084 putc('"', output_file);
1085 do { putc(*s, output_file); } while (*++s);
1086 fprintf(output_file, "\",");
1094 if (!rflag) ++outline;
1095 putc('\n', output_file);
1098 fprintf(output_file, "0,");
1101 if (!rflag) outline += 2;
1102 fprintf(output_file, "\n};\n");
1105 if (!rflag) ++outline;
1106 fprintf(output_file, "const char * const %srule[] = {\n", symbol_prefix);
1107 for (i = 2; i < nrules; ++i)
1109 fprintf(output_file, "\"%s :", symbol_name[rlhs[i]]);
1110 for (j = rrhs[i]; ritem[j] > 0; ++j)
1112 s = symbol_name[ritem[j]];
1115 fprintf(output_file, " \\\"");
1121 fprintf(output_file, "\\\\\\\\");
1123 fprintf(output_file, "\\\\%c", s[1]);
1127 putc(*s, output_file);
1129 fprintf(output_file, "\\\"");
1131 else if (s[0] == '\'')
1134 fprintf(output_file, " '\\\"'");
1135 else if (s[1] == '\\')
1138 fprintf(output_file, " '\\\\\\\\");
1140 fprintf(output_file, " '\\\\%c", s[2]);
1142 while (*++s != '\'')
1143 putc(*s, output_file);
1144 putc('\'', output_file);
1147 fprintf(output_file, " '%c'", s[1]);
1150 fprintf(output_file, " %s", s);
1152 if (!rflag) ++outline;
1153 fprintf(output_file, "\",\n");
1156 if (!rflag) outline += 2;
1157 fprintf(output_file, "};\n#endif\n");
1164 if (!unionized && ntags == 0)
1167 fprintf(code_file, "#ifndef YYSTYPE\ntypedef int YYSTYPE;\n#endif\n");
1173 output_trailing_text(void)
1187 if ((c = getc(in)) == EOF)
1192 fprintf(out, line_format, lineno, input_file_name);
1204 fprintf(out, line_format, lineno, input_file_name);
1206 do { putc(c, out); } while ((c = *++cptr) != '\n');
1212 while ((c = getc(in)) != EOF)
1226 fprintf(out, line_format, ++outline + 1, code_file_name);
1231 output_semantic_actions(void)
1236 fclose(action_file);
1237 action_file = fopen(action_file_name, "r");
1238 if (action_file == NULL)
1239 open_error(action_file_name);
1241 if ((c = getc(action_file)) == EOF)
1249 while ((c = getc(action_file)) != EOF)
1264 fprintf(out, line_format, ++outline + 1, code_file_name);
1274 for (cp = first_state; cp; cp = next)
1288 for (sp = first_shift; sp; sp = next)
1298 free_reductions(void)
1300 reductions *rp, *next;
1302 FREE(reduction_table);
1303 for (rp = first_reduction; rp; rp = next)
1313 * inputs - loc location in table
1314 * output - size increased to
1315 * side effects - table is increase by at least 200 short words
1319 increase_maxtable(int loc)
1326 do { newmax += 200; } while (newmax <= loc);
1327 table = (short *) REALLOC(table, newmax*sizeof(short));
1328 if (table == 0) no_space();
1329 check = (short *) REALLOC(check, newmax*sizeof(short));
1330 if (check == 0) no_space();
1331 for (l = maxtable; l < newmax; ++l)