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 #include "quotearg.h"
  25 #include "files.h"
  26 #include "symtab.h"
  27 #include "gram.h"
  28 #include "LR0.h"
  29 #include "lalr.h"
  30 #include "conflicts.h"
  31 #include "getargs.h"
  32 #include "state.h"
  33 #include "reader.h"
  34 #include "print.h"
  35 #include "reduce.h"
  36 #include "closure.h"
  37 #include "bitset.h"
  38
  39 static bitset shiftset;
  40 static bitset lookaheadset;
  41
  42 #if 0
  43 static void
  44 print_token (int extnum, int token)
  45 {
  46   fprintf (out, _(" type %d is %s\n"), extnum, tags[token]);
  47 }
  48 #endif
  49
  50 \f
  51
  52 /*---------------------------------------.
  53 | *WIDTH := max (*WIDTH, strlen (STR)).  |
  54 `---------------------------------------*/
  55
  56 static void
  57 max_length (size_t *width, const char *str)
  58 {
  59   size_t len = strlen (str);
  60   if (len > *width)
  61     *width = len;
  62 }
  63
  64 /*--------------------------------.
  65 | Report information on a state.  |
  66 `--------------------------------*/
  67
  68 static void
  69 print_core (FILE *out, state_t *state)
  70 {
  71   int i;
  72   item_number_t *sitems = state->items;
  73   int snritems   = state->nitems;
  74   symbol_t *previous_lhs = NULL;
  75
  76   /* Output all the items of a state, not only its kernel.  */
  77   if (report_flag & report_itemsets)
  78     {
  79       closure (sitems, snritems);
  80       sitems = itemset;
  81       snritems = nritemset;
  82     }
  83
  84   if (!snritems)
  85     return;
  86
  87   fputc ('\n', out);
  88
  89   for (i = 0; i < snritems; i++)
  90     {
  91       item_number_t *sp;
  92       item_number_t *sp1;
  93       int rule;
  94
  95       sp1 = sp = ritem + sitems[i];
  96
  97       while (*sp >= 0)
  98         sp++;
  99
 100       rule = item_number_as_rule_number (*sp);
 101
 102       rule_lhs_print (&rules[rule], previous_lhs, out);
 103       previous_lhs = rules[rule].lhs;
 104
 105       for (sp = rules[rule].rhs; sp < sp1; sp++)
 106         fprintf (out, " %s", symbols[*sp]->tag);
 107       fputs (" .", out);
 108       for (/* Nothing */; *sp >= 0; ++sp)
 109         fprintf (out, " %s", symbols[*sp]->tag);
 110
 111       /* Display the lookaheads?  */
 112       if (report_flag & report_lookaheads)
 113         state_rule_lookaheads_print (state, &rules[rule], out);
 114
 115       fputc ('\n', out);
 116     }
 117 }
 118
 119
 120 /*----------------------------------------------------------------.
 121 | Report the shifts iff DISPLAY_SHIFTS_P or the gotos of STATE on |
 122 | OUT.                                                            |
 123 `----------------------------------------------------------------*/
 124
 125 static void
 126 print_transitions (state_t *state, FILE *out, bool display_transitions_p)
 127 {
 128   transitions_t *transitions = state->transitions;
 129   size_t width = 0;
 130   int i;
 131
 132   /* Compute the width of the lookaheads column.  */
 133   for (i = 0; i < transitions->num; i++)
 134     if (!TRANSITION_IS_DISABLED (transitions, i)
 135         && TRANSITION_IS_SHIFT (transitions, i) == display_transitions_p)
 136       {
 137         symbol_t *symbol = symbols[TRANSITION_SYMBOL (transitions, i)];
 138         max_length (&width, symbol->tag);
 139       }
 140
 141   /* Nothing to report. */
 142   if (!width)
 143     return;
 144
 145   fputc ('\n', out);
 146   width += 2;
 147
 148   /* Report lookaheads and shifts.  */
 149   for (i = 0; i < transitions->num; i++)
 150     if (!TRANSITION_IS_DISABLED (transitions, i)
 151         && TRANSITION_IS_SHIFT (transitions, i) == display_transitions_p)
 152       {
 153         symbol_t *symbol = symbols[TRANSITION_SYMBOL (transitions, i)];
 154         const char *tag = symbol->tag;
 155         state_t *state1 = transitions->states[i];
 156         int j;
 157
 158         fprintf (out, "    %s", tag);
 159         for (j = width - strlen (tag); j > 0; --j)
 160           fputc (' ', out);
 161         if (display_transitions_p)
 162           fprintf (out, _("shift, and go to state %d\n"), state1->number);
 163         else
 164           fprintf (out, _("go to state %d\n"), state1->number);
 165       }
 166 }
 167
 168
 169 /*------------------------------------------------------------.
 170 | Report the explicit errors of STATE raised from %nonassoc.  |
 171 `------------------------------------------------------------*/
 172
 173 static void
 174 print_errs (FILE *out, state_t *state)
 175 {
 176   errs_t *errp = state->errs;
 177   size_t width = 0;
 178   int i;
 179
 180   /* Compute the width of the lookaheads column.  */
 181   for (i = 0; i < errp->num; ++i)
 182     if (errp->symbols[i])
 183       max_length (&width, errp->symbols[i]->tag);
 184
 185   /* Nothing to report. */
 186   if (!width)
 187     return;
 188
 189   fputc ('\n', out);
 190   width += 2;
 191
 192   /* Report lookaheads and errors.  */
 193   for (i = 0; i < errp->num; ++i)
 194     if (errp->symbols[i])
 195       {
 196         const char *tag = errp->symbols[i]->tag;
 197         int j;
 198         fprintf (out, "    %s", tag);
 199         for (j = width - strlen (tag); j > 0; --j)
 200           fputc (' ', out);
 201         fputs (_("error (nonassociative)\n"), out);
 202       }
 203 }
 204
 205
 206 /*----------------------------------------------------------.
 207 | Return the default rule of this STATE if it has one, NULL |
 208 | otherwise.                                                |
 209 `----------------------------------------------------------*/
 210
 211 static rule_t *
 212 state_default_rule (state_t *state)
 213 {
 214   reductions_t *redp = state->reductions;
 215   rule_t *default_rule = NULL;
 216   int cmax = 0;
 217   int i;
 218
 219   /* No need for a lookahead.  */
 220   if (state->consistent)
 221     return redp->rules[0];
 222
 223   /* 1. Each reduction is possibly masked by the lookaheads on which
 224      we shift (S/R conflicts)...  */
 225   bitset_zero (shiftset);
 226   {
 227     transitions_t *transitions = state->transitions;
 228     FOR_EACH_SHIFT (transitions, i)
 229       {
 230         /* If this state has a shift for the error token, don't use a
 231              default rule.  */
 232         if (TRANSITION_IS_ERROR (transitions, i))
 233           return NULL;
 234         bitset_set (shiftset, TRANSITION_SYMBOL (transitions, i));
 235       }
 236   }
 237
 238   /* 2. Each reduction is possibly masked by the lookaheads on which
 239      we raise an error (due to %nonassoc).  */
 240   {
 241     errs_t *errp = state->errs;
 242     for (i = 0; i < errp->num; i++)
 243       if (errp->symbols[i])
 244         bitset_set (shiftset, errp->symbols[i]->number);
 245   }
 246
 247   for (i = 0; i < redp->num; ++i)
 248     {
 249       int count = 0;
 250
 251       /* How many non-masked lookaheads are there for this reduction?
 252          */
 253       bitset_andn (lookaheadset, redp->lookaheads[i], shiftset);
 254       count = bitset_count (lookaheadset);
 255
 256       if (count > cmax)
 257         {
 258           cmax = count;
 259           default_rule = redp->rules[i];
 260         }
 261
 262       /* 3. And finally, each reduction is possibly masked by previous
 263          reductions (in R/R conflicts, we keep the first reductions).
 264          */
 265       bitset_or (shiftset, shiftset, redp->lookaheads[i]);
 266     }
 267
 268   return default_rule;
 269 }
 270
 271
 272 /*--------------------------------------------------------------------.
 273 | Report a reduction of RULE on LOOKAHEADS (which can be `default').  |
 274 | If not ENABLED, the rule is masked by a shift or a reduce (S/R and  |
 275 | R/R conflicts).                                                     |
 276 `--------------------------------------------------------------------*/
 277
 278 static void
 279 print_reduction (FILE *out, size_t width,
 280                  const char *lookahead,
 281                  rule_t *rule, bool enabled)
 282 {
 283   int j;
 284   fprintf (out, "    %s", lookahead);
 285   for (j = width - strlen (lookahead); j > 0; --j)
 286     fputc (' ', out);
 287   if (!enabled)
 288     fputc ('[', out);
 289   if (rule->number)
 290     fprintf (out, _("reduce using rule %d (%s)"),
 291              rule->number, rule->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 this STATE.  |
 302 `----------------------------------------------------*/
 303
 304 static void
 305 print_reductions (FILE *out, state_t *state)
 306 {
 307   transitions_t *transitions = state->transitions;
 308   reductions_t *redp = state->reductions;
 309   rule_t *default_rule = NULL;
 310   size_t width = 0;
 311   int i, j;
 312
 313   if (redp->num == 0)
 314     return;
 315
 316   default_rule = state_default_rule (state);
 317
 318   bitset_zero (shiftset);
 319   FOR_EACH_SHIFT (transitions, i)
 320     bitset_set (shiftset, TRANSITION_SYMBOL (transitions, i));
 321
 322   /* Compute the width of the lookaheads column.  */
 323   if (default_rule)
 324     width = strlen (_("$default"));
 325
 326   if (redp->lookaheads)
 327     for (i = 0; i < ntokens; i++)
 328       {
 329         int count = bitset_test (shiftset, i);
 330
 331         for (j = 0; j < redp->num; ++j)
 332           if (bitset_test (redp->lookaheads[j], i))
 333             {
 334               if (count == 0)
 335                 {
 336                   if (redp->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 (redp->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 < redp->num; ++j)
 362           if (bitset_test (redp->lookaheads[j], i))
 363             {
 364               if (count == 0)
 365                 {
 366                   if (redp->rules[j] != default_rule)
 367                     print_reduction (out, width,
 368                                      symbols[i]->tag,
 369                                      redp->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                                    redp->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 STATE.                      |
 397 `--------------------------------------------------------------*/
 398
 399 static void
 400 print_actions (FILE *out, state_t *state)
 401 {
 402   /* Print shifts.  */
 403   print_transitions (state, out, true);
 404   print_errs (out, state);
 405   print_reductions (out, state);
 406   /* Print gotos.  */
 407   print_transitions (state, out, false);
 408 }
 409
 410
 411 /*--------------------------------------.
 412 | Report all the data on STATE on OUT.  |
 413 `--------------------------------------*/
 414
 415 static void
 416 print_state (FILE *out, state_t *state)
 417 {
 418   fputs ("\n\n", out);
 419   fprintf (out, _("state %d"), state->number);
 420   fputc ('\n', out);
 421   print_core (out, state);
 422   print_actions (out, state);
 423   if ((report_flag & report_solved_conflicts)
 424       && state->solved_conflicts)
 425     {
 426       fputc ('\n', out);
 427       fputs (state->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_t 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_t r;
 462         item_number_t *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_t r;
 488       const char *tag = symbols[i]->tag;
 489
 490       for (r = 0; r < nrules; r++)
 491         {
 492           item_number_t *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_t *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_t 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 }