1 /* Output the generated parsing program for Bison.
3 Copyright (C) 1984, 1986, 1989, 1992, 2000-2010 Free Software
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"
43 # define ARRAY_CARDINALITY(Array) (sizeof (Array) / sizeof *(Array))
45 static struct obstack format_obstack
;
48 /*-------------------------------------------------------------------.
49 | Create a function NAME which associates to the muscle NAME the |
50 | result of formatting the FIRST and then TABLE_DATA[BEGIN..END[ (of |
51 | TYPE), and to the muscle NAME_max, the max value of the |
53 `-------------------------------------------------------------------*/
56 #define GENERATE_MUSCLE_INSERT_TABLE(Name, Type) \
59 Name (char const *name, \
72 obstack_fgrow1 (&format_obstack, "%6d", first); \
73 for (i = begin; i < end; ++i) \
75 obstack_1grow (&format_obstack, ','); \
78 obstack_sgrow (&format_obstack, "\n "); \
83 obstack_fgrow1 (&format_obstack, "%6d", table_data[i]); \
84 if (table_data[i] < min) \
85 min = table_data[i]; \
86 if (max < table_data[i]) \
87 max = table_data[i]; \
89 obstack_1grow (&format_obstack, 0); \
90 muscle_insert (name, obstack_finish (&format_obstack)); \
94 /* Build `NAME_min' and `NAME_max' in the obstack. */ \
95 obstack_fgrow1 (&format_obstack, "%s_min", name); \
96 obstack_1grow (&format_obstack, 0); \
97 MUSCLE_INSERT_LONG_INT (obstack_finish (&format_obstack), lmin); \
98 obstack_fgrow1 (&format_obstack, "%s_max", name); \
99 obstack_1grow (&format_obstack, 0); \
100 MUSCLE_INSERT_LONG_INT (obstack_finish (&format_obstack), lmax); \
103 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_unsigned_int_table
, unsigned int)
104 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_int_table
, int)
105 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_base_table
, base_number
)
106 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_rule_number_table
, rule_number
)
107 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_symbol_number_table
, symbol_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 ("symbols_number", nsyms
);
147 MUSCLE_INSERT_INT ("undef_token_number", undeftoken
->number
);
148 MUSCLE_INSERT_INT ("user_token_number_max", max_user_token_number
);
150 muscle_insert_symbol_number_table ("translate",
152 token_translations
[0],
153 1, max_user_token_number
+ 1);
155 /* tname -- token names. */
158 /* We assume that the table will be output starting at column 2. */
160 struct quoting_options
*qo
= clone_quoting_options (0);
161 set_quoting_style (qo
, c_quoting_style
);
162 set_quoting_flags (qo
, QA_SPLIT_TRIGRAPHS
);
163 for (i
= 0; i
< nsyms
; i
++)
165 char *cp
= quotearg_alloc (symbols
[i
]->tag
, -1, qo
);
166 /* Width of the next token, including the two quotes, the
167 comma and the space. */
168 int width
= strlen (cp
) + 2;
172 obstack_sgrow (&format_obstack
, "\n ");
177 obstack_1grow (&format_obstack
, ' ');
178 MUSCLE_OBSTACK_SGROW (&format_obstack
, cp
);
180 obstack_1grow (&format_obstack
, ',');
184 obstack_sgrow (&format_obstack
, " ]b4_null[");
186 /* Finish table and store. */
187 obstack_1grow (&format_obstack
, 0);
188 muscle_insert ("tname", obstack_finish (&format_obstack
));
191 /* Output YYTOKNUM. */
194 int *values
= xnmalloc (ntokens
, sizeof *values
);
195 for (i
= 0; i
< ntokens
; ++i
)
196 values
[i
] = symbols
[i
]->user_token_number
;
197 muscle_insert_int_table ("toknum", values
,
198 values
[0], 1, ntokens
);
204 /*----------------------------------------------------------------.
205 | Prepare the muscles related to the rules: r1, r2, rline, dprec, |
207 `----------------------------------------------------------------*/
212 unsigned int *rline
= xnmalloc (nrules
, sizeof *rline
);
213 symbol_number
*r1
= xnmalloc (nrules
, sizeof *r1
);
214 unsigned int *r2
= xnmalloc (nrules
, sizeof *r2
);
215 int *dprec
= xnmalloc (nrules
, sizeof *dprec
);
216 int *merger
= xnmalloc (nrules
, sizeof *merger
);
219 for (r
= 0; r
< nrules
; ++r
)
221 /* LHS of the rule R. */
222 r1
[r
] = rules
[r
].lhs
->number
;
223 /* Length of rule R's RHS. */
224 r2
[r
] = rule_rhs_length(&rules
[r
]);
225 /* Line where rule was defined. */
226 rline
[r
] = rules
[r
].location
.start
.line
;
227 /* Dynamic precedence (GLR). */
228 dprec
[r
] = rules
[r
].dprec
;
229 /* Merger-function index (GLR). */
230 merger
[r
] = rules
[r
].merger
;
233 muscle_insert_unsigned_int_table ("rline", rline
, 0, 0, nrules
);
234 muscle_insert_symbol_number_table ("r1", r1
, 0, 0, nrules
);
235 muscle_insert_unsigned_int_table ("r2", r2
, 0, 0, nrules
);
236 muscle_insert_int_table ("dprec", dprec
, 0, 0, nrules
);
237 muscle_insert_int_table ("merger", merger
, 0, 0, nrules
);
239 MUSCLE_INSERT_INT ("rules_number", nrules
);
240 MUSCLE_INSERT_INT ("max_left_semantic_context", max_left_semantic_context
);
249 /*--------------------------------------------.
250 | Prepare the muscles related to the states. |
251 `--------------------------------------------*/
254 prepare_states (void)
257 symbol_number
*values
= xnmalloc (nstates
, sizeof *values
);
258 for (i
= 0; i
< nstates
; ++i
)
259 values
[i
] = states
[i
]->accessing_symbol
;
260 muscle_insert_symbol_number_table ("stos", values
,
264 MUSCLE_INSERT_INT ("last", high
);
265 MUSCLE_INSERT_INT ("final_state_number", final_state
->number
);
266 MUSCLE_INSERT_INT ("states_number", nstates
);
270 /*-------------------------------------------------------.
271 | Compare two symbols by type-name, and then by number. |
272 `-------------------------------------------------------*/
275 symbol_type_name_cmp (const symbol
**lhs
, const symbol
**rhs
)
277 int res
= UNIQSTR_CMP((*lhs
)->type_name
, (*rhs
)->type_name
);
280 return (*lhs
)->number
- (*rhs
)->number
;
284 /*----------------------------------------------------------------.
285 | Return a (malloc'ed) table of the symbols sorted by type-name. |
286 `----------------------------------------------------------------*/
289 symbols_by_type_name (void)
291 typedef int (*qcmp_type
) (const void *, const void *);
292 symbol
**res
= xmemdup (symbols
, nsyms
* sizeof *res
);
293 qsort (res
, nsyms
, sizeof *res
, (qcmp_type
) &symbol_type_name_cmp
);
298 /*------------------------------------------------------------------.
299 | Define b4_type_names, which is a list of (lists of the numbers of |
300 | symbols with same type-name). |
301 `------------------------------------------------------------------*/
304 type_names_output (FILE *out
)
307 symbol
**syms
= symbols_by_type_name ();
308 fputs ("m4_define([b4_type_names],\n[", out
);
309 for (i
= 0; i
< nsyms
; /* nothing */)
311 // The index of the first symbol of the current type-name.
313 fputs (i
? ",\n[" : "[", out
);
314 for (; i
< nsyms
&& syms
[i
]->type_name
== syms
[i0
]->type_name
; ++i
)
315 fprintf (out
, "%s%d", i
!= i0
? ", " : "", syms
[i
]->number
);
318 fputs ("])\n\n", out
);
323 /*-------------------------------------.
324 | The list of all the symbol numbers. |
325 `-------------------------------------*/
328 symbol_numbers_output (FILE *out
)
331 fputs ("m4_define([b4_symbol_numbers],\n[", out
);
332 for (i
= 0; i
< nsyms
; ++i
)
333 fprintf (out
, "%s[%d]", i
? ", " : "", i
);
334 fputs ("])\n\n", out
);
338 /*---------------------------------.
339 | Output the user actions to OUT. |
340 `---------------------------------*/
343 user_actions_output (FILE *out
)
347 fputs ("m4_define([b4_actions], \n[", out
);
348 for (r
= 0; r
< nrules
; ++r
)
351 fprintf (out
, "b4_case(%d, [b4_syncline(%d, ", r
+ 1,
352 rules
[r
].action_location
.start
.line
);
353 escaped_output (out
, rules
[r
].action_location
.start
.file
);
354 fprintf (out
, ")\n[ %s]])\n\n", rules
[r
].action
);
356 fputs ("])\n\n", out
);
359 /*------------------------------------.
360 | Output the merge functions to OUT. |
361 `------------------------------------*/
364 merger_output (FILE *out
)
369 fputs ("m4_define([b4_mergers], \n[[", out
);
370 for (n
= 1, p
= merge_functions
; p
!= NULL
; n
+= 1, p
= p
->next
)
372 if (p
->type
[0] == '\0')
373 fprintf (out
, " case %d: *yy0 = %s (*yy0, *yy1); break;\n",
376 fprintf (out
, " case %d: yy0->%s = %s (*yy0, *yy1); break;\n",
377 n
, p
->type
, p
->name
);
379 fputs ("]])\n\n", out
);
383 /*---------------------------------------------.
384 | Prepare the muscles for symbol definitions. |
385 `---------------------------------------------*/
388 prepare_symbol_definitions (void)
391 for (i
= 0; i
< nsyms
; ++i
)
393 symbol
*sym
= symbols
[i
];
397 #define SET_KEY(Entry) \
398 obstack_fgrow2 (&format_obstack, "symbol(%d, %s)", i, Entry); \
399 obstack_1grow (&format_obstack, 0); \
400 key = obstack_finish (&format_obstack);
402 // Whether the symbol has an identifier.
403 value
= symbol_id_get (sym
);
405 MUSCLE_INSERT_INT (key
, !!value
);
409 MUSCLE_INSERT_STRING (key
, value
? value
: "");
411 // Its tag. Typically for documentation purpose.
413 MUSCLE_INSERT_STRING (key
, sym
->tag
);
415 SET_KEY("user_number");
416 MUSCLE_INSERT_INT (key
, sym
->user_token_number
);
419 MUSCLE_INSERT_INT (key
,
420 i
< ntokens
&& sym
!= errtoken
&& sym
!= undeftoken
);
423 MUSCLE_INSERT_INT (key
, sym
->number
);
426 MUSCLE_INSERT_INT (key
, !!sym
->type_name
);
429 MUSCLE_INSERT_STRING (key
, sym
->type_name
? sym
->type_name
: "");
431 #define CODE_PROP(PropName) \
433 code_props const *p = symbol_ ## PropName ## _get (sym); \
434 SET_KEY("has_" #PropName); \
435 MUSCLE_INSERT_INT (key, !!p->code); \
439 SET_KEY(#PropName "_file"); \
440 MUSCLE_INSERT_STRING (key, p->location.start.file); \
442 SET_KEY(#PropName "_line"); \
443 MUSCLE_INSERT_INT (key, p->location.start.line); \
445 SET_KEY(#PropName); \
446 MUSCLE_INSERT_STRING_RAW (key, p->code); \
450 CODE_PROP(destructor
);
458 /*--------------------------------------.
459 | Output the tokens definition to OUT. |
460 `--------------------------------------*/
463 token_definitions_output (FILE *out
)
466 char const *sep
= "";
468 fputs ("m4_define([b4_tokens], \n[", out
);
469 for (i
= 0; i
< ntokens
; ++i
)
471 symbol
*sym
= symbols
[i
];
472 int number
= sym
->user_token_number
;
473 uniqstr id
= symbol_id_get (sym
);
475 /* At this stage, if there are literal string aliases, they are
476 part of SYMBOLS, so we should not find their aliased symbols
478 aver (number
!= USER_NUMBER_HAS_STRING_ALIAS
);
480 /* Skip error token and tokens without identifier. */
481 if (sym
!= errtoken
&& id
)
483 fprintf (out
, "%s[[[%s]], %d]",
488 fputs ("])\n\n", out
);
493 prepare_actions (void)
495 /* Figure out the actions for the specified state, indexed by
496 lookahead token type. */
498 muscle_insert_rule_number_table ("defact", yydefact
,
499 yydefact
[0], 1, nstates
);
501 /* Figure out what to do after reducing with each rule, depending on
502 the saved state from before the beginning of parsing the data
503 that matched this rule. */
504 muscle_insert_state_number_table ("defgoto", yydefgoto
,
505 yydefgoto
[0], 1, nsyms
- ntokens
);
509 muscle_insert_base_table ("pact", base
,
510 base
[0], 1, nstates
);
511 MUSCLE_INSERT_INT ("pact_ninf", base_ninf
);
514 muscle_insert_base_table ("pgoto", base
,
515 base
[nstates
], nstates
+ 1, nvectors
);
517 muscle_insert_base_table ("table", table
,
518 table
[0], 1, high
+ 1);
519 MUSCLE_INSERT_INT ("table_ninf", table_ninf
);
521 muscle_insert_base_table ("check", check
,
522 check
[0], 1, high
+ 1);
524 /* GLR parsing slightly modifies YYTABLE and YYCHECK (and thus
525 YYPACT) so that in states with unresolved conflicts, the default
526 reduction is not used in the conflicted entries, so that there is
527 a place to put a conflict pointer.
529 This means that YYCONFLP and YYCONFL are nonsense for a non-GLR
530 parser, so we could avoid accidents by not writing them out in
531 that case. Nevertheless, it seems even better to be able to use
532 the GLR skeletons even without the non-deterministic tables. */
533 muscle_insert_unsigned_int_table ("conflict_list_heads", conflict_table
,
534 conflict_table
[0], 1, high
+ 1);
535 muscle_insert_unsigned_int_table ("conflicting_rules", conflict_list
,
536 0, 1, conflict_list_cnt
);
540 /*--------------------------------------------.
541 | Output the definitions of all the muscles. |
542 `--------------------------------------------*/
545 muscles_output (FILE *out
)
547 fputs ("m4_init()\n", out
);
549 symbol_numbers_output (out
);
550 token_definitions_output (out
);
551 type_names_output (out
);
552 user_actions_output (out
);
554 muscles_m4_output (out
);
557 /*---------------------------.
558 | Call the skeleton parser. |
559 `---------------------------*/
562 output_skeleton (void)
566 char const *argv
[10];
569 /* Compute the names of the package data dir and skeleton files. */
570 char const m4sugar
[] = "m4sugar/m4sugar.m4";
571 char const m4bison
[] = "bison.m4";
576 char const *m4
= (p
= getenv ("M4")) ? p
: M4
;
577 char const *pkgdatadir
= compute_pkgdatadir ();
578 size_t skeleton_size
= strlen (skeleton
) + 1;
579 size_t pkgdatadirlen
= strlen (pkgdatadir
);
580 while (pkgdatadirlen
&& pkgdatadir
[pkgdatadirlen
- 1] == '/')
582 full_skeleton
= xmalloc (pkgdatadirlen
+ 1
583 + (skeleton_size
< sizeof m4sugar
584 ? sizeof m4sugar
: skeleton_size
));
585 strncpy (full_skeleton
, pkgdatadir
, pkgdatadirlen
);
586 full_skeleton
[pkgdatadirlen
] = '/';
587 strcpy (full_skeleton
+ pkgdatadirlen
+ 1, m4sugar
);
588 full_m4sugar
= xstrdup (full_skeleton
);
589 strcpy (full_skeleton
+ pkgdatadirlen
+ 1, m4bison
);
590 full_m4bison
= xstrdup (full_skeleton
);
591 if (strchr (skeleton
, '/'))
592 strcpy (full_skeleton
, skeleton
);
594 strcpy (full_skeleton
+ pkgdatadirlen
+ 1, skeleton
);
596 /* Test whether m4sugar.m4 is readable, to check for proper
597 installation. A faulty installation can cause deadlock, so a
598 cheap sanity check is worthwhile. */
599 xfclose (xfopen (full_m4sugar
, "r"));
601 /* Create an m4 subprocess connected to us via two pipes. */
603 if (trace_flag
& trace_tools
)
604 fprintf (stderr
, "running: %s %s - %s %s\n",
605 m4
, full_m4sugar
, full_m4bison
, full_skeleton
);
607 /* Some future version of GNU M4 (most likely 1.6) may treat the -dV in a
608 position-dependent manner. Keep it as the first argument so that all
611 See the thread starting at
612 <http://lists.gnu.org/archive/html/bug-bison/2008-07/msg00000.html>
618 /* When POSIXLY_CORRECT is set, GNU M4 1.6 and later disable GNU
619 extensions, which Bison's skeletons depend on. With older M4,
620 it has no effect. M4 1.4.12 added a -g/--gnu command-line
621 option to make it explicit that a program wants GNU M4
622 extensions even when POSIXLY_CORRECT is set.
624 See the thread starting at
625 <http://lists.gnu.org/archive/html/bug-bison/2008-07/msg00000.html>
628 argv
[i
++] = M4_GNU_OPTION
;
631 argv
[i
++] = pkgdatadir
;
632 if (trace_flag
& trace_m4
)
634 argv
[i
++] = full_m4sugar
;
636 argv
[i
++] = full_m4bison
;
637 argv
[i
++] = full_skeleton
;
639 aver (i
<= ARRAY_CARDINALITY (argv
));
643 pid
= create_subpipe (argv
, filter_fd
);
646 free (full_skeleton
);
648 if (trace_flag
& trace_muscles
)
649 muscles_output (stderr
);
651 FILE *out
= fdopen (filter_fd
[0], "w");
653 error (EXIT_FAILURE
, get_errno (),
655 muscles_output (out
);
659 /* Read and process m4's output. */
660 timevar_push (TV_M4
);
661 end_of_output_subpipe (pid
, filter_fd
);
662 in
= fdopen (filter_fd
[1], "r");
664 error (EXIT_FAILURE
, get_errno (),
668 reap_subpipe (pid
, m4
);
675 /* BISON_USE_PUSH_FOR_PULL is for the test suite and should not be documented
677 char const *use_push_for_pull_env
= getenv ("BISON_USE_PUSH_FOR_PULL");
678 bool use_push_for_pull_flag
= false;
679 if (use_push_for_pull_env
!= NULL
680 && use_push_for_pull_env
[0] != '\0'
681 && 0 != strcmp (use_push_for_pull_env
, "0"))
682 use_push_for_pull_flag
= true;
685 MUSCLE_INSERT_BOOL ("defines_flag", defines_flag
);
686 MUSCLE_INSERT_BOOL ("glr_flag", glr_parser
);
687 MUSCLE_INSERT_BOOL ("nondeterministic_flag", nondeterministic_parser
);
688 MUSCLE_INSERT_BOOL ("synclines_flag", !no_lines_flag
);
689 MUSCLE_INSERT_BOOL ("tag_seen_flag", tag_seen
);
690 MUSCLE_INSERT_BOOL ("use_push_for_pull_flag", use_push_for_pull_flag
);
691 MUSCLE_INSERT_BOOL ("yacc_flag", yacc_flag
);
694 if (spec_name_prefix
)
695 MUSCLE_INSERT_STRING ("prefix", spec_name_prefix
);
697 MUSCLE_INSERT_STRING ("file_name_all_but_ext", all_but_ext
);
699 #define DEFINE(Name) MUSCLE_INSERT_STRING (#Name, Name ? Name : "")
701 DEFINE (parser_file_name
);
702 DEFINE (spec_defines_file
);
703 DEFINE (spec_file_prefix
);
704 DEFINE (spec_graph_file
);
705 DEFINE (spec_name_prefix
);
706 DEFINE (spec_outfile
);
707 DEFINE (spec_verbose_file
);
710 /* Find the right skeleton file, and add muscles about the skeletons. */
712 MUSCLE_INSERT_C_STRING ("skeleton", skeleton
);
714 skeleton
= language
->skeleton
;
716 /* About the skeletons. */
718 /* b4_pkgdatadir is used inside m4_include in the skeletons, so digraphs
719 would never be expanded. Hopefully no one has M4-special characters in
720 his Bison installation path. */
721 MUSCLE_INSERT_STRING_RAW ("pkgdatadir", compute_pkgdatadir ());
726 /*----------------------------------------------------------.
727 | Output the parsing tables and the parser code to ftable. |
728 `----------------------------------------------------------*/
733 obstack_init (&format_obstack
);
739 prepare_symbol_definitions ();
743 /* Process the selected skeleton file. */
746 obstack_free (&format_obstack
, NULL
);
750 compute_pkgdatadir (void)
752 char const *pkgdatadir
= getenv ("BISON_PKGDATADIR");
753 return pkgdatadir
? pkgdatadir
: PKGDATADIR
;