]>
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 ??
100 #include "complain.h"
104 #include "conflicts.h"
105 #include "muscle_tab.h"
107 extern void berror
PARAMS((const char *));
111 static short **froms
= NULL
;
112 static short **tos
= NULL
;
113 static short *tally
= NULL
;
114 static short *width
= NULL
;
115 static short *actrow
= NULL
;
116 static short *state_count
= NULL
;
117 static short *order
= NULL
;
118 static short *base
= NULL
;
119 static short *pos
= NULL
;
120 static short *table
= NULL
;
121 static short *check
= NULL
;
125 struct obstack muscle_obstack
;
126 struct obstack output_obstack
;
131 output_table_data (struct obstack
*oout
,
140 obstack_fgrow1 (oout
, "%6d", first
);
141 for (i
= begin
; i
< end
; ++i
)
143 obstack_1grow (oout
, ',');
146 obstack_sgrow (oout
, "\n ");
151 obstack_fgrow1 (oout
, "%6d", table_data
[i
]);
153 obstack_1grow (oout
, 0);
158 output_token_translations (void)
160 output_table_data (&output_obstack
, token_translations
,
161 0, 1, max_user_token_number
+ 1);
162 muscle_insert ("translate", obstack_finish (&output_obstack
));
163 XFREE (token_translations
);
172 short *values
= XCALLOC (short, nrules
+ 1);
173 for (i
= 0; i
< nrules
+ 1; ++i
)
174 values
[i
] = rule_table
[i
].rhs
;
175 output_table_data (&output_obstack
, values
,
180 muscle_insert ("prhs", obstack_finish (&output_obstack
));
183 size_t yyrhs_size
= 1;
187 for (sp
= ritem
+ 1; *sp
; sp
++)
189 yyrhs
= XMALLOC (short, yyrhs_size
);
191 for (sp
= ritem
+ 1, i
= 1; *sp
; ++sp
, ++i
)
192 yyrhs
[i
] = *sp
> 0 ? *sp
: 0;
194 output_table_data (&output_obstack
, yyrhs
,
195 ritem
[0], 1, yyrhs_size
);
196 muscle_insert ("rhs", obstack_finish (&output_obstack
));
202 if (!semantic_parser
&& !no_parser_flag
)
203 obstack_sgrow (&table_obstack
, "\n#endif\n");
212 short *values
= (short *) alloca (sizeof (short) * nstates
);
213 for (i
= 0; i
< nstates
; ++i
)
214 values
[i
] = state_table
[i
].accessing_symbol
;
215 output_table_data (&output_obstack
, values
,
217 muscle_insert ("stos", obstack_finish (&output_obstack
));
222 output_rule_data (void)
226 short *short_tab
= NULL
;
229 short *values
= XCALLOC (short, nrules
+ 1);
230 for (i
= 0; i
< nrules
+ 1; ++i
)
231 values
[i
] = rule_table
[i
].line
;
232 output_table_data (&output_obstack
, values
,
234 muscle_insert ("rline", obstack_finish (&output_obstack
));
240 for (i
= 0; i
< nsyms
; i
++)
241 /* this used to be i<=nsyms, but that output a final "" symbol
242 almost by accident */
244 /* Width of the next token, including the two quotes, the coma
249 for (p
= tags
[i
]; p
&& *p
; p
++)
250 if (*p
== '"' || *p
== '\\' || *p
== '\n' || *p
== '\t'
253 else if (*p
< 040 || *p
>= 0177)
258 if (j
+ strsize
> 75)
260 obstack_sgrow (&output_obstack
, "\n ");
264 obstack_1grow (&output_obstack
, '\"');
265 for (p
= tags
[i
]; p
&& *p
; p
++)
267 if (*p
== '"' || *p
== '\\')
268 obstack_fgrow1 (&output_obstack
, "\\%c", *p
);
270 obstack_sgrow (&output_obstack
, "\\n");
272 obstack_sgrow (&output_obstack
, "\\t");
274 obstack_sgrow (&output_obstack
, "\\b");
275 else if (*p
< 040 || *p
>= 0177)
276 obstack_fgrow1 (&output_obstack
, "\\%03o", *p
);
278 obstack_1grow (&output_obstack
, *p
);
281 obstack_sgrow (&output_obstack
, "\", ");
284 /* add a NULL entry to list of tokens */
285 obstack_sgrow (&output_obstack
, "NULL");
287 /* Finish table and store. */
288 obstack_1grow (&output_obstack
, 0);
289 muscle_insert ("tname", obstack_finish (&output_obstack
));
291 /* Output YYTOKNUM. */
292 output_table_data (&output_obstack
, user_toknums
,
294 muscle_insert ("toknum", obstack_finish (&output_obstack
));
298 short *values
= XCALLOC (short, nrules
+ 1);
299 for (i
= 0; i
< nrules
+ 1; ++i
)
300 values
[i
] = rule_table
[i
].lhs
;
301 output_table_data (&output_obstack
, values
,
303 muscle_insert ("r1", obstack_finish (&output_obstack
));
308 short_tab
= XMALLOC (short, nrules
+ 1);
309 for (i
= 1; i
< nrules
; i
++)
310 short_tab
[i
] = rule_table
[i
+ 1].rhs
- rule_table
[i
].rhs
- 1;
311 short_tab
[nrules
] = nitems
- rule_table
[nrules
].rhs
- 1;
312 output_table_data (&output_obstack
, short_tab
,
314 muscle_insert ("r2", obstack_finish (&output_obstack
));
317 XFREE (rule_table
+ 1);
320 /*------------------------------------------------------------------.
321 | Decide what to do for each type of token if seen as the lookahead |
322 | token in specified state. The value returned is used as the |
323 | default action (yydefact) for the state. In addition, actrow is |
324 | filled with what to do for each kind of token, index by symbol |
325 | number, with zero meaning do the default action. The value |
326 | MINSHORT, a very negative number, means this situation is an |
327 | error. The parser recognizes this value specially. |
329 | This is where conflicts are resolved. The loop over lookahead |
330 | rules considered lower-numbered rules last, and the last rule |
331 | considered that likes a token gets to handle it. |
332 `------------------------------------------------------------------*/
335 action_row (int state
)
354 int nodefault
= 0; /* set nonzero to inhibit having any default reduction */
356 for (i
= 0; i
< ntokens
; i
++)
361 redp
= state_table
[state
].reduction_table
;
369 /* loop over all the rules available here which require
371 m
= state_table
[state
].lookaheads
;
372 n
= state_table
[state
+ 1].lookaheads
;
374 for (i
= n
- 1; i
>= m
; i
--)
380 /* and find each token which the rule finds acceptable
382 for (j
= 0; j
< ntokens
; j
++)
384 /* and record this rule as the rule to use if that
400 shiftp
= state_table
[state
].shift_table
;
402 /* Now see which tokens are allowed for shifts in this state. For
403 them, record the shift as the thing to do. So shift is preferred
410 for (i
= 0; i
< k
; i
++)
412 shift_state
= shiftp
->shifts
[i
];
416 symbol
= state_table
[shift_state
].accessing_symbol
;
421 actrow
[symbol
] = shift_state
;
423 /* Do not use any default reduction if there is a shift for
425 if (symbol
== error_token_number
)
430 errp
= err_table
[state
];
432 /* See which tokens are an explicit error in this state (due to
433 %nonassoc). For them, record MINSHORT as the action. */
439 for (i
= 0; i
< k
; i
++)
441 symbol
= errp
->errs
[i
];
442 actrow
[symbol
] = MINSHORT
;
446 /* Now find the most common reduction and make it the default action
449 if (nreds
>= 1 && !nodefault
)
451 if (state_table
[state
].consistent
)
452 default_rule
= redp
->rules
[0];
456 for (i
= m
; i
< n
; i
++)
461 for (j
= 0; j
< ntokens
; j
++)
463 if (actrow
[j
] == rule
)
474 /* actions which match the default are replaced with zero,
475 which means "use the default" */
479 for (j
= 0; j
< ntokens
; j
++)
481 if (actrow
[j
] == default_rule
)
485 default_rule
= -default_rule
;
490 /* If have no default rule, the default is an error.
491 So replace any action which says "error" with "use default". */
493 if (default_rule
== 0)
494 for (j
= 0; j
< ntokens
; j
++)
496 if (actrow
[j
] == MINSHORT
)
514 for (i
= 0; i
< ntokens
; i
++)
523 froms
[state
] = sp1
= sp
= XCALLOC (short, count
);
524 tos
[state
] = sp2
= XCALLOC (short, count
);
526 for (i
= 0; i
< ntokens
; i
++)
535 tally
[state
] = count
;
536 width
[state
] = sp1
[-1] - sp
[0] + 1;
540 /*------------------------------------------------------------------.
541 | Figure out the actions for the specified state, indexed by |
542 | lookahead token type. |
544 | The YYDEFACT table is output now. The detailed info is saved for |
545 | putting into YYTABLE later. |
546 `------------------------------------------------------------------*/
552 short *yydefact
= XCALLOC (short, nstates
);
554 actrow
= XCALLOC (short, ntokens
);
555 for (i
= 0; i
< nstates
; ++i
)
557 yydefact
[i
] = action_row (i
);
561 output_table_data (&output_obstack
, yydefact
,
562 yydefact
[0], 1, nstates
);
563 muscle_insert ("defact", obstack_finish (&output_obstack
));
571 save_column (int symbol
, int default_state
)
580 short begin
= goto_map
[symbol
];
581 short end
= goto_map
[symbol
+ 1];
584 for (i
= begin
; i
< end
; i
++)
586 if (to_state
[i
] != default_state
)
593 symno
= symbol
- ntokens
+ nstates
;
595 froms
[symno
] = sp1
= sp
= XCALLOC (short, count
);
596 tos
[symno
] = sp2
= XCALLOC (short, count
);
598 for (i
= begin
; i
< end
; i
++)
600 if (to_state
[i
] != default_state
)
602 *sp1
++ = from_state
[i
];
603 *sp2
++ = to_state
[i
];
607 tally
[symno
] = count
;
608 width
[symno
] = sp1
[-1] - sp
[0] + 1;
612 default_goto (int symbol
)
620 m
= goto_map
[symbol
];
621 n
= goto_map
[symbol
+ 1];
626 for (i
= 0; i
< nstates
; i
++)
629 for (i
= m
; i
< n
; i
++)
630 state_count
[to_state
[i
]]++;
635 for (i
= 0; i
< nstates
; i
++)
637 if (state_count
[i
] > max
)
639 max
= state_count
[i
];
644 return default_state
;
648 /*-------------------------------------------------------------------.
649 | Figure out what to do after reducing with each rule, depending on |
650 | the saved state from before the beginning of parsing the data that |
651 | matched this rule. |
653 | The YYDEFGOTO table is output now. The detailed info is saved for |
654 | putting into YYTABLE later. |
655 `-------------------------------------------------------------------*/
661 short *yydefgoto
= XMALLOC (short, nsyms
- ntokens
);
663 state_count
= XCALLOC (short, nstates
);
664 for (i
= ntokens
; i
< nsyms
; ++i
)
666 int default_state
= default_goto (i
);
667 save_column (i
, default_state
);
668 yydefgoto
[i
- ntokens
] = default_state
;
671 output_table_data (&output_obstack
, yydefgoto
,
672 yydefgoto
[0], 1, nsyms
- ntokens
);
673 muscle_insert ("defgoto", obstack_finish (&output_obstack
));
680 /* The next few functions decide how to pack the actions and gotos
681 information into yytable. */
692 order
= XCALLOC (short, nvectors
);
695 for (i
= 0; i
< nvectors
; i
++)
703 while (j
>= 0 && (width
[order
[j
]] < w
))
706 while (j
>= 0 && (width
[order
[j
]] == w
) && (tally
[order
[j
]] < t
))
709 for (k
= nentries
- 1; k
> j
; k
--)
710 order
[k
+ 1] = order
[k
];
720 matching_state (int vector
)
737 for (prev
= vector
- 1; prev
>= 0; prev
--)
740 if (width
[j
] != w
|| tally
[j
] != t
)
744 for (k
= 0; match
&& k
< t
; k
++)
746 if (tos
[j
][k
] != tos
[i
][k
] || froms
[j
][k
] != froms
[i
][k
])
759 pack_vector (int vector
)
778 for (j
= lowzero
- from
[0]; j
< MAXTABLE
; j
++)
782 for (k
= 0; ok
&& k
< t
; k
++)
786 fatal (_("maximum table size (%d) exceeded"), MAXTABLE
);
792 for (k
= 0; ok
&& k
< vector
; k
++)
800 for (k
= 0; k
< t
; k
++)
804 check
[loc
] = from
[k
];
807 while (table
[lowzero
] != 0)
817 berror ("pack_vector");
818 return 0; /* JF keep lint happy */
829 base
= XCALLOC (short, nvectors
);
830 pos
= XCALLOC (short, nentries
);
831 table
= XCALLOC (short, MAXTABLE
);
832 check
= XCALLOC (short, MAXTABLE
);
837 for (i
= 0; i
< nvectors
; i
++)
840 for (i
= 0; i
< MAXTABLE
; i
++)
843 for (i
= 0; i
< nentries
; i
++)
845 state
= matching_state (i
);
848 place
= pack_vector (i
);
853 base
[order
[i
]] = place
;
856 for (i
= 0; i
< nvectors
; i
++)
869 /* the following functions output yytable, yycheck
870 and the vectors whose elements index the portion starts */
876 output_table_data (&output_obstack
, base
,
877 base
[0], 1, nstates
);
878 muscle_insert ("pact", obstack_finish (&output_obstack
));
881 output_table_data (&output_obstack
, base
,
882 base
[nstates
], nstates
+ 1, nvectors
);
883 muscle_insert ("pgoto", obstack_finish (&output_obstack
));
892 output_table_data (&output_obstack
, table
,
893 table
[0], 1, high
+ 1);
894 muscle_insert ("table", obstack_finish (&output_obstack
));
902 output_table_data (&output_obstack
, check
,
903 check
[0], 1, high
+ 1);
904 muscle_insert ("check", obstack_finish (&output_obstack
));
908 /* compute and output yydefact, yydefgoto, yypact, yypgoto, yytable
912 output_actions (void)
914 nvectors
= nstates
+ nvars
;
916 froms
= XCALLOC (short *, nvectors
);
917 tos
= XCALLOC (short *, nvectors
);
918 tally
= XCALLOC (short, nvectors
);
919 width
= XCALLOC (short, nvectors
);
922 LIST_FREE (shifts
, first_shift
);
923 LIST_FREE (reductions
, first_reduction
);
928 XFREE (goto_map
+ ntokens
);
943 /*------------------------------------------------------------.
944 | Copy the parser code from SKEL_FILENAME into OOUT obstack. |
945 | and do the muscle substitution. |
946 `------------------------------------------------------------*/
949 output_parser (const char *skel_filename
, struct obstack
*oout
)
955 fskel
= xfopen (skel_filename
, "r");
957 /* New output code. */
966 obstack_1grow (oout
, c
);
969 else if ((c
= getc (fskel
)) == '%')
971 /* Read the muscle. */
972 const char *muscle_key
= 0;
973 const char *muscle_value
= 0;
975 while (isalnum (c
= getc (fskel
)) || c
== '_')
976 obstack_1grow (&muscle_obstack
, c
);
977 obstack_1grow (&muscle_obstack
, 0);
979 /* Output the right value, or see if it's something special. */
980 muscle_key
= obstack_finish (&muscle_obstack
);
981 muscle_value
= muscle_find (muscle_key
);
983 obstack_sgrow (oout
, muscle_value
);
984 else if (!strcmp (muscle_key
, "line"))
985 obstack_fgrow1 (oout
, "%d", line
+ 1);
986 else if (!strcmp (muscle_key
, "input_line"))
987 obstack_fgrow1 (oout
, "%d", lineno
);
990 obstack_sgrow (oout
, "%%");
991 obstack_sgrow (oout
, muscle_key
);
995 obstack_1grow (oout
, '%');
1002 /*----------------------------------------.
1003 | Prepare the master parser to be output |
1004 `----------------------------------------*/
1007 output_master_parser (void)
1011 if (semantic_parser
)
1012 skeleton
= skeleton_find ("BISON_HAIRY", BISON_HAIRY
);
1014 skeleton
= skeleton_find ("BISON_SIMPLE", BISON_SIMPLE
);
1016 muscle_insert ("skeleton", skeleton
);
1017 output_parser (skeleton
, &table_obstack
);
1023 #define MUSCLE_INSERT_INT(Key, Value) \
1025 obstack_fgrow1 (&muscle_obstack, "%d", Value); \
1026 obstack_1grow (&muscle_obstack, 0); \
1027 muscle_insert (Key, obstack_finish (&muscle_obstack)); \
1030 #define MUSCLE_INSERT_STRING(Key, Value) \
1032 obstack_sgrow (&muscle_obstack, Value); \
1033 obstack_1grow (&muscle_obstack, 0); \
1034 muscle_insert (Key, obstack_finish (&muscle_obstack)); \
1037 #define MUSCLE_INSERT_PREFIX(Key, Value) \
1039 obstack_fgrow2 (&muscle_obstack, "%s%s", spec_name_prefix, Value); \
1040 obstack_1grow (&muscle_obstack, 0); \
1041 muscle_insert (Key, obstack_finish (&muscle_obstack)); \
1047 MUSCLE_INSERT_INT ("last", high
);
1048 MUSCLE_INSERT_INT ("flag", MINSHORT
);
1049 MUSCLE_INSERT_INT ("pure", pure_parser
);
1050 MUSCLE_INSERT_INT ("nsym", nsyms
);
1051 MUSCLE_INSERT_INT ("debug", debug_flag
);
1052 MUSCLE_INSERT_INT ("final", final_state
);
1053 MUSCLE_INSERT_INT ("maxtok", max_user_token_number
);
1054 MUSCLE_INSERT_INT ("ntbase", ntokens
);
1055 MUSCLE_INSERT_INT ("error_verbose", error_verbose_flag
);
1057 MUSCLE_INSERT_INT ("nnts", nvars
);
1058 MUSCLE_INSERT_INT ("nrules", nrules
);
1059 MUSCLE_INSERT_INT ("nstates", nstates
);
1060 MUSCLE_INSERT_INT ("ntokens", ntokens
);
1062 MUSCLE_INSERT_INT ("locations_flag", locations_flag
);
1064 /* We need to save the actions in the muscle %%action. */
1065 muscle_insert ("action", obstack_finish (&action_obstack
));
1067 if (spec_name_prefix
)
1068 MUSCLE_INSERT_STRING ("prefix", spec_name_prefix
);
1071 /*----------------------------------------------------------.
1072 | Output the parsing tables and the parser code to ftable. |
1073 `----------------------------------------------------------*/
1078 obstack_init (&output_obstack
);
1080 LIST_FREE (core
, first_state
);
1082 output_token_translations ();
1086 if (semantic_parser
)
1088 output_rule_data ();
1089 XFREE (user_toknums
);
1093 if (!no_parser_flag
) */
1096 /* Copy definitions in directive. */
1097 muscle_insert ("prologue", obstack_finish (&attrs_obstack
));
1099 output_master_parser ();
1101 obstack_free (&muscle_obstack
, 0);
1102 obstack_free (&output_obstack
, 0);
1103 obstack_free (&action_obstack
, 0);