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 bool error_verbose = false;
  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   MUSCLE_INSERT_INT ("max_left_semantic_context", max_left_semantic_context);
 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: *yy0 = %s (*yy0, *yy1); break;\n",
 329                  n, p->name);
 330       else
 331         fprintf (out, "  case %d: yy0->%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   char const *sep = "";
 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                sep, sym->tag, number);
 381       sep = ",\n";
 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   char const *sep = "";
 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[", sep);
 407         sep = ",\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   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   char const *sep = "";
 429
 430   fputs ("m4_define([b4_symbol_printers], \n[", out);
 431   for (i = 0; i < nsyms; ++i)
 432     if (symbols[i]->printer)
 433       {
 434         symbol *sym = symbols[i];
 435
 436         /* Filename, lineno,
 437            Symbol-name, Symbol-number,
 438            printer, typename. */
 439         fprintf (out, "%s[", sep);
 440         sep = ",\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   fputs ("])\n\n", out);
 450 }
 451
 452
 453 static void
 454 prepare_actions (void)
 455 {
 456   /* Figure out the actions for the specified state, indexed by
 457      lookahead token type.  */
 458
 459   muscle_insert_rule_number_table ("defact", yydefact,
 460                                    yydefact[0], 1, nstates);
 461
 462   /* Figure out what to do after reducing with each rule, depending on
 463      the saved state from before the beginning of parsing the data
 464      that matched this rule.  */
 465   muscle_insert_state_number_table ("defgoto", yydefgoto,
 466                                     yydefgoto[0], 1, nsyms - ntokens);
 467
 468
 469   /* Output PACT. */
 470   muscle_insert_base_table ("pact", base,
 471                              base[0], 1, nstates);
 472   MUSCLE_INSERT_INT ("pact_ninf", base_ninf);
 473
 474   /* Output PGOTO. */
 475   muscle_insert_base_table ("pgoto", base,
 476                              base[nstates], nstates + 1, nvectors);
 477
 478   muscle_insert_base_table ("table", table,
 479                             table[0], 1, high + 1);
 480   MUSCLE_INSERT_INT ("table_ninf", table_ninf);
 481
 482   muscle_insert_base_table ("check", check,
 483                             check[0], 1, high + 1);
 484
 485   /* GLR parsing slightly modifies YYTABLE and YYCHECK (and thus
 486      YYPACT) so that in states with unresolved conflicts, the default
 487      reduction is not used in the conflicted entries, so that there is
 488      a place to put a conflict pointer.
 489
 490      This means that YYCONFLP and YYCONFL are nonsense for a non-GLR
 491      parser, so we could avoid accidents by not writing them out in
 492      that case.  Nevertheless, it seems even better to be able to use
 493      the GLR skeletons even without the non-deterministic tables.  */
 494   muscle_insert_unsigned_int_table ("conflict_list_heads", conflict_table,
 495                                     conflict_table[0], 1, high + 1);
 496   muscle_insert_unsigned_int_table ("conflicting_rules", conflict_list,
 497                                     conflict_list[0], 1, conflict_list_cnt);
 498 }
 499
 500 \f
 501 /*---------------------------.
 502 | Call the skeleton parser.  |
 503 `---------------------------*/
 504
 505 static void
 506 output_skeleton (void)
 507 {
 508   FILE *in;
 509   FILE *out;
 510   int filter_fd[2];
 511   char const *argv[6];
 512   pid_t pid;
 513
 514   /* Compute the names of the package data dir and skeleton file.
 515      Test whether m4sugar.m4 is readable, to check for proper
 516      installation.  A faulty installation can cause deadlock, so a
 517      cheap sanity check is worthwhile.  */
 518   char const m4sugar[] = "m4sugar/m4sugar.m4";
 519   char *full_m4sugar;
 520   char *full_cm4;
 521   char *full_skeleton;
 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_skeleton = xmalloc (pkgdatadirlen + 1
 530                            + (skeleton_size < sizeof m4sugar
 531                               ? sizeof m4sugar : skeleton_size));
 532   strcpy (full_skeleton, pkgdatadir);
 533   full_skeleton[pkgdatadirlen] = '/';
 534   strcpy (full_skeleton + pkgdatadirlen + 1, m4sugar);
 535   full_m4sugar = xstrdup (full_skeleton);
 536   strcpy (full_skeleton + pkgdatadirlen + 1, "c.m4");
 537   full_cm4 = xstrdup (full_skeleton);
 538   strcpy (full_skeleton + pkgdatadirlen + 1, skeleton);
 539   xfclose (xfopen (full_m4sugar, "r"));
 540
 541   /* Create an m4 subprocess connected to us via two pipes.  */
 542
 543   if (trace_flag & trace_tools)
 544     fprintf (stderr, "running: %s %s - %s %s\n",
 545              m4, full_m4sugar, full_cm4, full_skeleton);
 546
 547   argv[0] = m4;
 548   argv[1] = full_m4sugar;
 549   argv[2] = "-";
 550   argv[3] = full_cm4;
 551   argv[4] = full_skeleton;
 552   argv[5] = NULL;
 553
 554   init_subpipe ();
 555   pid = create_subpipe (argv, filter_fd);
 556   free (full_m4sugar);
 557   free (full_cm4);
 558   free (full_skeleton);
 559
 560   out = fdopen (filter_fd[0], "w");
 561   if (! out)
 562     error (EXIT_FAILURE, get_errno (), "fdopen");
 563
 564   /* Output the definitions of all the muscles.  */
 565   fputs ("m4_init()\n", out);
 566
 567   user_actions_output (out);
 568   merger_output (out);
 569   token_definitions_output (out);
 570   symbol_destructors_output (out);
 571   symbol_printers_output (out);
 572
 573   muscles_m4_output (out);
 574
 575   fputs ("m4_wrap([m4_divert_pop(0)])\n", out);
 576   fputs ("m4_divert_push(0)dnl\n", out);
 577   xfclose (out);
 578
 579   /* Read and process m4's output.  */
 580   timevar_push (TV_M4);
 581   in = fdopen (filter_fd[1], "r");
 582   if (! in)
 583     error (EXIT_FAILURE, get_errno (), "fdopen");
 584   scan_skel (in);
 585   xfclose (in);
 586   reap_subpipe (pid, m4);
 587   timevar_pop (TV_M4);
 588 }
 589
 590 static void
 591 prepare (void)
 592 {
 593   /* Flags. */
 594   MUSCLE_INSERT_BOOL ("debug", debug_flag);
 595   MUSCLE_INSERT_BOOL ("defines_flag", defines_flag);
 596   MUSCLE_INSERT_BOOL ("error_verbose", error_verbose);
 597   MUSCLE_INSERT_BOOL ("locations_flag", locations_flag);
 598   MUSCLE_INSERT_BOOL ("pure", pure_parser);
 599   MUSCLE_INSERT_BOOL ("synclines_flag", !no_lines_flag);
 600
 601   /* File names.  */
 602   MUSCLE_INSERT_STRING ("prefix", spec_name_prefix ? spec_name_prefix : "yy");
 603
 604   /* User Code.  */
 605   obstack_1grow (&pre_prologue_obstack, 0);
 606   obstack_1grow (&post_prologue_obstack, 0);
 607   muscle_insert ("pre_prologue", obstack_finish (&pre_prologue_obstack));
 608   muscle_insert ("post_prologue", obstack_finish (&post_prologue_obstack));
 609
 610   /* Find the right skeleton file.  */
 611   if (!skeleton)
 612     {
 613       if (glr_parser || nondeterministic_parser)
 614         skeleton = "glr.c";
 615       else
 616         skeleton = "yacc.c";
 617     }
 618
 619   /* Parse the skeleton file and output the needed parsers.  */
 620   MUSCLE_INSERT_C_STRING ("skeleton", skeleton);
 621 }
 622
 623
 624 /*----------------------------------------------------------.
 625 | Output the parsing tables and the parser code to ftable.  |
 626 `----------------------------------------------------------*/
 627
 628 void
 629 output (void)
 630 {
 631   obstack_init (&format_obstack);
 632
 633   prepare_symbols ();
 634   prepare_rules ();
 635   prepare_states ();
 636   prepare_actions ();
 637
 638   prepare ();
 639
 640   /* Process the selected skeleton file.  */
 641   output_skeleton ();
 642
 643   obstack_free (&format_obstack, NULL);
 644   obstack_free (&pre_prologue_obstack, NULL);
 645   obstack_free (&post_prologue_obstack, NULL);
 646 }