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.first_line;
 233       /* Dynamic precedence (GLR) */
 234       dprec[r] = rules[r].dprec;
 235       /* Merger-function index (GLR) */
 236       merger[r] = rules[r].merger;
 237     }
 238   assert (i == nritems);
 239
 240   muscle_insert_item_number_table ("rhs", rhs, ritem[0], 1, nritems);
 241   muscle_insert_unsigned_int_table ("prhs", prhs, 0, 0, nrules);
 242   muscle_insert_unsigned_int_table ("rline", rline, 0, 0, nrules);
 243   muscle_insert_symbol_number_table ("r1", r1, 0, 0, nrules);
 244   muscle_insert_unsigned_int_table ("r2", r2, 0, 0, nrules);
 245   muscle_insert_short_table ("dprec", dprec, 0, 0, nrules);
 246   muscle_insert_short_table ("merger", merger, 0, 0, nrules);
 247
 248   MUSCLE_INSERT_INT ("rules_number", nrules);
 249
 250   free (rhs);
 251   free (prhs);
 252   free (rline);
 253   free (r1);
 254   free (r2);
 255   free (dprec);
 256   free (merger);
 257 }
 258
 259 /*--------------------------------------------.
 260 | Prepare the muscles related to the states.  |
 261 `--------------------------------------------*/
 262
 263 static void
 264 prepare_states (void)
 265 {
 266   state_number_t i;
 267   symbol_number_t *values =
 268     (symbol_number_t *) alloca (sizeof (symbol_number_t) * nstates);
 269   for (i = 0; i < nstates; ++i)
 270     values[i] = states[i]->accessing_symbol;
 271   muscle_insert_symbol_number_table ("stos", values,
 272                                      0, 1, nstates);
 273
 274   MUSCLE_INSERT_INT ("last", high);
 275   MUSCLE_INSERT_INT ("final_state_number", final_state->number);
 276   MUSCLE_INSERT_INT ("states_number", nstates);
 277 }
 278
 279
 280
 281 /*---------------------------------.
 282 | Output the user actions to OUT.  |
 283 `---------------------------------*/
 284
 285 static void
 286 user_actions_output (FILE *out)
 287 {
 288   rule_number_t r;
 289
 290   fputs ("m4_define([b4_actions], \n[[", out);
 291   for (r = 0; r < nrules; ++r)
 292     if (rules[r].action)
 293       {
 294         fprintf (out, "  case %d:\n", r + 1);
 295
 296         fprintf (out, "]b4_syncline([[%d]], ",
 297                  rules[r].action_location.first_line);
 298         escaped_file_name_output (out, rules[r].action_location.file);
 299         fprintf (out, ")[\n");
 300         fprintf (out, "    %s\n    break;\n\n",
 301                  rules[r].action);
 302       }
 303   fputs ("]])\n\n", out);
 304 }
 305
 306 /*--------------------------------------.
 307 | Output the merge functions to OUT.   |
 308 `--------------------------------------*/
 309
 310 static void
 311 merger_output (FILE *out)
 312 {
 313   int n;
 314   merger_list* p;
 315
 316   fputs ("m4_define([b4_mergers], \n[[", out);
 317   for (n = 1, p = merge_functions; p != NULL; n += 1, p = p->next)
 318     {
 319       if (p->type[0] == '\0')
 320         fprintf (out, "  case %d: yyval = %s (*yy0, *yy1); break;\n",
 321                  n, p->name);
 322       else
 323         fprintf (out, "  case %d: yyval.%s = %s (*yy0, *yy1); break;\n",
 324                  n, p->type, p->name);
 325     }
 326   fputs ("]])\n\n", out);
 327 }
 328
 329 /*--------------------------------------.
 330 | Output the tokens definition to OUT.  |
 331 `--------------------------------------*/
 332
 333 static void
 334 token_definitions_output (FILE *out)
 335 {
 336   int i;
 337   int first = 1;
 338
 339   fputs ("m4_define([b4_tokens], \n[", out);
 340   for (i = 0; i < ntokens; ++i)
 341     {
 342       symbol_t *symbol = symbols[i];
 343       int number = symbol->user_token_number;
 344
 345       /* At this stage, if there are literal aliases, they are part of
 346          SYMBOLS, so we should not find symbols which are the aliases
 347          here.  */
 348       assert (number != USER_NUMBER_ALIAS);
 349
 350       /* Skip error token.  */
 351       if (symbol == errtoken)
 352         continue;
 353
 354       /* If this string has an alias, then it is necessarily the alias
 355          which is to be output.  */
 356       if (symbol->alias)
 357         symbol = symbol->alias;
 358
 359       /* Don't output literal chars or strings (when defined only as a
 360          string).  Note that must be done after the alias resolution:
 361          think about `%token 'f' "f"'.  */
 362       if (symbol->tag[0] == '\'' || symbol->tag[0] == '\"')
 363         continue;
 364
 365       /* Don't #define nonliteral tokens whose names contain periods
 366          or '$' (as does the default value of the EOF token).  */
 367       if (strchr (symbol->tag, '.') || strchr (symbol->tag, '$'))
 368         continue;
 369
 370       fprintf (out, "%s[[[%s]], [%d]]",
 371                first ? "" : ",\n", symbol->tag, number);
 372
 373       first = 0;
 374     }
 375   fputs ("])\n\n", out);
 376 }
 377
 378
 379 /*---------------------------------------.
 380 | Output the symbol destructors to OUT.  |
 381 `---------------------------------------*/
 382
 383 static void
 384 symbol_destructors_output (FILE *out)
 385 {
 386   int i;
 387   int first = 1;
 388
 389   fputs ("m4_define([b4_symbol_destructors], \n[", out);
 390   for (i = 0; i < nsyms; ++i)
 391     if (symbols[i]->destructor)
 392       {
 393         symbol_t *symbol = symbols[i];
 394
 395         /* Filename, lineno,
 396            Symbol-name, Symbol-number,
 397            destructor, typename. */
 398         fprintf (out, "%s[",
 399                  first ? "" : ",\n");
 400         escaped_file_name_output (out, symbol->destructor_location.file);
 401         fprintf (out, ", [[%d]], [[%s]], [[%d]], [[%s]], [[%s]]]",
 402                  symbol->destructor_location.first_line,
 403                  symbol->tag,
 404                  symbol->number,
 405                  symbol->destructor,
 406                  symbol->type_name);
 407
 408         first = 0;
 409       }
 410   fputs ("])\n\n", out);
 411 }
 412
 413
 414 /*------------------------------------.
 415 | Output the symbol printers to OUT.  |
 416 `------------------------------------*/
 417
 418 static void
 419 symbol_printers_output (FILE *out)
 420 {
 421   int i;
 422   int first = 1;
 423
 424   fputs ("m4_define([b4_symbol_printers], \n[", out);
 425   for (i = 0; i < nsyms; ++i)
 426     if (symbols[i]->destructor)
 427       {
 428         symbol_t *symbol = symbols[i];
 429
 430         /* Filename, lineno,
 431            Symbol-name, Symbol-number,
 432            printer, typename. */
 433         fprintf (out, "%s[",
 434                  first ? "" : ",\n");
 435         escaped_file_name_output (out, symbol->printer_location.file);
 436         fprintf (out, ", [[%d]], [[%s]], [[%d]], [[%s]], [[%s]]]",
 437                  symbol->printer_location.first_line,
 438                  symbol->tag,
 439                  symbol->number,
 440                  symbol->printer,
 441                  symbol->type_name);
 442
 443         first = 0;
 444       }
 445   fputs ("])\n\n", out);
 446 }
 447
 448
 449 static void
 450 prepare_actions (void)
 451 {
 452   /* Figure out the actions for the specified state, indexed by
 453      lookahead token type.  */
 454
 455   muscle_insert_rule_number_table ("defact", yydefact,
 456                                    yydefact[0], 1, nstates);
 457
 458   /* Figure out what to do after reducing with each rule, depending on
 459      the saved state from before the beginning of parsing the data
 460      that matched this rule.  */
 461   muscle_insert_state_number_table ("defgoto", yydefgoto,
 462                                     yydefgoto[0], 1, nsyms - ntokens);
 463
 464
 465   /* Output PACT. */
 466   muscle_insert_base_table ("pact", base,
 467                              base[0], 1, nstates);
 468   MUSCLE_INSERT_INT ("pact_ninf", base_ninf);
 469
 470   /* Output PGOTO. */
 471   muscle_insert_base_table ("pgoto", base,
 472                              base[nstates], nstates + 1, nvectors);
 473
 474   muscle_insert_base_table ("table", table,
 475                             table[0], 1, high + 1);
 476   MUSCLE_INSERT_INT ("table_ninf", table_ninf);
 477
 478   muscle_insert_base_table ("check", check,
 479                             check[0], 1, high + 1);
 480
 481   /* GLR parsing slightly modifies YYTABLE and YYCHECK (and thus
 482      YYPACT) so that in states with unresolved conflicts, the default
 483      reduction is not used in the conflicted entries, so that there is
 484      a place to put a conflict pointer.
 485
 486      This means that YYCONFLP and YYCONFL are nonsense for a non-GLR
 487      parser, so we could avoid accidents by not writing them out in
 488      that case.  Nevertheless, it seems even better to be able to use
 489      the GLR skeletons even without the non-deterministic tables.  */
 490   muscle_insert_unsigned_int_table ("conflict_list_heads", conflict_table,
 491                                     conflict_table[0], 1, high + 1);
 492   muscle_insert_unsigned_int_table ("conflicting_rules", conflict_list,
 493                                     conflict_list[0], 1, conflict_list_cnt);
 494 }
 495
 496 \f
 497 /*---------------------------.
 498 | Call the skeleton parser.  |
 499 `---------------------------*/
 500
 501 static void
 502 output_skeleton (void)
 503 {
 504   FILE *in;
 505   FILE *out;
 506   int filter_fd[2];
 507   char const *argv[7];
 508   pid_t pid;
 509
 510   /* Compute the names of the package data dir and skeleton file.
 511      Test whether m4sugar.m4 is readable, to check for proper
 512      installation.  A faulty installation can cause deadlock, so a
 513      cheap sanity check is worthwhile.  */
 514   char const m4sugar[] = "m4sugar/m4sugar.m4";
 515   char *full_path;
 516   char const *p;
 517   char const *m4 = (p = getenv ("M4")) ? p : M4;
 518   char const *pkgdatadir = (p = getenv ("BISON_PKGDATADIR")) ? p : PKGDATADIR;
 519   size_t skeleton_size = strlen (skeleton) + 1;
 520   size_t pkgdatadirlen = strlen (pkgdatadir);
 521   while (pkgdatadirlen && pkgdatadir[pkgdatadirlen - 1] == '/')
 522     pkgdatadirlen--;
 523   full_path = xmalloc (pkgdatadirlen + 1
 524                        + (skeleton_size < sizeof m4sugar
 525                           ? sizeof m4sugar : skeleton_size));
 526   strcpy (full_path, pkgdatadir);
 527   full_path[pkgdatadirlen] = '/';
 528   strcpy (full_path + pkgdatadirlen + 1, m4sugar);
 529   in = fopen (full_path, "r");
 530   if (! in)
 531     error (EXIT_FAILURE, errno, "%s", full_path);
 532   xfclose (in);
 533   strcpy (full_path + pkgdatadirlen + 1, skeleton);
 534
 535   /* Create an m4 subprocess connected to us via two pipes.  */
 536
 537   if (trace_flag & trace_tools)
 538     fprintf (stderr, "running: %s -I %s %s - %s\n",
 539              m4, pkgdatadir, m4sugar, full_path);
 540
 541   argv[0] = m4;
 542   argv[1] = "-I";
 543   argv[2] = pkgdatadir;
 544   argv[3] = m4sugar;
 545   argv[4] = "-";
 546   argv[5] = full_path;
 547   argv[6] = NULL;
 548
 549   init_subpipe ();
 550   pid = create_subpipe (argv, filter_fd);
 551   free (full_path);
 552
 553   out = fdopen (filter_fd[0], "w");
 554   if (! out)
 555     error (EXIT_FAILURE, errno, "fdopen");
 556
 557   /* Output the definitions of all the muscles.  */
 558   fputs ("m4_init()\n", out);
 559
 560   user_actions_output (out);
 561   merger_output (out);
 562   token_definitions_output (out);
 563   symbol_destructors_output (out);
 564   symbol_printers_output (out);
 565
 566   muscles_m4_output (out);
 567
 568   fputs ("m4_wrap([m4_divert_pop(0)])\n", out);
 569   fputs ("m4_divert_push(0)dnl\n", out);
 570   xfclose (out);
 571
 572   /* Read and process m4's output.  */
 573   timevar_push (TV_M4);
 574   in = fdopen (filter_fd[1], "r");
 575   if (! in)
 576     error (EXIT_FAILURE, errno, "fdopen");
 577   scan_skel (in);
 578   xfclose (in);
 579   reap_subpipe (pid, m4);
 580   timevar_pop (TV_M4);
 581 }
 582
 583 static void
 584 prepare (void)
 585 {
 586   /* Flags. */
 587   MUSCLE_INSERT_INT ("debug", debug_flag);
 588   MUSCLE_INSERT_INT ("defines_flag", defines_flag);
 589   MUSCLE_INSERT_INT ("error_verbose", error_verbose);
 590   MUSCLE_INSERT_INT ("locations_flag", locations_flag);
 591   MUSCLE_INSERT_INT ("pure", pure_parser);
 592   MUSCLE_INSERT_INT ("synclines_flag", !no_lines_flag);
 593
 594   /* FIXME: This is wrong: the muscles should decide whether they hold
 595      a copy or not, but the situation is too obscure currently.  */
 596   MUSCLE_INSERT_STRING ("prefix", spec_name_prefix ? spec_name_prefix : "yy");
 597
 598   /* User Code.  */
 599   obstack_1grow (&pre_prologue_obstack, 0);
 600   obstack_1grow (&post_prologue_obstack, 0);
 601   muscle_insert ("pre_prologue", obstack_finish (&pre_prologue_obstack));
 602   muscle_insert ("post_prologue", obstack_finish (&post_prologue_obstack));
 603
 604   /* Find the right skeleton file.  */
 605   if (!skeleton)
 606     {
 607       if (glr_parser)
 608         skeleton = "glr.c";
 609       else
 610         skeleton = "yacc.c";
 611     }
 612
 613   /* Parse the skeleton file and output the needed parsers.  */
 614   MUSCLE_INSERT_C_STRING ("skeleton", skeleton);
 615 }
 616
 617
 618 /*----------------------------------------------------------.
 619 | Output the parsing tables and the parser code to ftable.  |
 620 `----------------------------------------------------------*/
 621
 622 void
 623 output (void)
 624 {
 625   obstack_init (&format_obstack);
 626
 627   prepare_symbols ();
 628   prepare_rules ();
 629   prepare_states ();
 630   prepare_actions ();
 631
 632   prepare ();
 633
 634   /* Process the selected skeleton file.  */
 635   output_skeleton ();
 636
 637   obstack_free (&format_obstack, NULL);
 638   obstack_free (&pre_prologue_obstack, NULL);
 639   obstack_free (&post_prologue_obstack, NULL);
 640 }