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