1 /* $Id: output.c,v 1.36 2010/11/26 16:47:40 tom Exp $ */
5 #define StaticOrR (rflag ? "" : "static ")
6 #define CountLine(fp) (!rflag || ((fp) == code_file))
10 static Value_t **froms;
12 static Value_t *tally;
13 static Value_t *width;
14 static Value_t *state_count;
15 static Value_t *order;
19 static Value_t *table;
20 static Value_t *check;
33 putl_code(const char *s)
40 puts_code(const char *s)
46 write_code_lineno(void)
51 fprintf(code_file, line_format, outline, code_file_name);
56 write_input_lineno(void)
61 fprintf(code_file, line_format, lineno, input_file_name);
66 define_prefixed(FILE * fp, const char *name)
68 int bump_line = CountLine(fp);
75 fprintf(fp, "#ifndef %s\n", name);
79 fprintf(fp, "#define %-10s %s%s\n", name, symbol_prefix, name + 2);
83 fprintf(fp, "#endif /* %s */\n", name);
87 output_prefix(FILE * fp)
89 if (symbol_prefix == NULL)
95 define_prefixed(fp, "yyparse");
96 define_prefixed(fp, "yylex");
97 define_prefixed(fp, "yyerror");
98 define_prefixed(fp, "yychar");
99 define_prefixed(fp, "yyval");
100 define_prefixed(fp, "yylval");
101 define_prefixed(fp, "yydebug");
102 define_prefixed(fp, "yynerrs");
103 define_prefixed(fp, "yyerrflag");
104 define_prefixed(fp, "yylhs");
105 define_prefixed(fp, "yylen");
106 define_prefixed(fp, "yydefred");
107 define_prefixed(fp, "yydgoto");
108 define_prefixed(fp, "yysindex");
109 define_prefixed(fp, "yyrindex");
110 define_prefixed(fp, "yygindex");
111 define_prefixed(fp, "yytable");
112 define_prefixed(fp, "yycheck");
113 define_prefixed(fp, "yyname");
114 define_prefixed(fp, "yyrule");
118 fprintf(fp, "#define YYPREFIX \"%s\"\n", symbol_prefix);
126 putc('\n', output_file);
130 output_line(const char *value)
132 fputs(value, output_file);
137 output_int(int value)
139 fprintf(output_file, "%5d,", value);
143 start_int_table(const char *name, int value)
145 int need = 34 - (int)(strlen(symbol_prefix) + strlen(name));
150 "%sconst short %s%s[] = {%*d,",
151 StaticOrR, symbol_prefix, name, need, value);
155 start_str_table(const char *name)
158 "%sconst char *%s%s[] = {",
159 StaticOrR, "yy", name);
171 output_rule_data(void)
176 start_int_table("lhs", symbol_value[start_symbol]);
179 for (i = 3; i < nrules; i++)
189 output_int(symbol_value[rlhs[i]]);
193 start_int_table("len", 2);
196 for (i = 3; i < nrules; i++)
206 output_int(rrhs[i + 1] - rrhs[i] - 1);
212 output_yydefred(void)
216 start_int_table("defred", (defred[0] ? defred[0] - 2 : 0));
219 for (i = 1; i < nstates; i++)
229 output_int((defred[i] ? defred[i] - 2 : 0));
239 Value_t shiftcount, reducecount;
241 Value_t *actionrow, *r, *s;
244 actionrow = NEW2(2 * ntokens, Value_t);
245 for (i = 0; i < nstates; ++i)
249 for (j = 0; j < 2 * ntokens; ++j)
254 for (p = parser[i]; p; p = p->next)
256 if (p->suppressed == 0)
258 if (p->action_code == SHIFT)
261 actionrow[p->symbol] = p->number;
263 else if (p->action_code == REDUCE && p->number != defred[i])
266 actionrow[p->symbol + ntokens] = p->number;
271 tally[i] = shiftcount;
272 tally[nstates + i] = reducecount;
274 width[nstates + i] = 0;
277 froms[i] = r = NEW2(shiftcount, Value_t);
278 tos[i] = s = NEW2(shiftcount, Value_t);
281 for (j = 0; j < ntokens; ++j)
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];
293 width[i] = (Value_t) (max - min + 1);
297 froms[nstates + i] = r = NEW2(reducecount, Value_t);
298 tos[nstates + i] = s = NEW2(reducecount, Value_t);
301 for (j = 0; j < ntokens; ++j)
303 if (actionrow[ntokens + j])
305 if (min > symbol_value[j])
306 min = symbol_value[j];
307 if (max < symbol_value[j])
308 max = symbol_value[j];
309 *r++ = symbol_value[j];
310 *s++ = (Value_t) (actionrow[ntokens + j] - 2);
313 width[nstates + i] = (Value_t) (max - min + 1);
321 default_goto(int symbol)
329 m = goto_map[symbol];
330 n = goto_map[symbol + 1];
335 for (i = 0; i < nstates; i++)
338 for (i = m; i < n; i++)
339 state_count[to_state[i]]++;
343 for (i = 0; i < nstates; i++)
345 if (state_count[i] > max)
347 max = state_count[i];
352 return (default_state);
356 save_column(int symbol, int default_state)
367 m = goto_map[symbol];
368 n = goto_map[symbol + 1];
371 for (i = m; i < n; i++)
373 if (to_state[i] != default_state)
379 symno = symbol_value[symbol] + 2 * nstates;
381 froms[symno] = sp1 = sp = NEW2(count, Value_t);
382 tos[symno] = sp2 = NEW2(count, Value_t);
384 for (i = m; i < n; i++)
386 if (to_state[i] != default_state)
388 *sp1++ = from_state[i];
389 *sp2++ = to_state[i];
393 tally[symno] = count;
394 width[symno] = (Value_t) (sp1[-1] - sp[0] + 1);
402 state_count = NEW2(nstates, Value_t);
404 k = default_goto(start_symbol + 1);
405 start_int_table("dgoto", k);
406 save_column(start_symbol + 1, k);
409 for (i = start_symbol + 2; i < nsyms; i++)
437 order = NEW2(nvectors, Value_t);
440 for (i = 0; i < nvectors; i++)
448 while (j >= 0 && (width[order[j]] < w))
451 while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
454 for (k = nentries - 1; k > j; k--)
455 order[k + 1] = order[k];
463 /* The function matching_vector determines if the vector specified by */
464 /* the input parameter matches a previously considered vector. The */
465 /* test at the start of the function checks if the vector represents */
466 /* a row of shifts over terminal symbols or a row of reductions, or a */
467 /* column of shifts over a nonterminal symbol. Berkeley Yacc does not */
468 /* check if a column of shifts over a nonterminal symbols matches a */
469 /* previously considered vector. Because of the nature of LR parsing */
470 /* tables, no two columns can match. Therefore, the only possible */
471 /* match would be between a row and a column. Such matches are */
472 /* unlikely. Therefore, to save time, no attempt is made to see if a */
473 /* column matches a previously considered vector. */
475 /* Matching_vector is poorly designed. The test could easily be made */
476 /* faster. Also, it depends on the vectors being in a specific */
480 matching_vector(int vector)
491 if (i >= 2 * nstates)
497 for (prev = vector - 1; prev >= 0; prev--)
500 if (width[j] != w || tally[j] != t)
504 for (k = 0; match && k < t; k++)
506 if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
518 pack_vector(int vector)
535 j = lowzero - from[0];
536 for (k = 1; k < t; ++k)
537 if (lowzero - from[k] > j)
538 j = lowzero - from[k];
544 for (k = 0; ok && k < t; k++)
547 if (loc >= maxtable - 1)
549 if (loc >= MAXTABLE - 1)
550 fatal("maximum table size exceeded");
557 while (newmax <= loc);
559 table = (Value_t *) REALLOC(table, (unsigned)newmax * sizeof(Value_t));
562 check = (Value_t *) REALLOC(check, (unsigned)newmax * sizeof(Value_t));
565 for (l = maxtable; l < newmax; ++l)
573 if (check[loc] != -1)
576 for (k = 0; ok && k < vector; k++)
583 for (k = 0; k < t; k++)
587 check[loc] = from[k];
592 while (check[lowzero] != -1)
607 base = NEW2(nvectors, Value_t);
608 pos = NEW2(nentries, Value_t);
611 table = NEW2(maxtable, Value_t);
612 check = NEW2(maxtable, Value_t);
617 for (i = 0; i < maxtable; i++)
620 for (i = 0; i < nentries; i++)
622 state = matching_vector(i);
625 place = (Value_t) pack_vector(i);
630 base[order[i]] = place;
633 for (i = 0; i < nvectors; i++)
651 start_int_table("sindex", base[0]);
654 for (i = 1; i < nstates; i++)
669 start_int_table("rindex", base[nstates]);
672 for (i = nstates + 1; i < 2 * nstates; i++)
687 start_int_table("gindex", base[2 * nstates]);
690 for (i = 2 * nstates + 1; i < nvectors - 1; i++)
714 fprintf(code_file, "#define YYTABLESIZE %d\n", high);
715 start_int_table("table", table[0]);
718 for (i = 1; i <= high; i++)
728 output_int(table[i]);
741 start_int_table("check", check[0]);
744 for (i = 1; i <= high; i++)
754 output_int(check[i]);
764 nvectors = 2 * nstates + nvars;
766 froms = NEW2(nvectors, Value_t *);
767 tos = NEW2(nvectors, Value_t *);
768 tally = NEW2(nvectors, Value_t);
769 width = NEW2(nvectors, Value_t);
775 FREE(accessing_symbol);
778 FREE(goto_map + ntokens);
790 is_C_identifier(char *name)
800 if (!isalpha(c) && c != '_' && c != '$')
802 while ((c = *++s) != '"')
804 if (!isalnum(c) && c != '_' && c != '$')
810 if (!isalpha(c) && c != '_' && c != '$')
812 while ((c = *++s) != 0)
814 if (!isalnum(c) && c != '_' && c != '$')
826 for (i = 2; i < ntokens; ++i)
829 if (is_C_identifier(s))
831 puts_code("#define ");
833 fprintf(defines_file, "#define ");
837 while ((c = *++s) != '"')
841 putc(c, defines_file);
850 putc(c, defines_file);
852 while ((c = *++s) != 0);
855 fprintf(code_file, " %d\n", symbol_value[i]);
857 fprintf(defines_file, " %d\n", symbol_value[i]);
862 fprintf(code_file, "#define YYERRCODE %d\n", symbol_value[1]);
864 if (dflag && unionized)
867 while ((c = getc(union_file)) != EOF)
868 putc(c, defines_file);
869 fprintf(defines_file, "extern YYSTYPE %slval;\n",
875 output_stored_text(void)
881 if (text_file == NULL)
882 open_error("text_file");
884 if ((c = getc(in)) == EOF)
887 while ((c = getc(in)) != EOF)
902 fprintf(code_file, "#define YYFINAL %d\n", final_state);
904 putl_code("#ifndef YYDEBUG\n");
906 fprintf(code_file, "#define YYDEBUG %d\n", tflag);
907 putl_code("#endif\n");
911 fprintf(output_file, "#ifndef YYDEBUG\n");
912 fprintf(output_file, "#define YYDEBUG %d\n", tflag);
913 fprintf(output_file, "#endif\n");
917 for (i = 2; i < ntokens; ++i)
918 if (symbol_value[i] > max)
919 max = symbol_value[i];
922 fprintf(code_file, "#define YYMAXTOKEN %d\n", max);
924 symnam = (const char **)MALLOC((unsigned)(max + 1) * sizeof(char *));
927 /* Note that it is not necessary to initialize the element */
929 for (i = 0; i < max; ++i)
931 for (i = ntokens - 1; i >= 2; --i)
932 symnam[symbol_value[i]] = symbol_name[i];
933 symnam[0] = "end-of-file";
935 output_line("#if YYDEBUG");
937 start_str_table("name");
939 for (i = 0; i <= max; ++i)
941 if ((s = symnam[i]) != 0)
962 fprintf(output_file, "\"\\\"");
968 fprintf(output_file, "\\\\");
970 fprintf(output_file, "\\\\");
972 putc(*s, output_file);
975 putc(*s, output_file);
977 fprintf(output_file, "\\\"\",");
979 else if (s[0] == '\'')
989 fprintf(output_file, "\"'\\\"'\",");
1010 fprintf(output_file, "\"'");
1012 while (*++s != '\'')
1016 fprintf(output_file, "\\\\");
1018 fprintf(output_file, "\\\\");
1020 putc(*s, output_file);
1023 putc(*s, output_file);
1025 fprintf(output_file, "'\",");
1030 k = (int)strlen(s) + 3;
1037 putc('"', output_file);
1040 putc(*s, output_file);
1043 fprintf(output_file, "\",");
1054 fprintf(output_file, "0,");
1060 start_str_table("rule");
1061 for (i = 2; i < nrules; ++i)
1063 fprintf(output_file, "\"%s :", symbol_name[rlhs[i]]);
1064 for (j = rrhs[i]; ritem[j] > 0; ++j)
1066 s = symbol_name[ritem[j]];
1069 fprintf(output_file, " \\\"");
1075 fprintf(output_file, "\\\\\\\\");
1077 fprintf(output_file, "\\\\%c", s[1]);
1081 putc(*s, output_file);
1083 fprintf(output_file, "\\\"");
1085 else if (s[0] == '\'')
1088 fprintf(output_file, " '\\\"'");
1089 else if (s[1] == '\\')
1092 fprintf(output_file, " '\\\\\\\\");
1094 fprintf(output_file, " '\\\\%c", s[2]);
1096 while (*++s != '\'')
1097 putc(*s, output_file);
1098 putc('\'', output_file);
1101 fprintf(output_file, " '%c'", s[1]);
1104 fprintf(output_file, " %s", s);
1106 fprintf(output_file, "\",");
1111 output_line("#endif");
1115 output_pure_parser(void)
1120 fprintf(code_file, "#define YYPURE %d\n", pure_parser);
1128 if (!unionized && ntags == 0)
1131 putl_code("#ifndef YYSTYPE\n");
1132 putl_code("typedef int YYSTYPE;\n");
1133 putl_code("#endif\n");
1139 output_trailing_text(void)
1152 if ((c = getc(in)) == EOF)
1154 write_input_lineno();
1160 write_input_lineno();
1165 while ((c = *++cptr) != '\n');
1170 while ((c = getc(in)) != EOF)
1180 write_code_lineno();
1184 output_semantic_actions(void)
1188 rewind(action_file);
1189 if ((c = getc(action_file)) == EOF)
1194 while ((c = getc(action_file)) != EOF)
1205 write_code_lineno();
1209 output_parse_decl(void)
1211 putl_code("/* compatibility with bison */\n");
1212 putl_code("#ifdef YYPARSE_PARAM\n");
1213 putl_code("/* compatibility with FreeBSD */\n");
1214 putl_code("# ifdef YYPARSE_PARAM_TYPE\n");
1215 putl_code("# define YYPARSE_DECL() yyparse(YYPARSE_PARAM_TYPE YYPARSE_PARAM)\n");
1216 putl_code("# else\n");
1217 putl_code("# define YYPARSE_DECL() yyparse(void *YYPARSE_PARAM)\n");
1218 putl_code("# endif\n");
1219 putl_code("#else\n");
1221 puts_code("# define YYPARSE_DECL() yyparse(");
1227 for (p = parse_param; p; p = p->next)
1228 fprintf(code_file, "%s %s%s%s", p->type, p->name, p->type2,
1229 p->next ? ", " : "");
1233 putl_code("#endif\n");
1238 output_lex_decl(void)
1240 putl_code("/* Parameters sent to lex. */\n");
1241 putl_code("#ifdef YYLEX_PARAM\n");
1244 putl_code("# define YYLEX_DECL() yylex(YYSTYPE *yylval, "
1245 "void *YYLEX_PARAM)\n");
1246 putl_code("# define YYLEX yylex(&yylval, YYLEX_PARAM)\n");
1250 putl_code("# define YYLEX_DECL() yylex(void *YYLEX_PARAM)\n");
1251 putl_code("# define YYLEX yylex(YYLEX_PARAM)\n");
1253 putl_code("#else\n");
1254 if (pure_parser && lex_param)
1257 puts_code("# define YYLEX_DECL() yylex(YYSTYPE *yylval, ");
1258 for (p = lex_param; p; p = p->next)
1259 fprintf(code_file, "%s %s%s%s", p->type, p->name, p->type2,
1260 p->next ? ", " : "");
1263 puts_code("# define YYLEX yylex(&yylval, ");
1264 for (p = lex_param; p; p = p->next)
1265 fprintf(code_file, "%s%s", p->name, p->next ? ", " : "");
1268 else if (pure_parser)
1270 putl_code("# define YYLEX_DECL() yylex(YYSTYPE *yylval)\n");
1271 putl_code("# define YYLEX yylex(&yylval)\n");
1276 puts_code("# define YYLEX_DECL() yylex(");
1277 for (p = lex_param; p; p = p->next)
1278 fprintf(code_file, "%s %s%s%s", p->type, p->name, p->type2,
1279 p->next ? ", " : "");
1282 puts_code("# define YYLEX yylex(");
1283 for (p = lex_param; p; p = p->next)
1284 fprintf(code_file, "%s%s", p->name, p->next ? ", " : "");
1289 putl_code("# define YYLEX_DECL() yylex(void)\n");
1290 putl_code("# define YYLEX yylex()\n");
1292 putl_code("#endif\n");
1297 output_error_decl(void)
1299 putl_code("/* Parameters sent to yyerror. */\n");
1302 putl_code("#define YYERROR_DECL() yyerror(YYSTYPE *v, const char *s)\n");
1303 putl_code("#define YYERROR_CALL(msg) yyerror(&yylval, msg)\n");
1307 putl_code("#define YYERROR_DECL() yyerror(const char *s)\n");
1308 putl_code("#define YYERROR_CALL(msg) yyerror(msg)\n");
1319 for (cp = first_state; cp; cp = next)
1332 for (sp = first_shift; sp; sp = next)
1340 free_reductions(void)
1342 reductions *rp, *next;
1344 FREE(reduction_table);
1345 for (rp = first_reduction; rp; rp = next)
1353 output_yyerror_call(const char *msg)
1355 puts_code(" yyerror(");
1358 puts_code("&yylval, ");
1362 putl_code("\");\n");
1371 output_prefix(output_file);
1372 output_pure_parser();
1373 output_stored_text();
1375 output_parse_decl();
1377 output_error_decl();
1378 write_section(xdecls);
1387 output_prefix(code_file);
1388 write_section(xdecls);
1389 write_section(tables);
1391 write_section(hdr_defs);
1394 write_section(hdr_vars);
1396 output_trailing_text();
1397 write_section(body_1);
1400 write_section(body_vars);
1402 write_section(body_2);
1403 output_yyerror_call("syntax error");
1404 write_section(body_3);
1405 output_semantic_actions();
1406 write_section(trailer);
1407 output_yyerror_call("yacc stack overflow");
1408 write_section(trailer_2);