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     fputs (state->solved_conflicts, out);
 426 }
 427 \f
 428 /*-----------------------------------------.
 429 | Print information on the whole grammar.  |
 430 `-----------------------------------------*/
 431
 432 #define END_TEST(End)                           \
 433 do {                                            \
 434   if (column + strlen(buffer) > (End))          \
 435     {                                           \
 436       fprintf (out, "%s\n   ", buffer);         \
 437       column = 3;                               \
 438       buffer[0] = 0;                            \
 439     }                                           \
 440 } while (0)
 441
 442
 443 static void
 444 print_grammar (FILE *out)
 445 {
 446   symbol_number_t i;
 447   char buffer[90];
 448   int column = 0;
 449
 450   grammar_rules_print (out);
 451
 452   /* TERMINAL (type #) : rule #s terminal is on RHS */
 453   fprintf (out, "%s\n\n", _("Terminals, with rules where they appear"));
 454   for (i = 0; i < max_user_token_number + 1; i++)
 455     if (token_translations[i] != undeftoken->number)
 456       {
 457         const char *tag = symbols[token_translations[i]]->tag;
 458         rule_number_t r;
 459         item_number_t *rhsp;
 460
 461         buffer[0] = 0;
 462         column = strlen (tag);
 463         fputs (tag, out);
 464         END_TEST (50);
 465         sprintf (buffer, " (%d)", i);
 466
 467         for (r = 0; r < nrules; r++)
 468           for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
 469             if (item_number_as_symbol_number (*rhsp) == token_translations[i])
 470               {
 471                 END_TEST (65);
 472                 sprintf (buffer + strlen (buffer), " %d", r);
 473                 break;
 474               }
 475         fprintf (out, "%s\n", buffer);
 476       }
 477   fputs ("\n\n", out);
 478
 479
 480   fprintf (out, "%s\n\n", _("Nonterminals, with rules where they appear"));
 481   for (i = ntokens; i < nsyms; i++)
 482     {
 483       int left_count = 0, right_count = 0;
 484       rule_number_t r;
 485       const char *tag = symbols[i]->tag;
 486
 487       for (r = 0; r < nrules; r++)
 488         {
 489           item_number_t *rhsp;
 490           if (rules[r].lhs->number == i)
 491             left_count++;
 492           for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
 493             if (item_number_as_symbol_number (*rhsp) == i)
 494               {
 495                 right_count++;
 496                 break;
 497               }
 498         }
 499
 500       buffer[0] = 0;
 501       fputs (tag, out);
 502       column = strlen (tag);
 503       sprintf (buffer, " (%d)", i);
 504       END_TEST (0);
 505
 506       if (left_count > 0)
 507         {
 508           END_TEST (50);
 509           sprintf (buffer + strlen (buffer), _(" on left:"));
 510
 511           for (r = 0; r < nrules; r++)
 512             {
 513               END_TEST (65);
 514               if (rules[r].lhs->number == i)
 515                 sprintf (buffer + strlen (buffer), " %d", r);
 516             }
 517         }
 518
 519       if (right_count > 0)
 520         {
 521           if (left_count > 0)
 522             sprintf (buffer + strlen (buffer), ",");
 523           END_TEST (50);
 524           sprintf (buffer + strlen (buffer), _(" on right:"));
 525           for (r = 0; r < nrules; r++)
 526             {
 527               item_number_t *rhsp;
 528               for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
 529                 if (item_number_as_symbol_number (*rhsp) == i)
 530                   {
 531                     END_TEST (65);
 532                     sprintf (buffer + strlen (buffer), " %d", r);
 533                     break;
 534                   }
 535             }
 536         }
 537       fprintf (out, "%s\n", buffer);
 538     }
 539 }
 540 \f
 541 void
 542 print_results (void)
 543 {
 544   state_number_t i;
 545
 546   /* We used to use just .out if SPEC_NAME_PREFIX (-p) was used, but
 547      that conflicts with Posix.  */
 548   FILE *out = xfopen (spec_verbose_file, "w");
 549
 550   reduce_output (out);
 551   grammar_rules_partial_print (out,
 552                                _("Rules never reduced"), rule_never_reduced_p);
 553   conflicts_output (out);
 554
 555   print_grammar (out);
 556
 557   /* If the whole state item sets, not only the kernels, are wanted,
 558      `closure' will be run, which needs memory allocation/deallocation.   */
 559   if (report_flag & report_itemsets)
 560     new_closure (nritems);
 561   /* Storage for print_reductions.  */
 562   shiftset =  bitset_create (ntokens, BITSET_FIXED);
 563   lookaheadset = bitset_create (ntokens, BITSET_FIXED);
 564   for (i = 0; i < nstates; i++)
 565     print_state (out, states[i]);
 566   bitset_free (shiftset);
 567   bitset_free (lookaheadset);
 568   if (report_flag & report_itemsets)
 569     free_closure ();
 570
 571   xfclose (out);
 572 }