src/print.c

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