src/print.c

   1 /* Print information on generated parser, for bison,
   2
   3    Copyright (C) 1984, 1986, 1989, 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
   9    it 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,
  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 Bison; see the file COPYING.  If not, write to
  20    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  21    Boston, MA 02111-1307, USA.  */
  22
  23
  24 #include "system.h"
  25
  26 #include <bitset.h>
  27 #include <quotearg.h>
  28
  29 #include "LR0.h"
  30 #include "closure.h"
  31 #include "conflicts.h"
  32 #include "files.h"
  33 #include "getargs.h"
  34 #include "gram.h"
  35 #include "lalr.h"
  36 #include "print.h"
  37 #include "reader.h"
  38 #include "reduce.h"
  39 #include "state.h"
  40 #include "symtab.h"
  41
  42 static bitset shiftset;
  43 static bitset lookaheadset;
  44
  45 #if 0
  46 static void
  47 print_token (int extnum, int token)
  48 {
  49   fprintf (out, _(" type %d is %s\n"), extnum, tags[token]);
  50 }
  51 #endif
  52
  53 \f
  54
  55 /*---------------------------------------.
  56 | *WIDTH := max (*WIDTH, strlen (STR)).  |
  57 `---------------------------------------*/
  58
  59 static void
  60 max_length (size_t *width, const char *str)
  61 {
  62   size_t len = strlen (str);
  63   if (len > *width)
  64     *width = len;
  65 }
  66
  67 /*--------------------------------.
  68 | Report information on a state.  |
  69 `--------------------------------*/
  70
  71 static void
  72 print_core (FILE *out, state *s)
  73 {
  74   int i;
  75   item_number *sitems = s->items;
  76   int snritems = s->nitems;
  77   symbol *previous_lhs = NULL;
  78
  79   /* Output all the items of a state, not only its kernel.  */
  80   if (report_flag & report_itemsets)
  81     {
  82       closure (sitems, snritems);
  83       sitems = itemset;
  84       snritems = nritemset;
  85     }
  86
  87   if (!snritems)
  88     return;
  89
  90   fputc ('\n', out);
  91
  92   for (i = 0; i < snritems; i++)
  93     {
  94       item_number *sp;
  95       item_number *sp1;
  96       rule_number r;
  97
  98       sp1 = sp = ritem + sitems[i];
  99
 100       while (*sp >= 0)
 101         sp++;
 102
 103       r = item_number_as_rule_number (*sp);
 104
 105       rule_lhs_print (&rules[r], previous_lhs, out);
 106       previous_lhs = rules[r].lhs;
 107
 108       for (sp = rules[r].rhs; sp < sp1; sp++)
 109         fprintf (out, " %s", symbols[*sp]->tag);
 110       fputs (" .", out);
 111       for (/* Nothing */; *sp >= 0; ++sp)
 112         fprintf (out, " %s", symbols[*sp]->tag);
 113
 114       /* Display the lookaheads?  */
 115       if (report_flag & report_lookaheads)
 116         state_rule_lookaheads_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 lookaheads 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 lookaheads 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 lookaheads 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 lookaheads 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 | Return the default rule of S if it has one, NULL otherwise.  |
 211 `-------------------------------------------------------------*/
 212
 213 static rule *
 214 state_default_rule (state *s)
 215 {
 216   reductions *reds = s->reductions;
 217   rule *default_rule = NULL;
 218   int cmax = 0;
 219   int i;
 220
 221   /* No need for a lookahead.  */
 222   if (s->consistent)
 223     return reds->rules[0];
 224
 225   /* 1. Each reduction is possibly masked by the lookaheads on which
 226      we shift (S/R conflicts)...  */
 227   bitset_zero (shiftset);
 228   {
 229     transitions *trans = s->transitions;
 230     FOR_EACH_SHIFT (trans, i)
 231       {
 232         /* If this state has a shift for the error token, don't use a
 233              default rule.  */
 234         if (TRANSITION_IS_ERROR (trans, i))
 235           return NULL;
 236         bitset_set (shiftset, TRANSITION_SYMBOL (trans, i));
 237       }
 238   }
 239
 240   /* 2. Each reduction is possibly masked by the lookaheads on which
 241      we raise an error (due to %nonassoc).  */
 242   {
 243     errs *errp = s->errs;
 244     for (i = 0; i < errp->num; i++)
 245       if (errp->symbols[i])
 246         bitset_set (shiftset, errp->symbols[i]->number);
 247   }
 248
 249   for (i = 0; i < reds->num; ++i)
 250     {
 251       int count = 0;
 252
 253       /* How many non-masked lookaheads are there for this reduction?
 254          */
 255       bitset_andn (lookaheadset, reds->lookaheads[i], shiftset);
 256       count = bitset_count (lookaheadset);
 257
 258       if (count > cmax)
 259         {
 260           cmax = count;
 261           default_rule = reds->rules[i];
 262         }
 263
 264       /* 3. And finally, each reduction is possibly masked by previous
 265          reductions (in R/R conflicts, we keep the first reductions).
 266          */
 267       bitset_or (shiftset, shiftset, reds->lookaheads[i]);
 268     }
 269
 270   return default_rule;
 271 }
 272
 273
 274 /*--------------------------------------------------------------------.
 275 | Report a reduction of RULE on LOOKAHEADS (which can be `default').  |
 276 | If not ENABLED, the rule is masked by a shift or a reduce (S/R and  |
 277 | R/R conflicts).                                                     |
 278 `--------------------------------------------------------------------*/
 279
 280 static void
 281 print_reduction (FILE *out, size_t width,
 282                  const char *lookahead,
 283                  rule *r, bool enabled)
 284 {
 285   int j;
 286   fprintf (out, "    %s", lookahead);
 287   for (j = width - strlen (lookahead); j > 0; --j)
 288     fputc (' ', out);
 289   if (!enabled)
 290     fputc ('[', out);
 291   if (r->number)
 292     fprintf (out, _("reduce using rule %d (%s)"), r->number, r->lhs->tag);
 293   else
 294     fprintf (out, _("accept"));
 295   if (!enabled)
 296     fputc (']', out);
 297   fputc ('\n', out);
 298 }
 299
 300
 301 /*-------------------------------------------.
 302 | Report on OUT the reduction actions of S.  |
 303 `-------------------------------------------*/
 304
 305 static void
 306 print_reductions (FILE *out, state *s)
 307 {
 308   transitions *trans = s->transitions;
 309   reductions *reds = s->reductions;
 310   rule *default_rule = NULL;
 311   size_t width = 0;
 312   int i, j;
 313
 314   if (reds->num == 0)
 315     return;
 316
 317   default_rule = state_default_rule (s);
 318
 319   bitset_zero (shiftset);
 320   FOR_EACH_SHIFT (trans, i)
 321     bitset_set (shiftset, TRANSITION_SYMBOL (trans, i));
 322
 323   /* Compute the width of the lookaheads column.  */
 324   if (default_rule)
 325     width = strlen (_("$default"));
 326
 327   if (reds->lookaheads)
 328     for (i = 0; i < ntokens; i++)
 329       {
 330         bool count = bitset_test (shiftset, i);
 331
 332         for (j = 0; j < reds->num; ++j)
 333           if (bitset_test (reds->lookaheads[j], i))
 334             {
 335               if (! count)
 336                 {
 337                   if (reds->rules[j] != default_rule)
 338                     max_length (&width, symbols[i]->tag);
 339                   count = true;
 340                 }
 341               else
 342                 {
 343                   max_length (&width, symbols[i]->tag);
 344                 }
 345             }
 346       }
 347
 348   /* Nothing to report. */
 349   if (!width)
 350     return;
 351
 352   fputc ('\n', out);
 353   width += 2;
 354
 355   /* Report lookaheads (or $default) and reductions.  */
 356   if (reds->lookaheads)
 357     for (i = 0; i < ntokens; i++)
 358       {
 359         bool defaulted = false;
 360         bool count = bitset_test (shiftset, i);
 361
 362         for (j = 0; j < reds->num; ++j)
 363           if (bitset_test (reds->lookaheads[j], i))
 364             {
 365               if (! count)
 366                 {
 367                   if (reds->rules[j] != default_rule)
 368                     print_reduction (out, width,
 369                                      symbols[i]->tag,
 370                                      reds->rules[j], true);
 371                   else
 372                     defaulted = true;
 373                   count = true;
 374                 }
 375               else
 376                 {
 377                   if (defaulted)
 378                     print_reduction (out, width,
 379                                      symbols[i]->tag,
 380                                      default_rule, true);
 381                   defaulted = false;
 382                   print_reduction (out, width,
 383                                    symbols[i]->tag,
 384                                    reds->rules[j], false);
 385                 }
 386             }
 387       }
 388
 389   if (default_rule)
 390     print_reduction (out, width,
 391                      _("$default"), default_rule, true);
 392 }
 393
 394
 395 /*--------------------------------------------------------------.
 396 | Report on OUT all the actions (shifts, gotos, reductions, and |
 397 | explicit erros from %nonassoc) of S.                          |
 398 `--------------------------------------------------------------*/
 399
 400 static void
 401 print_actions (FILE *out, state *s)
 402 {
 403   /* Print shifts.  */
 404   print_transitions (s, out, true);
 405   print_errs (out, s);
 406   print_reductions (out, s);
 407   /* Print gotos.  */
 408   print_transitions (s, out, false);
 409 }
 410
 411
 412 /*----------------------------------.
 413 | Report all the data on S on OUT.  |
 414 `----------------------------------*/
 415
 416 static void
 417 print_state (FILE *out, state *s)
 418 {
 419   fputs ("\n\n", out);
 420   fprintf (out, _("state %d"), s->number);
 421   fputc ('\n', out);
 422   print_core (out, s);
 423   print_actions (out, s);
 424   if ((report_flag & report_solved_conflicts) && s->solved_conflicts)
 425     {
 426       fputc ('\n', out);
 427       fputs (s->solved_conflicts, out);
 428     }
 429 }
 430 \f
 431 /*-----------------------------------------.
 432 | Print information on the whole grammar.  |
 433 `-----------------------------------------*/
 434
 435 #define END_TEST(End)                           \
 436 do {                                            \
 437   if (column + strlen(buffer) > (End))          \
 438     {                                           \
 439       fprintf (out, "%s\n   ", buffer);         \
 440       column = 3;                               \
 441       buffer[0] = 0;                            \
 442     }                                           \
 443 } while (0)
 444
 445
 446 static void
 447 print_grammar (FILE *out)
 448 {
 449   symbol_number i;
 450   char buffer[90];
 451   int column = 0;
 452
 453   grammar_rules_print (out);
 454
 455   /* TERMINAL (type #) : rule #s terminal is on RHS */
 456   fprintf (out, "%s\n\n", _("Terminals, with rules where they appear"));
 457   for (i = 0; i < max_user_token_number + 1; i++)
 458     if (token_translations[i] != undeftoken->number)
 459       {
 460         const char *tag = symbols[token_translations[i]]->tag;
 461         rule_number r;
 462         item_number *rhsp;
 463
 464         buffer[0] = 0;
 465         column = strlen (tag);
 466         fputs (tag, out);
 467         END_TEST (50);
 468         sprintf (buffer, " (%d)", i);
 469
 470         for (r = 0; r < nrules; r++)
 471           for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
 472             if (item_number_as_symbol_number (*rhsp) == token_translations[i])
 473               {
 474                 END_TEST (65);
 475                 sprintf (buffer + strlen (buffer), " %d", r);
 476                 break;
 477               }
 478         fprintf (out, "%s\n", buffer);
 479       }
 480   fputs ("\n\n", out);
 481
 482
 483   fprintf (out, "%s\n\n", _("Nonterminals, with rules where they appear"));
 484   for (i = ntokens; i < nsyms; i++)
 485     {
 486       int left_count = 0, right_count = 0;
 487       rule_number r;
 488       const char *tag = symbols[i]->tag;
 489
 490       for (r = 0; r < nrules; r++)
 491         {
 492           item_number *rhsp;
 493           if (rules[r].lhs->number == i)
 494             left_count++;
 495           for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
 496             if (item_number_as_symbol_number (*rhsp) == i)
 497               {
 498                 right_count++;
 499                 break;
 500               }
 501         }
 502
 503       buffer[0] = 0;
 504       fputs (tag, out);
 505       column = strlen (tag);
 506       sprintf (buffer, " (%d)", i);
 507       END_TEST (0);
 508
 509       if (left_count > 0)
 510         {
 511           END_TEST (50);
 512           sprintf (buffer + strlen (buffer), _(" on left:"));
 513
 514           for (r = 0; r < nrules; r++)
 515             {
 516               END_TEST (65);
 517               if (rules[r].lhs->number == i)
 518                 sprintf (buffer + strlen (buffer), " %d", r);
 519             }
 520         }
 521
 522       if (right_count > 0)
 523         {
 524           if (left_count > 0)
 525             sprintf (buffer + strlen (buffer), ",");
 526           END_TEST (50);
 527           sprintf (buffer + strlen (buffer), _(" on right:"));
 528           for (r = 0; r < nrules; r++)
 529             {
 530               item_number *rhsp;
 531               for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
 532                 if (item_number_as_symbol_number (*rhsp) == i)
 533                   {
 534                     END_TEST (65);
 535                     sprintf (buffer + strlen (buffer), " %d", r);
 536                     break;
 537                   }
 538             }
 539         }
 540       fprintf (out, "%s\n", buffer);
 541     }
 542 }
 543 \f
 544 void
 545 print_results (void)
 546 {
 547   state_number i;
 548
 549   /* We used to use just .out if SPEC_NAME_PREFIX (-p) was used, but
 550      that conflicts with Posix.  */
 551   FILE *out = xfopen (spec_verbose_file, "w");
 552
 553   reduce_output (out);
 554   grammar_rules_partial_print (out,
 555                                _("Rules never reduced"), rule_never_reduced_p);
 556   conflicts_output (out);
 557
 558   print_grammar (out);
 559
 560   /* If the whole state item sets, not only the kernels, are wanted,
 561      `closure' will be run, which needs memory allocation/deallocation.   */
 562   if (report_flag & report_itemsets)
 563     new_closure (nritems);
 564   /* Storage for print_reductions.  */
 565   shiftset =  bitset_create (ntokens, BITSET_FIXED);
 566   lookaheadset = bitset_create (ntokens, BITSET_FIXED);
 567   for (i = 0; i < nstates; i++)
 568     print_state (out, states[i]);
 569   bitset_free (shiftset);
 570   bitset_free (lookaheadset);
 571   if (report_flag & report_itemsets)
 572     free_closure ();
 573
 574   xfclose (out);
 575 }