src/output.c

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