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