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
38 static char sccsid[] = "@(#)output.c 5.7 (Berkeley) 5/24/93";
50 static short *state_count;
69 while (fgets(buf, sizeof buf, stdin) != NULL) {
72 if (buf[strlen(buf)-1] != '\n')
73 fprintf(stderr, "jay: line %d is too long\n", lno), done(1);
76 case 't': if (!tflag) fputs("//t", stdout);
79 cp = strtok(buf, " \t\r\n");
81 if (strcmp(cp, "actions") == 0) output_semantic_actions();
82 else if (strcmp(cp, "debug") == 0) output_debug();
83 else if (strcmp(cp, "epilog") == 0) output_trailing_text();
84 else if (strcmp(cp, "prolog") == 0)
85 output_stored_text(prolog_file, prolog_file_name);
86 else if (strcmp(cp, "local") == 0)
87 output_stored_text(local_file, local_file_name);
88 else if (strcmp(cp, "tables") == 0)
89 output_rule_data(), output_yydefred(), output_actions();
90 else if (strcmp(cp, "tokens") == 0)
91 output_defines(strtok(NULL, "\r\n"));
93 fprintf(stderr, "jay: unknown call (%s) in line %d\n", cp, lno);
96 fputs(buf+1, stdout), ++ outline;
107 printf(" %s static %s short [] yyLhs = {%16d,",
108 csharp ? "" : " protected",
109 csharp ? "" : " final",
110 symbol_value[start_symbol]);
113 for (i = 3; i < nrules; i++)
124 printf("%5d,", symbol_value[rlhs[i]]);
129 printf(" %s static %s short [] yyLen = {%12d,",
130 csharp ? "" : "protected",
131 csharp ? "" : "final",
135 for (i = 3; i < nrules; i++)
146 printf("%5d,", rrhs[i + 1] - rrhs[i] - 1);
157 printf(" %s static %s short [] yyDefRed = {%13d,",
158 csharp ? "" : "protected",
159 csharp ? "" : "final",
160 (defred[0] ? defred[0] - 2 : 0));
163 for (i = 1; i < nstates; i++)
174 printf("%5d,", (defred[i] ? defred[i] - 2 : 0));
184 nvectors = 2*nstates + nvars;
186 froms = NEW2(nvectors, short *);
187 tos = NEW2(nvectors, short *);
188 tally = NEW2(nvectors, short);
189 width = NEW2(nvectors, short);
195 FREE(accessing_symbol);
198 FREE(goto_map + ntokens);
213 register int shiftcount, reducecount;
214 register int max, min;
215 register short *actionrow, *r, *s;
218 actionrow = NEW2(2*ntokens, short);
219 for (i = 0; i < nstates; ++i)
223 for (j = 0; j < 2*ntokens; ++j)
228 for (p = parser[i]; p; p = p->next)
230 if (p->suppressed == 0)
232 if (p->action_code == SHIFT)
235 actionrow[p->symbol] = p->number;
237 else if (p->action_code == REDUCE && p->number != defred[i])
240 actionrow[p->symbol + ntokens] = p->number;
245 tally[i] = shiftcount;
246 tally[nstates+i] = reducecount;
248 width[nstates+i] = 0;
251 froms[i] = r = NEW2(shiftcount, short);
252 tos[i] = s = NEW2(shiftcount, short);
255 for (j = 0; j < ntokens; ++j)
259 if (min > symbol_value[j])
260 min = symbol_value[j];
261 if (max < symbol_value[j])
262 max = symbol_value[j];
263 *r++ = symbol_value[j];
267 width[i] = max - min + 1;
271 froms[nstates+i] = r = NEW2(reducecount, short);
272 tos[nstates+i] = s = NEW2(reducecount, short);
275 for (j = 0; j < ntokens; ++j)
277 if (actionrow[ntokens+j])
279 if (min > symbol_value[j])
280 min = symbol_value[j];
281 if (max < symbol_value[j])
282 max = symbol_value[j];
283 *r++ = symbol_value[j];
284 *s++ = actionrow[ntokens+j] - 2;
287 width[nstates+i] = max - min + 1;
296 register int i, j, k;
298 state_count = NEW2(nstates, short);
300 k = default_goto(start_symbol + 1);
301 printf(" protected static %s short [] yyDgoto = {%14d,", csharp ? "" : "final", k);
302 save_column(start_symbol + 1, k);
305 for (i = start_symbol + 2; i < nsyms; i++)
333 register int default_state;
336 m = goto_map[symbol];
337 n = goto_map[symbol + 1];
339 if (m == n) return (0);
341 for (i = 0; i < nstates; i++)
344 for (i = m; i < n; i++)
345 state_count[to_state[i]]++;
349 for (i = 0; i < nstates; i++)
351 if (state_count[i] > max)
353 max = state_count[i];
358 return (default_state);
363 save_column(symbol, default_state)
376 m = goto_map[symbol];
377 n = goto_map[symbol + 1];
380 for (i = m; i < n; i++)
382 if (to_state[i] != default_state)
385 if (count == 0) return;
387 symno = symbol_value[symbol] + 2*nstates;
389 froms[symno] = sp1 = sp = NEW2(count, short);
390 tos[symno] = sp2 = NEW2(count, short);
392 for (i = m; i < n; i++)
394 if (to_state[i] != default_state)
396 *sp1++ = from_state[i];
397 *sp2++ = to_state[i];
401 tally[symno] = count;
402 width[symno] = sp1[-1] - sp[0] + 1;
413 order = NEW2(nvectors, short);
416 for (i = 0; i < nvectors; i++)
424 while (j >= 0 && (width[order[j]] < w))
427 while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
430 for (k = nentries - 1; k > j; k--)
431 order[k + 1] = order[k];
446 base = NEW2(nvectors, short);
447 pos = NEW2(nentries, short);
450 table = NEW2(maxtable, short);
451 check = NEW2(maxtable, short);
456 for (i = 0; i < maxtable; i++)
459 for (i = 0; i < nentries; i++)
461 state = matching_vector(i);
464 place = pack_vector(i);
469 base[order[i]] = place;
472 for (i = 0; i < nvectors; i++)
486 /* The function matching_vector determines if the vector specified by */
487 /* the input parameter matches a previously considered vector. The */
488 /* test at the start of the function checks if the vector represents */
489 /* a row of shifts over terminal symbols or a row of reductions, or a */
490 /* column of shifts over a nonterminal symbol. Berkeley Yacc does not */
491 /* check if a column of shifts over a nonterminal symbols matches a */
492 /* previously considered vector. Because of the nature of LR parsing */
493 /* tables, no two columns can match. Therefore, the only possible */
494 /* match would be between a row and a column. Such matches are */
495 /* unlikely. Therefore, to save time, no attempt is made to see if a */
496 /* column matches a previously considered vector. */
498 /* Matching_vector is poorly designed. The test could easily be made */
499 /* faster. Also, it depends on the vectors being in a specific */
503 matching_vector(vector)
521 for (prev = vector - 1; prev >= 0; prev--)
524 if (width[j] != w || tally[j] != t)
528 for (k = 0; match && k < t; k++)
530 if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
547 register int i, j, k, l;
551 register short *from;
562 j = lowzero - from[0];
563 for (k = 1; k < t; ++k)
564 if (lowzero - from[k] > j)
565 j = lowzero - from[k];
571 for (k = 0; ok && k < t; k++)
577 fatal("maximum table size exceeded");
580 do { newmax += 200; } while (newmax <= loc);
581 table = (short *) REALLOC(table, newmax*sizeof(short));
582 if (table == 0) no_space();
583 check = (short *) REALLOC(check, newmax*sizeof(short));
584 if (check == 0) no_space();
585 for (l = maxtable; l < newmax; ++l)
593 if (check[loc] != -1)
596 for (k = 0; ok && k < vector; k++)
603 for (k = 0; k < t; k++)
607 check[loc] = from[k];
608 if (loc > high) high = loc;
611 while (check[lowzero] != -1)
625 printf(" protected static %s short [] yySindex = {%13d,", csharp?"":"final", base[0]);
628 for (i = 1; i < nstates; i++)
639 printf("%5d,", base[i]);
643 printf("\n };\n protected static %s short [] yyRindex = {%13d,",
644 csharp ? "" : "final",
648 for (i = nstates + 1; i < 2*nstates; i++)
659 printf("%5d,", base[i]);
663 printf("\n };\n protected static %s short [] yyGindex = {%13d,",
664 csharp ? "" : "final",
668 for (i = 2*nstates + 1; i < nvectors - 1; i++)
679 printf("%5d,", base[i]);
694 printf(" protected static %s short [] yyTable = {%14d,", csharp ? "" : "final", table[0]);
697 for (i = 1; i <= high; i++)
708 printf("%5d,", table[i]);
723 printf(" protected static %s short [] yyCheck = {%14d,",
724 csharp ? "" : "final",
728 for (i = 1; i <= high; i++)
739 printf("%5d,", check[i]);
749 is_C_identifier(name)
760 if (!isalpha(c) && c != '_' && c != '$')
762 while ((c = *++s) != '"')
764 if (!isalnum(c) && c != '_' && c != '$')
770 if (!isalpha(c) && c != '_' && c != '$')
774 if (!isalnum(c) && c != '_' && c != '$')
781 output_defines(prefix)
787 for (i = 2; i < ntokens; ++i)
790 if (is_C_identifier(s))
793 printf(" %s ", prefix);
797 while ((c = *++s) != '"')
811 printf(" = %d%s\n", symbol_value[i], csharp ? ";" : ";");
816 printf(" %s yyErrorCode = %d%s\n", prefix ? prefix : "", symbol_value[1], csharp ? ";" : ";");
820 output_stored_text(file, name)
828 in = fopen(name, "r");
831 if ((c = getc(in)) != EOF) {
835 while ((c = getc(in)) != EOF)
841 printf(default_line_format, ++outline + 1);
849 register int i, j, k, max;
851 char * prefix = tflag ? "" : "//t";
854 printf(" protected static %s int yyFinal = %d;\n", csharp ? "" : "final", final_state);
857 printf ("%s // Put this array into a separate class so it is only initialized if debugging is actually used\n", prefix);
858 printf ("%s // Use MarshalByRefObject to disable inlining\n", prefix);
859 printf("%s class YYRules %s {\n", prefix, csharp ? ": MarshalByRefObject" : "");
860 printf("%s public static %s string [] yyRule = {\n", prefix, csharp ? "" : "final");
861 for (i = 2; i < nrules; ++i)
863 printf("%s \"%s :", prefix, symbol_name[rlhs[i]]);
864 for (j = rrhs[i]; ritem[j] > 0; ++j)
866 s = symbol_name[ritem[j]];
877 printf("\\\\%c", s[1]);
885 else if (s[0] == '\'')
889 else if (s[1] == '\\')
892 printf(" '\\\\\\\\");
894 printf(" '\\\\%c", s[2]);
901 printf(" '%c'", s[1]);
910 printf("%s };\n", prefix);
911 printf ("%s public static string getRule (int index) {\n", prefix);
912 printf ("%s return yyRule [index];\n", prefix);
913 printf ("%s }\n", prefix);
914 printf ("%s}\n", prefix);
917 for (i = 2; i < ntokens; ++i)
918 if (symbol_value[i] > max)
919 max = symbol_value[i];
921 /* need yyNames for yyExpecting() */
923 printf(" protected static %s string [] yyNames = {", csharp ? "" : "final");
924 symnam = (char **) MALLOC((max+1)*sizeof(char *));
925 if (symnam == 0) no_space();
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 j = 70; fputs(" ", stdout);
936 for (i = 0; i <= max; ++i)
977 else if (s[0] == '\'')
988 printf("\"'\\\"'\",");
1012 while (*++s != '\'')
1039 do { putchar(*s); } while (*++s);
1060 output_trailing_text()
1062 register int c, last;
1073 if ((c = getc(in)) == EOF)
1076 printf(line_format, lineno, input_file_name);
1085 printf(line_format, lineno, input_file_name);
1086 do { putchar(c); } while ((c = *++cptr) != '\n');
1092 while ((c = getc(in)) != EOF)
1105 printf(default_line_format, ++outline + 1);
1109 output_semantic_actions()
1111 register int c, last;
1113 fclose(action_file);
1114 action_file = fopen(action_file_name, "r");
1115 if (action_file == NULL)
1116 open_error(action_file_name);
1118 if ((c = getc(action_file)) == EOF)
1125 while ((c = getc(action_file)) != EOF)
1139 printf(default_line_format, ++outline + 1);
1145 register core *cp, *next;
1148 for (cp = first_state; cp; cp = next)
1158 register shifts *sp, *next;
1161 for (sp = first_shift; sp; sp = next)
1172 register reductions *rp, *next;
1174 FREE(reduction_table);
1175 for (rp = first_reduction; rp; rp = next)