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