src/output.c

   1 /* Output the generated parsing program for Bison.
   2
   3    Copyright (C) 1984, 1986, 1989, 1992, 2000, 2001, 2002, 2003
   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     /* We assume that the table will be output starting at column 2. */
 163     int j = 2;
 164     for (i = 0; i < nsyms; i++)
 165       {
 166         const char *cp = quotearg_style (c_quoting_style, symbols[i]->tag);
 167         /* Width of the next token, including the two quotes, the
 168            comma and the space.  */
 169         int width = strlen (cp) + 2;
 170
 171         if (j + width > 75)
 172           {
 173             obstack_sgrow (&format_obstack, "\n ");
 174             j = 1;
 175           }
 176
 177         if (i)
 178           obstack_1grow (&format_obstack, ' ');
 179         MUSCLE_OBSTACK_SGROW (&format_obstack, cp);
 180         obstack_1grow (&format_obstack, ',');
 181         j += width;
 182       }
 183     /* Add a NULL entry to list of tokens (well, 0, as NULL might not be
 184        defined).  */
 185     obstack_sgrow (&format_obstack, " 0");
 186
 187     /* Finish table and store. */
 188     obstack_1grow (&format_obstack, 0);
 189     muscle_insert ("tname", obstack_finish (&format_obstack));
 190   }
 191
 192   /* Output YYTOKNUM. */
 193   {
 194     int i;
 195     int *values = MALLOC (values, ntokens);
 196     for (i = 0; i < ntokens; ++i)
 197       values[i] = symbols[i]->user_token_number;
 198     muscle_insert_int_table ("toknum", values,
 199                              values[0], 1, ntokens);
 200     free (values);
 201   }
 202 }
 203
 204
 205 /*-------------------------------------------------------------.
 206 | Prepare the muscles related to the rules: rhs, prhs, r1, r2, |
 207 | rline, dprec, merger.                                        |
 208 `-------------------------------------------------------------*/
 209
 210 static void
 211 prepare_rules (void)
 212 {
 213   rule_number r;
 214   unsigned int i = 0;
 215   item_number *rhs = MALLOC (rhs, nritems);
 216   unsigned int *prhs = MALLOC (prhs, nrules);
 217   unsigned int *rline = MALLOC (rline, nrules);
 218   symbol_number *r1 = MALLOC (r1, nrules);
 219   unsigned int *r2 = MALLOC (r2, nrules);
 220   short *dprec = MALLOC (dprec, nrules);
 221   short *merger = MALLOC (merger, nrules);
 222
 223   for (r = 0; r < nrules; ++r)
 224     {
 225       item_number *rhsp = NULL;
 226       /* Index of rule R in RHS. */
 227       prhs[r] = i;
 228       /* RHS of the rule R. */
 229       for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp)
 230         rhs[i++] = *rhsp;
 231       /* LHS of the rule R. */
 232       r1[r] = rules[r].lhs->number;
 233       /* Length of rule R's RHS. */
 234       r2[r] = i - prhs[r];
 235       /* Separator in RHS. */
 236       rhs[i++] = -1;
 237       /* Line where rule was defined. */
 238       rline[r] = rules[r].location.start.line;
 239       /* Dynamic precedence (GLR).  */
 240       dprec[r] = rules[r].dprec;
 241       /* Merger-function index (GLR).  */
 242       merger[r] = rules[r].merger;
 243     }
 244   if (i != nritems)
 245     abort ();
 246
 247   muscle_insert_item_number_table ("rhs", rhs, ritem[0], 1, nritems);
 248   muscle_insert_unsigned_int_table ("prhs", prhs, 0, 0, nrules);
 249   muscle_insert_unsigned_int_table ("rline", rline, 0, 0, nrules);
 250   muscle_insert_symbol_number_table ("r1", r1, 0, 0, nrules);
 251   muscle_insert_unsigned_int_table ("r2", r2, 0, 0, nrules);
 252   muscle_insert_short_table ("dprec", dprec, 0, 0, nrules);
 253   muscle_insert_short_table ("merger", merger, 0, 0, nrules);
 254
 255   MUSCLE_INSERT_INT ("rules_number", nrules);
 256
 257   free (rhs);
 258   free (prhs);
 259   free (rline);
 260   free (r1);
 261   free (r2);
 262   free (dprec);
 263   free (merger);
 264 }
 265
 266 /*--------------------------------------------.
 267 | Prepare the muscles related to the states.  |
 268 `--------------------------------------------*/
 269
 270 static void
 271 prepare_states (void)
 272 {
 273   state_number i;
 274   symbol_number *values = MALLOC (values, nstates);
 275   for (i = 0; i < nstates; ++i)
 276     values[i] = states[i]->accessing_symbol;
 277   muscle_insert_symbol_number_table ("stos", values,
 278                                      0, 1, nstates);
 279   free (values);
 280
 281   MUSCLE_INSERT_INT ("last", high);
 282   MUSCLE_INSERT_INT ("final_state_number", final_state->number);
 283   MUSCLE_INSERT_INT ("states_number", nstates);
 284 }
 285
 286
 287
 288 /*---------------------------------.
 289 | Output the user actions to OUT.  |
 290 `---------------------------------*/
 291
 292 static void
 293 user_actions_output (FILE *out)
 294 {
 295   rule_number r;
 296
 297   fputs ("m4_define([b4_actions], \n[[", out);
 298   for (r = 0; r < nrules; ++r)
 299     if (rules[r].action)
 300       {
 301         fprintf (out, "  case %d:\n", r + 1);
 302
 303         fprintf (out, "]b4_syncline([[%d]], ",
 304                  rules[r].action_location.start.line);
 305         escaped_file_name_output (out, rules[r].action_location.start.file);
 306         fprintf (out, ")[\n");
 307         fprintf (out, "    %s\n    break;\n\n",
 308                  rules[r].action);
 309       }
 310   fputs ("]])\n\n", out);
 311 }
 312
 313 /*--------------------------------------.
 314 | Output the merge functions to OUT.   |
 315 `--------------------------------------*/
 316
 317 static void
 318 merger_output (FILE *out)
 319 {
 320   int n;
 321   merger_list* p;
 322
 323   fputs ("m4_define([b4_mergers], \n[[", out);
 324   for (n = 1, p = merge_functions; p != NULL; n += 1, p = p->next)
 325     {
 326       if (p->type[0] == '\0')
 327         fprintf (out, "  case %d: yyval = %s (*yy0, *yy1); break;\n",
 328                  n, p->name);
 329       else
 330         fprintf (out, "  case %d: yyval.%s = %s (*yy0, *yy1); break;\n",
 331                  n, p->type, p->name);
 332     }
 333   fputs ("]])\n\n", out);
 334 }
 335
 336 /*--------------------------------------.
 337 | Output the tokens definition to OUT.  |
 338 `--------------------------------------*/
 339
 340 static void
 341 token_definitions_output (FILE *out)
 342 {
 343   int i;
 344   int first = 1;
 345
 346   fputs ("m4_define([b4_tokens], \n[", out);
 347   for (i = 0; i < ntokens; ++i)
 348     {
 349       symbol *sym = symbols[i];
 350       int number = sym->user_token_number;
 351
 352       /* At this stage, if there are literal aliases, they are part of
 353          SYMBOLS, so we should not find symbols which are the aliases
 354          here.  */
 355       if (number == USER_NUMBER_ALIAS)
 356         abort ();
 357
 358       /* Skip error token.  */
 359       if (sym == errtoken)
 360         continue;
 361
 362       /* If this string has an alias, then it is necessarily the alias
 363          which is to be output.  */
 364       if (sym->alias)
 365         sym = sym->alias;
 366
 367       /* Don't output literal chars or strings (when defined only as a
 368          string).  Note that must be done after the alias resolution:
 369          think about `%token 'f' "f"'.  */
 370       if (sym->tag[0] == '\'' || sym->tag[0] == '\"')
 371         continue;
 372
 373       /* Don't #define nonliteral tokens whose names contain periods
 374          or '$' (as does the default value of the EOF token).  */
 375       if (strchr (sym->tag, '.') || strchr (sym->tag, '$'))
 376         continue;
 377
 378       fprintf (out, "%s[[[%s]], [%d]]",
 379                first ? "" : ",\n", sym->tag, number);
 380
 381       first = 0;
 382     }
 383   fputs ("])\n\n", out);
 384 }
 385
 386
 387 /*---------------------------------------.
 388 | Output the symbol destructors to OUT.  |
 389 `---------------------------------------*/
 390
 391 static void
 392 symbol_destructors_output (FILE *out)
 393 {
 394   int i;
 395   int first = 1;
 396
 397   fputs ("m4_define([b4_symbol_destructors], \n[", out);
 398   for (i = 0; i < nsyms; ++i)
 399     if (symbols[i]->destructor)
 400       {
 401         symbol *sym = symbols[i];
 402
 403         /* Filename, lineno,
 404            Symbol-name, Symbol-number,
 405            destructor, typename. */
 406         fprintf (out, "%s[",
 407                  first ? "" : ",\n");
 408         escaped_file_name_output (out, sym->destructor_location.start.file);
 409         fprintf (out, ", [[%d]], [[%s]], [[%d]], [[%s]], [[%s]]]",
 410                  sym->destructor_location.start.line,
 411                  sym->tag,
 412                  sym->number,
 413                  sym->destructor,
 414                  sym->type_name);
 415
 416         first = 0;
 417       }
 418   fputs ("])\n\n", out);
 419 }
 420
 421
 422 /*------------------------------------.
 423 | Output the symbol printers to OUT.  |
 424 `------------------------------------*/
 425
 426 static void
 427 symbol_printers_output (FILE *out)
 428 {
 429   int i;
 430   int first = 1;
 431
 432   fputs ("m4_define([b4_symbol_printers], \n[", out);
 433   for (i = 0; i < nsyms; ++i)
 434     if (symbols[i]->printer)
 435       {
 436         symbol *sym = symbols[i];
 437
 438         /* Filename, lineno,
 439            Symbol-name, Symbol-number,
 440            printer, typename. */
 441         fprintf (out, "%s[",
 442                  first ? "" : ",\n");
 443         escaped_file_name_output (out, sym->printer_location.start.file);
 444         fprintf (out, ", [[%d]], [[%s]], [[%d]], [[%s]], [[%s]]]",
 445                  sym->printer_location.start.line,
 446                  sym->tag,
 447                  sym->number,
 448                  sym->printer,
 449                  sym->type_name);
 450
 451         first = 0;
 452       }
 453   fputs ("])\n\n", out);
 454 }
 455
 456
 457 static void
 458 prepare_actions (void)
 459 {
 460   /* Figure out the actions for the specified state, indexed by
 461      lookahead token type.  */
 462
 463   muscle_insert_rule_number_table ("defact", yydefact,
 464                                    yydefact[0], 1, nstates);
 465
 466   /* Figure out what to do after reducing with each rule, depending on
 467      the saved state from before the beginning of parsing the data
 468      that matched this rule.  */
 469   muscle_insert_state_number_table ("defgoto", yydefgoto,
 470                                     yydefgoto[0], 1, nsyms - ntokens);
 471
 472
 473   /* Output PACT. */
 474   muscle_insert_base_table ("pact", base,
 475                              base[0], 1, nstates);
 476   MUSCLE_INSERT_INT ("pact_ninf", base_ninf);
 477
 478   /* Output PGOTO. */
 479   muscle_insert_base_table ("pgoto", base,
 480                              base[nstates], nstates + 1, nvectors);
 481
 482   muscle_insert_base_table ("table", table,
 483                             table[0], 1, high + 1);
 484   MUSCLE_INSERT_INT ("table_ninf", table_ninf);
 485
 486   muscle_insert_base_table ("check", check,
 487                             check[0], 1, high + 1);
 488
 489   /* GLR parsing slightly modifies YYTABLE and YYCHECK (and thus
 490      YYPACT) so that in states with unresolved conflicts, the default
 491      reduction is not used in the conflicted entries, so that there is
 492      a place to put a conflict pointer.
 493
 494      This means that YYCONFLP and YYCONFL are nonsense for a non-GLR
 495      parser, so we could avoid accidents by not writing them out in
 496      that case.  Nevertheless, it seems even better to be able to use
 497      the GLR skeletons even without the non-deterministic tables.  */
 498   muscle_insert_unsigned_int_table ("conflict_list_heads", conflict_table,
 499                                     conflict_table[0], 1, high + 1);
 500   muscle_insert_unsigned_int_table ("conflicting_rules", conflict_list,
 501                                     conflict_list[0], 1, conflict_list_cnt);
 502 }
 503
 504 \f
 505 /*---------------------------.
 506 | Call the skeleton parser.  |
 507 `---------------------------*/
 508
 509 static void
 510 output_skeleton (void)
 511 {
 512   FILE *in;
 513   FILE *out;
 514   int filter_fd[2];
 515   char const *argv[6];
 516   pid_t pid;
 517
 518   /* Compute the names of the package data dir and skeleton file.
 519      Test whether m4sugar.m4 is readable, to check for proper
 520      installation.  A faulty installation can cause deadlock, so a
 521      cheap sanity check is worthwhile.  */
 522   char const m4sugar[] = "m4sugar/m4sugar.m4";
 523   char *full_m4sugar;
 524   char *full_cm4;
 525   char *full_path;
 526   char const *p;
 527   char const *m4 = (p = getenv ("M4")) ? p : M4;
 528   char const *pkgdatadir = (p = getenv ("BISON_PKGDATADIR")) ? p : PKGDATADIR;
 529   size_t skeleton_size = strlen (skeleton) + 1;
 530   size_t pkgdatadirlen = strlen (pkgdatadir);
 531   while (pkgdatadirlen && pkgdatadir[pkgdatadirlen - 1] == '/')
 532     pkgdatadirlen--;
 533   full_path = xmalloc (pkgdatadirlen + 1
 534                        + (skeleton_size < sizeof m4sugar
 535                           ? sizeof m4sugar : skeleton_size));
 536   strcpy (full_path, pkgdatadir);
 537   full_path[pkgdatadirlen] = '/';
 538   strcpy (full_path + pkgdatadirlen + 1, m4sugar);
 539   full_m4sugar = xstrdup (full_path);
 540   strcpy (full_path + pkgdatadirlen + 1, "c.m4");
 541   full_cm4 = xstrdup (full_path);
 542   strcpy (full_path + pkgdatadirlen + 1, skeleton);
 543   xfclose (xfopen (full_m4sugar, "r"));
 544
 545   /* Create an m4 subprocess connected to us via two pipes.  */
 546
 547   if (trace_flag & trace_tools)
 548     fprintf (stderr, "running: %s %s - %s %s\n",
 549              m4, full_m4sugar, full_cm4, full_path);
 550
 551   argv[0] = m4;
 552   argv[1] = full_m4sugar;
 553   argv[2] = "-";
 554   argv[3] = full_cm4;
 555   argv[4] = full_path;
 556   argv[5] = NULL;
 557
 558   init_subpipe ();
 559   pid = create_subpipe (argv, filter_fd);
 560   free (full_m4sugar);
 561   free (full_cm4);
 562   free (full_path);
 563
 564   out = fdopen (filter_fd[0], "w");
 565   if (! out)
 566     error (EXIT_FAILURE, get_errno (), "fdopen");
 567
 568   /* Output the definitions of all the muscles.  */
 569   fputs ("m4_init()\n", out);
 570
 571   user_actions_output (out);
 572   merger_output (out);
 573   token_definitions_output (out);
 574   symbol_destructors_output (out);
 575   symbol_printers_output (out);
 576
 577   muscles_m4_output (out);
 578
 579   fputs ("m4_wrap([m4_divert_pop(0)])\n", out);
 580   fputs ("m4_divert_push(0)dnl\n", out);
 581   xfclose (out);
 582
 583   /* Read and process m4's output.  */
 584   timevar_push (TV_M4);
 585   in = fdopen (filter_fd[1], "r");
 586   if (! in)
 587     error (EXIT_FAILURE, get_errno (), "fdopen");
 588   scan_skel (in);
 589   xfclose (in);
 590   reap_subpipe (pid, m4);
 591   timevar_pop (TV_M4);
 592 }
 593
 594 static void
 595 prepare (void)
 596 {
 597   /* Flags. */
 598   MUSCLE_INSERT_INT ("debug", debug_flag);
 599   MUSCLE_INSERT_INT ("defines_flag", defines_flag);
 600   MUSCLE_INSERT_INT ("error_verbose", error_verbose);
 601   MUSCLE_INSERT_INT ("locations_flag", locations_flag);
 602   MUSCLE_INSERT_INT ("pure", pure_parser);
 603   MUSCLE_INSERT_INT ("synclines_flag", !no_lines_flag);
 604
 605   /* File names.  */
 606   MUSCLE_INSERT_STRING ("prefix", spec_name_prefix ? spec_name_prefix : "yy");
 607
 608   /* User Code.  */
 609   obstack_1grow (&pre_prologue_obstack, 0);
 610   obstack_1grow (&post_prologue_obstack, 0);
 611   muscle_insert ("pre_prologue", obstack_finish (&pre_prologue_obstack));
 612   muscle_insert ("post_prologue", obstack_finish (&post_prologue_obstack));
 613
 614   /* Find the right skeleton file.  */
 615   if (!skeleton)
 616     {
 617       if (glr_parser)
 618         skeleton = "glr.c";
 619       else
 620         skeleton = "yacc.c";
 621     }
 622
 623   /* Parse the skeleton file and output the needed parsers.  */
 624   MUSCLE_INSERT_C_STRING ("skeleton", skeleton);
 625 }
 626
 627
 628 /*----------------------------------------------------------.
 629 | Output the parsing tables and the parser code to ftable.  |
 630 `----------------------------------------------------------*/
 631
 632 void
 633 output (void)
 634 {
 635   obstack_init (&format_obstack);
 636
 637   prepare_symbols ();
 638   prepare_rules ();
 639   prepare_states ();
 640   prepare_actions ();
 641
 642   prepare ();
 643
 644   /* Process the selected skeleton file.  */
 645   output_skeleton ();
 646
 647   obstack_free (&format_obstack, NULL);
 648   obstack_free (&pre_prologue_obstack, NULL);
 649   obstack_free (&post_prologue_obstack, NULL);
 650 }