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-skel.h"
40#include "symtab.h"
41#include "tables.h"
42
43
44static 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									\
57static void								\
58Name (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
102GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_unsigned_int_table, unsigned int)
103GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_int_table, int)
104GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_base_table, base_number)
105GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_rule_number_table, rule_number)
106GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_symbol_number_table, symbol_number)
107GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_item_number_table, item_number)
108GENERATE_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
115static void
116escaped_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
140static void
141prepare_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    /* Add a NULL entry to list of tokens (well, 0, as NULL might not be
179       defined).  */
180    obstack_sgrow (&format_obstack, " 0");
181
182    /* Finish table and store. */
183    obstack_1grow (&format_obstack, 0);
184    muscle_insert ("tname", obstack_finish (&format_obstack));
185  }
186
187  /* Output YYTOKNUM. */
188  {
189    int i;
190    int *values = xnmalloc (ntokens, sizeof *values);
191    for (i = 0; i < ntokens; ++i)
192      values[i] = symbols[i]->user_token_number;
193    muscle_insert_int_table ("toknum", values,
194			     values[0], 1, ntokens);
195    free (values);
196  }
197}
198
199
200/*-------------------------------------------------------------.
201| Prepare the muscles related to the rules: rhs, prhs, r1, r2, |
202| rline, dprec, merger.                                        |
203`-------------------------------------------------------------*/
204
205static void
206prepare_rules (void)
207{
208  rule_number r;
209  unsigned int i = 0;
210  item_number *rhs = xnmalloc (nritems, sizeof *rhs);
211  unsigned int *prhs = xnmalloc (nrules, sizeof *prhs);
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);
217
218  for (r = 0; r < nrules; ++r)
219    {
220      item_number *rhsp = NULL;
221      /* Index of rule R in RHS. */
222      prhs[r] = i;
223      /* RHS of the rule R. */
224      for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp)
225	rhs[i++] = *rhsp;
226      /* LHS of the rule R. */
227      r1[r] = rules[r].lhs->number;
228      /* Length of rule R's RHS. */
229      r2[r] = i - prhs[r];
230      /* Separator in RHS. */
231      rhs[i++] = -1;
232      /* Line where rule was defined. */
233      rline[r] = rules[r].location.start.line;
234      /* Dynamic precedence (GLR).  */
235      dprec[r] = rules[r].dprec;
236      /* Merger-function index (GLR).  */
237      merger[r] = rules[r].merger;
238    }
239  assert (i == nritems);
240
241  muscle_insert_item_number_table ("rhs", rhs, ritem[0], 1, nritems);
242  muscle_insert_unsigned_int_table ("prhs", prhs, 0, 0, nrules);
243  muscle_insert_unsigned_int_table ("rline", rline, 0, 0, nrules);
244  muscle_insert_symbol_number_table ("r1", r1, 0, 0, nrules);
245  muscle_insert_unsigned_int_table ("r2", r2, 0, 0, nrules);
246  muscle_insert_int_table ("dprec", dprec, 0, 0, nrules);
247  muscle_insert_int_table ("merger", merger, 0, 0, nrules);
248
249  MUSCLE_INSERT_INT ("rules_number", nrules);
250  MUSCLE_INSERT_INT ("max_left_semantic_context", max_left_semantic_context);
251
252  free (rhs);
253  free (prhs);
254  free (rline);
255  free (r1);
256  free (r2);
257  free (dprec);
258  free (merger);
259}
260
261/*--------------------------------------------.
262| Prepare the muscles related to the states.  |
263`--------------------------------------------*/
264
265static void
266prepare_states (void)
267{
268  state_number i;
269  symbol_number *values = xnmalloc (nstates, sizeof *values);
270  for (i = 0; i < nstates; ++i)
271    values[i] = states[i]->accessing_symbol;
272  muscle_insert_symbol_number_table ("stos", values,
273				     0, 1, nstates);
274  free (values);
275
276  MUSCLE_INSERT_INT ("last", high);
277  MUSCLE_INSERT_INT ("final_state_number", final_state->number);
278  MUSCLE_INSERT_INT ("states_number", nstates);
279}
280
281
282
283/*---------------------------------.
284| Output the user actions to OUT.  |
285`---------------------------------*/
286
287static void
288user_actions_output (FILE *out)
289{
290  rule_number r;
291
292  fputs ("m4_define([b4_actions], \n[[", out);
293  for (r = 0; r < nrules; ++r)
294    if (rules[r].action)
295      {
296	fprintf (out, "  case %d:\n", r + 1);
297
298	fprintf (out, "]b4_syncline(%d, ",
299		 rules[r].action_location.start.line);
300	escaped_output (out, rules[r].action_location.start.file);
301	fprintf (out, ")[\n");
302	fprintf (out, "    %s\n    break;\n\n",
303		 rules[r].action);
304      }
305  fputs ("]])\n\n", out);
306}
307
308/*--------------------------------------.
309| Output the merge functions to OUT.   |
310`--------------------------------------*/
311
312static void
313merger_output (FILE *out)
314{
315  int n;
316  merger_list* p;
317
318  fputs ("m4_define([b4_mergers], \n[[", out);
319  for (n = 1, p = merge_functions; p != NULL; n += 1, p = p->next)
320    {
321      if (p->type[0] == '\0')
322	fprintf (out, "  case %d: *yy0 = %s (*yy0, *yy1); break;\n",
323		 n, p->name);
324      else
325	fprintf (out, "  case %d: yy0->%s = %s (*yy0, *yy1); break;\n",
326		 n, p->type, p->name);
327    }
328  fputs ("]])\n\n", out);
329}
330
331/*--------------------------------------.
332| Output the tokens definition to OUT.  |
333`--------------------------------------*/
334
335static void
336token_definitions_output (FILE *out)
337{
338  int i;
339  char const *sep = "";
340
341  fputs ("m4_define([b4_tokens], \n[", out);
342  for (i = 0; i < ntokens; ++i)
343    {
344      symbol *sym = symbols[i];
345      int number = sym->user_token_number;
346
347      /* At this stage, if there are literal aliases, they are part of
348	 SYMBOLS, so we should not find symbols which are the aliases
349	 here.  */
350      assert (number != USER_NUMBER_ALIAS);
351
352      /* Skip error token.  */
353      if (sym == errtoken)
354	continue;
355
356      /* If this string has an alias, then it is necessarily the alias
357	 which is to be output.  */
358      if (sym->alias)
359	sym = sym->alias;
360
361      /* Don't output literal chars or strings (when defined only as a
362	 string).  Note that must be done after the alias resolution:
363	 think about `%token 'f' "f"'.  */
364      if (sym->tag[0] == '\'' || sym->tag[0] == '\"')
365	continue;
366
367      /* Don't #define nonliteral tokens whose names contain periods
368	 or '$' (as does the default value of the EOF token).  */
369      if (strchr (sym->tag, '.') || strchr (sym->tag, '$'))
370	continue;
371
372      fprintf (out, "%s[[[%s]], %d]",
373	       sep, sym->tag, number);
374      sep = ",\n";
375    }
376  fputs ("])\n\n", out);
377}
378
379
380/*---------------------------------------.
381| Output the symbol destructors to OUT.  |
382`---------------------------------------*/
383
384static void
385symbol_destructors_output (FILE *out)
386{
387  int i;
388  char const *sep = "";
389
390  fputs ("m4_define([b4_symbol_destructors], \n[", out);
391  for (i = 0; i < nsyms; ++i)
392    if (symbols[i]->destructor)
393      {
394	symbol *sym = symbols[i];
395
396	/* Filename, lineno,
397	   Symbol-name, Symbol-number,
398	   destructor, optional typename.  */
399	fprintf (out, "%s[", sep);
400	sep = ",\n";
401	escaped_output (out, sym->destructor_location.start.file);
402	fprintf (out, ", %d, ", sym->destructor_location.start.line);
403	escaped_output (out, sym->tag);
404	fprintf (out, ", %d, [[%s]]", sym->number, sym->destructor);
405	if (sym->type_name)
406	  fprintf (out, ", [[%s]]", sym->type_name);
407	fputc (']', out);
408      }
409  fputs ("])\n\n", out);
410}
411
412
413/*------------------------------------.
414| Output the symbol printers to OUT.  |
415`------------------------------------*/
416
417static void
418symbol_printers_output (FILE *out)
419{
420  int i;
421  char const *sep = "";
422
423  fputs ("m4_define([b4_symbol_printers], \n[", out);
424  for (i = 0; i < nsyms; ++i)
425    if (symbols[i]->printer)
426      {
427	symbol *sym = symbols[i];
428
429	/* Filename, lineno,
430	   Symbol-name, Symbol-number,
431	   printer, optional typename.  */
432	fprintf (out, "%s[", sep);
433	sep = ",\n";
434	escaped_output (out, sym->printer_location.start.file);
435	fprintf (out, ", %d, ", sym->printer_location.start.line);
436	escaped_output (out, sym->tag);
437	fprintf (out, ", %d, [[%s]]", sym->number, sym->printer);
438	if (sym->type_name)
439	  fprintf (out, ", [[%s]]", sym->type_name);
440	fputc (']', out);
441      }
442  fputs ("])\n\n", out);
443}
444
445
446static void
447prepare_actions (void)
448{
449  /* Figure out the actions for the specified state, indexed by
450     look-ahead token type.  */
451
452  muscle_insert_rule_number_table ("defact", yydefact,
453				   yydefact[0], 1, nstates);
454
455  /* Figure out what to do after reducing with each rule, depending on
456     the saved state from before the beginning of parsing the data
457     that matched this rule.  */
458  muscle_insert_state_number_table ("defgoto", yydefgoto,
459				    yydefgoto[0], 1, nsyms - ntokens);
460
461
462  /* Output PACT. */
463  muscle_insert_base_table ("pact", base,
464			     base[0], 1, nstates);
465  MUSCLE_INSERT_INT ("pact_ninf", base_ninf);
466
467  /* Output PGOTO. */
468  muscle_insert_base_table ("pgoto", base,
469			     base[nstates], nstates + 1, nvectors);
470
471  muscle_insert_base_table ("table", table,
472			    table[0], 1, high + 1);
473  MUSCLE_INSERT_INT ("table_ninf", table_ninf);
474
475  muscle_insert_base_table ("check", check,
476			    check[0], 1, high + 1);
477
478  /* GLR parsing slightly modifies YYTABLE and YYCHECK (and thus
479     YYPACT) so that in states with unresolved conflicts, the default
480     reduction is not used in the conflicted entries, so that there is
481     a place to put a conflict pointer.
482
483     This means that YYCONFLP and YYCONFL are nonsense for a non-GLR
484     parser, so we could avoid accidents by not writing them out in
485     that case.  Nevertheless, it seems even better to be able to use
486     the GLR skeletons even without the non-deterministic tables.  */
487  muscle_insert_unsigned_int_table ("conflict_list_heads", conflict_table,
488				    conflict_table[0], 1, high + 1);
489  muscle_insert_unsigned_int_table ("conflicting_rules", conflict_list,
490				    0, 1, conflict_list_cnt);
491}
492
493
494/*---------------------------.
495| Call the skeleton parser.  |
496`---------------------------*/
497
498static void
499output_skeleton (void)
500{
501  FILE *in;
502  FILE *out;
503  int filter_fd[2];
504  char const *argv[6];
505  pid_t pid;
506
507  /* Compute the names of the package data dir and skeleton file.
508     Test whether m4sugar.m4 is readable, to check for proper
509     installation.  A faulty installation can cause deadlock, so a
510     cheap sanity check is worthwhile.  */
511  char const m4sugar[] = "m4sugar/m4sugar.m4";
512  char *full_m4sugar;
513  char *full_skeleton;
514  char const *p;
515  char const *m4 = (p = getenv ("M4")) ? p : M4;
516  char const *pkgdatadir = (p = getenv ("BISON_PKGDATADIR")) ? p : PKGDATADIR;
517  size_t skeleton_size = strlen (skeleton) + 1;
518  size_t pkgdatadirlen = strlen (pkgdatadir);
519  while (pkgdatadirlen && pkgdatadir[pkgdatadirlen - 1] == '/')
520    pkgdatadirlen--;
521  full_skeleton = xmalloc (pkgdatadirlen + 1
522			   + (skeleton_size < sizeof m4sugar
523			      ? sizeof m4sugar : skeleton_size));
524  strcpy (full_skeleton, pkgdatadir);
525  full_skeleton[pkgdatadirlen] = '/';
526  strcpy (full_skeleton + pkgdatadirlen + 1, m4sugar);
527  full_m4sugar = xstrdup (full_skeleton);
528  strcpy (full_skeleton + pkgdatadirlen + 1, skeleton);
529  xfclose (xfopen (full_m4sugar, "r"));
530
531  /* Create an m4 subprocess connected to us via two pipes.  */
532
533  if (trace_flag & trace_tools)
534    fprintf (stderr, "running: %s %s - %s\n",
535	     m4, full_m4sugar, full_skeleton);
536
537  argv[0] = m4;
538  argv[1] = full_m4sugar;
539  argv[2] = "-";
540  argv[3] = full_skeleton;
541  argv[4] = trace_flag & trace_m4 ? "-dV" : NULL;
542  argv[5] = NULL;
543
544  init_subpipe ();
545  pid = create_subpipe (argv, filter_fd);
546  free (full_m4sugar);
547  free (full_skeleton);
548
549  out = fdopen (filter_fd[0], "w");
550  if (! out)
551    error (EXIT_FAILURE, get_errno (),
552	   "fdopen");
553
554  /* Output the definitions of all the muscles.  */
555  fputs ("m4_init()\n", out);
556
557  user_actions_output (out);
558  merger_output (out);
559  token_definitions_output (out);
560  symbol_destructors_output (out);
561  symbol_printers_output (out);
562
563  muscles_m4_output (out);
564
565  fputs ("m4_wrap([m4_divert_pop(0)])\n", out);
566  fputs ("m4_divert_push(0)dnl\n", out);
567  xfclose (out);
568
569  /* Read and process m4's output.  */
570  timevar_push (TV_M4);
571  end_of_output_subpipe (pid, filter_fd);
572  in = fdopen (filter_fd[1], "r");
573  if (! in)
574    error (EXIT_FAILURE, get_errno (),
575	   "fdopen");
576  scan_skel (in);
577  xfclose (in);
578  reap_subpipe (pid, m4);
579  timevar_pop (TV_M4);
580}
581
582static void
583prepare (void)
584{
585  /* Flags. */
586  MUSCLE_INSERT_BOOL ("debug_flag", debug_flag);
587  MUSCLE_INSERT_BOOL ("defines_flag", defines_flag);
588  MUSCLE_INSERT_BOOL ("error_verbose_flag", error_verbose);
589  MUSCLE_INSERT_BOOL ("locations_flag", locations_flag);
590  MUSCLE_INSERT_BOOL ("pure_flag", pure_parser);
591  MUSCLE_INSERT_BOOL ("synclines_flag", !no_lines_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
634void
635output (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}
653