1 /* $Id: output.c,v 1.45 2013/03/05 00:29:17 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;
25 putc_code(FILE * fp, int c)
27 if ((c == '\n') && (fp == code_file))
33 putl_code(FILE * fp, const char *s)
41 puts_code(FILE * fp, const char *s)
47 write_code_lineno(FILE * fp)
49 if (!lflag && (fp == code_file))
52 fprintf(fp, line_format, outline, code_file_name);
57 write_input_lineno(void)
62 fprintf(code_file, line_format, lineno, input_file_name);
67 define_prefixed(FILE * fp, const char *name)
69 int bump_line = CountLine(fp);
76 fprintf(fp, "#ifndef %s\n", name);
80 fprintf(fp, "#define %-10s %s%s\n", name, symbol_prefix, name + 2);
84 fprintf(fp, "#endif /* %s */\n", name);
88 output_prefix(FILE * fp)
90 if (symbol_prefix == NULL)
96 define_prefixed(fp, "yyparse");
97 define_prefixed(fp, "yylex");
98 define_prefixed(fp, "yyerror");
99 define_prefixed(fp, "yychar");
100 define_prefixed(fp, "yyval");
101 define_prefixed(fp, "yylval");
102 define_prefixed(fp, "yydebug");
103 define_prefixed(fp, "yynerrs");
104 define_prefixed(fp, "yyerrflag");
105 define_prefixed(fp, "yylhs");
106 define_prefixed(fp, "yylen");
107 define_prefixed(fp, "yydefred");
108 define_prefixed(fp, "yydgoto");
109 define_prefixed(fp, "yysindex");
110 define_prefixed(fp, "yyrindex");
111 define_prefixed(fp, "yygindex");
112 define_prefixed(fp, "yytable");
113 define_prefixed(fp, "yycheck");
114 define_prefixed(fp, "yyname");
115 define_prefixed(fp, "yyrule");
119 fprintf(fp, "#define YYPREFIX \"%s\"\n", symbol_prefix);
127 putc('\n', output_file);
131 output_line(const char *value)
133 fputs(value, output_file);
138 output_int(int value)
140 fprintf(output_file, "%5d,", value);
144 start_int_table(const char *name, int value)
146 int need = 34 - (int)(strlen(symbol_prefix) + strlen(name));
151 "%sconst short %s%s[] = {%*d,",
152 StaticOrR, symbol_prefix, name, need, value);
156 start_str_table(const char *name)
159 "%sconst char *%s%s[] = {",
160 StaticOrR, "yy", name);
172 output_rule_data(void)
177 start_int_table("lhs", symbol_value[start_symbol]);
180 for (i = 3; i < nrules; i++)
190 output_int(symbol_value[rlhs[i]]);
194 start_int_table("len", 2);
197 for (i = 3; i < nrules; i++)
207 output_int(rrhs[i + 1] - rrhs[i] - 1);
213 output_yydefred(void)
217 start_int_table("defred", (defred[0] ? defred[0] - 2 : 0));
220 for (i = 1; i < nstates; i++)
230 output_int((defred[i] ? defred[i] - 2 : 0));
240 Value_t shiftcount, reducecount;
242 Value_t *actionrow, *r, *s;
245 actionrow = NEW2(2 * ntokens, Value_t);
246 for (i = 0; i < nstates; ++i)
250 for (j = 0; j < 2 * ntokens; ++j)
255 for (p = parser[i]; p; p = p->next)
257 if (p->suppressed == 0)
259 if (p->action_code == SHIFT)
262 actionrow[p->symbol] = p->number;
264 else if (p->action_code == REDUCE && p->number != defred[i])
267 actionrow[p->symbol + ntokens] = p->number;
272 tally[i] = shiftcount;
273 tally[nstates + i] = reducecount;
275 width[nstates + i] = 0;
278 froms[i] = r = NEW2(shiftcount, Value_t);
279 tos[i] = s = NEW2(shiftcount, Value_t);
282 for (j = 0; j < ntokens; ++j)
286 if (min > symbol_value[j])
287 min = symbol_value[j];
288 if (max < symbol_value[j])
289 max = symbol_value[j];
290 *r++ = symbol_value[j];
294 width[i] = (Value_t) (max - min + 1);
298 froms[nstates + i] = r = NEW2(reducecount, Value_t);
299 tos[nstates + i] = s = NEW2(reducecount, Value_t);
302 for (j = 0; j < ntokens; ++j)
304 if (actionrow[ntokens + j])
306 if (min > symbol_value[j])
307 min = symbol_value[j];
308 if (max < symbol_value[j])
309 max = symbol_value[j];
310 *r++ = symbol_value[j];
311 *s++ = (Value_t) (actionrow[ntokens + j] - 2);
314 width[nstates + i] = (Value_t) (max - min + 1);
322 default_goto(int symbol)
330 m = goto_map[symbol];
331 n = goto_map[symbol + 1];
336 for (i = 0; i < nstates; i++)
339 for (i = m; i < n; i++)
340 state_count[to_state[i]]++;
344 for (i = 0; i < nstates; i++)
346 if (state_count[i] > max)
348 max = state_count[i];
353 return (default_state);
357 save_column(int symbol, int default_state)
368 m = goto_map[symbol];
369 n = goto_map[symbol + 1];
372 for (i = m; i < n; i++)
374 if (to_state[i] != default_state)
380 symno = symbol_value[symbol] + 2 * nstates;
382 froms[symno] = sp1 = sp = NEW2(count, Value_t);
383 tos[symno] = sp2 = NEW2(count, Value_t);
385 for (i = m; i < n; i++)
387 if (to_state[i] != default_state)
389 *sp1++ = from_state[i];
390 *sp2++ = to_state[i];
394 tally[symno] = count;
395 width[symno] = (Value_t) (sp1[-1] - sp[0] + 1);
403 state_count = NEW2(nstates, Value_t);
405 k = default_goto(start_symbol + 1);
406 start_int_table("dgoto", k);
407 save_column(start_symbol + 1, k);
410 for (i = start_symbol + 2; i < nsyms; i++)
438 order = NEW2(nvectors, Value_t);
441 for (i = 0; i < nvectors; i++)
449 while (j >= 0 && (width[order[j]] < w))
452 while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
455 for (k = nentries - 1; k > j; k--)
456 order[k + 1] = order[k];
464 /* The function matching_vector determines if the vector specified by */
465 /* the input parameter matches a previously considered vector. The */
466 /* test at the start of the function checks if the vector represents */
467 /* a row of shifts over terminal symbols or a row of reductions, or a */
468 /* column of shifts over a nonterminal symbol. Berkeley Yacc does not */
469 /* check if a column of shifts over a nonterminal symbols matches a */
470 /* previously considered vector. Because of the nature of LR parsing */
471 /* tables, no two columns can match. Therefore, the only possible */
472 /* match would be between a row and a column. Such matches are */
473 /* unlikely. Therefore, to save time, no attempt is made to see if a */
474 /* column matches a previously considered vector. */
476 /* Matching_vector is poorly designed. The test could easily be made */
477 /* faster. Also, it depends on the vectors being in a specific */
481 matching_vector(int vector)
492 if (i >= 2 * nstates)
498 for (prev = vector - 1; prev >= 0; prev--)
501 if (width[j] != w || tally[j] != t)
505 for (k = 0; match && k < t; k++)
507 if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
519 pack_vector(int vector)
536 j = lowzero - from[0];
537 for (k = 1; k < t; ++k)
538 if (lowzero - from[k] > j)
539 j = lowzero - from[k];
545 for (k = 0; ok && k < t; k++)
548 if (loc >= maxtable - 1)
550 if (loc >= MAXTABLE - 1)
551 fatal("maximum table size exceeded");
558 while (newmax <= loc);
560 table = TREALLOC(Value_t, table, newmax);
563 check = TREALLOC(Value_t, check, newmax);
566 for (l = maxtable; l < newmax; ++l)
574 if (check[loc] != -1)
577 for (k = 0; ok && k < vector; k++)
584 for (k = 0; k < t; k++)
588 check[loc] = from[k];
593 while (check[lowzero] != -1)
608 base = NEW2(nvectors, Value_t);
609 pos = NEW2(nentries, Value_t);
612 table = NEW2(maxtable, Value_t);
613 check = NEW2(maxtable, Value_t);
618 for (i = 0; i < maxtable; i++)
621 for (i = 0; i < nentries; i++)
623 state = matching_vector(i);
626 place = (Value_t) pack_vector(i);
631 base[order[i]] = place;
634 for (i = 0; i < nvectors; i++)
652 start_int_table("sindex", base[0]);
655 for (i = 1; i < nstates; i++)
670 start_int_table("rindex", base[nstates]);
673 for (i = nstates + 1; i < 2 * nstates; i++)
688 start_int_table("gindex", base[2 * nstates]);
691 for (i = 2 * nstates + 1; i < nvectors - 1; i++)
715 fprintf(code_file, "#define YYTABLESIZE %d\n", high);
716 start_int_table("table", table[0]);
719 for (i = 1; i <= high; i++)
729 output_int(table[i]);
742 start_int_table("check", check[0]);
745 for (i = 1; i <= high; i++)
755 output_int(check[i]);
765 nvectors = 2 * nstates + nvars;
767 froms = NEW2(nvectors, Value_t *);
768 tos = NEW2(nvectors, Value_t *);
769 tally = NEW2(nvectors, Value_t);
770 width = NEW2(nvectors, Value_t);
776 FREE(accessing_symbol);
779 FREE(goto_map + ntokens);
791 is_C_identifier(char *name)
801 if (!isalpha(c) && c != '_' && c != '$')
803 while ((c = *++s) != '"')
805 if (!isalnum(c) && c != '_' && c != '$')
811 if (!isalpha(c) && c != '_' && c != '$')
813 while ((c = *++s) != 0)
815 if (!isalnum(c) && c != '_' && c != '$')
822 output_defines(FILE * fp)
827 for (i = 2; i < ntokens; ++i)
830 if (is_C_identifier(s) && (!sflag || *s != '"'))
832 fprintf(fp, "#define ");
836 while ((c = *++s) != '"')
847 while ((c = *++s) != 0);
851 fprintf(fp, " %d\n", symbol_value[i]);
857 if (fp != defines_file || iflag)
858 fprintf(fp, "#define YYERRCODE %d\n", symbol_value[1]);
860 if (fp == defines_file || (iflag && !dflag))
867 while ((c = getc(union_file)) != EOF)
870 fprintf(fp, "extern YYSTYPE %slval;\n", symbol_prefix);
876 output_stored_text(FILE * fp)
882 if (text_file == NULL)
883 open_error("text_file");
885 if ((c = getc(in)) == EOF)
888 while ((c = getc(in)) != EOF)
892 write_code_lineno(fp);
903 fprintf(code_file, "#define YYFINAL %d\n", final_state);
905 putl_code(code_file, "#ifndef YYDEBUG\n");
907 fprintf(code_file, "#define YYDEBUG %d\n", tflag);
908 putl_code(code_file, "#endif\n");
912 fprintf(output_file, "#ifndef YYDEBUG\n");
913 fprintf(output_file, "#define YYDEBUG %d\n", tflag);
914 fprintf(output_file, "#endif\n");
918 for (i = 2; i < ntokens; ++i)
919 if (symbol_value[i] > max)
920 max = symbol_value[i];
923 fprintf(code_file, "#define YYMAXTOKEN %d\n", max);
925 symnam = TMALLOC(const char *, max + 1);
928 /* Note that it is not necessary to initialize the element */
930 for (i = 0; i < max; ++i)
932 for (i = ntokens - 1; i >= 2; --i)
933 symnam[symbol_value[i]] = symbol_name[i];
934 symnam[0] = "end-of-file";
936 output_line("#if YYDEBUG");
938 start_str_table("name");
940 for (i = 0; i <= max; ++i)
942 if ((s = symnam[i]) != 0)
963 fprintf(output_file, "\"\\\"");
969 fprintf(output_file, "\\\\");
971 fprintf(output_file, "\\\\");
973 putc(*s, output_file);
976 putc(*s, output_file);
978 fprintf(output_file, "\\\"\",");
980 else if (s[0] == '\'')
990 fprintf(output_file, "\"'\\\"'\",");
1011 fprintf(output_file, "\"'");
1013 while (*++s != '\'')
1017 fprintf(output_file, "\\\\");
1019 fprintf(output_file, "\\\\");
1021 putc(*s, output_file);
1024 putc(*s, output_file);
1026 fprintf(output_file, "'\",");
1031 k = (int)strlen(s) + 3;
1038 putc('"', output_file);
1041 putc(*s, output_file);
1044 fprintf(output_file, "\",");
1055 fprintf(output_file, "0,");
1061 start_str_table("rule");
1062 for (i = 2; i < nrules; ++i)
1064 fprintf(output_file, "\"%s :", symbol_name[rlhs[i]]);
1065 for (j = rrhs[i]; ritem[j] > 0; ++j)
1067 s = symbol_name[ritem[j]];
1070 fprintf(output_file, " \\\"");
1076 fprintf(output_file, "\\\\\\\\");
1078 fprintf(output_file, "\\\\%c", s[1]);
1082 putc(*s, output_file);
1084 fprintf(output_file, "\\\"");
1086 else if (s[0] == '\'')
1089 fprintf(output_file, " '\\\"'");
1090 else if (s[1] == '\\')
1093 fprintf(output_file, " '\\\\\\\\");
1095 fprintf(output_file, " '\\\\%c", s[2]);
1097 while (*++s != '\'')
1098 putc(*s, output_file);
1099 putc('\'', output_file);
1102 fprintf(output_file, " '%c'", s[1]);
1105 fprintf(output_file, " %s", s);
1107 fprintf(output_file, "\",");
1112 output_line("#endif");
1116 output_pure_parser(FILE * fp)
1118 putc_code(fp, '\n');
1120 if (fp == code_file)
1122 fprintf(fp, "#define YYPURE %d\n", pure_parser);
1123 putc_code(fp, '\n');
1127 output_stype(FILE * fp)
1129 if (!unionized && ntags == 0)
1131 putc_code(fp, '\n');
1132 putl_code(fp, "#ifndef YYSTYPE\n");
1133 putl_code(fp, "typedef int YYSTYPE;\n");
1134 putl_code(fp, "#endif\n");
1139 output_trailing_text(void)
1152 if ((c = getc(in)) == EOF)
1154 write_input_lineno();
1155 putc_code(code_file, c);
1160 write_input_lineno();
1163 putc_code(code_file, c);
1165 while ((c = *++cptr) != '\n');
1166 putc_code(code_file, c);
1170 while ((c = getc(in)) != EOF)
1172 putc_code(code_file, c);
1178 putc_code(code_file, '\n');
1180 write_code_lineno(code_file);
1184 output_semantic_actions(void)
1188 rewind(action_file);
1189 if ((c = getc(action_file)) == EOF)
1193 putc_code(code_file, c);
1194 while ((c = getc(action_file)) != EOF)
1196 putc_code(code_file, c);
1202 putc_code(code_file, '\n');
1205 write_code_lineno(code_file);
1209 output_parse_decl(FILE * fp)
1211 putl_code(fp, "\n");
1212 putl_code(fp, "/* compatibility with bison */\n");
1213 putl_code(fp, "#ifdef YYPARSE_PARAM\n");
1214 putl_code(fp, "/* compatibility with FreeBSD */\n");
1215 putl_code(fp, "# ifdef YYPARSE_PARAM_TYPE\n");
1217 "# define YYPARSE_DECL() yyparse(YYPARSE_PARAM_TYPE YYPARSE_PARAM)\n");
1218 putl_code(fp, "# else\n");
1219 putl_code(fp, "# define YYPARSE_DECL() yyparse(void *YYPARSE_PARAM)\n");
1220 putl_code(fp, "# endif\n");
1221 putl_code(fp, "#else\n");
1223 puts_code(fp, "# define YYPARSE_DECL() yyparse(");
1225 puts_code(fp, "void");
1229 for (p = parse_param; p; p = p->next)
1230 fprintf(fp, "%s %s%s%s", p->type, p->name, p->type2,
1231 p->next ? ", " : "");
1233 putl_code(fp, ")\n");
1235 putl_code(fp, "#endif\n");
1239 output_lex_decl(FILE * fp)
1241 putl_code(fp, "\n");
1242 putl_code(fp, "/* Parameters sent to lex. */\n");
1243 putl_code(fp, "#ifdef YYLEX_PARAM\n");
1246 putl_code(fp, "# ifdef YYLEX_PARAM_TYPE\n");
1247 putl_code(fp, "# define YYLEX_DECL() yylex(YYSTYPE *yylval,"
1248 " YYLEX_PARAM_TYPE YYLEX_PARAM)\n");
1249 putl_code(fp, "# else\n");
1250 putl_code(fp, "# define YYLEX_DECL() yylex(YYSTYPE *yylval,"
1251 " void * YYLEX_PARAM)\n");
1252 putl_code(fp, "# endif\n");
1253 putl_code(fp, "# define YYLEX yylex(&yylval, YYLEX_PARAM)\n");
1257 putl_code(fp, "# define YYLEX_DECL() yylex(void *YYLEX_PARAM)\n");
1258 putl_code(fp, "# define YYLEX yylex(YYLEX_PARAM)\n");
1260 putl_code(fp, "#else\n");
1261 if (pure_parser && lex_param)
1264 puts_code(fp, "# define YYLEX_DECL() yylex(YYSTYPE *yylval, ");
1265 for (p = lex_param; p; p = p->next)
1266 fprintf(fp, "%s %s%s%s", p->type, p->name, p->type2,
1267 p->next ? ", " : "");
1268 putl_code(fp, ")\n");
1270 puts_code(fp, "# define YYLEX yylex(&yylval, ");
1271 for (p = lex_param; p; p = p->next)
1272 fprintf(fp, "%s%s", p->name, p->next ? ", " : "");
1273 putl_code(fp, ")\n");
1275 else if (pure_parser)
1277 putl_code(fp, "# define YYLEX_DECL() yylex(YYSTYPE *yylval)\n");
1278 putl_code(fp, "# define YYLEX yylex(&yylval)\n");
1283 puts_code(fp, "# define YYLEX_DECL() yylex(");
1284 for (p = lex_param; p; p = p->next)
1285 fprintf(fp, "%s %s%s%s", p->type, p->name, p->type2,
1286 p->next ? ", " : "");
1287 putl_code(fp, ")\n");
1289 puts_code(fp, "# define YYLEX yylex(");
1290 for (p = lex_param; p; p = p->next)
1291 fprintf(fp, "%s%s", p->name, p->next ? ", " : "");
1292 putl_code(fp, ")\n");
1296 putl_code(fp, "# define YYLEX_DECL() yylex(void)\n");
1297 putl_code(fp, "# define YYLEX yylex()\n");
1299 putl_code(fp, "#endif\n");
1303 output_error_decl(FILE * fp)
1305 putl_code(fp, "\n");
1306 putl_code(fp, "/* Parameters sent to yyerror. */\n");
1311 putl_code(fp, "#ifndef YYERROR_DECL\n");
1312 fprintf(fp, "#define YYERROR_DECL() yyerror(");
1313 for (p = parse_param; p; p = p->next)
1314 fprintf(fp, "%s %s%s, ", p->type, p->name, p->type2);
1315 putl_code(fp, "const char *s)\n");
1316 putl_code(fp, "#endif\n");
1318 putl_code(fp, "#ifndef YYERROR_CALL\n");
1319 puts_code(fp, "#define YYERROR_CALL(msg) yyerror(");
1321 for (p = parse_param; p; p = p->next)
1322 fprintf(fp, "%s, ", p->name);
1324 putl_code(fp, "msg)\n");
1325 putl_code(fp, "#endif\n");
1329 putl_code(fp, "#ifndef YYERROR_DECL\n");
1330 putl_code(fp, "#define YYERROR_DECL() yyerror(const char *s)\n");
1331 putl_code(fp, "#endif\n");
1332 putl_code(fp, "#ifndef YYERROR_CALL\n");
1333 putl_code(fp, "#define YYERROR_CALL(msg) yyerror(msg)\n");
1334 putl_code(fp, "#endif\n");
1344 for (cp = first_state; cp; cp = next)
1357 for (sp = first_shift; sp; sp = next)
1365 free_reductions(void)
1367 reductions *rp, *next;
1369 FREE(reduction_table);
1370 for (rp = first_reduction; rp; rp = next)
1378 output_yyerror_call(const char *msg)
1380 FILE *fp = code_file;
1382 puts_code(fp, " yyerror(");
1386 for (p = parse_param; p; p = p->next)
1387 fprintf(fp, "%s, ", p->name);
1389 puts_code(fp, "\"");
1391 putl_code(fp, "\");\n");
1395 output_externs(FILE * fp, const char *const section[])
1401 for (i = 0; (s = section[i]) != 0; ++i)
1403 if (*s && *s != '#')
1404 fputs("extern\t", fp);
1405 while ((c = *s) != 0)
1410 if (fp == code_file)
1428 fprintf(code_file, "#include \"%s\"\n", externs_file_name);
1434 output_prefix(iflag ? externs_file : output_file);
1435 output_pure_parser(fp);
1436 output_stored_text(fp);
1438 output_parse_decl(fp);
1439 output_lex_decl(fp);
1440 output_error_decl(fp);
1441 write_section(fp, xdecls);
1445 output_externs(externs_file, global_vars);
1447 output_externs(externs_file, impure_vars);
1455 fprintf(code_file, "#include \"%s\"\n", defines_file_name);
1458 output_defines(externs_file);
1462 putc_code(code_file, '\n');
1463 output_defines(code_file);
1467 output_defines(defines_file);
1476 output_prefix(code_file);
1477 write_section(code_file, xdecls);
1478 write_section(code_file, tables);
1480 write_section(code_file, global_vars);
1483 write_section(code_file, impure_vars);
1485 write_section(code_file, hdr_defs);
1488 write_section(code_file, hdr_vars);
1490 output_trailing_text();
1491 write_section(code_file, body_1);
1494 write_section(code_file, body_vars);
1496 write_section(code_file, body_2);
1497 output_yyerror_call("syntax error");
1498 write_section(code_file, body_3);
1499 output_semantic_actions();
1500 write_section(code_file, trailer);
1501 output_yyerror_call("yacc stack overflow");
1502 write_section(code_file, trailer_2);