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)
 504     error (EXIT_FAILURE, errno, "%s", full_path);
 505   xfclose (in);
 506   strcpy (full_path + pkgdatadirlen + 1, skeleton);
 507
 508   /* Create an m4 subprocess connected to us via two pipes.  */
 509
 510   if (trace_flag & trace_tools)
 511     fprintf (stderr, "running: %s -I %s %s - %s\n",
 512              m4, pkgdatadir, m4sugar, full_path);
 513
 514   argv[0] = m4;
 515   argv[1] = "-I";
 516   argv[2] = pkgdatadir;
 517   argv[3] = m4sugar;
 518   argv[4] = "-";
 519   argv[5] = full_path;
 520   argv[6] = NULL;
 521
 522   init_subpipe ();
 523   pid = create_subpipe (argv, filter_fd);
 524   free (full_path);
 525
 526   out = fdopen (filter_fd[0], "w");
 527   if (! out)
 528     error (EXIT_FAILURE, errno, "fdopen");
 529
 530   /* Output the definitions of all the muscles.  */
 531   fputs ("m4_init()\n", out);
 532
 533   user_actions_output (out);
 534   merger_output (out);
 535   token_definitions_output (out);
 536   symbol_destructors_output (out);
 537   symbol_printers_output (out);
 538
 539   muscles_m4_output (out);
 540
 541   fputs ("m4_wrap([m4_divert_pop(0)])\n", out);
 542   fputs ("m4_divert_push(0)dnl\n", out);
 543   xfclose (out);
 544
 545   /* Read and process m4's output.  */
 546   timevar_push (TV_M4);
 547   in = fdopen (filter_fd[1], "r");
 548   if (! in)
 549     error (EXIT_FAILURE, errno, "fdopen");
 550   scan_skel (in);
 551   xfclose (in);
 552   reap_subpipe (pid, m4);
 553   timevar_pop (TV_M4);
 554 }
 555
 556 static void
 557 prepare (void)
 558 {
 559   /* Flags. */
 560   MUSCLE_INSERT_INT ("locations_flag", locations_flag);
 561   MUSCLE_INSERT_INT ("defines_flag", defines_flag);
 562   MUSCLE_INSERT_INT ("error_verbose", error_verbose);
 563   MUSCLE_INSERT_INT ("pure", pure_parser);
 564   MUSCLE_INSERT_INT ("debug", debug_flag);
 565
 566   /* FIXME: This is wrong: the muscles should decide whether they hold
 567      a copy or not, but the situation is too obscure currently.  */
 568   MUSCLE_INSERT_STRING ("prefix", spec_name_prefix ? spec_name_prefix : "yy");
 569   MUSCLE_INSERT_STRING ("output_infix", output_infix ? output_infix : "");
 570   MUSCLE_INSERT_STRING ("output_prefix", short_base_name);
 571   MUSCLE_INSERT_STRING ("output_parser_name", parser_file_name);
 572   MUSCLE_INSERT_STRING ("output_header_name", spec_defines_file);
 573
 574   /* User Code.  */
 575   obstack_1grow (&pre_prologue_obstack, 0);
 576   obstack_1grow (&post_prologue_obstack, 0);
 577   muscle_insert ("pre_prologue", obstack_finish (&pre_prologue_obstack));
 578   muscle_insert ("post_prologue", obstack_finish (&post_prologue_obstack));
 579
 580   /* Find the right skeleton file.  */
 581   if (!skeleton)
 582     {
 583       if (glr_parser)
 584         skeleton = "glr.c";
 585       else
 586         skeleton = "yacc.c";
 587     }
 588
 589   /* Parse the skeleton file and output the needed parsers.  */
 590   MUSCLE_INSERT_STRING ("skeleton", skeleton);
 591 }
 592
 593
 594 /*----------------------------------------------------------.
 595 | Output the parsing tables and the parser code to ftable.  |
 596 `----------------------------------------------------------*/
 597
 598 void
 599 output (void)
 600 {
 601   obstack_init (&format_obstack);
 602
 603   prepare_symbols ();
 604   prepare_rules ();
 605   prepare_states ();
 606   prepare_actions ();
 607
 608   prepare ();
 609
 610   /* Process the selected skeleton file.  */
 611   output_skeleton ();
 612
 613   obstack_free (&format_obstack, NULL);
 614   obstack_free (&pre_prologue_obstack, NULL);
 615   obstack_free (&post_prologue_obstack, NULL);
 616 }