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
;
65 free_reductions (void);
74 output_actions (void);
86 output_defines (const char *prefix
);
89 output_rule_data (void);
92 output_semantic_actions (void);
95 output_stored_text (FILE *file
, const char *name
);
101 output_trailing_text (void);
104 save_column (int symbol
, int default_state
);
110 output_yydefred (void);
113 default_goto (int symbol
);
116 matching_vector (int vector
);
119 pack_vector (int vector
);
122 token_actions (void);
137 while (fgets(buf
, sizeof buf
, stdin
) != NULL
) {
140 if (buf
[strlen(buf
)-1] != '\n')
141 fprintf(stderr
, "jay: line %d is too long\n", lno
), done(1);
144 case 't': if (!tflag
) fputs("//t", output_file
);
147 cp
= strtok(buf
, " \t\r\n");
149 if (strcmp(cp
, "actions") == 0) output_semantic_actions();
150 else if (strcmp(cp
, "debug") == 0) output_debug();
151 else if (strcmp(cp
, "epilog") == 0) output_trailing_text();
152 else if (strcmp(cp
, "prolog") == 0)
153 output_stored_text(prolog_file
, prolog_file_name
);
154 else if (strcmp(cp
, "local") == 0)
155 output_stored_text(local_file
, local_file_name
);
156 else if (strcmp(cp
, "tables") == 0)
157 output_rule_data(), output_yydefred(), output_actions();
158 else if (strcmp(cp
, "tokens") == 0)
159 output_defines(strtok(NULL
, "\r\n"));
161 fprintf(stderr
, "jay: unknown call (%s) in line %d\n", cp
, lno
);
165 fputs(buf
+1, output_file
), ++ outline
;
171 output_rule_data (void)
176 fprintf(output_file
, "/*\n All more than 3 lines long rules are wrapped into a method\n*/\n");
178 for (i
= 0; i
< nmethods
; ++i
)
180 fprintf(output_file
, "%s", methods
[i
]);
182 fprintf(output_file
, "\n\n");
186 fprintf(output_file
, default_line_format
, ++outline
+ 1);
188 fprintf(output_file
, " %s static %s short [] yyLhs = {%16d,",
189 csharp
? "" : " protected",
190 csharp
? "readonly" : "final",
191 symbol_value
[start_symbol
]);
194 for (i
= 3; i
< nrules
; i
++)
199 putc('\n', output_file
);
205 fprintf(output_file
, "%5d,", symbol_value
[rlhs
[i
]]);
208 fprintf(output_file
, "\n };\n");
210 fprintf(output_file
, " %s static %s short [] yyLen = {%12d,",
211 csharp
? "" : "protected",
212 csharp
? "readonly" : "final",
216 for (i
= 3; i
< nrules
; i
++)
221 putc('\n', output_file
);
227 fprintf(output_file
, "%5d,", rrhs
[i
+ 1] - rrhs
[i
] - 1);
230 fprintf(output_file
, "\n };\n");
234 output_yydefred (void)
238 fprintf(output_file
, " %s static %s short [] yyDefRed = {%13d,",
239 csharp
? "" : "protected",
240 csharp
? "readonly" : "final",
241 (defred
[0] ? defred
[0] - 2 : 0));
244 for (i
= 1; i
< nstates
; i
++)
251 putc('\n', output_file
);
255 fprintf(output_file
, "%5d,", (defred
[i
] ? defred
[i
] - 2 : 0));
259 fprintf(output_file
, "\n };\n");
263 output_actions (void)
265 nvectors
= 2*nstates
+ nvars
;
267 froms
= NEW2(nvectors
, short *);
268 tos
= NEW2(nvectors
, short *);
269 tally
= NEW2(nvectors
, short);
270 width
= NEW2(nvectors
, short);
276 FREE(accessing_symbol
);
279 FREE(goto_map
+ ntokens
);
294 register int shiftcount
, reducecount
;
295 register int max
, min
;
296 register short *actionrow
, *r
, *s
;
299 actionrow
= NEW2(2*ntokens
, short);
300 for (i
= 0; i
< nstates
; ++i
)
304 for (j
= 0; j
< 2*ntokens
; ++j
)
309 for (p
= parser
[i
]; p
; p
= p
->next
)
311 if (p
->suppressed
== 0)
313 if (p
->action_code
== SHIFT
)
316 actionrow
[p
->symbol
] = p
->number
;
318 else if (p
->action_code
== REDUCE
&& p
->number
!= defred
[i
])
321 actionrow
[p
->symbol
+ ntokens
] = p
->number
;
326 tally
[i
] = shiftcount
;
327 tally
[nstates
+i
] = reducecount
;
329 width
[nstates
+i
] = 0;
332 froms
[i
] = r
= NEW2(shiftcount
, short);
333 tos
[i
] = s
= NEW2(shiftcount
, short);
336 for (j
= 0; j
< ntokens
; ++j
)
340 if (min
> symbol_value
[j
])
341 min
= symbol_value
[j
];
342 if (max
< symbol_value
[j
])
343 max
= symbol_value
[j
];
344 *r
++ = symbol_value
[j
];
348 width
[i
] = max
- min
+ 1;
352 froms
[nstates
+i
] = r
= NEW2(reducecount
, short);
353 tos
[nstates
+i
] = s
= NEW2(reducecount
, short);
356 for (j
= 0; j
< ntokens
; ++j
)
358 if (actionrow
[ntokens
+j
])
360 if (min
> symbol_value
[j
])
361 min
= symbol_value
[j
];
362 if (max
< symbol_value
[j
])
363 max
= symbol_value
[j
];
364 *r
++ = symbol_value
[j
];
365 *s
++ = actionrow
[ntokens
+j
] - 2;
368 width
[nstates
+i
] = max
- min
+ 1;
378 register int i
, j
, k
;
380 state_count
= NEW2(nstates
, short);
382 k
= default_goto(start_symbol
+ 1);
383 fprintf(output_file
, " protected static %s short [] yyDgoto = {%14d,", csharp
? "readonly" : "final", k
);
384 save_column(start_symbol
+ 1, k
);
387 for (i
= start_symbol
+ 2; i
< nsyms
; i
++)
392 putc('\n', output_file
);
399 fprintf(output_file
, "%5d,", k
);
404 fprintf(output_file
, "\n };\n");
409 default_goto (int symbol
)
414 register int default_state
;
417 m
= goto_map
[symbol
];
418 n
= goto_map
[symbol
+ 1];
420 if (m
== n
) return (0);
422 for (i
= 0; i
< nstates
; i
++)
425 for (i
= m
; i
< n
; i
++)
426 state_count
[to_state
[i
]]++;
430 for (i
= 0; i
< nstates
; i
++)
432 if (state_count
[i
] > max
)
434 max
= state_count
[i
];
439 return (default_state
);
443 save_column (int symbol
, int default_state
)
454 m
= goto_map
[symbol
];
455 n
= goto_map
[symbol
+ 1];
458 for (i
= m
; i
< n
; i
++)
460 if (to_state
[i
] != default_state
)
463 if (count
== 0) return;
465 symno
= symbol_value
[symbol
] + 2*nstates
;
467 froms
[symno
] = sp1
= sp
= NEW2(count
, short);
468 tos
[symno
] = sp2
= NEW2(count
, short);
470 for (i
= m
; i
< n
; i
++)
472 if (to_state
[i
] != default_state
)
474 *sp1
++ = from_state
[i
];
475 *sp2
++ = to_state
[i
];
479 tally
[symno
] = count
;
480 width
[symno
] = sp1
[-1] - sp
[0] + 1;
492 order
= NEW2(nvectors
, short);
495 for (i
= 0; i
< nvectors
; i
++)
503 while (j
>= 0 && (width
[order
[j
]] < w
))
506 while (j
>= 0 && (width
[order
[j
]] == w
) && (tally
[order
[j
]] < t
))
509 for (k
= nentries
- 1; k
> j
; k
--)
510 order
[k
+ 1] = order
[k
];
525 base
= NEW2(nvectors
, short);
526 pos
= NEW2(nentries
, short);
529 table
= NEW2(maxtable
, short);
530 check
= NEW2(maxtable
, short);
535 for (i
= 0; i
< maxtable
; i
++)
538 for (i
= 0; i
< nentries
; i
++)
540 state
= matching_vector(i
);
543 place
= pack_vector(i
);
548 base
[order
[i
]] = place
;
551 for (i
= 0; i
< nvectors
; i
++)
565 /* The function matching_vector determines if the vector specified by */
566 /* the input parameter matches a previously considered vector. The */
567 /* test at the start of the function checks if the vector represents */
568 /* a row of shifts over terminal symbols or a row of reductions, or a */
569 /* column of shifts over a nonterminal symbol. Berkeley Yacc does not */
570 /* check if a column of shifts over a nonterminal symbols matches a */
571 /* previously considered vector. Because of the nature of LR parsing */
572 /* tables, no two columns can match. Therefore, the only possible */
573 /* match would be between a row and a column. Such matches are */
574 /* unlikely. Therefore, to save time, no attempt is made to see if a */
575 /* column matches a previously considered vector. */
577 /* Matching_vector is poorly designed. The test could easily be made */
578 /* faster. Also, it depends on the vectors being in a specific */
582 matching_vector (int vector
)
599 for (prev
= vector
- 1; prev
>= 0; prev
--)
602 if (width
[j
] != w
|| tally
[j
] != t
)
606 for (k
= 0; match
&& k
< t
; k
++)
608 if (tos
[j
][k
] != tos
[i
][k
] || froms
[j
][k
] != froms
[i
][k
])
620 pack_vector (int vector
)
622 register int i
, j
, k
, l
;
626 register short *from
;
637 j
= lowzero
- from
[0];
638 for (k
= 1; k
< t
; ++k
)
639 if (lowzero
- from
[k
] > j
)
640 j
= lowzero
- from
[k
];
646 for (k
= 0; ok
&& k
< t
; k
++)
652 fatal("maximum table size exceeded");
655 do { newmax
+= 200; } while (newmax
<= loc
);
656 table
= (short *) REALLOC(table
, newmax
*sizeof(short));
657 if (table
== 0) no_space();
658 check
= (short *) REALLOC(check
, newmax
*sizeof(short));
659 if (check
== 0) no_space();
660 for (l
= maxtable
; l
< newmax
; ++l
)
668 if (check
[loc
] != -1)
671 for (k
= 0; ok
&& k
< vector
; k
++)
678 for (k
= 0; k
< t
; k
++)
682 check
[loc
] = from
[k
];
683 if (loc
> high
) high
= loc
;
686 while (check
[lowzero
] != -1)
699 fprintf(output_file
, " protected static %s short [] yySindex = {%13d,", csharp
? "readonly":"final", base
[0]);
702 for (i
= 1; i
< nstates
; i
++)
707 putc('\n', output_file
);
713 fprintf(output_file
, "%5d,", base
[i
]);
717 fprintf(output_file
, "\n };\n protected static %s short [] yyRindex = {%13d,",
718 csharp
? "readonly" : "final",
722 for (i
= nstates
+ 1; i
< 2*nstates
; i
++)
727 putc('\n', output_file
);
733 fprintf(output_file
, "%5d,", base
[i
]);
737 fprintf(output_file
, "\n };\n protected static %s short [] yyGindex = {%13d,",
738 csharp
? "readonly" : "final",
742 for (i
= 2*nstates
+ 1; i
< nvectors
- 1; i
++)
747 putc('\n', output_file
);
753 fprintf(output_file
, "%5d,", base
[i
]);
757 fprintf(output_file
, "\n };\n");
767 fprintf(output_file
, " protected static %s short [] yyTable = {%14d,", csharp
? "readonly" : "final", table
[0]);
770 for (i
= 1; i
<= high
; i
++)
775 putc('\n', output_file
);
781 fprintf(output_file
, "%5d,", table
[i
]);
785 fprintf(output_file
, "\n };\n");
795 fprintf(output_file
, " protected static %s short [] yyCheck = {%14d,",
796 csharp
? "readonly" : "final",
800 for (i
= 1; i
<= high
; i
++)
805 putc('\n', output_file
);
811 fprintf(output_file
, "%5d,", check
[i
]);
815 fprintf(output_file
, "\n };\n");
820 is_C_identifier (const char *name
)
830 if (!isalpha(c
) && c
!= '_' && c
!= '$')
832 while ((c
= *++s
) != '"')
834 if (!isalnum(c
) && c
!= '_' && c
!= '$')
840 if (!isalpha(c
) && c
!= '_' && c
!= '$')
844 if (!isalnum(c
) && c
!= '_' && c
!= '$')
851 output_defines (const char *prefix
)
856 for (i
= 2; i
< ntokens
; ++i
)
859 if (is_C_identifier(s
))
862 fprintf(output_file
, " %s ", prefix
);
866 while ((c
= *++s
) != '"')
868 putc(c
, output_file
);
875 putc(c
, output_file
);
880 fprintf(output_file
, " = %d%s\n", symbol_value
[i
], csharp
? ";" : ";");
885 fprintf(output_file
, " %s yyErrorCode = %d%s\n", prefix
? prefix
: "", symbol_value
[1], csharp
? ";" : ";");
889 output_stored_text (FILE *file
, const char *name
)
895 in
= fopen(name
, "r");
898 if ((c
= getc(in
)) != EOF
) {
901 putc(c
, output_file
);
902 while ((c
= getc(in
)) != EOF
)
906 putc(c
, output_file
);
908 fprintf(output_file
, default_line_format
, ++outline
+ 1);
916 register int i
, j
, k
, max
;
918 const char * prefix
= tflag
? "" : "//t";
921 fprintf(output_file
, " protected %s int yyFinal = %d;\n", csharp
? "const" : "static final", final_state
);
924 fprintf(output_file
, "%s // Put this array into a separate class so it is only initialized if debugging is actually used\n", prefix
);
925 fprintf(output_file
, "%s // Use MarshalByRefObject to disable inlining\n", prefix
);
926 fprintf(output_file
, "%s class YYRules %s {\n", prefix
, csharp
? ": MarshalByRefObject" : "");
927 fprintf(output_file
, "%s public static %s string [] yyRule = {\n", prefix
, csharp
? "readonly" : "final");
928 for (i
= 2; i
< nrules
; ++i
)
930 fprintf(output_file
, "%s \"%s :", prefix
, symbol_name
[rlhs
[i
]]);
931 for (j
= rrhs
[i
]; ritem
[j
] > 0; ++j
)
933 s
= symbol_name
[ritem
[j
]];
936 fprintf(output_file
, " \\\"");
942 fprintf(output_file
, "\\\\\\\\");
944 fprintf(output_file
, "\\\\%c", s
[1]);
948 putc(*s
, output_file
);
950 fprintf(output_file
, "\\\"");
952 else if (s
[0] == '\'')
955 fprintf(output_file
, " '\\\"'");
956 else if (s
[1] == '\\')
959 fprintf(output_file
, " '\\\\\\\\");
961 fprintf(output_file
, " '\\\\%c", s
[2]);
964 putc(*s
, output_file
);
965 putc('\'', output_file
);
968 fprintf(output_file
, " '%c'", s
[1]);
971 fprintf(output_file
, " %s", s
);
974 fprintf(output_file
, "\",\n");
977 fprintf(output_file
, "%s };\n", prefix
);
978 fprintf(output_file
, "%s public static string getRule (int index) {\n", prefix
);
979 fprintf(output_file
, "%s return yyRule [index];\n", prefix
);
980 fprintf(output_file
, "%s }\n", prefix
);
981 fprintf(output_file
, "%s}\n", prefix
);
984 for (i
= 2; i
< ntokens
; ++i
)
985 if (symbol_value
[i
] > max
)
986 max
= symbol_value
[i
];
988 /* need yyNames for yyExpecting() */
990 fprintf(output_file
, " protected static %s string [] yyNames = {", csharp
? "readonly" : "final");
991 symnam
= (char **) MALLOC((max
+1)*sizeof(char *));
992 if (symnam
== 0) no_space();
994 /* Note that it is not necessary to initialize the element */
996 for (i
= 0; i
< max
; ++i
)
998 for (i
= ntokens
- 1; i
>= 2; --i
)
999 symnam
[symbol_value
[i
]] = symbol_name
[i
];
1000 symnam
[0] = (char*)"end-of-file";
1002 j
= 70; fputs(" ", output_file
);
1003 for (i
= 0; i
<= max
; ++i
)
1005 if ((s
= symnam
[i
]))
1024 fprintf(output_file
, "\n ");
1027 fprintf(output_file
, "\"\\\"");
1033 fprintf(output_file
, "\\\\");
1035 fprintf(output_file
, "\\\\");
1037 putc(*s
, output_file
);
1040 putc(*s
, output_file
);
1042 fprintf(output_file
, "\\\"\",");
1044 else if (s
[0] == '\'')
1052 fprintf(output_file
, "\n ");
1055 fprintf(output_file
, "\"'\\\"'\",");
1060 while (*++s
!= '\'')
1074 fprintf(output_file
, "\n ");
1077 fprintf(output_file
, "\"'");
1079 while (*++s
!= '\'')
1083 fprintf(output_file
, "\\\\");
1085 fprintf(output_file
, "\\\\");
1087 putc(*s
, output_file
);
1090 putc(*s
, output_file
);
1092 fprintf(output_file
, "'\",");
1102 fprintf(output_file
, "\n ");
1105 putc('"', output_file
);
1106 do { putc(*s
, output_file
); } while (*++s
);
1107 fprintf(output_file
, "\",");
1116 fprintf(output_file
, "\n ");
1119 fprintf(output_file
, "null,");
1123 fprintf(output_file
, "\n };\n");
1128 output_trailing_text (void)
1130 register int c
, last
;
1141 if ((c
= getc(in
)) == EOF
)
1144 fprintf(output_file
, line_format
, lineno
, input_file_name
);
1147 putc(c
, output_file
);
1153 fprintf(output_file
, line_format
, lineno
, input_file_name
);
1154 do { putc(c
, output_file
); } while ((c
= *++cptr
) != '\n');
1156 putc('\n', output_file
);
1160 while ((c
= getc(in
)) != EOF
)
1164 putc(c
, output_file
);
1171 putc('\n', output_file
);
1173 fprintf(output_file
, default_line_format
, ++outline
+ 1);
1177 output_semantic_actions (void)
1179 register int c
, last
;
1181 fclose(action_file
);
1182 action_file
= fopen(action_file_name
, "r");
1183 if (action_file
== NULL
)
1184 open_error(action_file_name
);
1186 if ((c
= getc(action_file
)) == EOF
)
1192 putc(c
, output_file
);
1193 while ((c
= getc(action_file
)) != EOF
)
1197 putc(c
, output_file
);
1204 putc('\n', output_file
);
1207 fprintf(output_file
, default_line_format
, ++outline
+ 1);
1211 free_itemsets (void)
1213 register core
*cp
, *next
;
1216 for (cp
= first_state
; cp
; cp
= next
)
1226 register shifts
*sp
, *next
;
1229 for (sp
= first_shift
; sp
; sp
= next
)
1237 free_reductions (void)
1239 register reductions
*rp
, *next
;
1241 FREE(reduction_table
);
1242 for (rp
= first_reduction
; rp
; rp
= next
)