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   fputs ("m4_init()\n", out);
 531
 532   user_actions_output (out);
 533   merger_output (out);
 534   token_definitions_output (out);
 535   symbol_destructors_output (out);
 536   symbol_printers_output (out);
 537
 538   muscles_m4_output (out);
 539
 540   fputs ("m4_wrap([m4_divert_pop(0)])\n", out);
 541   fputs ("m4_divert_push(0)dnl\n", out);
 542   if (ferror (out))
 543     error (EXIT_FAILURE, 0, "pipe output error");
 544   xfclose (out);
 545
 546   /* Read and process m4's output.  */
 547   timevar_push (TV_M4);
 548   in = fdopen (filter_fd[1], "r");
 549   if (! in)
 550     error (EXIT_FAILURE, errno, "fdopen");
 551   scan_skel (in);
 552   if (ferror (in))
 553     error (EXIT_FAILURE, 0, "pipe input error");
 554   xfclose (in);
 555   reap_subpipe (pid, m4);
 556   timevar_pop (TV_M4);
 557 }
 558
 559 static void
 560 prepare (void)
 561 {
 562   /* Flags. */
 563   MUSCLE_INSERT_INT ("locations_flag", locations_flag);
 564   MUSCLE_INSERT_INT ("defines_flag", defines_flag);
 565   MUSCLE_INSERT_INT ("error_verbose", error_verbose);
 566   MUSCLE_INSERT_INT ("pure", pure_parser);
 567   MUSCLE_INSERT_INT ("debug", debug_flag);
 568
 569   /* FIXME: This is wrong: the muscles should decide whether they hold
 570      a copy or not, but the situation is too obscure currently.  */
 571   MUSCLE_INSERT_STRING ("prefix", spec_name_prefix ? spec_name_prefix : "yy");
 572   MUSCLE_INSERT_STRING ("output_infix", output_infix ? output_infix : "");
 573   MUSCLE_INSERT_STRING ("output_prefix", short_base_name);
 574   MUSCLE_INSERT_STRING ("output_parser_name", parser_file_name);
 575   MUSCLE_INSERT_STRING ("output_header_name", spec_defines_file);
 576
 577   /* User Code.  */
 578   obstack_1grow (&pre_prologue_obstack, 0);
 579   obstack_1grow (&post_prologue_obstack, 0);
 580   muscle_insert ("pre_prologue", obstack_finish (&pre_prologue_obstack));
 581   muscle_insert ("post_prologue", obstack_finish (&post_prologue_obstack));
 582
 583   /* Find the right skeleton file.  */
 584   if (!skeleton)
 585     {
 586       if (glr_parser)
 587         skeleton = "glr.c";
 588       else
 589         skeleton = "yacc.c";
 590     }
 591
 592   /* Parse the skeleton file and output the needed parsers.  */
 593   MUSCLE_INSERT_STRING ("skeleton", skeleton);
 594 }
 595
 596
 597 /*----------------------------------------------------------.
 598 | Output the parsing tables and the parser code to ftable.  |
 599 `----------------------------------------------------------*/
 600
 601 void
 602 output (void)
 603 {
 604   obstack_init (&format_obstack);
 605
 606   prepare_symbols ();
 607   prepare_rules ();
 608   prepare_states ();
 609   prepare_actions ();
 610
 611   prepare ();
 612
 613   /* Process the selected skeleton file.  */
 614   output_skeleton ();
 615
 616   obstack_free (&format_obstack, NULL);
 617   obstack_free (&pre_prologue_obstack, NULL);
 618   obstack_free (&post_prologue_obstack, NULL);
 619 }