1 /* Output the generated parsing program for Bison.
3 Copyright (C) 1984, 1986, 1989, 1992, 2000, 2001, 2002, 2003, 2004,
4 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
6 This file is part of Bison, the GNU Compiler Compiler.
8 This program is free software: you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation, either version 3 of the License, or
11 (at your option) any later version.
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program. If not, see <http://www.gnu.org/licenses/>. */
24 #include <configmake.h>
26 #include <get-errno.h>
35 #include "muscle_tab.h"
38 #include "scan-code.h" /* max_left_semantic_context */
39 #include "scan-skel.h"
44 static struct obstack format_obstack
;
47 /*-------------------------------------------------------------------.
48 | Create a function NAME which associates to the muscle NAME the |
49 | result of formatting the FIRST and then TABLE_DATA[BEGIN..END[ (of |
50 | TYPE), and to the muscle NAME_max, the max value of the |
52 `-------------------------------------------------------------------*/
55 #define GENERATE_MUSCLE_INSERT_TABLE(Name, Type) \
58 Name (char const *name, \
71 obstack_fgrow1 (&format_obstack, "%6d", first); \
72 for (i = begin; i < end; ++i) \
74 obstack_1grow (&format_obstack, ','); \
77 obstack_sgrow (&format_obstack, "\n "); \
82 obstack_fgrow1 (&format_obstack, "%6d", table_data[i]); \
83 if (table_data[i] < min) \
84 min = table_data[i]; \
85 if (max < table_data[i]) \
86 max = table_data[i]; \
88 obstack_1grow (&format_obstack, 0); \
89 muscle_insert (name, obstack_finish (&format_obstack)); \
93 /* Build `NAME_min' and `NAME_max' in the obstack. */ \
94 obstack_fgrow1 (&format_obstack, "%s_min", name); \
95 obstack_1grow (&format_obstack, 0); \
96 MUSCLE_INSERT_LONG_INT (obstack_finish (&format_obstack), lmin); \
97 obstack_fgrow1 (&format_obstack, "%s_max", name); \
98 obstack_1grow (&format_obstack, 0); \
99 MUSCLE_INSERT_LONG_INT (obstack_finish (&format_obstack), lmax); \
102 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_unsigned_int_table
, unsigned int)
103 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_int_table
, int)
104 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_base_table
, base_number
)
105 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_rule_number_table
, rule_number
)
106 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_symbol_number_table
, symbol_number
)
107 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_item_number_table
, item_number
)
108 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_state_number_table
, state_number
)
111 /*--------------------------------------------------------------------.
112 | Print to OUT a representation of STRING escaped both for C and M4. |
113 `--------------------------------------------------------------------*/
116 escaped_output (FILE *out
, char const *string
)
121 for (p
= quotearg_style (c_quoting_style
, string
); *p
; p
++)
124 case '$': fputs ("$][", out
); break;
125 case '@': fputs ("@@", out
); break;
126 case '[': fputs ("@{", out
); break;
127 case ']': fputs ("@}", out
); break;
128 default: fputc (*p
, out
); break;
135 /*------------------------------------------------------------------.
136 | Prepare the muscles related to the symbols: translate, tname, and |
138 `------------------------------------------------------------------*/
141 prepare_symbols (void)
143 MUSCLE_INSERT_BOOL ("token_table", token_table_flag
);
144 MUSCLE_INSERT_INT ("tokens_number", ntokens
);
145 MUSCLE_INSERT_INT ("nterms_number", nvars
);
146 MUSCLE_INSERT_INT ("undef_token_number", undeftoken
->number
);
147 MUSCLE_INSERT_INT ("user_token_number_max", max_user_token_number
);
149 muscle_insert_symbol_number_table ("translate",
151 token_translations
[0],
152 1, max_user_token_number
+ 1);
154 /* tname -- token names. */
157 /* We assume that the table will be output starting at column 2. */
159 struct quoting_options
*qo
= clone_quoting_options (0);
160 set_quoting_style (qo
, c_quoting_style
);
161 set_quoting_flags (qo
, QA_SPLIT_TRIGRAPHS
);
162 for (i
= 0; i
< nsyms
; i
++)
164 char *cp
= quotearg_alloc (symbols
[i
]->tag
, -1, qo
);
165 /* Width of the next token, including the two quotes, the
166 comma and the space. */
167 int width
= strlen (cp
) + 2;
171 obstack_sgrow (&format_obstack
, "\n ");
176 obstack_1grow (&format_obstack
, ' ');
177 MUSCLE_OBSTACK_SGROW (&format_obstack
, cp
);
179 obstack_1grow (&format_obstack
, ',');
183 obstack_sgrow (&format_obstack
, " ]b4_null[");
185 /* Finish table and store. */
186 obstack_1grow (&format_obstack
, 0);
187 muscle_insert ("tname", obstack_finish (&format_obstack
));
190 /* Output YYTOKNUM. */
193 int *values
= xnmalloc (ntokens
, sizeof *values
);
194 for (i
= 0; i
< ntokens
; ++i
)
195 values
[i
] = symbols
[i
]->user_token_number
;
196 muscle_insert_int_table ("toknum", values
,
197 values
[0], 1, ntokens
);
203 /*-------------------------------------------------------------.
204 | Prepare the muscles related to the rules: rhs, prhs, r1, r2, |
205 | rline, dprec, merger. |
206 `-------------------------------------------------------------*/
213 item_number
*rhs
= xnmalloc (nritems
, sizeof *rhs
);
214 unsigned int *prhs
= xnmalloc (nrules
, sizeof *prhs
);
215 unsigned int *rline
= xnmalloc (nrules
, sizeof *rline
);
216 symbol_number
*r1
= xnmalloc (nrules
, sizeof *r1
);
217 unsigned int *r2
= xnmalloc (nrules
, sizeof *r2
);
218 int *dprec
= xnmalloc (nrules
, sizeof *dprec
);
219 int *merger
= xnmalloc (nrules
, sizeof *merger
);
221 for (r
= 0; r
< nrules
; ++r
)
223 item_number
*rhsp
= NULL
;
224 /* Index of rule R in RHS. */
226 /* RHS of the rule R. */
227 for (rhsp
= rules
[r
].rhs
; *rhsp
>= 0; ++rhsp
)
229 /* LHS of the rule R. */
230 r1
[r
] = rules
[r
].lhs
->number
;
231 /* Length of rule R's RHS. */
233 /* Separator in RHS. */
235 /* Line where rule was defined. */
236 rline
[r
] = rules
[r
].location
.start
.line
;
237 /* Dynamic precedence (GLR). */
238 dprec
[r
] = rules
[r
].dprec
;
239 /* Merger-function index (GLR). */
240 merger
[r
] = rules
[r
].merger
;
244 muscle_insert_item_number_table ("rhs", rhs
, ritem
[0], 1, nritems
);
245 muscle_insert_unsigned_int_table ("prhs", prhs
, 0, 0, nrules
);
246 muscle_insert_unsigned_int_table ("rline", rline
, 0, 0, nrules
);
247 muscle_insert_symbol_number_table ("r1", r1
, 0, 0, nrules
);
248 muscle_insert_unsigned_int_table ("r2", r2
, 0, 0, nrules
);
249 muscle_insert_int_table ("dprec", dprec
, 0, 0, nrules
);
250 muscle_insert_int_table ("merger", merger
, 0, 0, nrules
);
252 MUSCLE_INSERT_INT ("rules_number", nrules
);
253 MUSCLE_INSERT_INT ("max_left_semantic_context", max_left_semantic_context
);
264 /*--------------------------------------------.
265 | Prepare the muscles related to the states. |
266 `--------------------------------------------*/
269 prepare_states (void)
272 symbol_number
*values
= xnmalloc (nstates
, sizeof *values
);
273 for (i
= 0; i
< nstates
; ++i
)
274 values
[i
] = states
[i
]->accessing_symbol
;
275 muscle_insert_symbol_number_table ("stos", values
,
279 MUSCLE_INSERT_INT ("last", high
);
280 MUSCLE_INSERT_INT ("final_state_number", final_state
->number
);
281 MUSCLE_INSERT_INT ("states_number", nstates
);
286 /*-----------------------------------------------.
287 | For each symbol type, its tags and type name. |
288 `-----------------------------------------------*/
291 type_names_output (FILE *out
)
294 char const *sep
= "";
296 fputs ("m4_define([b4_type_names],\n[", out
);
297 for (i
= 0; i
< nsyms
; ++i
)
299 symbol
*sym
= symbols
[i
];
300 /* Symbol-name, Symbol-number, optional typename. */
301 fprintf (out
, "%s[", i
? ",\n" : "");
302 escaped_output (out
, sym
->tag
);
303 fprintf (out
, ", %d, [[%s]]]",
305 sym
->type_name
? sym
->type_name
: "");
307 fputs ("])\n\n", out
);
311 /*---------------------------------.
312 | Output the user actions to OUT. |
313 `---------------------------------*/
316 user_actions_output (FILE *out
)
320 fputs ("m4_define([b4_actions], \n[", out
);
321 for (r
= 0; r
< nrules
; ++r
)
324 fprintf (out
, "b4_case(%d, [b4_syncline(%d, ", r
+ 1,
325 rules
[r
].action_location
.start
.line
);
326 escaped_output (out
, rules
[r
].action_location
.start
.file
);
327 fprintf (out
, ")\n[ %s]])\n\n", rules
[r
].action
);
329 fputs ("])\n\n", out
);
332 /*--------------------------------------.
333 | Output the merge functions to OUT. |
334 `--------------------------------------*/
337 merger_output (FILE *out
)
342 fputs ("m4_define([b4_mergers], \n[[", out
);
343 for (n
= 1, p
= merge_functions
; p
!= NULL
; n
+= 1, p
= p
->next
)
345 if (p
->type
[0] == '\0')
346 fprintf (out
, " case %d: *yy0 = %s (*yy0, *yy1); break;\n",
349 fprintf (out
, " case %d: yy0->%s = %s (*yy0, *yy1); break;\n",
350 n
, p
->type
, p
->name
);
352 fputs ("]])\n\n", out
);
355 /*--------------------------------------.
356 | Output the tokens definition to OUT. |
357 `--------------------------------------*/
360 token_definitions_output (FILE *out
)
363 char const *sep
= "";
365 fputs ("m4_define([b4_tokens], \n[", out
);
366 for (i
= 0; i
< ntokens
; ++i
)
368 symbol
*sym
= symbols
[i
];
369 int number
= sym
->user_token_number
;
371 /* At this stage, if there are literal aliases, they are part of
372 SYMBOLS, so we should not find symbols which are the aliases
374 aver (number
!= USER_NUMBER_ALIAS
);
376 /* Skip error token. */
380 /* If this string has an alias, then it is necessarily the alias
381 which is to be output. */
385 /* Don't output literal chars or strings (when defined only as a
386 string). Note that must be done after the alias resolution:
387 think about `%token 'f' "f"'. */
388 if (sym
->tag
[0] == '\'' || sym
->tag
[0] == '\"')
391 /* Don't #define nonliteral tokens whose names contain periods
392 or '$' (as does the default value of the EOF token). */
393 if (strchr (sym
->tag
, '.') || strchr (sym
->tag
, '$'))
396 fprintf (out
, "%s[[[%s]], %d]",
397 sep
, sym
->tag
, number
);
400 fputs ("])\n\n", out
);
404 /*---------------------------------------------------.
405 | Output the symbol destructors or printers to OUT. |
406 `---------------------------------------------------*/
409 symbol_code_props_output (FILE *out
, char const *what
,
410 code_props
const *(*get
)(symbol
const *))
413 char const *sep
= "";
415 fputs ("m4_define([b4_symbol_", out
);
417 fputs ("], \n[", out
);
418 for (i
= 0; i
< nsyms
; ++i
)
420 symbol
*sym
= symbols
[i
];
421 char const *code
= (*get
) (sym
)->code
;
424 location loc
= (*get
) (sym
)->location
;
426 Symbol-name, Symbol-number,
427 code, optional typename. */
428 fprintf (out
, "%s[", sep
);
430 escaped_output (out
, loc
.start
.file
);
431 fprintf (out
, ", %d, ", loc
.start
.line
);
432 escaped_output (out
, sym
->tag
);
433 fprintf (out
, ", %d, [[%s]]", sym
->number
, code
);
435 fprintf (out
, ", [[%s]]", sym
->type_name
);
439 fputs ("])\n\n", out
);
444 prepare_actions (void)
446 /* Figure out the actions for the specified state, indexed by
447 lookahead token type. */
449 muscle_insert_rule_number_table ("defact", yydefact
,
450 yydefact
[0], 1, nstates
);
452 /* Figure out what to do after reducing with each rule, depending on
453 the saved state from before the beginning of parsing the data
454 that matched this rule. */
455 muscle_insert_state_number_table ("defgoto", yydefgoto
,
456 yydefgoto
[0], 1, nsyms
- ntokens
);
460 muscle_insert_base_table ("pact", base
,
461 base
[0], 1, nstates
);
462 MUSCLE_INSERT_INT ("pact_ninf", base_ninf
);
465 muscle_insert_base_table ("pgoto", base
,
466 base
[nstates
], nstates
+ 1, nvectors
);
468 muscle_insert_base_table ("table", table
,
469 table
[0], 1, high
+ 1);
470 MUSCLE_INSERT_INT ("table_ninf", table_ninf
);
472 muscle_insert_base_table ("check", check
,
473 check
[0], 1, high
+ 1);
475 /* GLR parsing slightly modifies YYTABLE and YYCHECK (and thus
476 YYPACT) so that in states with unresolved conflicts, the default
477 reduction is not used in the conflicted entries, so that there is
478 a place to put a conflict pointer.
480 This means that YYCONFLP and YYCONFL are nonsense for a non-GLR
481 parser, so we could avoid accidents by not writing them out in
482 that case. Nevertheless, it seems even better to be able to use
483 the GLR skeletons even without the non-deterministic tables. */
484 muscle_insert_unsigned_int_table ("conflict_list_heads", conflict_table
,
485 conflict_table
[0], 1, high
+ 1);
486 muscle_insert_unsigned_int_table ("conflicting_rules", conflict_list
,
487 0, 1, conflict_list_cnt
);
490 /*---------------------------.
491 | Call the skeleton parser. |
492 `---------------------------*/
495 output_skeleton (void)
503 /* Compute the names of the package data dir and skeleton files. */
504 char const m4sugar
[] = "m4sugar/m4sugar.m4";
505 char const m4bison
[] = "bison.m4";
510 char const *m4
= (p
= getenv ("M4")) ? p
: M4
;
511 char const *pkgdatadir
= compute_pkgdatadir ();
512 size_t skeleton_size
= strlen (skeleton
) + 1;
513 size_t pkgdatadirlen
= strlen (pkgdatadir
);
514 while (pkgdatadirlen
&& pkgdatadir
[pkgdatadirlen
- 1] == '/')
516 full_skeleton
= xmalloc (pkgdatadirlen
+ 1
517 + (skeleton_size
< sizeof m4sugar
518 ? sizeof m4sugar
: skeleton_size
));
519 strncpy (full_skeleton
, pkgdatadir
, pkgdatadirlen
);
520 full_skeleton
[pkgdatadirlen
] = '/';
521 strcpy (full_skeleton
+ pkgdatadirlen
+ 1, m4sugar
);
522 full_m4sugar
= xstrdup (full_skeleton
);
523 strcpy (full_skeleton
+ pkgdatadirlen
+ 1, m4bison
);
524 full_m4bison
= xstrdup (full_skeleton
);
525 if (strchr (skeleton
, '/'))
526 strcpy (full_skeleton
, skeleton
);
528 strcpy (full_skeleton
+ pkgdatadirlen
+ 1, skeleton
);
530 /* Test whether m4sugar.m4 is readable, to check for proper
531 installation. A faulty installation can cause deadlock, so a
532 cheap sanity check is worthwhile. */
533 xfclose (xfopen (full_m4sugar
, "r"));
535 /* Create an m4 subprocess connected to us via two pipes. */
537 if (trace_flag
& trace_tools
)
538 fprintf (stderr
, "running: %s %s - %s %s\n",
539 m4
, full_m4sugar
, full_m4bison
, full_skeleton
);
541 /* Some future version of GNU M4 (most likely 1.6) may treat the -dV in a
542 position-dependent manner. Keep it as the first argument so that all
545 See the thread starting at
546 <http://lists.gnu.org/archive/html/bug-bison/2008-07/msg00000.html>
552 argv
[i
++] = pkgdatadir
;
553 if (trace_flag
& trace_m4
)
555 argv
[i
++] = full_m4sugar
;
557 argv
[i
++] = full_m4bison
;
558 argv
[i
++] = full_skeleton
;
561 /* When POSIXLY_CORRECT is set, some future versions of GNU M4 (most likely
562 2.0) may drop some of the GNU extensions that Bison's skeletons depend
563 upon. So that the next release of Bison is forward compatible with those
564 future versions of GNU M4, we unset POSIXLY_CORRECT here.
566 FIXME: A user might set POSIXLY_CORRECT to affect processes run from
567 macros like m4_syscmd in a custom skeleton. For now, Bison makes no
568 promises about the behavior of custom skeletons, so this scenario is not a
569 concern. However, we eventually want to eliminate this shortcoming. The
570 next release of GNU M4 (1.4.12 or 1.6) will accept the -g command-line
571 option as a no-op, and later releases will accept it to indicate that
572 POSIXLY_CORRECT should be ignored. Once the GNU M4 versions that accept
573 -g are pervasive, Bison should use -g instead of unsetting
576 See the thread starting at
577 <http://lists.gnu.org/archive/html/bug-bison/2008-07/msg00000.html>
579 unsetenv ("POSIXLY_CORRECT");
581 pid
= create_subpipe (argv
, filter_fd
);
584 free (full_skeleton
);
586 out
= fdopen (filter_fd
[0], "w");
588 error (EXIT_FAILURE
, get_errno (),
591 /* Output the definitions of all the muscles. */
592 fputs ("m4_init()\n", out
);
594 type_names_output (out
);
595 user_actions_output (out
);
597 token_definitions_output (out
);
598 symbol_code_props_output (out
, "destructors", &symbol_destructor_get
);
599 symbol_code_props_output (out
, "printers", &symbol_printer_get
);
601 muscles_m4_output (out
);
604 /* Read and process m4's output. */
605 timevar_push (TV_M4
);
606 end_of_output_subpipe (pid
, filter_fd
);
607 in
= fdopen (filter_fd
[1], "r");
609 error (EXIT_FAILURE
, get_errno (),
613 reap_subpipe (pid
, m4
);
620 /* BISON_USE_PUSH_FOR_PULL is for the test suite and should not be documented
622 char const *use_push_for_pull_env
= getenv ("BISON_USE_PUSH_FOR_PULL");
623 bool use_push_for_pull_flag
= false;
624 if (use_push_for_pull_env
!= NULL
625 && use_push_for_pull_env
[0] != '\0'
626 && 0 != strcmp (use_push_for_pull_env
, "0"))
627 use_push_for_pull_flag
= true;
630 MUSCLE_INSERT_BOOL ("debug_flag", debug_flag
);
631 MUSCLE_INSERT_BOOL ("defines_flag", defines_flag
);
632 MUSCLE_INSERT_BOOL ("error_verbose_flag", error_verbose
);
633 MUSCLE_INSERT_BOOL ("glr_flag", glr_parser
);
634 MUSCLE_INSERT_BOOL ("locations_flag", locations_flag
);
635 MUSCLE_INSERT_BOOL ("nondeterministic_flag", nondeterministic_parser
);
636 MUSCLE_INSERT_BOOL ("synclines_flag", !no_lines_flag
);
637 MUSCLE_INSERT_BOOL ("tag_seen_flag", tag_seen
);
638 MUSCLE_INSERT_BOOL ("use_push_for_pull_flag", use_push_for_pull_flag
);
639 MUSCLE_INSERT_BOOL ("yacc_flag", yacc_flag
);
642 if (spec_name_prefix
)
643 MUSCLE_INSERT_STRING ("prefix", spec_name_prefix
);
645 MUSCLE_INSERT_STRING ("file_name_all_but_ext", all_but_ext
);
647 #define DEFINE(Name) MUSCLE_INSERT_STRING (#Name, Name ? Name : "")
649 DEFINE (parser_file_name
);
650 DEFINE (spec_defines_file
);
651 DEFINE (spec_file_prefix
);
652 DEFINE (spec_graph_file
);
653 DEFINE (spec_name_prefix
);
654 DEFINE (spec_outfile
);
655 DEFINE (spec_verbose_file
);
658 /* Find the right skeleton file, and add muscles about the skeletons. */
660 MUSCLE_INSERT_C_STRING ("skeleton", skeleton
);
662 skeleton
= language
->skeleton
;
664 /* About the skeletons. */
666 /* b4_pkgdatadir is used inside m4_include in the skeletons, so digraphs
667 would never be expanded. Hopefully no one has M4-special characters in
668 his Bison installation path. */
669 MUSCLE_INSERT_STRING_RAW ("pkgdatadir", compute_pkgdatadir ());
674 /*----------------------------------------------------------.
675 | Output the parsing tables and the parser code to ftable. |
676 `----------------------------------------------------------*/
681 obstack_init (&format_obstack
);
690 /* Process the selected skeleton file. */
693 obstack_free (&format_obstack
, NULL
);
697 compute_pkgdatadir (void)
699 char const *pkgdatadir
= getenv ("BISON_PKGDATADIR");
700 return pkgdatadir
? pkgdatadir
: PKGDATADIR
;