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;
106 printf("/*\n All more than 3 lines long rules are wrapped into a method\n*/\n");
108 for (i = 0; i < nmethods; ++i)
110 printf("%s", methods[i]);
116 printf(default_line_format, ++outline + 1);
118 printf(" %s static %s short [] yyLhs = {%16d,",
119 csharp ? "" : " protected",
120 csharp ? "readonly" : "final",
121 symbol_value[start_symbol]);
124 for (i = 3; i < nrules; i++)
135 printf("%5d,", symbol_value[rlhs[i]]);
140 printf(" %s static %s short [] yyLen = {%12d,",
141 csharp ? "" : "protected",
142 csharp ? "readonly" : "final",
146 for (i = 3; i < nrules; i++)
157 printf("%5d,", rrhs[i + 1] - rrhs[i] - 1);
168 printf(" %s static %s short [] yyDefRed = {%13d,",
169 csharp ? "" : "protected",
170 csharp ? "readonly" : "final",
171 (defred[0] ? defred[0] - 2 : 0));
174 for (i = 1; i < nstates; i++)
185 printf("%5d,", (defred[i] ? defred[i] - 2 : 0));
195 nvectors = 2*nstates + nvars;
197 froms = NEW2(nvectors, short *);
198 tos = NEW2(nvectors, short *);
199 tally = NEW2(nvectors, short);
200 width = NEW2(nvectors, short);
206 FREE(accessing_symbol);
209 FREE(goto_map + ntokens);
224 register int shiftcount, reducecount;
225 register int max, min;
226 register short *actionrow, *r, *s;
229 actionrow = NEW2(2*ntokens, short);
230 for (i = 0; i < nstates; ++i)
234 for (j = 0; j < 2*ntokens; ++j)
239 for (p = parser[i]; p; p = p->next)
241 if (p->suppressed == 0)
243 if (p->action_code == SHIFT)
246 actionrow[p->symbol] = p->number;
248 else if (p->action_code == REDUCE && p->number != defred[i])
251 actionrow[p->symbol + ntokens] = p->number;
256 tally[i] = shiftcount;
257 tally[nstates+i] = reducecount;
259 width[nstates+i] = 0;
262 froms[i] = r = NEW2(shiftcount, short);
263 tos[i] = s = NEW2(shiftcount, short);
266 for (j = 0; j < ntokens; ++j)
270 if (min > symbol_value[j])
271 min = symbol_value[j];
272 if (max < symbol_value[j])
273 max = symbol_value[j];
274 *r++ = symbol_value[j];
278 width[i] = max - min + 1;
282 froms[nstates+i] = r = NEW2(reducecount, short);
283 tos[nstates+i] = s = NEW2(reducecount, short);
286 for (j = 0; j < ntokens; ++j)
288 if (actionrow[ntokens+j])
290 if (min > symbol_value[j])
291 min = symbol_value[j];
292 if (max < symbol_value[j])
293 max = symbol_value[j];
294 *r++ = symbol_value[j];
295 *s++ = actionrow[ntokens+j] - 2;
298 width[nstates+i] = max - min + 1;
307 register int i, j, k;
309 state_count = NEW2(nstates, short);
311 k = default_goto(start_symbol + 1);
312 printf(" protected static %s short [] yyDgoto = {%14d,", csharp ? "readonly" : "final", k);
313 save_column(start_symbol + 1, k);
316 for (i = start_symbol + 2; i < nsyms; i++)
344 register int default_state;
347 m = goto_map[symbol];
348 n = goto_map[symbol + 1];
350 if (m == n) return (0);
352 for (i = 0; i < nstates; i++)
355 for (i = m; i < n; i++)
356 state_count[to_state[i]]++;
360 for (i = 0; i < nstates; i++)
362 if (state_count[i] > max)
364 max = state_count[i];
369 return (default_state);
374 save_column(symbol, default_state)
387 m = goto_map[symbol];
388 n = goto_map[symbol + 1];
391 for (i = m; i < n; i++)
393 if (to_state[i] != default_state)
396 if (count == 0) return;
398 symno = symbol_value[symbol] + 2*nstates;
400 froms[symno] = sp1 = sp = NEW2(count, short);
401 tos[symno] = sp2 = NEW2(count, short);
403 for (i = m; i < n; i++)
405 if (to_state[i] != default_state)
407 *sp1++ = from_state[i];
408 *sp2++ = to_state[i];
412 tally[symno] = count;
413 width[symno] = sp1[-1] - sp[0] + 1;
424 order = NEW2(nvectors, short);
427 for (i = 0; i < nvectors; i++)
435 while (j >= 0 && (width[order[j]] < w))
438 while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
441 for (k = nentries - 1; k > j; k--)
442 order[k + 1] = order[k];
457 base = NEW2(nvectors, short);
458 pos = NEW2(nentries, short);
461 table = NEW2(maxtable, short);
462 check = NEW2(maxtable, short);
467 for (i = 0; i < maxtable; i++)
470 for (i = 0; i < nentries; i++)
472 state = matching_vector(i);
475 place = pack_vector(i);
480 base[order[i]] = place;
483 for (i = 0; i < nvectors; i++)
497 /* The function matching_vector determines if the vector specified by */
498 /* the input parameter matches a previously considered vector. The */
499 /* test at the start of the function checks if the vector represents */
500 /* a row of shifts over terminal symbols or a row of reductions, or a */
501 /* column of shifts over a nonterminal symbol. Berkeley Yacc does not */
502 /* check if a column of shifts over a nonterminal symbols matches a */
503 /* previously considered vector. Because of the nature of LR parsing */
504 /* tables, no two columns can match. Therefore, the only possible */
505 /* match would be between a row and a column. Such matches are */
506 /* unlikely. Therefore, to save time, no attempt is made to see if a */
507 /* column matches a previously considered vector. */
509 /* Matching_vector is poorly designed. The test could easily be made */
510 /* faster. Also, it depends on the vectors being in a specific */
514 matching_vector(vector)
532 for (prev = vector - 1; prev >= 0; prev--)
535 if (width[j] != w || tally[j] != t)
539 for (k = 0; match && k < t; k++)
541 if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
558 register int i, j, k, l;
562 register short *from;
573 j = lowzero - from[0];
574 for (k = 1; k < t; ++k)
575 if (lowzero - from[k] > j)
576 j = lowzero - from[k];
582 for (k = 0; ok && k < t; k++)
588 fatal("maximum table size exceeded");
591 do { newmax += 200; } while (newmax <= loc);
592 table = (short *) REALLOC(table, newmax*sizeof(short));
593 if (table == 0) no_space();
594 check = (short *) REALLOC(check, newmax*sizeof(short));
595 if (check == 0) no_space();
596 for (l = maxtable; l < newmax; ++l)
604 if (check[loc] != -1)
607 for (k = 0; ok && k < vector; k++)
614 for (k = 0; k < t; k++)
618 check[loc] = from[k];
619 if (loc > high) high = loc;
622 while (check[lowzero] != -1)
636 printf(" protected static %s short [] yySindex = {%13d,", csharp? "readonly":"final", base[0]);
639 for (i = 1; i < nstates; i++)
650 printf("%5d,", base[i]);
654 printf("\n };\n protected static %s short [] yyRindex = {%13d,",
655 csharp ? "readonly" : "final",
659 for (i = nstates + 1; i < 2*nstates; i++)
670 printf("%5d,", base[i]);
674 printf("\n };\n protected static %s short [] yyGindex = {%13d,",
675 csharp ? "readonly" : "final",
679 for (i = 2*nstates + 1; i < nvectors - 1; i++)
690 printf("%5d,", base[i]);
705 printf(" protected static %s short [] yyTable = {%14d,", csharp ? "readonly" : "final", table[0]);
708 for (i = 1; i <= high; i++)
719 printf("%5d,", table[i]);
734 printf(" protected static %s short [] yyCheck = {%14d,",
735 csharp ? "readonly" : "final",
739 for (i = 1; i <= high; i++)
750 printf("%5d,", check[i]);
760 is_C_identifier(name)
771 if (!isalpha(c) && c != '_' && c != '$')
773 while ((c = *++s) != '"')
775 if (!isalnum(c) && c != '_' && c != '$')
781 if (!isalpha(c) && c != '_' && c != '$')
785 if (!isalnum(c) && c != '_' && c != '$')
792 output_defines(prefix)
798 for (i = 2; i < ntokens; ++i)
801 if (is_C_identifier(s))
804 printf(" %s ", prefix);
808 while ((c = *++s) != '"')
822 printf(" = %d%s\n", symbol_value[i], csharp ? ";" : ";");
827 printf(" %s yyErrorCode = %d%s\n", prefix ? prefix : "", symbol_value[1], csharp ? ";" : ";");
831 output_stored_text(file, name)
839 in = fopen(name, "r");
842 if ((c = getc(in)) != EOF) {
846 while ((c = getc(in)) != EOF)
852 printf(default_line_format, ++outline + 1);
860 register int i, j, k, max;
862 char * prefix = tflag ? "" : "//t";
865 printf(" protected %s int yyFinal = %d;\n", csharp ? "const" : "static final", final_state);
868 printf ("%s // Put this array into a separate class so it is only initialized if debugging is actually used\n", prefix);
869 printf ("%s // Use MarshalByRefObject to disable inlining\n", prefix);
870 printf("%s class YYRules %s {\n", prefix, csharp ? ": MarshalByRefObject" : "");
871 printf("%s public static %s string [] yyRule = {\n", prefix, csharp ? "readonly" : "final");
872 for (i = 2; i < nrules; ++i)
874 printf("%s \"%s :", prefix, symbol_name[rlhs[i]]);
875 for (j = rrhs[i]; ritem[j] > 0; ++j)
877 s = symbol_name[ritem[j]];
888 printf("\\\\%c", s[1]);
896 else if (s[0] == '\'')
900 else if (s[1] == '\\')
903 printf(" '\\\\\\\\");
905 printf(" '\\\\%c", s[2]);
912 printf(" '%c'", s[1]);
921 printf("%s };\n", prefix);
922 printf ("%s public static string getRule (int index) {\n", prefix);
923 printf ("%s return yyRule [index];\n", prefix);
924 printf ("%s }\n", prefix);
925 printf ("%s}\n", prefix);
928 for (i = 2; i < ntokens; ++i)
929 if (symbol_value[i] > max)
930 max = symbol_value[i];
932 /* need yyNames for yyExpecting() */
934 printf(" protected static %s string [] yyNames = {", csharp ? "readonly" : "final");
935 symnam = (char **) MALLOC((max+1)*sizeof(char *));
936 if (symnam == 0) no_space();
938 /* Note that it is not necessary to initialize the element */
940 for (i = 0; i < max; ++i)
942 for (i = ntokens - 1; i >= 2; --i)
943 symnam[symbol_value[i]] = symbol_name[i];
944 symnam[0] = "end-of-file";
946 j = 70; fputs(" ", stdout);
947 for (i = 0; i <= max; ++i)
988 else if (s[0] == '\'')
999 printf("\"'\\\"'\",");
1004 while (*++s != '\'')
1023 while (*++s != '\'')
1050 do { putchar(*s); } while (*++s);
1071 output_trailing_text()
1073 register int c, last;
1084 if ((c = getc(in)) == EOF)
1087 printf(line_format, lineno, input_file_name);
1096 printf(line_format, lineno, input_file_name);
1097 do { putchar(c); } while ((c = *++cptr) != '\n');
1103 while ((c = getc(in)) != EOF)
1116 printf(default_line_format, ++outline + 1);
1120 output_semantic_actions()
1122 register int c, last;
1124 fclose(action_file);
1125 action_file = fopen(action_file_name, "r");
1126 if (action_file == NULL)
1127 open_error(action_file_name);
1129 if ((c = getc(action_file)) == EOF)
1136 while ((c = getc(action_file)) != EOF)
1150 printf(default_line_format, ++outline + 1);
1156 register core *cp, *next;
1159 for (cp = first_state; cp; cp = next)
1169 register shifts *sp, *next;
1172 for (sp = first_shift; sp; sp = next)
1183 register reductions *rp, *next;
1185 FREE(reduction_table);
1186 for (rp = first_reduction; rp; rp = next)