]>
git.saurik.com Git - bison.git/blob - src/output.c
1 /* Output the generated parsing program for bison,
2 Copyright 1984, 1986, 1989, 1992, 2000, 2001 Free Software Foundation, Inc.
4 This file is part of Bison, the GNU Compiler Compiler.
6 Bison is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 Bison is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with Bison; see the file COPYING. If not, write to the Free
18 Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
22 /* The parser tables consist of these tables.
23 Starred ones needed only for the semantic parser.
24 Double starred are output only if switches are set.
26 yytranslate = vector mapping yylex's token numbers into bison's token
29 ** yytname = vector of string-names indexed by bison token number
31 ** yytoknum = vector of yylex token numbers corresponding to entries
34 yyrline = vector of line-numbers of all rules. For yydebug printouts.
36 yyrhs = vector of items of all rules.
37 This is exactly what ritems contains. For yydebug and for semantic
40 yyprhs[r] = index in yyrhs of first item for rule r.
42 yyr1[r] = symbol number of symbol that rule r derives.
44 yyr2[r] = number of symbols composing right hand side of rule r.
46 * yystos[s] = the symbol number of the symbol that leads to state s.
48 yydefact[s] = default rule to reduce with in state s,
49 when yytable doesn't specify something else to do.
50 Zero means the default is an error.
52 yydefgoto[i] = default state to go to after a reduction of a rule that
53 generates variable ntokens + i, except when yytable
54 specifies something else to do.
56 yypact[s] = index in yytable of the portion describing state s.
57 The lookahead token's type is used to index that portion
58 to find out what to do.
60 If the value in yytable is positive,
61 we shift the token and go to that state.
63 If the value is negative, it is minus a rule number to reduce by.
65 If the value is zero, the default action from yydefact[s] is used.
67 yypgoto[i] = the index in yytable of the portion describing
68 what to do after reducing a rule that derives variable i + ntokens.
69 This portion is indexed by the parser state number, s,
70 as of before the text for this nonterminal was read.
71 The value from yytable is the state to go to if
72 the corresponding value in yycheck is s.
74 yytable = a vector filled with portions for different uses,
75 found via yypact and yypgoto.
77 yycheck = a vector indexed in parallel with yytable.
78 It indicates, in a roundabout way, the bounds of the
79 portion you are trying to examine.
81 Suppose that the portion of yytable starts at index p
82 and the index to be examined within the portion is i.
83 Then if yycheck[p+i] != i, i is outside the bounds
84 of what is actually allocated, and the default
85 (from yydefact or yydefgoto) should be used.
86 Otherwise, yytable[p+i] should be used.
88 YYFINAL = the state number of the termination state.
89 YYFLAG = most negative short int. Used to flag ??
101 #include "complain.h"
105 #include "conflicts.h"
106 #include "macrotab.h"
108 extern void berror
PARAMS((const char *));
112 static short **froms
;
116 static short *actrow
;
117 static short *state_count
;
126 struct obstack macro_obstack
;
127 struct obstack output_obstack
;
132 output_table_data (struct obstack
* oout
,
141 obstack_fgrow1 (oout
, "%6d", first
);
142 for (i
= begin
; i
< end
; ++i
)
144 obstack_1grow (oout
, ',');
147 obstack_sgrow (oout
, "\n ");
152 obstack_fgrow1 (oout
, "%6d", table_data
[i
]);
154 obstack_1grow (oout
, 0);
159 output_token_translations (void)
161 output_table_data (&output_obstack
, token_translations
,
162 0, 1, max_user_token_number
+ 1);
163 macro_insert ("translate", obstack_finish (&output_obstack
));
170 output_table_data (&output_obstack
, rrhs
,
172 macro_insert ("prhs", obstack_finish (&output_obstack
));
175 size_t yyrhs_size
= 1;
179 for (sp
= ritem
+ 1; *sp
; sp
++)
181 yyrhs
= XMALLOC (short, yyrhs_size
);
183 for (sp
= ritem
+ 1, i
= 1; *sp
; ++sp
, ++i
)
184 yyrhs
[i
] = *sp
> 0 ? *sp
: 0;
186 output_table_data (&output_obstack
, yyrhs
,
187 ritem
[0], 1, yyrhs_size
);
188 macro_insert ("rhs", obstack_finish (&output_obstack
));
194 if (!semantic_parser
&& !no_parser_flag
)
195 obstack_sgrow (&table_obstack
, "\n#endif\n");
203 output_table_data (&output_obstack
, accessing_symbol
,
205 macro_insert ("stos", obstack_finish (&output_obstack
));
210 output_rule_data (void)
214 short *short_tab
= NULL
;
216 output_table_data (&output_obstack
, rline
,
218 macro_insert ("rline", obstack_finish (&output_obstack
));
221 for (i
= 0; i
< nsyms
; i
++)
222 /* this used to be i<=nsyms, but that output a final "" symbol
223 almost by accident */
225 /* Width of the next token, including the two quotes, the coma
230 for (p
= tags
[i
]; p
&& *p
; p
++)
231 if (*p
== '"' || *p
== '\\' || *p
== '\n' || *p
== '\t'
234 else if (*p
< 040 || *p
>= 0177)
239 if (j
+ strsize
> 75)
241 obstack_sgrow (&output_obstack
, "\n ");
245 obstack_1grow (&output_obstack
, '\"');
246 for (p
= tags
[i
]; p
&& *p
; p
++)
248 if (*p
== '"' || *p
== '\\')
249 obstack_fgrow1 (&output_obstack
, "\\%c", *p
);
251 obstack_sgrow (&output_obstack
, "\\n");
253 obstack_sgrow (&output_obstack
, "\\t");
255 obstack_sgrow (&output_obstack
, "\\b");
256 else if (*p
< 040 || *p
>= 0177)
257 obstack_fgrow1 (&output_obstack
, "\\%03o", *p
);
259 obstack_1grow (&output_obstack
, *p
);
262 obstack_sgrow (&output_obstack
, "\", ");
265 /* add a NULL entry to list of tokens */
266 obstack_sgrow (&output_obstack
, "NULL");
268 /* Finish table and store. */
269 obstack_1grow (&output_obstack
, 0);
270 macro_insert ("tname", obstack_finish (&output_obstack
));
272 /* Output YYTOKNUM. */
273 output_table_data (&output_obstack
, user_toknums
,
275 macro_insert ("toknum", obstack_finish (&output_obstack
));
278 output_table_data (&output_obstack
, rlhs
,
280 macro_insert ("r1", obstack_finish (&output_obstack
));
284 short_tab
= XMALLOC (short, nrules
+ 1);
285 for (i
= 1; i
< nrules
; i
++)
286 short_tab
[i
] = rrhs
[i
+ 1] - rrhs
[i
] - 1;
287 short_tab
[nrules
] = nitems
- rrhs
[nrules
] - 1;
288 output_table_data (&output_obstack
, short_tab
,
290 macro_insert ("r2", obstack_finish (&output_obstack
));
296 /*------------------------------------------------------------------.
297 | Decide what to do for each type of token if seen as the lookahead |
298 | token in specified state. The value returned is used as the |
299 | default action (yydefact) for the state. In addition, actrow is |
300 | filled with what to do for each kind of token, index by symbol |
301 | number, with zero meaning do the default action. The value |
302 | MINSHORT, a very negative number, means this situation is an |
303 | error. The parser recognizes this value specially. |
305 | This is where conflicts are resolved. The loop over lookahead |
306 | rules considered lower-numbered rules last, and the last rule |
307 | considered that likes a token gets to handle it. |
308 `------------------------------------------------------------------*/
311 action_row (int state
)
330 int nodefault
= 0; /* set nonzero to inhibit having any default reduction */
332 for (i
= 0; i
< ntokens
; i
++)
337 redp
= reduction_table
[state
];
345 /* loop over all the rules available here which require
347 m
= lookaheads
[state
];
348 n
= lookaheads
[state
+ 1];
350 for (i
= n
- 1; i
>= m
; i
--)
353 wordp
= LA
+ i
* tokensetsize
;
356 /* and find each token which the rule finds acceptable
358 for (j
= 0; j
< ntokens
; j
++)
360 /* and record this rule as the rule to use if that
376 shiftp
= shift_table
[state
];
378 /* Now see which tokens are allowed for shifts in this state. For
379 them, record the shift as the thing to do. So shift is preferred
386 for (i
= 0; i
< k
; i
++)
388 shift_state
= shiftp
->shifts
[i
];
392 symbol
= accessing_symbol
[shift_state
];
397 actrow
[symbol
] = shift_state
;
399 /* Do not use any default reduction if there is a shift for
401 if (symbol
== error_token_number
)
406 errp
= err_table
[state
];
408 /* See which tokens are an explicit error in this state (due to
409 %nonassoc). For them, record MINSHORT as the action. */
415 for (i
= 0; i
< k
; i
++)
417 symbol
= errp
->errs
[i
];
418 actrow
[symbol
] = MINSHORT
;
422 /* Now find the most common reduction and make it the default action
425 if (nreds
>= 1 && !nodefault
)
427 if (consistent
[state
])
428 default_rule
= redp
->rules
[0];
432 for (i
= m
; i
< n
; i
++)
437 for (j
= 0; j
< ntokens
; j
++)
439 if (actrow
[j
] == rule
)
450 /* actions which match the default are replaced with zero,
451 which means "use the default" */
455 for (j
= 0; j
< ntokens
; j
++)
457 if (actrow
[j
] == default_rule
)
461 default_rule
= -default_rule
;
466 /* If have no default rule, the default is an error.
467 So replace any action which says "error" with "use default". */
469 if (default_rule
== 0)
470 for (j
= 0; j
< ntokens
; j
++)
472 if (actrow
[j
] == MINSHORT
)
490 for (i
= 0; i
< ntokens
; i
++)
499 froms
[state
] = sp1
= sp
= XCALLOC (short, count
);
500 tos
[state
] = sp2
= XCALLOC (short, count
);
502 for (i
= 0; i
< ntokens
; i
++)
511 tally
[state
] = count
;
512 width
[state
] = sp1
[-1] - sp
[0] + 1;
516 /*------------------------------------------------------------------.
517 | Figure out the actions for the specified state, indexed by |
518 | lookahead token type. |
520 | The YYDEFACT table is output now. The detailed info is saved for |
521 | putting into YYTABLE later. |
522 `------------------------------------------------------------------*/
528 short *yydefact
= XCALLOC (short, nstates
);
530 actrow
= XCALLOC (short, ntokens
);
531 for (i
= 0; i
< nstates
; ++i
)
533 yydefact
[i
] = action_row (i
);
537 output_table_data (&output_obstack
, yydefact
,
538 yydefact
[0], 1, nstates
);
539 macro_insert ("defact", obstack_finish (&output_obstack
));
549 shifts
*sp
, *sptmp
; /* JF derefrenced freed ptr */
553 for (sp
= first_shift
; sp
; sp
= sptmp
)
562 free_reductions (void)
564 reductions
*rp
, *rptmp
; /* JF fixed freed ptr */
566 XFREE (reduction_table
);
568 for (rp
= first_reduction
; rp
; rp
= rptmp
)
578 save_column (int symbol
, int default_state
)
587 short begin
= goto_map
[symbol
];
588 short end
= goto_map
[symbol
+ 1];
591 for (i
= begin
; i
< end
; i
++)
593 if (to_state
[i
] != default_state
)
600 symno
= symbol
- ntokens
+ nstates
;
602 froms
[symno
] = sp1
= sp
= XCALLOC (short, count
);
603 tos
[symno
] = sp2
= XCALLOC (short, count
);
605 for (i
= begin
; i
< end
; i
++)
607 if (to_state
[i
] != default_state
)
609 *sp1
++ = from_state
[i
];
610 *sp2
++ = to_state
[i
];
614 tally
[symno
] = count
;
615 width
[symno
] = sp1
[-1] - sp
[0] + 1;
619 default_goto (int symbol
)
627 m
= goto_map
[symbol
];
628 n
= goto_map
[symbol
+ 1];
633 for (i
= 0; i
< nstates
; i
++)
636 for (i
= m
; i
< n
; i
++)
637 state_count
[to_state
[i
]]++;
642 for (i
= 0; i
< nstates
; i
++)
644 if (state_count
[i
] > max
)
646 max
= state_count
[i
];
651 return default_state
;
655 /*-------------------------------------------------------------------.
656 | Figure out what to do after reducing with each rule, depending on |
657 | the saved state from before the beginning of parsing the data that |
658 | matched this rule. |
660 | The YYDEFGOTO table is output now. The detailed info is saved for |
661 | putting into YYTABLE later. |
662 `-------------------------------------------------------------------*/
668 short *yydefgoto
= XMALLOC (short, nsyms
- ntokens
);
670 state_count
= XCALLOC (short, nstates
);
671 for (i
= ntokens
; i
< nsyms
; ++i
)
673 int default_state
= default_goto (i
);
674 save_column (i
, default_state
);
675 yydefgoto
[i
- ntokens
] = default_state
;
678 output_table_data (&output_obstack
, yydefgoto
,
679 yydefgoto
[0], 1, nsyms
- ntokens
);
680 macro_insert ("defgoto", obstack_finish (&output_obstack
));
687 /* The next few functions decide how to pack the actions and gotos
688 information into yytable. */
699 order
= XCALLOC (short, nvectors
);
702 for (i
= 0; i
< nvectors
; i
++)
710 while (j
>= 0 && (width
[order
[j
]] < w
))
713 while (j
>= 0 && (width
[order
[j
]] == w
) && (tally
[order
[j
]] < t
))
716 for (k
= nentries
- 1; k
> j
; k
--)
717 order
[k
+ 1] = order
[k
];
727 matching_state (int vector
)
744 for (prev
= vector
- 1; prev
>= 0; prev
--)
747 if (width
[j
] != w
|| tally
[j
] != t
)
751 for (k
= 0; match
&& k
< t
; k
++)
753 if (tos
[j
][k
] != tos
[i
][k
] || froms
[j
][k
] != froms
[i
][k
])
766 pack_vector (int vector
)
785 for (j
= lowzero
- from
[0]; j
< MAXTABLE
; j
++)
789 for (k
= 0; ok
&& k
< t
; k
++)
793 fatal (_("maximum table size (%d) exceeded"), MAXTABLE
);
799 for (k
= 0; ok
&& k
< vector
; k
++)
807 for (k
= 0; k
< t
; k
++)
811 check
[loc
] = from
[k
];
814 while (table
[lowzero
] != 0)
824 berror ("pack_vector");
825 return 0; /* JF keep lint happy */
836 base
= XCALLOC (short, nvectors
);
837 pos
= XCALLOC (short, nentries
);
838 table
= XCALLOC (short, MAXTABLE
);
839 check
= XCALLOC (short, MAXTABLE
);
844 for (i
= 0; i
< nvectors
; i
++)
847 for (i
= 0; i
< MAXTABLE
; i
++)
850 for (i
= 0; i
< nentries
; i
++)
852 state
= matching_state (i
);
855 place
= pack_vector (i
);
860 base
[order
[i
]] = place
;
863 for (i
= 0; i
< nvectors
; i
++)
876 /* the following functions output yytable, yycheck
877 and the vectors whose elements index the portion starts */
883 output_table_data (&output_obstack
, base
,
884 base
[0], 1, nstates
);
885 macro_insert ("pact", obstack_finish (&output_obstack
));
888 output_table_data (&output_obstack
, base
,
889 base
[nstates
], nstates
+ 1, nvectors
);
890 macro_insert ("pgoto", obstack_finish (&output_obstack
));
899 output_table_data (&output_obstack
, table
,
900 table
[0], 1, high
+ 1);
901 macro_insert ("table", obstack_finish (&output_obstack
));
909 output_table_data (&output_obstack
, check
,
910 check
[0], 1, high
+ 1);
911 macro_insert ("check", obstack_finish (&output_obstack
));
915 /* compute and output yydefact, yydefgoto, yypact, yypgoto, yytable
919 output_actions (void)
921 nvectors
= nstates
+ nvars
;
923 froms
= XCALLOC (short *, nvectors
);
924 tos
= XCALLOC (short *, nvectors
);
925 tally
= XCALLOC (short, nvectors
);
926 width
= XCALLOC (short, nvectors
);
934 XFREE (accessing_symbol
);
937 XFREE (goto_map
+ ntokens
);
950 /*------------------------------------------.
951 | Copy the parser code into TABLE_OBSTACK. |
952 `------------------------------------------*/
960 int actions_dumped
= 0;
962 /* Loop over lines in the standard parser file. */
966 skeleton
= skeleton_find ("BISON_HAIRY", BISON_HAIRY
);
968 skeleton
= skeleton_find ("BISON_SIMPLE", BISON_SIMPLE
);
970 fskel
= xfopen (skeleton
, "r");
972 /* New output code. */
981 obstack_1grow (&table_obstack
, c
);
984 else if ((c
= getc (fskel
)) == '%')
986 /* Read the macro. */
987 const char* macro_key
= 0;
988 const char* macro_value
= 0;
989 while (isalnum (c
= getc (fskel
)) || c
== '_')
990 obstack_1grow (¯o_obstack
, c
);
991 obstack_1grow (¯o_obstack
, 0);
993 /* Output the right value, or see if it's something special. */
994 macro_key
= obstack_finish (¯o_obstack
);
995 macro_value
= macro_find (macro_key
);
997 obstack_sgrow (&table_obstack
, macro_value
);
998 else if (!strcmp (macro_key
, "line"))
999 obstack_fgrow1 (&table_obstack
, "%d", line
+ 1);
1000 else if (!strcmp (macro_key
, "action"))
1002 size_t size
= obstack_object_size (&action_obstack
);
1003 obstack_grow (&table_obstack
,
1004 obstack_finish (&action_obstack
), size
);
1008 obstack_sgrow (&table_obstack
, "%%");
1009 obstack_sgrow (&table_obstack
, macro_key
);
1013 obstack_1grow (&table_obstack
, '%');
1021 free_itemsets (void)
1025 XFREE (state_table
);
1027 for (cp
= first_state
; cp
; cp
= cptmp
)
1036 #define MACRO_INSERT_INT(Key, Value) \
1038 obstack_fgrow1 (¯o_obstack, "%d", Value); \
1039 obstack_1grow (¯o_obstack, 0); \
1040 macro_insert (Key, obstack_finish (¯o_obstack)); \
1043 #define MACRO_INSERT_STRING(Key, Value) \
1045 obstack_sgrow (¯o_obstack, Value); \
1046 obstack_1grow (¯o_obstack, 0); \
1047 macro_insert (Key, obstack_finish (¯o_obstack)); \
1050 #define MACRO_INSERT_PREFIX(Key, Value) \
1052 obstack_fgrow2 (¯o_obstack, "%s%s", spec_name_prefix, Value); \
1053 obstack_1grow (¯o_obstack, 0); \
1054 macro_insert (Key, obstack_finish (¯o_obstack)); \
1060 MACRO_INSERT_INT ("last", high
);
1061 MACRO_INSERT_INT ("flag", MINSHORT
);
1062 MACRO_INSERT_INT ("pure", pure_parser
);
1063 MACRO_INSERT_INT ("nsym", nsyms
);
1064 MACRO_INSERT_INT ("debug", debug_flag
);
1065 MACRO_INSERT_INT ("final", final_state
);
1066 MACRO_INSERT_INT ("maxtok", max_user_token_number
);
1067 MACRO_INSERT_INT ("ntbase", ntokens
);
1068 MACRO_INSERT_INT ("verbose", 0);
1070 MACRO_INSERT_STRING ("filename", infile
);
1072 MACRO_INSERT_INT ("nnts", nvars
);
1073 MACRO_INSERT_INT ("nrules", nrules
);
1074 MACRO_INSERT_INT ("nstates", nstates
);
1075 MACRO_INSERT_INT ("ntokens", ntokens
);
1077 if (spec_name_prefix
)
1079 MACRO_INSERT_PREFIX ("yylex", "lex");
1080 MACRO_INSERT_PREFIX ("yychar", "char");
1081 MACRO_INSERT_PREFIX ("yylval", "lval");
1082 MACRO_INSERT_PREFIX ("yydebug", "debug");
1083 MACRO_INSERT_PREFIX ("yyerror", "error");
1084 MACRO_INSERT_PREFIX ("yynerrs", "nerrs");
1085 MACRO_INSERT_PREFIX ("yyparse", "parse");
1089 /*----------------------------------------------------------.
1090 | Output the parsing tables and the parser code to ftable. |
1091 `----------------------------------------------------------*/
1096 obstack_init (&output_obstack
);
1099 reader_output_yylsp (&table_obstack
); */
1103 output_token_translations ();
1107 if (semantic_parser
)
1109 output_rule_data ();
1113 if (!no_parser_flag
) */
1116 /* Copy definitions in directive. */
1117 macro_insert ("prologue", obstack_finish (&attrs_obstack
));
1120 obstack_free (¯o_obstack
, 0);
1121 obstack_free (&output_obstack
, 0);