src/output.c

   1 /* Output the generated parsing program for bison,
   2    Copyright (C) 1984, 1986, 1989, 1992, 2000, 2001, 2002
   3    Free Software Foundation, Inc.
   4
   5    This file is part of Bison, the GNU Compiler Compiler.
   6
   7    Bison is free software; you can redistribute it and/or modify it
   8    under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 2, or (at your option)
  10    any later version.
  11
  12    Bison is distributed in the hope that it will be useful, but
  13    WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15    General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with Bison; see the file COPYING.  If not, write to the Free
  19    Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  20    02111-1307, USA.  */
  21
  22
  23 #include "system.h"
  24 #include "quotearg.h"
  25 #include "error.h"
  26 #include "subpipe.h"
  27 #include "getargs.h"
  28 #include "files.h"
  29 #include "gram.h"
  30 #include "complain.h"
  31 #include "output.h"
  32 #include "reader.h"
  33 #include "symtab.h"
  34 #include "tables.h"
  35 #include "muscle_tab.h"
  36
  37 /* From src/scan-skel.l. */
  38 void scan_skel (FILE *);
  39
  40
  41 static struct obstack format_obstack;
  42
  43 int error_verbose = 0;
  44
  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 (const char *name,                                                 \
  59       Type *table_data,                                                 \
  60       Type first,                                                       \
  61       int begin,                                                        \
  62       int end)                                                          \
  63 {                                                                       \
  64   Type min = first;                                                     \
  65   Type max = first;                                                     \
  66   int i;                                                                \
  67   int j = 1;                                                            \
  68                                                                         \
  69   obstack_fgrow1 (&format_obstack, "%6d", first);                       \
  70   for (i = begin; i < end; ++i)                                         \
  71     {                                                                   \
  72       obstack_1grow (&format_obstack, ',');                             \
  73       if (j >= 10)                                                      \
  74         {                                                               \
  75           obstack_sgrow (&format_obstack, "\n  ");                      \
  76           j = 1;                                                        \
  77         }                                                               \
  78       else                                                              \
  79         ++j;                                                            \
  80       obstack_fgrow1 (&format_obstack, "%6d", table_data[i]);           \
  81       if (table_data[i] < min)                                          \
  82         min = table_data[i];                                            \
  83       if (max < table_data[i])                                          \
  84         max = table_data[i];                                            \
  85     }                                                                   \
  86   obstack_1grow (&format_obstack, 0);                                   \
  87   muscle_insert (name, obstack_finish (&format_obstack));               \
  88                                                                         \
  89   /* Build `NAME_min' and `NAME_max' in the obstack. */                 \
  90   obstack_fgrow1 (&format_obstack, "%s_min", name);                     \
  91   obstack_1grow (&format_obstack, 0);                                   \
  92   MUSCLE_INSERT_LONG_INT (obstack_finish (&format_obstack),             \
  93                           (long int) min);                              \
  94   obstack_fgrow1 (&format_obstack, "%s_max", name);                     \
  95   obstack_1grow (&format_obstack, 0);                                   \
  96   MUSCLE_INSERT_LONG_INT (obstack_finish (&format_obstack),             \
  97                           (long int) max);                              \
  98 }
  99
 100 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_unsigned_int_table, unsigned int)
 101 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_int_table, int)
 102 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_short_table, short)
 103 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_base_table, base_t)
 104 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_rule_number_table, rule_number_t)
 105 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_symbol_number_table, symbol_number_t)
 106 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_item_number_table, item_number_t)
 107 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_state_number_table, state_number_t)
 108
 109
 110 /*-----------------------------------------------------------------.
 111 | Prepare the muscles related to the tokens: translate, tname, and |
 112 | toknum.                                                          |
 113 `-----------------------------------------------------------------*/
 114
 115 static void
 116 prepare_tokens (void)
 117 {
 118   muscle_insert_symbol_number_table ("translate",
 119                                      token_translations,
 120                                      token_translations[0],
 121                                      1, max_user_token_number + 1);
 122
 123   {
 124     int i;
 125     int j = 0;
 126     for (i = 0; i < nsyms; i++)
 127       {
 128         /* Be sure not to use twice the same QUOTEARG slot:
 129            SYMBOL_TAG_GET uses slot 0.  */
 130         const char *cp =
 131           quotearg_n_style (1, c_quoting_style,
 132                             symbols[i]->tag);
 133         /* Width of the next token, including the two quotes, the coma
 134            and the space.  */
 135         int strsize = strlen (cp) + 2;
 136
 137         if (j + strsize > 75)
 138           {
 139             obstack_sgrow (&format_obstack, "\n  ");
 140             j = 2;
 141           }
 142
 143         obstack_sgrow (&format_obstack, cp);
 144         obstack_sgrow (&format_obstack, ", ");
 145         j += strsize;
 146       }
 147     /* Add a NULL entry to list of tokens (well, 0, as NULL might not be
 148        defined).  */
 149     obstack_sgrow (&format_obstack, "0");
 150
 151     /* Finish table and store. */
 152     obstack_1grow (&format_obstack, 0);
 153     muscle_insert ("tname", obstack_finish (&format_obstack));
 154   }
 155
 156   /* Output YYTOKNUM. */
 157   {
 158     int i;
 159     int *values = XCALLOC (int, ntokens);
 160     for (i = 0; i < ntokens; ++i)
 161       values[i] = symbols[i]->user_token_number;
 162     muscle_insert_int_table ("toknum", values,
 163                              values[0], 1, ntokens);
 164     free (values);
 165   }
 166 }
 167
 168
 169 /*-------------------------------------------------------------.
 170 | Prepare the muscles related to the rules: rhs, prhs, r1, r2, |
 171 | rline, dprec, merger                                         |
 172 `-------------------------------------------------------------*/
 173
 174 static void
 175 prepare_rules (void)
 176 {
 177   rule_number_t r;
 178   unsigned int i = 0;
 179   item_number_t *rhs = XMALLOC (item_number_t, nritems);
 180   unsigned int *prhs = XMALLOC (unsigned int, nrules);
 181   unsigned int *rline = XMALLOC (unsigned int, nrules);
 182   symbol_number_t *r1 = XMALLOC (symbol_number_t, nrules);
 183   unsigned int *r2 = XMALLOC (unsigned int, nrules);
 184   short *dprec = XMALLOC (short, nrules);
 185   short *merger = XMALLOC (short, nrules);
 186
 187   for (r = 0; r < nrules; ++r)
 188     {
 189       item_number_t *rhsp = NULL;
 190       /* Index of rule R in RHS. */
 191       prhs[r] = i;
 192       /* RHS of the rule R. */
 193       for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp)
 194         rhs[i++] = *rhsp;
 195       /* LHS of the rule R. */
 196       r1[r] = rules[r].lhs->number;
 197       /* Length of rule R's RHS. */
 198       r2[r] = i - prhs[r];
 199       /* Separator in RHS. */
 200       rhs[i++] = -1;
 201       /* Line where rule was defined. */
 202       rline[r] = rules[r].location.first_line;
 203       /* Dynamic precedence (GLR) */
 204       dprec[r] = rules[r].dprec;
 205       /* Merger-function index (GLR) */
 206       merger[r] = rules[r].merger;
 207     }
 208   assert (i == nritems);
 209
 210   muscle_insert_item_number_table ("rhs", rhs, ritem[0], 1, nritems);
 211   muscle_insert_unsigned_int_table ("prhs", prhs, 0, 0, nrules);
 212   muscle_insert_unsigned_int_table ("rline", rline, 0, 0, nrules);
 213   muscle_insert_symbol_number_table ("r1", r1, 0, 0, nrules);
 214   muscle_insert_unsigned_int_table ("r2", r2, 0, 0, nrules);
 215   muscle_insert_short_table ("dprec", dprec, 0, 0, nrules);
 216   muscle_insert_short_table ("merger", merger, 0, 0, nrules);
 217
 218   free (rhs);
 219   free (prhs);
 220   free (rline);
 221   free (r1);
 222   free (r2);
 223   free (dprec);
 224   free (merger);
 225 }
 226
 227 /*--------------------------------------------.
 228 | Prepare the muscles related to the states.  |
 229 `--------------------------------------------*/
 230
 231 static void
 232 prepare_states (void)
 233 {
 234   state_number_t i;
 235   symbol_number_t *values =
 236     (symbol_number_t *) alloca (sizeof (symbol_number_t) * nstates);
 237   for (i = 0; i < nstates; ++i)
 238     values[i] = states[i]->accessing_symbol;
 239   muscle_insert_symbol_number_table ("stos", values,
 240                                      0, 1, nstates);
 241 }
 242
 243
 244
 245 /*---------------------------------.
 246 | Output the user actions to OUT.  |
 247 `---------------------------------*/
 248
 249 static void
 250 user_actions_output (FILE *out)
 251 {
 252   rule_number_t r;
 253
 254   fputs ("m4_define([b4_actions], \n[[", out);
 255   for (r = 0; r < nrules; ++r)
 256     if (rules[r].action)
 257       {
 258         fprintf (out, "  case %d:\n", r + 1);
 259
 260         if (!no_lines_flag)
 261           fprintf (out, muscle_find ("linef"),
 262                    rules[r].action_location.first_line,
 263                    quotearg_style (c_quoting_style,
 264                                    muscle_find ("filename")));
 265         fprintf (out, "    %s\n    break;\n\n",
 266                  rules[r].action);
 267       }
 268   fputs ("]])\n\n", out);
 269 }
 270
 271 /*--------------------------------------.
 272 | Output the merge functions to OUT.   |
 273 `--------------------------------------*/
 274
 275 static void
 276 merger_output (FILE *out)
 277 {
 278   int n;
 279   merger_list* p;
 280
 281   fputs ("m4_define([b4_mergers], \n[[", out);
 282   for (n = 1, p = merge_functions; p != NULL; n += 1, p = p->next)
 283     {
 284       if (p->type[0] == '\0')
 285         fprintf (out, "  case %d: yyval = %s (*yy0, *yy1); break;\n",
 286                  n, p->name);
 287       else
 288         fprintf (out, "  case %d: yyval.%s = %s (*yy0, *yy1); break;\n",
 289                  n, p->type, p->name);
 290     }
 291   fputs ("]])\n\n", out);
 292 }
 293
 294 /*--------------------------------------.
 295 | Output the tokens definition to OUT.  |
 296 `--------------------------------------*/
 297
 298 static void
 299 token_definitions_output (FILE *out)
 300 {
 301   int i;
 302   int first = 1;
 303
 304   fputs ("m4_define([b4_tokens], \n[", out);
 305   for (i = 0; i < ntokens; ++i)
 306     {
 307       symbol_t *symbol = symbols[i];
 308       int number = symbol->user_token_number;
 309
 310       /* At this stage, if there are literal aliases, they are part of
 311          SYMBOLS, so we should not find symbols which are the aliases
 312          here.  */
 313       assert (number != USER_NUMBER_ALIAS);
 314
 315       /* Skip error token.  */
 316       if (symbol == errtoken)
 317         continue;
 318
 319       /* If this string has an alias, then it is necessarily the alias
 320          which is to be output.  */
 321       if (symbol->alias)
 322         symbol = symbol->alias;
 323
 324       /* Don't output literal chars or strings (when defined only as a
 325          string).  Note that must be done after the alias resolution:
 326          think about `%token 'f' "f"'.  */
 327       if (symbol->tag[0] == '\'' || symbol->tag[0] == '\"')
 328         continue;
 329
 330       /* Don't #define nonliteral tokens whose names contain periods
 331          or '$' (as does the default value of the EOF token).  */
 332       if (strchr (symbol->tag, '.') || strchr (symbol->tag, '$'))
 333         continue;
 334
 335       fprintf (out, "%s[[[%s]], [%d]]",
 336                first ? "" : ",\n", symbol->tag, number);
 337
 338       first = 0;
 339     }
 340   fputs ("])\n\n", out);
 341 }
 342
 343
 344 /*---------------------------------------.
 345 | Output the symbol destructors to OUT.  |
 346 `---------------------------------------*/
 347
 348 static void
 349 symbol_destructors_output (FILE *out)
 350 {
 351   int i;
 352   int first = 1;
 353
 354   fputs ("m4_define([b4_symbol_destructors], \n[", out);
 355   for (i = 0; i < nsyms; ++i)
 356     if (symbols[i]->destructor)
 357       {
 358         symbol_t *symbol = symbols[i];
 359
 360         /* Filename, lineno,
 361            Symbol-name, Symbol-number,
 362            destructor, typename. */
 363         fprintf (out, "%s[[[%s]], [[%d]], [[%s]], [[%d]], [[%s]], [[%s]]]",
 364                  first ? "" : ",\n",
 365                  infile, symbol->destructor_location.first_line,
 366                  symbol->tag,
 367                  symbol->number,
 368                  symbol->destructor,
 369                  symbol->type_name);
 370
 371         first = 0;
 372       }
 373   fputs ("])\n\n", out);
 374 }
 375
 376
 377 /*------------------------------------.
 378 | Output the symbol printers to OUT.  |
 379 `------------------------------------*/
 380
 381 static void
 382 symbol_printers_output (FILE *out)
 383 {
 384   int i;
 385   int first = 1;
 386
 387   fputs ("m4_define([b4_symbol_printers], \n[", out);
 388   for (i = 0; i < nsyms; ++i)
 389     if (symbols[i]->destructor)
 390       {
 391         symbol_t *symbol = symbols[i];
 392
 393         /* Filename, lineno,
 394            Symbol-name, Symbol-number,
 395            printer, typename. */
 396         fprintf (out, "%s[[[%s]], [[%d]], [[%s]], [[%d]], [[%s]], [[%s]]]",
 397                  first ? "" : ",\n",
 398                  infile, symbol->printer_location.first_line,
 399                  symbol->tag,
 400                  symbol->number,
 401                  symbol->printer,
 402                  symbol->type_name);
 403
 404         first = 0;
 405       }
 406   fputs ("])\n\n", out);
 407 }
 408
 409
 410 static void
 411 prepare_actions (void)
 412 {
 413   /* Figure out the actions for the specified state, indexed by
 414      lookahead token type.  */
 415
 416   muscle_insert_rule_number_table ("defact", yydefact,
 417                                    yydefact[0], 1, nstates);
 418
 419   /* Figure out what to do after reducing with each rule, depending on
 420      the saved state from before the beginning of parsing the data
 421      that matched this rule.  */
 422   muscle_insert_state_number_table ("defgoto", yydefgoto,
 423                                     yydefgoto[0], 1, nsyms - ntokens);
 424
 425
 426   /* Output PACT. */
 427   muscle_insert_base_table ("pact", base,
 428                              base[0], 1, nstates);
 429   MUSCLE_INSERT_INT ("pact_ninf", base_ninf);
 430
 431   /* Output PGOTO. */
 432   muscle_insert_base_table ("pgoto", base,
 433                              base[nstates], nstates + 1, nvectors);
 434
 435   muscle_insert_base_table ("table", table,
 436                             table[0], 1, high + 1);
 437   MUSCLE_INSERT_INT ("table_ninf", table_ninf);
 438
 439   muscle_insert_base_table ("check", check,
 440                             check[0], 1, high + 1);
 441
 442   /* GLR parsing slightly modifies YYTABLE and YYCHECK (and thus
 443      YYPACT) so that in states with unresolved conflicts, the default
 444      reduction is not used in the conflicted entries, so that there is
 445      a place to put a conflict pointer.
 446
 447      This means that YYCONFLP and YYCONFL are nonsense for a non-GLR
 448      parser, so we could avoid accidents by not writing them out in
 449      that case.  Nevertheless, it seems even better to be able to use
 450      the GLR skeletons even without the non-deterministic tables.  */
 451   muscle_insert_unsigned_int_table ("conflict_list_heads", conflict_table,
 452                                     conflict_table[0], 1, high+1);
 453   muscle_insert_unsigned_int_table ("conflicting_rules", conflict_list,
 454                                     conflict_list[0], 1, conflict_list_cnt);
 455 }
 456
 457 \f
 458 /*---------------------------.
 459 | Call the skeleton parser.  |
 460 `---------------------------*/
 461
 462 static void
 463 output_skeleton (void)
 464 {
 465   FILE *in;
 466   FILE *out;
 467   int filter_fd[2];
 468   char const *argv[7];
 469   pid_t pid;
 470
 471   /* Compute the names of the package data dir and skeleton file.
 472      Test whether m4sugar.m4 is readable, to check for proper
 473      installation.  A faulty installation can cause deadlock, so a
 474      cheap sanity check is worthwhile.  */
 475   char const m4sugar[] = "m4sugar/m4sugar.m4";
 476   char *full_path;
 477   char const *p;
 478   char const *m4 = (p = getenv ("M4")) ? p : M4;
 479   char const *pkgdatadir = (p = getenv ("BISON_PKGDATADIR")) ? p : PKGDATADIR;
 480   size_t skeleton_size = strlen (skeleton) + 1;
 481   size_t pkgdatadirlen = strlen (pkgdatadir);
 482   while (pkgdatadirlen && pkgdatadir[pkgdatadirlen - 1] == '/')
 483     pkgdatadirlen--;
 484   full_path = xmalloc (pkgdatadirlen + 1
 485                        + (skeleton_size < sizeof m4sugar
 486                           ? sizeof m4sugar : skeleton_size));
 487   strcpy (full_path, pkgdatadir);
 488   full_path[pkgdatadirlen] = '/';
 489   strcpy (full_path + pkgdatadirlen + 1, m4sugar);
 490   in = fopen (full_path, "r");
 491   if (! in || fclose (in) != 0)
 492     error (EXIT_FAILURE, errno, "%s", full_path);
 493   strcpy (full_path + pkgdatadirlen + 1, skeleton);
 494
 495   /* Create an m4 subprocess connected to us via two pipes.  */
 496
 497   if (trace_flag & trace_tools)
 498     fprintf (stderr, "running: %s -I %s %s - %s\n",
 499              m4, pkgdatadir, m4sugar, full_path);
 500
 501   argv[0] = m4;
 502   argv[1] = "-I";
 503   argv[2] = pkgdatadir;
 504   argv[3] = m4sugar;
 505   argv[4] = "-";
 506   argv[5] = full_path;
 507   argv[6] = NULL;
 508
 509   init_subpipe ();
 510   pid = create_subpipe (argv, filter_fd);
 511   free (full_path);
 512
 513   out = fdopen (filter_fd[0], "w");
 514   if (! out)
 515     error (EXIT_FAILURE, errno, "fdopen");
 516
 517   /* Output the definitions of all the muscles.  */
 518
 519   /* There are no comments, especially not `#': we do want M4 expansion
 520      after `#': think of CPP macros!  */
 521   fputs ("m4_changecom()\n", out);
 522   fputs ("m4_init()\n", out);
 523
 524   user_actions_output (out);
 525   merger_output (out);
 526   token_definitions_output (out);
 527   symbol_destructors_output (out);
 528   symbol_printers_output (out);
 529
 530   muscles_m4_output (out);
 531
 532   fputs ("m4_wrap([m4_divert_pop(0)])\n", out);
 533   fputs ("m4_divert_push(0)dnl\n", out);
 534   if (ferror (out))
 535     error (EXIT_FAILURE, 0, "pipe output error");
 536   xfclose (out);
 537
 538   /* Read and process m4's output.  */
 539   timevar_push (TV_M4);
 540   in = fdopen (filter_fd[1], "r");
 541   if (! in)
 542     error (EXIT_FAILURE, errno, "fdopen");
 543   scan_skel (in);
 544   if (ferror (in))
 545     error (EXIT_FAILURE, 0, "pipe input error");
 546   xfclose (in);
 547   reap_subpipe (pid, m4);
 548   timevar_pop (TV_M4);
 549 }
 550
 551 static void
 552 prepare (void)
 553 {
 554   /* Flags. */
 555   MUSCLE_INSERT_INT ("locations_flag", locations_flag);
 556   MUSCLE_INSERT_INT ("defines_flag", defines_flag);
 557   MUSCLE_INSERT_INT ("error_verbose", error_verbose);
 558   MUSCLE_INSERT_INT ("pure", pure_parser);
 559   MUSCLE_INSERT_INT ("debug", debug_flag);
 560
 561   /* FIXME: This is wrong: the muscles should decide whether they hold
 562      a copy or not, but the situation is too obscure currently.  */
 563   MUSCLE_INSERT_STRING ("prefix", spec_name_prefix ? spec_name_prefix : "yy");
 564   MUSCLE_INSERT_STRING ("output_infix", output_infix ? output_infix : "");
 565   MUSCLE_INSERT_STRING ("output_prefix", short_base_name);
 566   MUSCLE_INSERT_STRING ("output_parser_name", parser_file_name);
 567   MUSCLE_INSERT_STRING ("output_header_name", spec_defines_file);
 568
 569   /* Symbols. */
 570   MUSCLE_INSERT_INT ("tokens_number", ntokens);
 571   MUSCLE_INSERT_INT ("nterms_number", nvars);
 572   MUSCLE_INSERT_INT ("undef_token_number", undeftoken->number);
 573   MUSCLE_INSERT_INT ("user_token_number_max", max_user_token_number);
 574
 575   /* Rules. */
 576   MUSCLE_INSERT_INT ("rules_number", nrules);
 577
 578   /* States. */
 579   MUSCLE_INSERT_INT ("last", high);
 580   MUSCLE_INSERT_INT ("final_state_number", final_state->number);
 581   MUSCLE_INSERT_INT ("states_number", nstates);
 582
 583   /* User Code.  */
 584   obstack_1grow (&pre_prologue_obstack, 0);
 585   obstack_1grow (&post_prologue_obstack, 0);
 586   muscle_insert ("pre_prologue", obstack_finish (&pre_prologue_obstack));
 587   muscle_insert ("post_prologue", obstack_finish (&post_prologue_obstack));
 588
 589   /* Find the right skeleton file.  */
 590   if (!skeleton)
 591     {
 592       if (glr_parser)
 593         skeleton = "glr.c";
 594       else
 595         skeleton = "yacc.c";
 596     }
 597
 598   /* Parse the skeleton file and output the needed parsers.  */
 599   MUSCLE_INSERT_STRING ("skeleton", skeleton);
 600 }
 601
 602
 603 /*----------------------------------------------------------.
 604 | Output the parsing tables and the parser code to ftable.  |
 605 `----------------------------------------------------------*/
 606
 607 void
 608 output (void)
 609 {
 610   obstack_init (&format_obstack);
 611
 612   prepare_tokens ();
 613   prepare_rules ();
 614   prepare_states ();
 615   prepare_actions ();
 616
 617   prepare ();
 618
 619   /* Process the selected skeleton file.  */
 620   output_skeleton ();
 621
 622   obstack_free (&format_obstack, NULL);
 623   obstack_free (&pre_prologue_obstack, NULL);
 624   obstack_free (&post_prologue_obstack, NULL);
 625 }