]> git.saurik.com Git - bison.git/blob - src/output.c
(print_core): Remove item set redundancy.
[bison.git] / src / output.c
1 /* Output the generated parsing program for Bison.
2
3 Copyright (C) 1984, 1986, 1989, 1992, 2000, 2001, 2002, 2003, 2004,
4 2005, 2006, 2007 Free Software Foundation, Inc.
5
6 This file is part of Bison, the GNU Compiler Compiler.
7
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.
12
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.
17
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/>. */
20
21 #include <config.h>
22 #include "system.h"
23
24 #include <configmake.h>
25 #include <error.h>
26 #include <get-errno.h>
27 #include <quotearg.h>
28 #include <subpipe.h>
29 #include <timevar.h>
30
31 #include "complain.h"
32 #include "files.h"
33 #include "getargs.h"
34 #include "gram.h"
35 #include "muscle_tab.h"
36 #include "output.h"
37 #include "reader.h"
38 #include "scan-code.h" /* max_left_semantic_context */
39 #include "scan-skel.h"
40 #include "symtab.h"
41 #include "tables.h"
42
43
44 static struct obstack format_obstack;
45
46
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 |
51 | TABLE_DATA. |
52 `-------------------------------------------------------------------*/
53
54
55 #define GENERATE_MUSCLE_INSERT_TABLE(Name, Type) \
56 \
57 static void \
58 Name (char const *name, \
59 Type *table_data, \
60 Type first, \
61 int begin, \
62 int end) \
63 { \
64 Type min = first; \
65 Type max = first; \
66 long int lmin; \
67 long int lmax; \
68 int i; \
69 int j = 1; \
70 \
71 obstack_fgrow1 (&format_obstack, "%6d", first); \
72 for (i = begin; i < end; ++i) \
73 { \
74 obstack_1grow (&format_obstack, ','); \
75 if (j >= 10) \
76 { \
77 obstack_sgrow (&format_obstack, "\n "); \
78 j = 1; \
79 } \
80 else \
81 ++j; \
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]; \
87 } \
88 obstack_1grow (&format_obstack, 0); \
89 muscle_insert (name, obstack_finish (&format_obstack)); \
90 \
91 lmin = min; \
92 lmax = max; \
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); \
100 }
101
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)
109
110
111 /*--------------------------------------------------------------------.
112 | Print to OUT a representation of STRING escaped both for C and M4. |
113 `--------------------------------------------------------------------*/
114
115 static void
116 escaped_output (FILE *out, char const *string)
117 {
118 char const *p;
119 fprintf (out, "[[");
120
121 for (p = quotearg_style (c_quoting_style, string); *p; p++)
122 switch (*p)
123 {
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;
129 }
130
131 fprintf (out, "]]");
132 }
133
134
135 /*------------------------------------------------------------------.
136 | Prepare the muscles related to the symbols: translate, tname, and |
137 | toknum. |
138 `------------------------------------------------------------------*/
139
140 static void
141 prepare_symbols (void)
142 {
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);
148
149 muscle_insert_symbol_number_table ("translate",
150 token_translations,
151 token_translations[0],
152 1, max_user_token_number + 1);
153
154 /* tname -- token names. */
155 {
156 int i;
157 /* We assume that the table will be output starting at column 2. */
158 int j = 2;
159 for (i = 0; i < nsyms; i++)
160 {
161 char const *cp = quotearg_style (c_quoting_style, symbols[i]->tag);
162 /* Width of the next token, including the two quotes, the
163 comma and the space. */
164 int width = strlen (cp) + 2;
165
166 if (j + width > 75)
167 {
168 obstack_sgrow (&format_obstack, "\n ");
169 j = 1;
170 }
171
172 if (i)
173 obstack_1grow (&format_obstack, ' ');
174 MUSCLE_OBSTACK_SGROW (&format_obstack, cp);
175 obstack_1grow (&format_obstack, ',');
176 j += width;
177 }
178 obstack_sgrow (&format_obstack, " ]b4_null[");
179
180 /* Finish table and store. */
181 obstack_1grow (&format_obstack, 0);
182 muscle_insert ("tname", obstack_finish (&format_obstack));
183 }
184
185 /* Output YYTOKNUM. */
186 {
187 int i;
188 int *values = xnmalloc (ntokens, sizeof *values);
189 for (i = 0; i < ntokens; ++i)
190 values[i] = symbols[i]->user_token_number;
191 muscle_insert_int_table ("toknum", values,
192 values[0], 1, ntokens);
193 free (values);
194 }
195 }
196
197
198 /*-------------------------------------------------------------.
199 | Prepare the muscles related to the rules: rhs, prhs, r1, r2, |
200 | rline, dprec, merger. |
201 `-------------------------------------------------------------*/
202
203 static void
204 prepare_rules (void)
205 {
206 rule_number r;
207 unsigned int i = 0;
208 item_number *rhs = xnmalloc (nritems, sizeof *rhs);
209 unsigned int *prhs = xnmalloc (nrules, sizeof *prhs);
210 unsigned int *rline = xnmalloc (nrules, sizeof *rline);
211 symbol_number *r1 = xnmalloc (nrules, sizeof *r1);
212 unsigned int *r2 = xnmalloc (nrules, sizeof *r2);
213 int *dprec = xnmalloc (nrules, sizeof *dprec);
214 int *merger = xnmalloc (nrules, sizeof *merger);
215
216 for (r = 0; r < nrules; ++r)
217 {
218 item_number *rhsp = NULL;
219 /* Index of rule R in RHS. */
220 prhs[r] = i;
221 /* RHS of the rule R. */
222 for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp)
223 rhs[i++] = *rhsp;
224 /* LHS of the rule R. */
225 r1[r] = rules[r].lhs->number;
226 /* Length of rule R's RHS. */
227 r2[r] = i - prhs[r];
228 /* Separator in RHS. */
229 rhs[i++] = -1;
230 /* Line where rule was defined. */
231 rline[r] = rules[r].location.start.line;
232 /* Dynamic precedence (GLR). */
233 dprec[r] = rules[r].dprec;
234 /* Merger-function index (GLR). */
235 merger[r] = rules[r].merger;
236 }
237 aver (i == nritems);
238
239 muscle_insert_item_number_table ("rhs", rhs, ritem[0], 1, nritems);
240 muscle_insert_unsigned_int_table ("prhs", prhs, 0, 0, nrules);
241 muscle_insert_unsigned_int_table ("rline", rline, 0, 0, nrules);
242 muscle_insert_symbol_number_table ("r1", r1, 0, 0, nrules);
243 muscle_insert_unsigned_int_table ("r2", r2, 0, 0, nrules);
244 muscle_insert_int_table ("dprec", dprec, 0, 0, nrules);
245 muscle_insert_int_table ("merger", merger, 0, 0, nrules);
246
247 MUSCLE_INSERT_INT ("rules_number", nrules);
248 MUSCLE_INSERT_INT ("max_left_semantic_context", max_left_semantic_context);
249
250 free (rhs);
251 free (prhs);
252 free (rline);
253 free (r1);
254 free (r2);
255 free (dprec);
256 free (merger);
257 }
258
259 /*--------------------------------------------.
260 | Prepare the muscles related to the states. |
261 `--------------------------------------------*/
262
263 static void
264 prepare_states (void)
265 {
266 state_number i;
267 symbol_number *values = xnmalloc (nstates, sizeof *values);
268 for (i = 0; i < nstates; ++i)
269 values[i] = states[i]->accessing_symbol;
270 muscle_insert_symbol_number_table ("stos", values,
271 0, 1, nstates);
272 free (values);
273
274 MUSCLE_INSERT_INT ("last", high);
275 MUSCLE_INSERT_INT ("final_state_number", final_state->number);
276 MUSCLE_INSERT_INT ("states_number", nstates);
277 }
278
279
280
281 /*---------------------------------.
282 | Output the user actions to OUT. |
283 `---------------------------------*/
284
285 static void
286 user_actions_output (FILE *out)
287 {
288 rule_number r;
289
290 fputs ("m4_define([b4_actions], \n[", out);
291 for (r = 0; r < nrules; ++r)
292 if (rules[r].action)
293 {
294 fprintf (out, "b4_case(%d, [b4_syncline(%d, ", r + 1,
295 rules[r].action_location.start.line);
296 escaped_output (out, rules[r].action_location.start.file);
297 fprintf (out, ")\n[ %s]])\n\n", rules[r].action);
298 }
299 fputs ("])\n\n", out);
300 }
301
302 /*--------------------------------------.
303 | Output the merge functions to OUT. |
304 `--------------------------------------*/
305
306 static void
307 merger_output (FILE *out)
308 {
309 int n;
310 merger_list* p;
311
312 fputs ("m4_define([b4_mergers], \n[[", out);
313 for (n = 1, p = merge_functions; p != NULL; n += 1, p = p->next)
314 {
315 if (p->type[0] == '\0')
316 fprintf (out, " case %d: *yy0 = %s (*yy0, *yy1); break;\n",
317 n, p->name);
318 else
319 fprintf (out, " case %d: yy0->%s = %s (*yy0, *yy1); break;\n",
320 n, p->type, p->name);
321 }
322 fputs ("]])\n\n", out);
323 }
324
325 /*--------------------------------------.
326 | Output the tokens definition to OUT. |
327 `--------------------------------------*/
328
329 static void
330 token_definitions_output (FILE *out)
331 {
332 int i;
333 char const *sep = "";
334
335 fputs ("m4_define([b4_tokens], \n[", out);
336 for (i = 0; i < ntokens; ++i)
337 {
338 symbol *sym = symbols[i];
339 int number = sym->user_token_number;
340
341 /* At this stage, if there are literal aliases, they are part of
342 SYMBOLS, so we should not find symbols which are the aliases
343 here. */
344 aver (number != USER_NUMBER_ALIAS);
345
346 /* Skip error token. */
347 if (sym == errtoken)
348 continue;
349
350 /* If this string has an alias, then it is necessarily the alias
351 which is to be output. */
352 if (sym->alias)
353 sym = sym->alias;
354
355 /* Don't output literal chars or strings (when defined only as a
356 string). Note that must be done after the alias resolution:
357 think about `%token 'f' "f"'. */
358 if (sym->tag[0] == '\'' || sym->tag[0] == '\"')
359 continue;
360
361 /* Don't #define nonliteral tokens whose names contain periods
362 or '$' (as does the default value of the EOF token). */
363 if (strchr (sym->tag, '.') || strchr (sym->tag, '$'))
364 continue;
365
366 fprintf (out, "%s[[[%s]], %d]",
367 sep, sym->tag, number);
368 sep = ",\n";
369 }
370 fputs ("])\n\n", out);
371 }
372
373
374 /*---------------------------------------------------.
375 | Output the symbol destructors or printers to OUT. |
376 `---------------------------------------------------*/
377
378 static void
379 symbol_code_props_output (FILE *out, char const *what,
380 code_props const *(*get)(symbol const *))
381 {
382 int i;
383 char const *sep = "";
384
385 fputs ("m4_define([b4_symbol_", out);
386 fputs (what, out);
387 fputs ("], \n[", out);
388 for (i = 0; i < nsyms; ++i)
389 {
390 symbol *sym = symbols[i];
391 char const *code = (*get) (sym)->code;
392 if (code)
393 {
394 location loc = (*get) (sym)->location;
395 /* Filename, lineno,
396 Symbol-name, Symbol-number,
397 code, optional typename. */
398 fprintf (out, "%s[", sep);
399 sep = ",\n";
400 escaped_output (out, loc.start.file);
401 fprintf (out, ", %d, ", loc.start.line);
402 escaped_output (out, sym->tag);
403 fprintf (out, ", %d, [[%s]]", sym->number, code);
404 if (sym->type_name)
405 fprintf (out, ", [[%s]]", sym->type_name);
406 fputc (']', out);
407 }
408 }
409 fputs ("])\n\n", out);
410 }
411
412
413 static void
414 prepare_actions (void)
415 {
416 /* Figure out the actions for the specified state, indexed by
417 lookahead token type. */
418
419 muscle_insert_rule_number_table ("defact", yydefact,
420 yydefact[0], 1, nstates);
421
422 /* Figure out what to do after reducing with each rule, depending on
423 the saved state from before the beginning of parsing the data
424 that matched this rule. */
425 muscle_insert_state_number_table ("defgoto", yydefgoto,
426 yydefgoto[0], 1, nsyms - ntokens);
427
428
429 /* Output PACT. */
430 muscle_insert_base_table ("pact", base,
431 base[0], 1, nstates);
432 MUSCLE_INSERT_INT ("pact_ninf", base_ninf);
433
434 /* Output PGOTO. */
435 muscle_insert_base_table ("pgoto", base,
436 base[nstates], nstates + 1, nvectors);
437
438 muscle_insert_base_table ("table", table,
439 table[0], 1, high + 1);
440 MUSCLE_INSERT_INT ("table_ninf", table_ninf);
441
442 muscle_insert_base_table ("check", check,
443 check[0], 1, high + 1);
444
445 /* GLR parsing slightly modifies YYTABLE and YYCHECK (and thus
446 YYPACT) so that in states with unresolved conflicts, the default
447 reduction is not used in the conflicted entries, so that there is
448 a place to put a conflict pointer.
449
450 This means that YYCONFLP and YYCONFL are nonsense for a non-GLR
451 parser, so we could avoid accidents by not writing them out in
452 that case. Nevertheless, it seems even better to be able to use
453 the GLR skeletons even without the non-deterministic tables. */
454 muscle_insert_unsigned_int_table ("conflict_list_heads", conflict_table,
455 conflict_table[0], 1, high + 1);
456 muscle_insert_unsigned_int_table ("conflicting_rules", conflict_list,
457 0, 1, conflict_list_cnt);
458 }
459
460 \f
461 /*---------------------------.
462 | Call the skeleton parser. |
463 `---------------------------*/
464
465 static void
466 output_skeleton (void)
467 {
468 FILE *in;
469 FILE *out;
470 int filter_fd[2];
471 char const *argv[7];
472 pid_t pid;
473
474 /* Compute the names of the package data dir and skeleton file.
475 Test whether m4sugar.m4 is readable, to check for proper
476 installation. A faulty installation can cause deadlock, so a
477 cheap sanity check is worthwhile. */
478 char const m4sugar[] = "m4sugar/m4sugar.m4";
479 char const m4bison[] = "bison.m4";
480 char *full_m4sugar;
481 char *full_m4bison;
482 char *full_skeleton;
483 char const *p;
484 char const *m4 = (p = getenv ("M4")) ? p : M4;
485 char const *pkgdatadir = compute_pkgdatadir ();
486 size_t skeleton_size = strlen (skeleton) + 1;
487 size_t pkgdatadirlen = strlen (pkgdatadir);
488 while (pkgdatadirlen && pkgdatadir[pkgdatadirlen - 1] == '/')
489 pkgdatadirlen--;
490 full_skeleton = xmalloc (pkgdatadirlen + 1
491 + (skeleton_size < sizeof m4sugar
492 ? sizeof m4sugar : skeleton_size));
493 strncpy (full_skeleton, pkgdatadir, pkgdatadirlen);
494 full_skeleton[pkgdatadirlen] = '/';
495 strcpy (full_skeleton + pkgdatadirlen + 1, m4sugar);
496 full_m4sugar = xstrdup (full_skeleton);
497 strcpy (full_skeleton + pkgdatadirlen + 1, m4bison);
498 full_m4bison = xstrdup (full_skeleton);
499 if (strchr (skeleton, '/'))
500 strcpy (full_skeleton, skeleton);
501 else
502 strcpy (full_skeleton + pkgdatadirlen + 1, skeleton);
503 xfclose (xfopen (full_m4sugar, "r"));
504
505 /* Create an m4 subprocess connected to us via two pipes. */
506
507 if (trace_flag & trace_tools)
508 fprintf (stderr, "running: %s %s - %s %s\n",
509 m4, full_m4sugar, full_m4bison, full_skeleton);
510
511 argv[0] = m4;
512 argv[1] = full_m4sugar;
513 argv[2] = "-";
514 argv[3] = full_m4bison;
515 argv[4] = full_skeleton;
516 argv[5] = trace_flag & trace_m4 ? "-dV" : NULL;
517 argv[6] = NULL;
518
519 init_subpipe ();
520 pid = create_subpipe (argv, filter_fd);
521 free (full_m4bison);
522 free (full_m4sugar);
523 free (full_skeleton);
524
525 out = fdopen (filter_fd[0], "w");
526 if (! out)
527 error (EXIT_FAILURE, get_errno (),
528 "fdopen");
529
530 /* Output the definitions of all the muscles. */
531 fputs ("m4_init()\n", out);
532
533 user_actions_output (out);
534 merger_output (out);
535 token_definitions_output (out);
536 symbol_code_props_output (out, "destructors", &symbol_destructor_get);
537 symbol_code_props_output (out, "printers", &symbol_printer_get);
538
539 muscles_m4_output (out);
540 xfclose (out);
541
542 /* Read and process m4's output. */
543 timevar_push (TV_M4);
544 end_of_output_subpipe (pid, filter_fd);
545 in = fdopen (filter_fd[1], "r");
546 if (! in)
547 error (EXIT_FAILURE, get_errno (),
548 "fdopen");
549 scan_skel (in);
550 xfclose (in);
551 reap_subpipe (pid, m4);
552 timevar_pop (TV_M4);
553 }
554
555 static void
556 prepare (void)
557 {
558 /* BISON_USE_PUSH_FOR_PULL is for the test suite and should not be documented
559 for the user. */
560 char const *use_push_for_pull_env = getenv ("BISON_USE_PUSH_FOR_PULL");
561 bool use_push_for_pull_flag = false;
562 if (use_push_for_pull_env != NULL
563 && use_push_for_pull_env[0] != '\0'
564 && 0 != strcmp (use_push_for_pull_env, "0"))
565 use_push_for_pull_flag = true;
566
567 /* Flags. */
568 MUSCLE_INSERT_BOOL ("debug_flag", debug_flag);
569 MUSCLE_INSERT_BOOL ("defines_flag", defines_flag);
570 MUSCLE_INSERT_BOOL ("error_verbose_flag", error_verbose);
571 MUSCLE_INSERT_BOOL ("glr_flag", glr_parser);
572 MUSCLE_INSERT_BOOL ("locations_flag", locations_flag);
573 MUSCLE_INSERT_BOOL ("nondeterministic_flag", nondeterministic_parser);
574 MUSCLE_INSERT_BOOL ("pure_flag", pure_parser);
575 MUSCLE_INSERT_BOOL ("synclines_flag", !no_lines_flag);
576 MUSCLE_INSERT_BOOL ("tag_seen_flag", tag_seen);
577 MUSCLE_INSERT_BOOL ("use_push_for_pull_flag", use_push_for_pull_flag);
578 MUSCLE_INSERT_BOOL ("yacc_flag", yacc_flag);
579
580 /* File names. */
581 if (spec_name_prefix)
582 MUSCLE_INSERT_STRING ("prefix", spec_name_prefix);
583
584 MUSCLE_INSERT_STRING ("file_name_all_but_ext", all_but_ext);
585
586 #define DEFINE(Name) MUSCLE_INSERT_STRING (#Name, Name ? Name : "")
587 DEFINE (dir_prefix);
588 DEFINE (parser_file_name);
589 DEFINE (spec_defines_file);
590 DEFINE (spec_file_prefix);
591 DEFINE (spec_graph_file);
592 DEFINE (spec_name_prefix);
593 DEFINE (spec_outfile);
594 DEFINE (spec_verbose_file);
595 #undef DEFINE
596
597 /* Find the right skeleton file, and add muscles about the skeletons. */
598 if (skeleton)
599 MUSCLE_INSERT_C_STRING ("skeleton", skeleton);
600 else
601 skeleton = language->skeleton;
602
603 /* About the skeletons. */
604 {
605 /* b4_pkgdatadir is used inside m4_include in the skeletons, so digraphs
606 would never be expanded. Hopefully no one has M4-special characters in
607 his Bison installation path. */
608 MUSCLE_INSERT_STRING_RAW ("pkgdatadir", compute_pkgdatadir ());
609 }
610 }
611
612
613 /*----------------------------------------------------------.
614 | Output the parsing tables and the parser code to ftable. |
615 `----------------------------------------------------------*/
616
617 void
618 output (void)
619 {
620 obstack_init (&format_obstack);
621
622 prepare_symbols ();
623 prepare_rules ();
624 prepare_states ();
625 prepare_actions ();
626
627 prepare ();
628
629 /* Process the selected skeleton file. */
630 output_skeleton ();
631
632 obstack_free (&format_obstack, NULL);
633 }
634
635 char const *
636 compute_pkgdatadir (void)
637 {
638 char const *pkgdatadir = getenv ("BISON_PKGDATADIR");
639 return pkgdatadir ? pkgdatadir : PKGDATADIR;
640 }