src/print.c

   1 /* Print information on generated parser, for bison,
   2
   3    Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004, 2005,
   4    2007, 2009 Free Software Foundation, Inc.
   5
   6    This file is part of Bison, the GNU Compiler Compiler.
   7
   8    This program is free software: you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation, either version 3 of the License, or
  11    (at your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  20
  21 #include <config.h>
  22 #include "system.h"
  23
  24 #include <bitset.h>
  25 #include <quotearg.h>
  26
  27 #include "LR0.h"
  28 #include "closure.h"
  29 #include "conflicts.h"
  30 #include "files.h"
  31 #include "getargs.h"
  32 #include "gram.h"
  33 #include "lalr.h"
  34 #include "muscle_tab.h"
  35 #include "print.h"
  36 #include "reader.h"
  37 #include "reduce.h"
  38 #include "state.h"
  39 #include "symtab.h"
  40 #include "tables.h"
  41
  42 static bitset no_reduce_set;
  43
  44 #if 0
  45 static void
  46 print_token (int extnum, int token)
  47 {
  48   fprintf (out, _(" type %d is %s\n"), extnum, tags[token]);
  49 }
  50 #endif
  51
  52 \f
  53
  54 /*---------------------------------------.
  55 | *WIDTH := max (*WIDTH, strlen (STR)).  |
  56 `---------------------------------------*/
  57
  58 static void
  59 max_length (size_t *width, const char *str)
  60 {
  61   size_t len = strlen (str);
  62   if (len > *width)
  63     *width = len;
  64 }
  65
  66 /*--------------------------------.
  67 | Report information on a state.  |
  68 `--------------------------------*/
  69
  70 static void
  71 print_core (FILE *out, state *s)
  72 {
  73   size_t i;
  74   item_number *sitems = s->items;
  75   size_t snritems = s->nitems;
  76   symbol *previous_lhs = NULL;
  77
  78   /* Output all the items of a state, not only its kernel.  */
  79   if (report_flag & report_itemsets)
  80     {
  81       closure (sitems, snritems);
  82       sitems = itemset;
  83       snritems = nitemset;
  84     }
  85
  86   if (!snritems)
  87     return;
  88
  89   fputc ('\n', out);
  90
  91   for (i = 0; i < snritems; i++)
  92     {
  93       item_number *sp;
  94       item_number *sp1;
  95       rule_number r;
  96
  97       sp1 = sp = ritem + sitems[i];
  98
  99       while (*sp >= 0)
 100         sp++;
 101
 102       r = item_number_as_rule_number (*sp);
 103
 104       rule_lhs_print (&rules[r], previous_lhs, out);
 105       previous_lhs = rules[r].lhs;
 106
 107       for (sp = rules[r].rhs; sp < sp1; sp++)
 108         fprintf (out, " %s", symbols[*sp]->tag);
 109       fputs (" .", out);
 110       for (/* Nothing */; *sp >= 0; ++sp)
 111         fprintf (out, " %s", symbols[*sp]->tag);
 112
 113       /* Display the lookahead tokens?  */
 114       if (report_flag & report_lookahead_tokens
 115           && item_number_is_rule_number (*sp1))
 116         state_rule_lookahead_tokens_print (s, &rules[r], out);
 117
 118       fputc ('\n', out);
 119     }
 120 }
 121
 122
 123 /*------------------------------------------------------------.
 124 | Report the shifts iff DISPLAY_SHIFTS_P or the gotos of S on |
 125 | OUT.                                                        |
 126 `------------------------------------------------------------*/
 127
 128 static void
 129 print_transitions (state *s, FILE *out, bool display_transitions_p)
 130 {
 131   transitions *trans = s->transitions;
 132   size_t width = 0;
 133   int i;
 134
 135   /* Compute the width of the lookahead token column.  */
 136   for (i = 0; i < trans->num; i++)
 137     if (!TRANSITION_IS_DISABLED (trans, i)
 138         && TRANSITION_IS_SHIFT (trans, i) == display_transitions_p)
 139       {
 140         symbol *sym = symbols[TRANSITION_SYMBOL (trans, i)];
 141         max_length (&width, sym->tag);
 142       }
 143
 144   /* Nothing to report. */
 145   if (!width)
 146     return;
 147
 148   fputc ('\n', out);
 149   width += 2;
 150
 151   /* Report lookahead tokens and shifts.  */
 152   for (i = 0; i < trans->num; i++)
 153     if (!TRANSITION_IS_DISABLED (trans, i)
 154         && TRANSITION_IS_SHIFT (trans, i) == display_transitions_p)
 155       {
 156         symbol *sym = symbols[TRANSITION_SYMBOL (trans, i)];
 157         const char *tag = sym->tag;
 158         state *s1 = trans->states[i];
 159         int j;
 160
 161         fprintf (out, "    %s", tag);
 162         for (j = width - strlen (tag); j > 0; --j)
 163           fputc (' ', out);
 164         if (display_transitions_p)
 165           fprintf (out, _("shift, and go to state %d\n"), s1->number);
 166         else
 167           fprintf (out, _("go to state %d\n"), s1->number);
 168       }
 169 }
 170
 171
 172 /*--------------------------------------------------------.
 173 | Report the explicit errors of S raised from %nonassoc.  |
 174 `--------------------------------------------------------*/
 175
 176 static void
 177 print_errs (FILE *out, state *s)
 178 {
 179   errs *errp = s->errs;
 180   size_t width = 0;
 181   int i;
 182
 183   /* Compute the width of the lookahead token column.  */
 184   for (i = 0; i < errp->num; ++i)
 185     if (errp->symbols[i])
 186       max_length (&width, errp->symbols[i]->tag);
 187
 188   /* Nothing to report. */
 189   if (!width)
 190     return;
 191
 192   fputc ('\n', out);
 193   width += 2;
 194
 195   /* Report lookahead tokens and errors.  */
 196   for (i = 0; i < errp->num; ++i)
 197     if (errp->symbols[i])
 198       {
 199         const char *tag = errp->symbols[i]->tag;
 200         int j;
 201         fprintf (out, "    %s", tag);
 202         for (j = width - strlen (tag); j > 0; --j)
 203           fputc (' ', out);
 204         fputs (_("error (nonassociative)\n"), out);
 205       }
 206 }
 207
 208
 209 /*-------------------------------------------------------------------------.
 210 | Report a reduction of RULE on LOOKAHEAD_TOKEN (which can be `default').  |
 211 | If not ENABLED, the rule is masked by a shift or a reduce (S/R and       |
 212 | R/R conflicts).                                                          |
 213 `-------------------------------------------------------------------------*/
 214
 215 static void
 216 print_reduction (FILE *out, size_t width,
 217                  const char *lookahead_token,
 218                  rule *r, bool enabled)
 219 {
 220   int j;
 221   fprintf (out, "    %s", lookahead_token);
 222   for (j = width - strlen (lookahead_token); j > 0; --j)
 223     fputc (' ', out);
 224   if (!enabled)
 225     fputc ('[', out);
 226   if (r->number)
 227     fprintf (out, _("reduce using rule %d (%s)"), r->number, r->lhs->tag);
 228   else
 229     fprintf (out, _("accept"));
 230   if (!enabled)
 231     fputc (']', out);
 232   fputc ('\n', out);
 233 }
 234
 235
 236 /*-------------------------------------------.
 237 | Report on OUT the reduction actions of S.  |
 238 `-------------------------------------------*/
 239
 240 static void
 241 print_reductions (FILE *out, state *s)
 242 {
 243   transitions *trans = s->transitions;
 244   reductions *reds = s->reductions;
 245   rule *default_reduction = NULL;
 246   size_t width = 0;
 247   int i, j;
 248   bool default_reduction_only = true;
 249
 250   if (reds->num == 0)
 251     return;
 252
 253   if (yydefact[s->number] != 0)
 254     default_reduction = &rules[yydefact[s->number] - 1];
 255
 256   bitset_zero (no_reduce_set);
 257   FOR_EACH_SHIFT (trans, i)
 258     bitset_set (no_reduce_set, TRANSITION_SYMBOL (trans, i));
 259   for (i = 0; i < s->errs->num; ++i)
 260     if (s->errs->symbols[i])
 261       bitset_set (no_reduce_set, s->errs->symbols[i]->number);
 262
 263   /* Compute the width of the lookahead token column.  */
 264   if (default_reduction)
 265     width = strlen (_("$default"));
 266
 267   if (reds->lookahead_tokens)
 268     for (i = 0; i < ntokens; i++)
 269       {
 270         bool count = bitset_test (no_reduce_set, i);
 271
 272         for (j = 0; j < reds->num; ++j)
 273           if (bitset_test (reds->lookahead_tokens[j], i))
 274             {
 275               if (! count)
 276                 {
 277                   if (reds->rules[j] != default_reduction)
 278                     max_length (&width, symbols[i]->tag);
 279                   count = true;
 280                 }
 281               else
 282                 {
 283                   max_length (&width, symbols[i]->tag);
 284                 }
 285             }
 286       }
 287
 288   /* Nothing to report. */
 289   if (!width)
 290     return;
 291
 292   fputc ('\n', out);
 293   width += 2;
 294
 295   /* Report lookahead tokens (or $default) and reductions.  */
 296   if (reds->lookahead_tokens)
 297     for (i = 0; i < ntokens; i++)
 298       {
 299         bool defaulted = false;
 300         bool count = bitset_test (no_reduce_set, i);
 301         if (count)
 302           default_reduction_only = false;
 303
 304         for (j = 0; j < reds->num; ++j)
 305           if (bitset_test (reds->lookahead_tokens[j], i))
 306             {
 307               if (! count)
 308                 {
 309                   if (reds->rules[j] != default_reduction)
 310                     {
 311                       default_reduction_only = false;
 312                       print_reduction (out, width,
 313                                        symbols[i]->tag,
 314                                        reds->rules[j], true);
 315                     }
 316                   else
 317                     defaulted = true;
 318                   count = true;
 319                 }
 320               else
 321                 {
 322                   default_reduction_only = false;
 323                   if (defaulted)
 324                     print_reduction (out, width,
 325                                      symbols[i]->tag,
 326                                      default_reduction, true);
 327                   defaulted = false;
 328                   print_reduction (out, width,
 329                                    symbols[i]->tag,
 330                                    reds->rules[j], false);
 331                 }
 332             }
 333       }
 334
 335   if (default_reduction)
 336     {
 337       char *default_reductions =
 338         muscle_percent_define_get ("lr.default-reductions");
 339       print_reduction (out, width, _("$default"), default_reduction, true);
 340       aver (0 == strcmp (default_reductions, "all")
 341             || (0 == strcmp (default_reductions, "consistent")
 342                 && default_reduction_only)
 343             || (reds->num == 1 && reds->rules[0]->number == 0));
 344       free (default_reductions);
 345     }
 346 }
 347
 348
 349 /*--------------------------------------------------------------.
 350 | Report on OUT all the actions (shifts, gotos, reductions, and |
 351 | explicit erros from %nonassoc) of S.                          |
 352 `--------------------------------------------------------------*/
 353
 354 static void
 355 print_actions (FILE *out, state *s)
 356 {
 357   /* Print shifts.  */
 358   print_transitions (s, out, true);
 359   print_errs (out, s);
 360   print_reductions (out, s);
 361   /* Print gotos.  */
 362   print_transitions (s, out, false);
 363 }
 364
 365
 366 /*----------------------------------.
 367 | Report all the data on S on OUT.  |
 368 `----------------------------------*/
 369
 370 static void
 371 print_state (FILE *out, state *s)
 372 {
 373   fputs ("\n\n", out);
 374   fprintf (out, _("state %d"), s->number);
 375   fputc ('\n', out);
 376   print_core (out, s);
 377   print_actions (out, s);
 378   if ((report_flag & report_solved_conflicts) && s->solved_conflicts)
 379     {
 380       fputc ('\n', out);
 381       fputs (s->solved_conflicts, out);
 382     }
 383 }
 384 \f
 385 /*-----------------------------------------.
 386 | Print information on the whole grammar.  |
 387 `-----------------------------------------*/
 388
 389 #define END_TEST(End)                           \
 390 do {                                            \
 391   if (column + strlen(buffer) > (End))          \
 392     {                                           \
 393       fprintf (out, "%s\n   ", buffer);         \
 394       column = 3;                               \
 395       buffer[0] = 0;                            \
 396     }                                           \
 397 } while (0)
 398
 399
 400 static void
 401 print_grammar (FILE *out)
 402 {
 403   symbol_number i;
 404   char buffer[90];
 405   int column = 0;
 406
 407   grammar_rules_print (out);
 408
 409   /* TERMINAL (type #) : rule #s terminal is on RHS */
 410   fprintf (out, "%s\n\n", _("Terminals, with rules where they appear"));
 411   for (i = 0; i < max_user_token_number + 1; i++)
 412     if (token_translations[i] != undeftoken->number)
 413       {
 414         const char *tag = symbols[token_translations[i]]->tag;
 415         rule_number r;
 416         item_number *rhsp;
 417
 418         buffer[0] = 0;
 419         column = strlen (tag);
 420         fputs (tag, out);
 421         END_TEST (65);
 422         sprintf (buffer, " (%d)", i);
 423
 424         for (r = 0; r < nrules; r++)
 425           for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
 426             if (item_number_as_symbol_number (*rhsp) == token_translations[i])
 427               {
 428                 END_TEST (65);
 429                 sprintf (buffer + strlen (buffer), " %d", r);
 430                 break;
 431               }
 432         fprintf (out, "%s\n", buffer);
 433       }
 434   fputs ("\n\n", out);
 435
 436
 437   fprintf (out, "%s\n\n", _("Nonterminals, with rules where they appear"));
 438   for (i = ntokens; i < nsyms; i++)
 439     {
 440       int left_count = 0, right_count = 0;
 441       rule_number r;
 442       const char *tag = symbols[i]->tag;
 443
 444       for (r = 0; r < nrules; r++)
 445         {
 446           item_number *rhsp;
 447           if (rules[r].lhs->number == i)
 448             left_count++;
 449           for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
 450             if (item_number_as_symbol_number (*rhsp) == i)
 451               {
 452                 right_count++;
 453                 break;
 454               }
 455         }
 456
 457       buffer[0] = 0;
 458       fputs (tag, out);
 459       column = strlen (tag);
 460       sprintf (buffer, " (%d)", i);
 461       END_TEST (0);
 462
 463       if (left_count > 0)
 464         {
 465           END_TEST (65);
 466           sprintf (buffer + strlen (buffer), _(" on left:"));
 467
 468           for (r = 0; r < nrules; r++)
 469             {
 470               if (rules[r].lhs->number == i)
 471                 {
 472                   END_TEST (65);
 473                   sprintf (buffer + strlen (buffer), " %d", r);
 474                 }
 475             }
 476         }
 477
 478       if (right_count > 0)
 479         {
 480           if (left_count > 0)
 481             sprintf (buffer + strlen (buffer), ",");
 482           END_TEST (65);
 483           sprintf (buffer + strlen (buffer), _(" on right:"));
 484           for (r = 0; r < nrules; r++)
 485             {
 486               item_number *rhsp;
 487               for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
 488                 if (item_number_as_symbol_number (*rhsp) == i)
 489                   {
 490                     END_TEST (65);
 491                     sprintf (buffer + strlen (buffer), " %d", r);
 492                     break;
 493                   }
 494             }
 495         }
 496       fprintf (out, "%s\n", buffer);
 497     }
 498 }
 499 \f
 500 void
 501 print_results (void)
 502 {
 503   state_number i;
 504
 505   /* We used to use just .out if SPEC_NAME_PREFIX (-p) was used, but
 506      that conflicts with Posix.  */
 507   FILE *out = xfopen (spec_verbose_file, "w");
 508
 509   reduce_output (out);
 510   grammar_rules_partial_print (out,
 511                                _("Rules useless in parser due to conflicts"),
 512                                  rule_useless_in_parser_p);
 513   conflicts_output (out);
 514
 515   print_grammar (out);
 516
 517   /* If the whole state item sets, not only the kernels, are wanted,
 518      `closure' will be run, which needs memory allocation/deallocation.   */
 519   if (report_flag & report_itemsets)
 520     new_closure (nritems);
 521   /* Storage for print_reductions.  */
 522   no_reduce_set =  bitset_create (ntokens, BITSET_FIXED);
 523   for (i = 0; i < nstates; i++)
 524     print_state (out, states[i]);
 525   bitset_free (no_reduce_set);
 526   if (report_flag & report_itemsets)
 527     free_closure ();
 528
 529   xfclose (out);
 530 }