src/print.c

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