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 | Print to OUT a representation of FILENAME escaped both for C and M4.  |
 112 `----------------------------------------------------------------------*/
 113
 114 static void
 115 escaped_file_name_output (FILE *out, char const *filename)
 116 {
 117   char const *p;
 118   fprintf (out, "[[");
 119
 120   for (p = quotearg_style (c_quoting_style, filename); *p; p++)
 121     switch (*p)
 122       {
 123       case '$': fputs ("$][", out); break;
 124       case '@': fputs ("@@",  out); break;
 125       case '[': fputs ("@{",  out); break;
 126       case ']': fputs ("@}",  out); break;
 127       default: fputc (*p, out); break;
 128       }
 129
 130   fprintf (out, "]]");
 131 }
 132
 133
 134 /*------------------------------------------------------------------.
 135 | Prepare the muscles related to the symbols: translate, tname, and |
 136 | toknum.                                                           |
 137 `------------------------------------------------------------------*/
 138
 139 static void
 140 prepare_symbols (void)
 141 {
 142   MUSCLE_INSERT_INT ("tokens_number", ntokens);
 143   MUSCLE_INSERT_INT ("nterms_number", nvars);
 144   MUSCLE_INSERT_INT ("undef_token_number", undeftoken->number);
 145   MUSCLE_INSERT_INT ("user_token_number_max", max_user_token_number);
 146
 147   muscle_insert_symbol_number_table ("translate",
 148                                      token_translations,
 149                                      token_translations[0],
 150                                      1, max_user_token_number + 1);
 151
 152   /* tname -- token names.  */
 153   {
 154     int i;
 155     int j = 0;
 156     for (i = 0; i < nsyms; i++)
 157       {
 158         /* Be sure not to use twice the same QUOTEARG slot:
 159            SYMBOL_TAG_GET uses slot 0.  */
 160         const char *cp =
 161           quotearg_n_style (1, c_quoting_style,
 162                             symbols[i]->tag);
 163         /* Width of the next token, including the two quotes, the comma
 164            and the space.  */
 165         int strsize = strlen (cp) + 2;
 166
 167         if (j + strsize > 75)
 168           {
 169             obstack_sgrow (&format_obstack, "\n  ");
 170             j = 2;
 171           }
 172
 173         MUSCLE_OBSTACK_SGROW (&format_obstack, cp);
 174         obstack_sgrow (&format_obstack, ", ");
 175         j += strsize;
 176       }
 177     /* Add a NULL entry to list of tokens (well, 0, as NULL might not be
 178        defined).  */
 179     obstack_sgrow (&format_obstack, "0");
 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 = XCALLOC (int, ntokens);
 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_t r;
 208   unsigned int i = 0;
 209   item_number_t *rhs = XMALLOC (item_number_t, nritems);
 210   unsigned int *prhs = XMALLOC (unsigned int, nrules);
 211   unsigned int *rline = XMALLOC (unsigned int, nrules);
 212   symbol_number_t *r1 = XMALLOC (symbol_number_t, nrules);
 213   unsigned int *r2 = XMALLOC (unsigned int, nrules);
 214   short *dprec = XMALLOC (short, nrules);
 215   short *merger = XMALLOC (short, nrules);
 216
 217   for (r = 0; r < nrules; ++r)
 218     {
 219       item_number_t *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   if (i != nritems)
 239     abort ();
 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_short_table ("dprec", dprec, 0, 0, nrules);
 247   muscle_insert_short_table ("merger", merger, 0, 0, nrules);
 248
 249   MUSCLE_INSERT_INT ("rules_number", nrules);
 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_t i;
 268   symbol_number_t *values =
 269     (symbol_number_t *) alloca (sizeof (symbol_number_t) * nstates);
 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
 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_t 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, "  case %d:\n", r + 1);
 296
 297         fprintf (out, "]b4_syncline([[%d]], ",
 298                  rules[r].action_location.start.line);
 299         escaped_file_name_output (out, rules[r].action_location.start.file);
 300         fprintf (out, ")[\n");
 301         fprintf (out, "    %s\n    break;\n\n",
 302                  rules[r].action);
 303       }
 304   fputs ("]])\n\n", out);
 305 }
 306
 307 /*--------------------------------------.
 308 | Output the merge functions to OUT.   |
 309 `--------------------------------------*/
 310
 311 static void
 312 merger_output (FILE *out)
 313 {
 314   int n;
 315   merger_list* p;
 316
 317   fputs ("m4_define([b4_mergers], \n[[", out);
 318   for (n = 1, p = merge_functions; p != NULL; n += 1, p = p->next)
 319     {
 320       if (p->type[0] == '\0')
 321         fprintf (out, "  case %d: yyval = %s (*yy0, *yy1); break;\n",
 322                  n, p->name);
 323       else
 324         fprintf (out, "  case %d: yyval.%s = %s (*yy0, *yy1); break;\n",
 325                  n, p->type, p->name);
 326     }
 327   fputs ("]])\n\n", out);
 328 }
 329
 330 /*--------------------------------------.
 331 | Output the tokens definition to OUT.  |
 332 `--------------------------------------*/
 333
 334 static void
 335 token_definitions_output (FILE *out)
 336 {
 337   int i;
 338   int first = 1;
 339
 340   fputs ("m4_define([b4_tokens], \n[", out);
 341   for (i = 0; i < ntokens; ++i)
 342     {
 343       symbol_t *symbol = symbols[i];
 344       int number = symbol->user_token_number;
 345
 346       /* At this stage, if there are literal aliases, they are part of
 347          SYMBOLS, so we should not find symbols which are the aliases
 348          here.  */
 349       if (number == USER_NUMBER_ALIAS)
 350         abort ();
 351
 352       /* Skip error token.  */
 353       if (symbol == 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 (symbol->alias)
 359         symbol = symbol->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 (symbol->tag[0] == '\'' || symbol->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 (symbol->tag, '.') || strchr (symbol->tag, '$'))
 370         continue;
 371
 372       fprintf (out, "%s[[[%s]], [%d]]",
 373                first ? "" : ",\n", symbol->tag, number);
 374
 375       first = 0;
 376     }
 377   fputs ("])\n\n", out);
 378 }
 379
 380
 381 /*---------------------------------------.
 382 | Output the symbol destructors to OUT.  |
 383 `---------------------------------------*/
 384
 385 static void
 386 symbol_destructors_output (FILE *out)
 387 {
 388   int i;
 389   int first = 1;
 390
 391   fputs ("m4_define([b4_symbol_destructors], \n[", out);
 392   for (i = 0; i < nsyms; ++i)
 393     if (symbols[i]->destructor)
 394       {
 395         symbol_t *symbol = symbols[i];
 396
 397         /* Filename, lineno,
 398            Symbol-name, Symbol-number,
 399            destructor, typename. */
 400         fprintf (out, "%s[",
 401                  first ? "" : ",\n");
 402         escaped_file_name_output (out, symbol->destructor_location.start.file);
 403         fprintf (out, ", [[%d]], [[%s]], [[%d]], [[%s]], [[%s]]]",
 404                  symbol->destructor_location.start.line,
 405                  symbol->tag,
 406                  symbol->number,
 407                  symbol->destructor,
 408                  symbol->type_name);
 409
 410         first = 0;
 411       }
 412   fputs ("])\n\n", out);
 413 }
 414
 415
 416 /*------------------------------------.
 417 | Output the symbol printers to OUT.  |
 418 `------------------------------------*/
 419
 420 static void
 421 symbol_printers_output (FILE *out)
 422 {
 423   int i;
 424   int first = 1;
 425
 426   fputs ("m4_define([b4_symbol_printers], \n[", out);
 427   for (i = 0; i < nsyms; ++i)
 428     if (symbols[i]->destructor)
 429       {
 430         symbol_t *symbol = symbols[i];
 431
 432         /* Filename, lineno,
 433            Symbol-name, Symbol-number,
 434            printer, typename. */
 435         fprintf (out, "%s[",
 436                  first ? "" : ",\n");
 437         escaped_file_name_output (out, symbol->printer_location.start.file);
 438         fprintf (out, ", [[%d]], [[%s]], [[%d]], [[%s]], [[%s]]]",
 439                  symbol->printer_location.start.line,
 440                  symbol->tag,
 441                  symbol->number,
 442                  symbol->printer,
 443                  symbol->type_name);
 444
 445         first = 0;
 446       }
 447   fputs ("])\n\n", out);
 448 }
 449
 450
 451 static void
 452 prepare_actions (void)
 453 {
 454   /* Figure out the actions for the specified state, indexed by
 455      lookahead token type.  */
 456
 457   muscle_insert_rule_number_table ("defact", yydefact,
 458                                    yydefact[0], 1, nstates);
 459
 460   /* Figure out what to do after reducing with each rule, depending on
 461      the saved state from before the beginning of parsing the data
 462      that matched this rule.  */
 463   muscle_insert_state_number_table ("defgoto", yydefgoto,
 464                                     yydefgoto[0], 1, nsyms - ntokens);
 465
 466
 467   /* Output PACT. */
 468   muscle_insert_base_table ("pact", base,
 469                              base[0], 1, nstates);
 470   MUSCLE_INSERT_INT ("pact_ninf", base_ninf);
 471
 472   /* Output PGOTO. */
 473   muscle_insert_base_table ("pgoto", base,
 474                              base[nstates], nstates + 1, nvectors);
 475
 476   muscle_insert_base_table ("table", table,
 477                             table[0], 1, high + 1);
 478   MUSCLE_INSERT_INT ("table_ninf", table_ninf);
 479
 480   muscle_insert_base_table ("check", check,
 481                             check[0], 1, high + 1);
 482
 483   /* GLR parsing slightly modifies YYTABLE and YYCHECK (and thus
 484      YYPACT) so that in states with unresolved conflicts, the default
 485      reduction is not used in the conflicted entries, so that there is
 486      a place to put a conflict pointer.
 487
 488      This means that YYCONFLP and YYCONFL are nonsense for a non-GLR
 489      parser, so we could avoid accidents by not writing them out in
 490      that case.  Nevertheless, it seems even better to be able to use
 491      the GLR skeletons even without the non-deterministic tables.  */
 492   muscle_insert_unsigned_int_table ("conflict_list_heads", conflict_table,
 493                                     conflict_table[0], 1, high + 1);
 494   muscle_insert_unsigned_int_table ("conflicting_rules", conflict_list,
 495                                     conflict_list[0], 1, conflict_list_cnt);
 496 }
 497
 498 \f
 499 /*---------------------------.
 500 | Call the skeleton parser.  |
 501 `---------------------------*/
 502
 503 static void
 504 output_skeleton (void)
 505 {
 506   FILE *in;
 507   FILE *out;
 508   int filter_fd[2];
 509   char const *argv[7];
 510   pid_t pid;
 511
 512   /* Compute the names of the package data dir and skeleton file.
 513      Test whether m4sugar.m4 is readable, to check for proper
 514      installation.  A faulty installation can cause deadlock, so a
 515      cheap sanity check is worthwhile.  */
 516   char const m4sugar[] = "m4sugar/m4sugar.m4";
 517   char *full_path;
 518   char const *p;
 519   char const *m4 = (p = getenv ("M4")) ? p : M4;
 520   char const *pkgdatadir = (p = getenv ("BISON_PKGDATADIR")) ? p : PKGDATADIR;
 521   size_t skeleton_size = strlen (skeleton) + 1;
 522   size_t pkgdatadirlen = strlen (pkgdatadir);
 523   while (pkgdatadirlen && pkgdatadir[pkgdatadirlen - 1] == '/')
 524     pkgdatadirlen--;
 525   full_path = xmalloc (pkgdatadirlen + 1
 526                        + (skeleton_size < sizeof m4sugar
 527                           ? sizeof m4sugar : skeleton_size));
 528   strcpy (full_path, pkgdatadir);
 529   full_path[pkgdatadirlen] = '/';
 530   strcpy (full_path + pkgdatadirlen + 1, m4sugar);
 531   xfclose (xfopen (full_path, "r"));
 532   strcpy (full_path + pkgdatadirlen + 1, skeleton);
 533
 534   /* Create an m4 subprocess connected to us via two pipes.  */
 535
 536   if (trace_flag & trace_tools)
 537     fprintf (stderr, "running: %s -I %s %s - %s\n",
 538              m4, pkgdatadir, m4sugar, full_path);
 539
 540   argv[0] = m4;
 541   argv[1] = "-I";
 542   argv[2] = pkgdatadir;
 543   argv[3] = m4sugar;
 544   argv[4] = "-";
 545   argv[5] = full_path;
 546   argv[6] = NULL;
 547
 548   init_subpipe ();
 549   pid = create_subpipe (argv, filter_fd);
 550   free (full_path);
 551
 552   out = fdopen (filter_fd[0], "w");
 553   if (! out)
 554     error (EXIT_FAILURE, errno, "fdopen");
 555
 556   /* Output the definitions of all the muscles.  */
 557   fputs ("m4_init()\n", out);
 558
 559   user_actions_output (out);
 560   merger_output (out);
 561   token_definitions_output (out);
 562   symbol_destructors_output (out);
 563   symbol_printers_output (out);
 564
 565   muscles_m4_output (out);
 566
 567   fputs ("m4_wrap([m4_divert_pop(0)])\n", out);
 568   fputs ("m4_divert_push(0)dnl\n", out);
 569   xfclose (out);
 570
 571   /* Read and process m4's output.  */
 572   timevar_push (TV_M4);
 573   in = fdopen (filter_fd[1], "r");
 574   if (! in)
 575     error (EXIT_FAILURE, errno, "fdopen");
 576   scan_skel (in);
 577   xfclose (in);
 578   reap_subpipe (pid, m4);
 579   timevar_pop (TV_M4);
 580 }
 581
 582 static void
 583 prepare (void)
 584 {
 585   /* Flags. */
 586   MUSCLE_INSERT_INT ("debug", debug_flag);
 587   MUSCLE_INSERT_INT ("defines_flag", defines_flag);
 588   MUSCLE_INSERT_INT ("error_verbose", error_verbose);
 589   MUSCLE_INSERT_INT ("locations_flag", locations_flag);
 590   MUSCLE_INSERT_INT ("pure", pure_parser);
 591   MUSCLE_INSERT_INT ("synclines_flag", !no_lines_flag);
 592
 593   /* File names.  */
 594   MUSCLE_INSERT_STRING ("prefix", spec_name_prefix ? spec_name_prefix : "yy");
 595
 596   /* User Code.  */
 597   obstack_1grow (&pre_prologue_obstack, 0);
 598   obstack_1grow (&post_prologue_obstack, 0);
 599   muscle_insert ("pre_prologue", obstack_finish (&pre_prologue_obstack));
 600   muscle_insert ("post_prologue", obstack_finish (&post_prologue_obstack));
 601
 602   /* Find the right skeleton file.  */
 603   if (!skeleton)
 604     {
 605       if (glr_parser)
 606         skeleton = "glr.c";
 607       else
 608         skeleton = "yacc.c";
 609     }
 610
 611   /* Parse the skeleton file and output the needed parsers.  */
 612   MUSCLE_INSERT_C_STRING ("skeleton", skeleton);
 613 }
 614
 615
 616 /*----------------------------------------------------------.
 617 | Output the parsing tables and the parser code to ftable.  |
 618 `----------------------------------------------------------*/
 619
 620 void
 621 output (void)
 622 {
 623   obstack_init (&format_obstack);
 624
 625   prepare_symbols ();
 626   prepare_rules ();
 627   prepare_states ();
 628   prepare_actions ();
 629
 630   prepare ();
 631
 632   /* Process the selected skeleton file.  */
 633   output_skeleton ();
 634
 635   obstack_free (&format_obstack, NULL);
 636   obstack_free (&pre_prologue_obstack, NULL);
 637   obstack_free (&post_prologue_obstack, NULL);
 638 }