1 /* $Id: output.c,v 1.21 2009/10/27 10:55:05 tom Exp $ */
7 static Value_t **froms;
10 static Value_t *width;
11 static Value_t *state_count;
12 static Value_t *order;
16 static Value_t *table;
17 static Value_t *check;
22 write_char(FILE * out, int c)
30 write_code_lineno(FILE * out)
33 fprintf(out, line_format, (outline++) + 1, code_file_name);
37 write_input_lineno(FILE * out)
42 fprintf(out, line_format, lineno, input_file_name);
47 define_prefixed(const char *name)
50 fprintf(code_file, "#define %-10s %s%s\n", name, symbol_prefix, name + 2);
56 if (symbol_prefix == NULL)
60 define_prefixed("yyparse");
61 define_prefixed("yylex");
62 define_prefixed("yyerror");
63 define_prefixed("yychar");
64 define_prefixed("yyval");
65 define_prefixed("yylval");
66 define_prefixed("yydebug");
67 define_prefixed("yynerrs");
68 define_prefixed("yyerrflag");
69 define_prefixed("yyss");
70 define_prefixed("yyssp");
71 define_prefixed("yyvs");
72 define_prefixed("yyvsp");
73 define_prefixed("yylhs");
74 define_prefixed("yylen");
75 define_prefixed("yydefred");
76 define_prefixed("yydgoto");
77 define_prefixed("yysindex");
78 define_prefixed("yyrindex");
79 define_prefixed("yygindex");
80 define_prefixed("yytable");
81 define_prefixed("yycheck");
82 define_prefixed("yyname");
83 define_prefixed("yyrule");
86 fprintf(code_file, "#define YYPREFIX \"%s\"\n", symbol_prefix);
94 putc('\n', output_file);
98 output_line(const char *value)
100 fputs(value, output_file);
105 output_int(int value)
107 fprintf(output_file, "%5d,", value);
111 start_int_table(const char *name, int value)
113 int need = 34 - (int)(strlen(symbol_prefix) + strlen(name));
118 "static const short %s%s[] = {%*d,",
119 symbol_prefix, name, need, value);
123 start_str_table(const char *name)
126 "static const char *%s%s[] = {",
127 symbol_prefix, name);
139 output_rule_data(void)
144 start_int_table("lhs", symbol_value[start_symbol]);
147 for (i = 3; i < nrules; i++)
157 output_int(symbol_value[rlhs[i]]);
161 start_int_table("len", 2);
164 for (i = 3; i < nrules; i++)
174 output_int(rrhs[i + 1] - rrhs[i] - 1);
180 output_yydefred(void)
184 start_int_table("defred", (defred[0] ? defred[0] - 2 : 0));
187 for (i = 1; i < nstates; i++)
197 output_int((defred[i] ? defred[i] - 2 : 0));
207 Value_t shiftcount, reducecount;
209 Value_t *actionrow, *r, *s;
212 actionrow = NEW2(2 * ntokens, Value_t);
213 for (i = 0; i < nstates; ++i)
217 for (j = 0; j < 2 * ntokens; ++j)
222 for (p = parser[i]; p; p = p->next)
224 if (p->suppressed == 0)
226 if (p->action_code == SHIFT)
229 actionrow[p->symbol] = p->number;
231 else if (p->action_code == REDUCE && p->number != defred[i])
234 actionrow[p->symbol + ntokens] = p->number;
239 tally[i] = shiftcount;
240 tally[nstates + i] = reducecount;
242 width[nstates + i] = 0;
245 froms[i] = r = NEW2(shiftcount, Value_t);
246 tos[i] = s = NEW2(shiftcount, Value_t);
249 for (j = 0; j < ntokens; ++j)
253 if (min > symbol_value[j])
254 min = symbol_value[j];
255 if (max < symbol_value[j])
256 max = symbol_value[j];
257 *r++ = symbol_value[j];
261 width[i] = (Value_t) (max - min + 1);
265 froms[nstates + i] = r = NEW2(reducecount, Value_t);
266 tos[nstates + i] = s = NEW2(reducecount, Value_t);
269 for (j = 0; j < ntokens; ++j)
271 if (actionrow[ntokens + j])
273 if (min > symbol_value[j])
274 min = symbol_value[j];
275 if (max < symbol_value[j])
276 max = symbol_value[j];
277 *r++ = symbol_value[j];
278 *s++ = (Value_t) (actionrow[ntokens + j] - 2);
281 width[nstates + i] = (Value_t) (max - min + 1);
289 default_goto(int symbol)
297 m = goto_map[symbol];
298 n = goto_map[symbol + 1];
303 for (i = 0; i < nstates; i++)
306 for (i = m; i < n; i++)
307 state_count[to_state[i]]++;
311 for (i = 0; i < nstates; i++)
313 if (state_count[i] > max)
315 max = state_count[i];
320 return (default_state);
324 save_column(int symbol, int default_state)
335 m = goto_map[symbol];
336 n = goto_map[symbol + 1];
339 for (i = m; i < n; i++)
341 if (to_state[i] != default_state)
347 symno = symbol_value[symbol] + 2 * nstates;
349 froms[symno] = sp1 = sp = NEW2(count, Value_t);
350 tos[symno] = sp2 = NEW2(count, Value_t);
352 for (i = m; i < n; i++)
354 if (to_state[i] != default_state)
356 *sp1++ = from_state[i];
357 *sp2++ = to_state[i];
361 tally[symno] = count;
362 width[symno] = (Value_t) (sp1[-1] - sp[0] + 1);
370 state_count = NEW2(nstates, Value_t);
372 k = default_goto(start_symbol + 1);
373 start_int_table("dgoto", k);
374 save_column(start_symbol + 1, k);
377 for (i = start_symbol + 2; i < nsyms; i++)
405 order = NEW2(nvectors, Value_t);
408 for (i = 0; i < nvectors; i++)
416 while (j >= 0 && (width[order[j]] < w))
419 while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
422 for (k = nentries - 1; k > j; k--)
423 order[k + 1] = order[k];
431 /* The function matching_vector determines if the vector specified by */
432 /* the input parameter matches a previously considered vector. The */
433 /* test at the start of the function checks if the vector represents */
434 /* a row of shifts over terminal symbols or a row of reductions, or a */
435 /* column of shifts over a nonterminal symbol. Berkeley Yacc does not */
436 /* check if a column of shifts over a nonterminal symbols matches a */
437 /* previously considered vector. Because of the nature of LR parsing */
438 /* tables, no two columns can match. Therefore, the only possible */
439 /* match would be between a row and a column. Such matches are */
440 /* unlikely. Therefore, to save time, no attempt is made to see if a */
441 /* column matches a previously considered vector. */
443 /* Matching_vector is poorly designed. The test could easily be made */
444 /* faster. Also, it depends on the vectors being in a specific */
448 matching_vector(int vector)
459 if (i >= 2 * nstates)
465 for (prev = vector - 1; prev >= 0; prev--)
468 if (width[j] != w || tally[j] != t)
472 for (k = 0; match && k < t; k++)
474 if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
486 pack_vector(int vector)
503 j = lowzero - from[0];
504 for (k = 1; k < t; ++k)
505 if (lowzero - from[k] > j)
506 j = lowzero - from[k];
512 for (k = 0; ok && k < t; k++)
515 if (loc >= maxtable - 1)
517 if (loc >= MAXTABLE - 1)
518 fatal("maximum table size exceeded");
525 while (newmax <= loc);
526 table = (Value_t *) REALLOC(table, (unsigned)newmax * sizeof(Value_t));
529 check = (Value_t *) REALLOC(check, (unsigned)newmax * sizeof(Value_t));
532 for (l = maxtable; l < newmax; ++l)
540 if (check[loc] != -1)
543 for (k = 0; ok && k < vector; k++)
550 for (k = 0; k < t; k++)
554 check[loc] = from[k];
559 while (check[lowzero] != -1)
574 base = NEW2(nvectors, Value_t);
575 pos = NEW2(nentries, Value_t);
578 table = NEW2(maxtable, Value_t);
579 check = NEW2(maxtable, Value_t);
584 for (i = 0; i < maxtable; i++)
587 for (i = 0; i < nentries; i++)
589 state = matching_vector(i);
592 place = (Value_t) pack_vector(i);
597 base[order[i]] = place;
600 for (i = 0; i < nvectors; i++)
618 start_int_table("sindex", base[0]);
621 for (i = 1; i < nstates; i++)
636 start_int_table("rindex", base[nstates]);
639 for (i = nstates + 1; i < 2 * nstates; i++)
654 start_int_table("gindex", base[2 * nstates]);
657 for (i = 2 * nstates + 1; i < nvectors - 1; i++)
681 fprintf(code_file, "#define YYTABLESIZE %d\n", high);
682 start_int_table("table", table[0]);
685 for (i = 1; i <= high; i++)
695 output_int(table[i]);
708 start_int_table("check", check[0]);
711 for (i = 1; i <= high; i++)
721 output_int(check[i]);
731 nvectors = 2 * nstates + nvars;
733 froms = NEW2(nvectors, Value_t *);
734 tos = NEW2(nvectors, Value_t *);
735 tally = NEW2(nvectors, Value_t);
736 width = NEW2(nvectors, Value_t);
742 FREE(accessing_symbol);
745 FREE(goto_map + ntokens);
757 is_C_identifier(char *name)
767 if (!isalpha(c) && c != '_' && c != '$')
769 while ((c = *++s) != '"')
771 if (!isalnum(c) && c != '_' && c != '$')
777 if (!isalpha(c) && c != '_' && c != '$')
779 while ((c = *++s) != 0)
781 if (!isalnum(c) && c != '_' && c != '$')
793 for (i = 2; i < ntokens; ++i)
796 if (is_C_identifier(s))
798 fprintf(code_file, "#define ");
800 fprintf(defines_file, "#define ");
804 while ((c = *++s) != '"')
808 putc(c, defines_file);
817 putc(c, defines_file);
819 while ((c = *++s) != 0);
822 fprintf(code_file, " %d\n", symbol_value[i]);
824 fprintf(defines_file, " %d\n", symbol_value[i]);
829 fprintf(code_file, "#define YYERRCODE %d\n", symbol_value[1]);
831 if (dflag && unionized)
834 while ((c = getc(union_file)) != EOF)
835 putc(c, defines_file);
836 fprintf(defines_file, " YYSTYPE;\nextern YYSTYPE %slval;\n",
842 output_stored_text(void)
848 if (text_file == NULL)
849 open_error("text_file");
851 if ((c = getc(in)) == EOF)
855 while ((c = getc(in)) != EOF)
859 write_code_lineno(out);
870 fprintf(code_file, "#define YYFINAL %d\n", final_state);
873 fprintf(code_file, "#ifndef YYDEBUG\n#define YYDEBUG %d\n#endif\n", tflag);
877 fprintf(output_file, "#ifndef YYDEBUG\n");
878 fprintf(output_file, "#define YYDEBUG %d\n", tflag);
879 fprintf(output_file, "#endif\n");
883 for (i = 2; i < ntokens; ++i)
884 if (symbol_value[i] > max)
885 max = symbol_value[i];
888 fprintf(code_file, "#define YYMAXTOKEN %d\n", max);
890 symnam = (const char **)MALLOC((unsigned)(max + 1) * sizeof(char *));
894 /* Note that it is not necessary to initialize the element */
896 for (i = 0; i < max; ++i)
898 for (i = ntokens - 1; i >= 2; --i)
899 symnam[symbol_value[i]] = symbol_name[i];
900 symnam[0] = "end-of-file";
902 output_line("#if YYDEBUG");
904 start_str_table("name");
906 for (i = 0; i <= max; ++i)
908 if ((s = symnam[i]) != 0)
929 fprintf(output_file, "\"\\\"");
935 fprintf(output_file, "\\\\");
937 fprintf(output_file, "\\\\");
939 putc(*s, output_file);
942 putc(*s, output_file);
944 fprintf(output_file, "\\\"\",");
946 else if (s[0] == '\'')
956 fprintf(output_file, "\"'\\\"'\",");
977 fprintf(output_file, "\"'");
983 fprintf(output_file, "\\\\");
985 fprintf(output_file, "\\\\");
987 putc(*s, output_file);
990 putc(*s, output_file);
992 fprintf(output_file, "'\",");
997 k = (int)strlen(s) + 3;
1004 putc('"', output_file);
1007 putc(*s, output_file);
1010 fprintf(output_file, "\",");
1021 fprintf(output_file, "0,");
1027 start_str_table("rule");
1028 for (i = 2; i < nrules; ++i)
1030 fprintf(output_file, "\"%s :", symbol_name[rlhs[i]]);
1031 for (j = rrhs[i]; ritem[j] > 0; ++j)
1033 s = symbol_name[ritem[j]];
1036 fprintf(output_file, " \\\"");
1042 fprintf(output_file, "\\\\\\\\");
1044 fprintf(output_file, "\\\\%c", s[1]);
1048 putc(*s, output_file);
1050 fprintf(output_file, "\\\"");
1052 else if (s[0] == '\'')
1055 fprintf(output_file, " '\\\"'");
1056 else if (s[1] == '\\')
1059 fprintf(output_file, " '\\\\\\\\");
1061 fprintf(output_file, " '\\\\%c", s[2]);
1063 while (*++s != '\'')
1064 putc(*s, output_file);
1065 putc('\'', output_file);
1068 fprintf(output_file, " '%c'", s[1]);
1071 fprintf(output_file, " %s", s);
1073 fprintf(output_file, "\",");
1078 output_line("#endif");
1084 if (!unionized && ntags == 0)
1087 fprintf(code_file, "#ifndef YYSTYPE\ntypedef int YYSTYPE;\n#endif\n");
1092 output_trailing_text(void)
1106 if ((c = getc(in)) == EOF)
1108 write_input_lineno(out);
1114 write_input_lineno(out);
1119 while ((c = *++cptr) != '\n');
1124 while ((c = getc(in)) != EOF)
1132 write_char(out, '\n');
1134 write_code_lineno(out);
1138 output_semantic_actions(void)
1143 rewind(action_file);
1144 if ((c = getc(action_file)) == EOF)
1150 while ((c = getc(action_file)) != EOF)
1158 write_char(out, '\n');
1161 write_code_lineno(out);
1170 for (cp = first_state; cp; cp = next)
1183 for (sp = first_shift; sp; sp = next)
1191 free_reductions(void)
1193 reductions *rp, *next;
1195 FREE(reduction_table);
1196 for (rp = first_reduction; rp; rp = next)
1210 output_stored_text();
1219 write_section(tables);
1220 write_section(header);
1221 output_trailing_text();
1222 write_section(body);
1223 output_semantic_actions();
1224 write_section(trailer);