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