]>
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"
110 static short **froms
= NULL
;
111 static short **tos
= NULL
;
112 static short *tally
= NULL
;
113 static short *width
= NULL
;
114 static short *actrow
= NULL
;
115 static short *state_count
= NULL
;
116 static short *order
= NULL
;
117 static short *base
= NULL
;
118 static short *pos
= NULL
;
119 static short *table
= NULL
;
120 static short *check
= NULL
;
124 struct obstack muscle_obstack
;
125 struct obstack output_obstack
;
127 int error_verbose
= 0;
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 muscle_insert ("translate", obstack_finish (&output_obstack
));
164 XFREE (token_translations
);
173 short *values
= XCALLOC (short, nrules
+ 1);
174 for (i
= 0; i
< nrules
+ 1; ++i
)
175 values
[i
] = rule_table
[i
].rhs
;
176 output_table_data (&output_obstack
, values
,
181 muscle_insert ("prhs", obstack_finish (&output_obstack
));
184 size_t yyrhs_size
= 1;
188 for (sp
= ritem
+ 1; *sp
; sp
++)
190 yyrhs
= XMALLOC (short, yyrhs_size
);
192 for (sp
= ritem
+ 1, i
= 1; *sp
; ++sp
, ++i
)
193 yyrhs
[i
] = *sp
> 0 ? *sp
: 0;
195 output_table_data (&output_obstack
, yyrhs
,
196 ritem
[0], 1, yyrhs_size
);
197 muscle_insert ("rhs", obstack_finish (&output_obstack
));
203 if (!semantic_parser
&& !no_parser_flag
)
204 obstack_sgrow (&table_obstack
, "\n#endif\n");
213 short *values
= (short *) alloca (sizeof (short) * nstates
);
214 for (i
= 0; i
< nstates
; ++i
)
215 values
[i
] = state_table
[i
]->accessing_symbol
;
216 output_table_data (&output_obstack
, values
,
218 muscle_insert ("stos", obstack_finish (&output_obstack
));
223 output_rule_data (void)
227 short *short_tab
= NULL
;
230 short *values
= XCALLOC (short, nrules
+ 1);
231 for (i
= 0; i
< nrules
+ 1; ++i
)
232 values
[i
] = rule_table
[i
].line
;
233 output_table_data (&output_obstack
, values
,
235 muscle_insert ("rline", obstack_finish (&output_obstack
));
241 for (i
= 0; i
< nsyms
; i
++)
242 /* this used to be i<=nsyms, but that output a final "" symbol
243 almost by accident */
245 /* Width of the next token, including the two quotes, the coma
250 for (p
= tags
[i
]; p
&& *p
; p
++)
251 if (*p
== '"' || *p
== '\\' || *p
== '\n' || *p
== '\t'
254 else if (*p
< 040 || *p
>= 0177)
259 if (j
+ strsize
> 75)
261 obstack_sgrow (&output_obstack
, "\n ");
265 obstack_1grow (&output_obstack
, '\"');
266 for (p
= tags
[i
]; p
&& *p
; p
++)
268 if (*p
== '"' || *p
== '\\')
269 obstack_fgrow1 (&output_obstack
, "\\%c", *p
);
271 obstack_sgrow (&output_obstack
, "\\n");
273 obstack_sgrow (&output_obstack
, "\\t");
275 obstack_sgrow (&output_obstack
, "\\b");
276 else if (*p
< 040 || *p
>= 0177)
277 obstack_fgrow1 (&output_obstack
, "\\%03o", *p
);
279 obstack_1grow (&output_obstack
, *p
);
282 obstack_sgrow (&output_obstack
, "\", ");
285 /* add a NULL entry to list of tokens */
286 obstack_sgrow (&output_obstack
, "NULL");
288 /* Finish table and store. */
289 obstack_1grow (&output_obstack
, 0);
290 muscle_insert ("tname", obstack_finish (&output_obstack
));
292 /* Output YYTOKNUM. */
293 output_table_data (&output_obstack
, user_toknums
,
295 muscle_insert ("toknum", obstack_finish (&output_obstack
));
299 short *values
= XCALLOC (short, nrules
+ 1);
300 for (i
= 0; i
< nrules
+ 1; ++i
)
301 values
[i
] = rule_table
[i
].lhs
;
302 output_table_data (&output_obstack
, values
,
304 muscle_insert ("r1", obstack_finish (&output_obstack
));
309 short_tab
= XMALLOC (short, nrules
+ 1);
310 for (i
= 1; i
< nrules
; i
++)
311 short_tab
[i
] = rule_table
[i
+ 1].rhs
- rule_table
[i
].rhs
- 1;
312 short_tab
[nrules
] = nitems
- rule_table
[nrules
].rhs
- 1;
313 output_table_data (&output_obstack
, short_tab
,
315 muscle_insert ("r2", obstack_finish (&output_obstack
));
318 XFREE (rule_table
+ 1);
321 /*------------------------------------------------------------------.
322 | Decide what to do for each type of token if seen as the lookahead |
323 | token in specified state. The value returned is used as the |
324 | default action (yydefact) for the state. In addition, actrow is |
325 | filled with what to do for each kind of token, index by symbol |
326 | number, with zero meaning do the default action. The value |
327 | MINSHORT, a very negative number, means this situation is an |
328 | error. The parser recognizes this value specially. |
330 | This is where conflicts are resolved. The loop over lookahead |
331 | rules considered lower-numbered rules last, and the last rule |
332 | considered that likes a token gets to handle it. |
333 `------------------------------------------------------------------*/
336 action_row (int state
)
351 int nodefault
= 0; /* set nonzero to inhibit having any default reduction */
353 for (i
= 0; i
< ntokens
; i
++)
358 redp
= state_table
[state
]->reductions
;
366 /* loop over all the rules available here which require
368 m
= state_table
[state
]->lookaheads
;
369 n
= state_table
[state
+ 1]->lookaheads
;
371 for (i
= n
- 1; i
>= m
; i
--)
372 /* and find each token which the rule finds acceptable
374 for (j
= 0; j
< ntokens
; j
++)
375 /* and record this rule as the rule to use if that
377 if (BITISSET (LA (i
), j
))
378 actrow
[j
] = -LAruleno
[i
];
382 /* Now see which tokens are allowed for shifts in this state. For
383 them, record the shift as the thing to do. So shift is preferred
385 shiftp
= state_table
[state
]->shifts
;
386 for (i
= 0; i
< shiftp
->nshifts
; i
++)
388 shift_state
= shiftp
->shifts
[i
];
392 symbol
= state_table
[shift_state
]->accessing_symbol
;
397 actrow
[symbol
] = shift_state
;
399 /* Do not use any default reduction if there is a shift for
401 if (symbol
== error_token_number
)
405 /* See which tokens are an explicit error in this state (due to
406 %nonassoc). For them, record MINSHORT as the action. */
407 errp
= state_table
[state
]->errs
;
413 for (i
= 0; i
< k
; i
++)
415 symbol
= errp
->errs
[i
];
416 actrow
[symbol
] = MINSHORT
;
420 /* Now find the most common reduction and make it the default action
423 if (nreds
>= 1 && !nodefault
)
425 if (state_table
[state
]->consistent
)
426 default_rule
= redp
->rules
[0];
430 for (i
= m
; i
< n
; i
++)
435 for (j
= 0; j
< ntokens
; j
++)
437 if (actrow
[j
] == rule
)
448 /* actions which match the default are replaced with zero,
449 which means "use the default" */
453 for (j
= 0; j
< ntokens
; j
++)
455 if (actrow
[j
] == default_rule
)
459 default_rule
= -default_rule
;
464 /* If have no default rule, the default is an error.
465 So replace any action which says "error" with "use default". */
467 if (default_rule
== 0)
468 for (j
= 0; j
< ntokens
; j
++)
470 if (actrow
[j
] == MINSHORT
)
488 for (i
= 0; i
< ntokens
; i
++)
497 froms
[state
] = sp1
= sp
= XCALLOC (short, count
);
498 tos
[state
] = sp2
= XCALLOC (short, count
);
500 for (i
= 0; i
< ntokens
; i
++)
509 tally
[state
] = count
;
510 width
[state
] = sp1
[-1] - sp
[0] + 1;
514 /*------------------------------------------------------------------.
515 | Figure out the actions for the specified state, indexed by |
516 | lookahead token type. |
518 | The YYDEFACT table is output now. The detailed info is saved for |
519 | putting into YYTABLE later. |
520 `------------------------------------------------------------------*/
526 short *yydefact
= XCALLOC (short, nstates
);
528 actrow
= XCALLOC (short, ntokens
);
529 for (i
= 0; i
< nstates
; ++i
)
531 yydefact
[i
] = action_row (i
);
535 output_table_data (&output_obstack
, yydefact
,
536 yydefact
[0], 1, nstates
);
537 muscle_insert ("defact", obstack_finish (&output_obstack
));
545 save_column (int symbol
, int default_state
)
554 short begin
= goto_map
[symbol
];
555 short end
= goto_map
[symbol
+ 1];
558 for (i
= begin
; i
< end
; i
++)
560 if (to_state
[i
] != default_state
)
567 symno
= symbol
- ntokens
+ nstates
;
569 froms
[symno
] = sp1
= sp
= XCALLOC (short, count
);
570 tos
[symno
] = sp2
= XCALLOC (short, count
);
572 for (i
= begin
; i
< end
; i
++)
574 if (to_state
[i
] != default_state
)
576 *sp1
++ = from_state
[i
];
577 *sp2
++ = to_state
[i
];
581 tally
[symno
] = count
;
582 width
[symno
] = sp1
[-1] - sp
[0] + 1;
586 default_goto (int symbol
)
594 m
= goto_map
[symbol
];
595 n
= goto_map
[symbol
+ 1];
600 for (i
= 0; i
< nstates
; i
++)
603 for (i
= m
; i
< n
; i
++)
604 state_count
[to_state
[i
]]++;
609 for (i
= 0; i
< nstates
; i
++)
611 if (state_count
[i
] > max
)
613 max
= state_count
[i
];
618 return default_state
;
622 /*-------------------------------------------------------------------.
623 | Figure out what to do after reducing with each rule, depending on |
624 | the saved state from before the beginning of parsing the data that |
625 | matched this rule. |
627 | The YYDEFGOTO table is output now. The detailed info is saved for |
628 | putting into YYTABLE later. |
629 `-------------------------------------------------------------------*/
635 short *yydefgoto
= XMALLOC (short, nsyms
- ntokens
);
637 state_count
= XCALLOC (short, nstates
);
638 for (i
= ntokens
; i
< nsyms
; ++i
)
640 int default_state
= default_goto (i
);
641 save_column (i
, default_state
);
642 yydefgoto
[i
- ntokens
] = default_state
;
645 output_table_data (&output_obstack
, yydefgoto
,
646 yydefgoto
[0], 1, nsyms
- ntokens
);
647 muscle_insert ("defgoto", obstack_finish (&output_obstack
));
654 /* The next few functions decide how to pack the actions and gotos
655 information into yytable. */
666 order
= XCALLOC (short, nvectors
);
669 for (i
= 0; i
< nvectors
; i
++)
677 while (j
>= 0 && (width
[order
[j
]] < w
))
680 while (j
>= 0 && (width
[order
[j
]] == w
) && (tally
[order
[j
]] < t
))
683 for (k
= nentries
- 1; k
> j
; k
--)
684 order
[k
+ 1] = order
[k
];
694 matching_state (int vector
)
711 for (prev
= vector
- 1; prev
>= 0; prev
--)
714 if (width
[j
] != w
|| tally
[j
] != t
)
718 for (k
= 0; match
&& k
< t
; k
++)
720 if (tos
[j
][k
] != tos
[i
][k
] || froms
[j
][k
] != froms
[i
][k
])
733 pack_vector (int vector
)
752 for (j
= lowzero
- from
[0]; j
< MAXTABLE
; j
++)
756 for (k
= 0; ok
&& k
< t
; k
++)
760 fatal (_("maximum table size (%d) exceeded"), MAXTABLE
);
766 for (k
= 0; ok
&& k
< vector
; k
++)
774 for (k
= 0; k
< t
; k
++)
778 check
[loc
] = from
[k
];
781 while (table
[lowzero
] != 0)
791 assert (!"pack_vector");
803 base
= XCALLOC (short, nvectors
);
804 pos
= XCALLOC (short, nentries
);
805 table
= XCALLOC (short, MAXTABLE
);
806 check
= XCALLOC (short, MAXTABLE
);
811 for (i
= 0; i
< nvectors
; i
++)
814 for (i
= 0; i
< MAXTABLE
; i
++)
817 for (i
= 0; i
< nentries
; i
++)
819 state
= matching_state (i
);
822 place
= pack_vector (i
);
827 base
[order
[i
]] = place
;
830 for (i
= 0; i
< nvectors
; i
++)
843 /* the following functions output yytable, yycheck
844 and the vectors whose elements index the portion starts */
850 output_table_data (&output_obstack
, base
,
851 base
[0], 1, nstates
);
852 muscle_insert ("pact", obstack_finish (&output_obstack
));
855 output_table_data (&output_obstack
, base
,
856 base
[nstates
], nstates
+ 1, nvectors
);
857 muscle_insert ("pgoto", obstack_finish (&output_obstack
));
866 output_table_data (&output_obstack
, table
,
867 table
[0], 1, high
+ 1);
868 muscle_insert ("table", obstack_finish (&output_obstack
));
876 output_table_data (&output_obstack
, check
,
877 check
[0], 1, high
+ 1);
878 muscle_insert ("check", obstack_finish (&output_obstack
));
882 /* compute and output yydefact, yydefgoto, yypact, yypgoto, yytable
886 output_actions (void)
888 nvectors
= nstates
+ nvars
;
890 froms
= XCALLOC (short *, nvectors
);
891 tos
= XCALLOC (short *, nvectors
);
892 tally
= XCALLOC (short, nvectors
);
893 width
= XCALLOC (short, nvectors
);
896 LIST_FREE (shifts
, first_shift
);
897 LIST_FREE (reductions
, first_reduction
);
902 XFREE (goto_map
+ ntokens
);
913 LIST_FREE (state_t
, first_state
);
918 /*------------------------------------------------------------.
919 | Copy the parser code from SKEL_FILENAME into OOUT obstack. |
920 | and do the muscle substitution. |
921 `------------------------------------------------------------*/
924 output_parser (const char *skel_filename
, struct obstack
*oout
)
930 fskel
= xfopen (skel_filename
, "r");
932 /* New output code. */
941 obstack_1grow (oout
, c
);
944 else if ((c
= getc (fskel
)) == '%')
946 /* Read the muscle. */
947 const char *muscle_key
= 0;
948 const char *muscle_value
= 0;
950 while (isalnum (c
= getc (fskel
)) || c
== '-')
951 obstack_1grow (&muscle_obstack
, c
);
952 obstack_1grow (&muscle_obstack
, 0);
954 /* Output the right value, or see if it's something special. */
955 muscle_key
= obstack_finish (&muscle_obstack
);
956 muscle_value
= muscle_find (muscle_key
);
958 obstack_sgrow (oout
, muscle_value
);
959 else if (!strcmp (muscle_key
, "line"))
960 obstack_fgrow1 (oout
, "%d", line
+ 1);
961 else if (!strcmp (muscle_key
, "input-line"))
962 obstack_fgrow1 (oout
, "%d", lineno
);
965 obstack_sgrow (oout
, "%%");
966 obstack_sgrow (oout
, muscle_key
);
970 obstack_1grow (oout
, '%');
977 /*----------------------------------------.
978 | Prepare the master parser to be output |
979 `----------------------------------------*/
982 output_master_parser (void)
987 skeleton
= skeleton_find ("BISON_HAIRY", BISON_HAIRY
);
989 skeleton
= skeleton_find ("BISON_SIMPLE", BISON_SIMPLE
);
991 muscle_insert ("skeleton", skeleton
);
992 output_parser (skeleton
, &table_obstack
);
998 #define MUSCLE_INSERT_INT(Key, Value) \
1000 obstack_fgrow1 (&muscle_obstack, "%d", Value); \
1001 obstack_1grow (&muscle_obstack, 0); \
1002 muscle_insert (Key, obstack_finish (&muscle_obstack)); \
1005 #define MUSCLE_INSERT_STRING(Key, Value) \
1007 obstack_sgrow (&muscle_obstack, Value); \
1008 obstack_1grow (&muscle_obstack, 0); \
1009 muscle_insert (Key, obstack_finish (&muscle_obstack)); \
1012 #define MUSCLE_INSERT_PREFIX(Key, Value) \
1014 obstack_fgrow2 (&muscle_obstack, "%s%s", spec_name_prefix, Value); \
1015 obstack_1grow (&muscle_obstack, 0); \
1016 muscle_insert (Key, obstack_finish (&muscle_obstack)); \
1022 MUSCLE_INSERT_INT ("last", high
);
1023 MUSCLE_INSERT_INT ("flag", MINSHORT
);
1024 MUSCLE_INSERT_INT ("pure", pure_parser
);
1025 MUSCLE_INSERT_INT ("nsym", nsyms
);
1026 MUSCLE_INSERT_INT ("debug", debug_flag
);
1027 MUSCLE_INSERT_INT ("final", final_state
);
1028 MUSCLE_INSERT_INT ("maxtok", max_user_token_number
);
1029 MUSCLE_INSERT_INT ("ntbase", ntokens
);
1030 MUSCLE_INSERT_INT ("error-verbose", error_verbose
);
1032 MUSCLE_INSERT_INT ("nnts", nvars
);
1033 MUSCLE_INSERT_INT ("nrules", nrules
);
1034 MUSCLE_INSERT_INT ("nstates", nstates
);
1035 MUSCLE_INSERT_INT ("ntokens", ntokens
);
1037 MUSCLE_INSERT_INT ("locations-flag", locations_flag
);
1039 /* We need to save the actions in the muscle %%action. */
1040 muscle_insert ("action", obstack_finish (&action_obstack
));
1042 if (spec_name_prefix
)
1043 MUSCLE_INSERT_STRING ("prefix", spec_name_prefix
);
1046 /*----------------------------------------------------------.
1047 | Output the parsing tables and the parser code to ftable. |
1048 `----------------------------------------------------------*/
1053 obstack_init (&output_obstack
);
1055 output_token_translations ();
1059 if (semantic_parser
)
1061 output_rule_data ();
1062 XFREE (user_toknums
);
1066 if (!no_parser_flag
) */
1069 /* Copy definitions in directive. */
1070 muscle_insert ("prologue", obstack_finish (&attrs_obstack
));
1072 output_master_parser ();
1074 obstack_free (&muscle_obstack
, 0);
1075 obstack_free (&output_obstack
, 0);
1076 obstack_free (&action_obstack
, 0);