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 static inline const char *
  51 escape (const char *s)
  52 {
  53   return quotearg_n_style (1, escape_quoting_style, s);
  54 }
  55
  56 /* Be cautious not to use twice the same slot in a single expression. */
  57 static inline const char *
  58 escape2 (const char *s)
  59 {
  60   return quotearg_n_style (2, escape_quoting_style, s);
  61 }
  62
  63 \f
  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
  75   /* New experimental feature: if TRACE_FLAGS output all the items of
  76      a state, not only its kernel.  */
  77   if (trace_flag)
  78     {
  79       closure (sitems, snritems);
  80       sitems = itemset;
  81       snritems = nritemset;
  82     }
  83
  84   if (snritems)
  85     {
  86       for (i = 0; i < snritems; i++)
  87         {
  88           item_number_t *sp;
  89           item_number_t *sp1;
  90           int rule;
  91
  92           sp1 = sp = ritem + sitems[i];
  93
  94           while (*sp >= 0)
  95             sp++;
  96
  97           rule = -(*sp);
  98           fprintf (out, "    %s  ->  ", escape (rules[rule].lhs->tag));
  99
 100           for (sp = rules[rule].rhs; sp < sp1; sp++)
 101             fprintf (out, "%s ", escape (symbols[*sp]->tag));
 102
 103           fputc ('.', out);
 104
 105           for (/* Nothing */; *sp >= 0; ++sp)
 106             fprintf (out, " %s", escape (symbols[*sp]->tag));
 107
 108           /* Experimental feature: display the lookaheads. */
 109           if (trace_flag && state->nlookaheads)
 110             {
 111               int j, k;
 112               int nlookaheads = 0;
 113               /* Look for lookaheads corresponding to this rule. */
 114               for (j = 0; j < state->nlookaheads; ++j)
 115                 for (k = 0; k < ntokens; ++k)
 116                   if (bitset_test (LA[state->lookaheadsp + j], k)
 117                       && LArule[state->lookaheadsp + j]->number == rule)
 118                     nlookaheads++;
 119               if (nlookaheads)
 120                 {
 121                   fprintf (out, "  [");
 122                   for (j = 0; j < state->nlookaheads; ++j)
 123                     for (k = 0; k < ntokens; ++k)
 124                       if (bitset_test (LA[state->lookaheadsp + j], k)
 125                           && LArule[state->lookaheadsp + j]->number == rule)
 126                         fprintf (out, "%s%s",
 127                                  quotearg_style (escape_quoting_style,
 128                                                  symbols[k]->tag),
 129                                  --nlookaheads ? ", " : "");
 130                   fprintf (out, "]");
 131                 }
 132             }
 133
 134           fprintf (out, _("   (rule %d)"), rule - 1);
 135           fputc ('\n', out);
 136         }
 137
 138       fputc ('\n', out);
 139     }
 140 }
 141
 142
 143 static void
 144 print_shifts (FILE *out, state_t *state)
 145 {
 146   int i;
 147   shifts *shiftp = state->shifts;
 148
 149   for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
 150     if (!SHIFT_IS_DISABLED (shiftp, i))
 151       {
 152         int state1 = shiftp->shifts[i];
 153         token_number_t symbol = states[state1]->accessing_symbol;
 154         fprintf (out,
 155                  _("    %-4s\tshift, and go to state %d\n"),
 156                  escape (symbols[symbol]->tag), state1);
 157       }
 158
 159   if (i > 0)
 160     fputc ('\n', out);
 161 }
 162
 163
 164 static void
 165 print_errs (FILE *out, state_t *state)
 166 {
 167   errs *errp = state->errs;
 168   int i;
 169
 170   for (i = 0; i < errp->nerrs; ++i)
 171     if (errp->errs[i])
 172       fprintf (out, _("    %-4s\terror (nonassociative)\n"),
 173                escape (symbols[errp->errs[i]]->tag));
 174
 175   if (i > 0)
 176     fputc ('\n', out);
 177 }
 178
 179
 180 static void
 181 print_gotos (FILE *out, state_t *state)
 182 {
 183   int i;
 184   shifts *shiftp = state->shifts;
 185
 186   for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
 187     /* Skip token shifts.  */;
 188
 189   if (i < shiftp->nshifts)
 190     {
 191       for (; i < shiftp->nshifts; i++)
 192         if (!SHIFT_IS_DISABLED (shiftp, i))
 193           {
 194             int state1 = shiftp->shifts[i];
 195             token_number_t symbol = states[state1]->accessing_symbol;
 196             fprintf (out, _("    %-4s\tgo to state %d\n"),
 197                      escape (symbols[symbol]->tag), state1);
 198           }
 199
 200       fputc ('\n', out);
 201     }
 202 }
 203
 204 static void
 205 print_reductions (FILE *out, state_t *state)
 206 {
 207   int i;
 208   shifts *shiftp = state->shifts;
 209   reductions *redp = state->reductions;
 210   errs *errp = state->errs;
 211   int nodefault = 0;
 212
 213   if (redp->nreds == 0)
 214     return;
 215
 216   if (state->consistent)
 217     {
 218       int rule = redp->rules[0];
 219       token_number_t symbol = rules[rule].lhs->number;
 220       fprintf (out, _("    $default\treduce using rule %d (%s)\n\n"),
 221                rule - 1, escape (symbols[symbol]->tag));
 222       return;
 223     }
 224
 225   bitset_zero (shiftset);
 226
 227   for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
 228     if (!SHIFT_IS_DISABLED (shiftp, i))
 229       {
 230         /* if this state has a shift for the error token, don't use a
 231            default rule.  */
 232         if (SHIFT_IS_ERROR (shiftp, i))
 233           nodefault = 1;
 234         bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i));
 235       }
 236
 237   for (i = 0; i < errp->nerrs; i++)
 238     if (errp->errs[i])
 239       bitset_set (shiftset, errp->errs[i]);
 240
 241   if (state->nlookaheads == 1 && !nodefault)
 242     {
 243       rule_t *default_rule = LArule[state->lookaheadsp];
 244
 245       bitset_and (lookaheadset, LA[state->lookaheadsp], shiftset);
 246
 247       for (i = 0; i < ntokens; i++)
 248         if (bitset_test (lookaheadset, i))
 249           fprintf (out, _("    %-4s\t[reduce using rule %d (%s)]\n"),
 250                    escape (symbols[i]->tag),
 251                    default_rule->number - 1,
 252                    escape2 (default_rule->lhs->tag));
 253
 254       fprintf (out, _("    $default\treduce using rule %d (%s)\n\n"),
 255                default_rule->number - 1,
 256                escape (default_rule->lhs->tag));
 257     }
 258   else if (state->nlookaheads >= 1)
 259     {
 260       int cmax = 0;
 261       int default_LA = -1;
 262       rule_t *default_rule = NULL;
 263
 264       if (!nodefault)
 265         for (i = 0; i < state->nlookaheads; ++i)
 266           {
 267             int count = 0;
 268             int j;
 269
 270             bitset_andn (lookaheadset, LA[state->lookaheadsp + i], shiftset);
 271
 272             for (j = 0; j < ntokens; j++)
 273               if (bitset_test (lookaheadset, j))
 274                 count++;
 275
 276             if (count > cmax)
 277               {
 278                 cmax = count;
 279                 default_LA = state->lookaheadsp + i;
 280                 default_rule = LArule[state->lookaheadsp + i];
 281               }
 282
 283             bitset_or (shiftset, shiftset, lookaheadset);
 284           }
 285
 286       bitset_zero (shiftset);
 287
 288       for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
 289         if (!SHIFT_IS_DISABLED (shiftp, i))
 290           bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i));
 291
 292       for (i = 0; i < ntokens; i++)
 293         {
 294           int j;
 295           int defaulted = 0;
 296           int count = bitset_test (shiftset, i);
 297
 298           for (j = 0; j < state->nlookaheads; ++j)
 299             if (bitset_test (LA[state->lookaheadsp + j], i))
 300               {
 301                 if (count == 0)
 302                   {
 303                     if (state->lookaheadsp + j != default_LA)
 304                       fprintf (out,
 305                                _("    %-4s\treduce using rule %d (%s)\n"),
 306                                escape (symbols[i]->tag),
 307                                LArule[state->lookaheadsp + j]->number - 1,
 308                                escape2 (LArule[state->lookaheadsp + j]->lhs->tag));
 309                     else
 310                       defaulted = 1;
 311
 312                     count++;
 313                   }
 314                 else
 315                   {
 316                     if (defaulted)
 317                       fprintf (out,
 318                                _("    %-4s\treduce using rule %d (%s)\n"),
 319                                escape (symbols[i]->tag),
 320                                LArule[default_LA]->number - 1,
 321                                escape2 (LArule[default_LA]->lhs->tag));
 322                     defaulted = 0;
 323                     fprintf (out,
 324                              _("    %-4s\t[reduce using rule %d (%s)]\n"),
 325                              escape (symbols[i]->tag),
 326                              LArule[state->lookaheadsp + j]->number - 1,
 327                              escape2 (LArule[state->lookaheadsp + j]->lhs->tag));
 328                   }
 329               }
 330         }
 331
 332       if (default_LA >= 0)
 333         fprintf (out, _("    $default\treduce using rule %d (%s)\n"),
 334                  default_rule->number - 1,
 335                  escape (default_rule->lhs->tag));
 336     }
 337 }
 338
 339
 340 static void
 341 print_actions (FILE *out, state_t *state)
 342 {
 343   reductions *redp = state->reductions;
 344   shifts *shiftp = state->shifts;
 345
 346   if (shiftp->nshifts == 0 && redp->nreds == 0)
 347     {
 348       if (final_state == state->number)
 349        fprintf (out, _("    $default\taccept\n"));
 350       else
 351        fprintf (out, _("    NO ACTIONS\n"));
 352       return;
 353     }
 354
 355   print_shifts (out, state);
 356   print_errs (out, state);
 357   print_reductions (out, state);
 358   print_gotos (out, state);
 359 }
 360
 361 static void
 362 print_state (FILE *out, state_t *state)
 363 {
 364   fprintf (out, _("state %d"), state->number);
 365   fputs ("\n\n", out);
 366   print_core (out, state);
 367   print_actions (out, state);
 368   fputs ("\n\n", out);
 369 }
 370 \f
 371 /*-----------------------------------------.
 372 | Print information on the whole grammar.  |
 373 `-----------------------------------------*/
 374
 375 #define END_TEST(End)                           \
 376 do {                                            \
 377   if (column + strlen(buffer) > (End))          \
 378     {                                           \
 379       fprintf (out, "%s\n   ", buffer);         \
 380       column = 3;                               \
 381       buffer[0] = 0;                            \
 382     }                                           \
 383 } while (0)
 384
 385
 386 static void
 387 print_grammar (FILE *out)
 388 {
 389   token_number_t i;
 390   int j;
 391   item_number_t *rule;
 392   char buffer[90];
 393   int column = 0;
 394
 395   /* rule # : LHS -> RHS */
 396   fprintf (out, "%s\n\n", _("Grammar"));
 397   fprintf (out, "  %s\n", _("Number, Line, Rule"));
 398   for (j = 1; j < nrules + 1; j++)
 399     {
 400       fprintf (out, _("  %3d %3d %s ->"),
 401                j - 1, rules[j].line, escape (rules[j].lhs->tag));
 402       rule = rules[j].rhs;
 403       if (*rule >= 0)
 404         while (*rule >= 0)
 405           fprintf (out, " %s", escape (symbols[*rule++]->tag));
 406       else
 407         fprintf (out, " /* %s */", _("empty"));
 408       fputc ('\n', out);
 409     }
 410   fputs ("\n\n", out);
 411
 412
 413   /* TERMINAL (type #) : rule #s terminal is on RHS */
 414   fprintf (out, "%s\n\n", _("Terminals, with rules where they appear"));
 415   for (i = 0; i < max_user_token_number + 1; i++)
 416     if (token_translations[i] != undeftoken->number)
 417       {
 418         buffer[0] = 0;
 419         column = strlen (escape (symbols[token_translations[i]]->tag));
 420         fputs (escape (symbols[token_translations[i]]->tag), out);
 421         END_TEST (50);
 422         sprintf (buffer, " (%d)", i);
 423
 424         for (j = 1; j < nrules + 1; j++)
 425           for (rule = rules[j].rhs; *rule >= 0; rule++)
 426             if (item_number_as_token_number (*rule) == token_translations[i])
 427               {
 428                 END_TEST (65);
 429                 sprintf (buffer + strlen (buffer), " %d", j - 1);
 430                 break;
 431               }
 432         fprintf (out, "%s\n", buffer);
 433       }
 434   fputs ("\n\n", out);
 435
 436
 437   fprintf (out, "%s\n\n", _("Nonterminals, with rules where they appear"));
 438   for (i = ntokens; i < nsyms; i++)
 439     {
 440       int left_count = 0, right_count = 0;
 441
 442       for (j = 1; j < nrules + 1; j++)
 443         {
 444           if (rules[j].lhs->number == i)
 445             left_count++;
 446           for (rule = rules[j].rhs; *rule >= 0; rule++)
 447             if (item_number_as_token_number (*rule) == i)
 448               {
 449                 right_count++;
 450                 break;
 451               }
 452         }
 453
 454       buffer[0] = 0;
 455       fputs (escape (symbols[i]->tag), out);
 456       column = strlen (escape (symbols[i]->tag));
 457       sprintf (buffer, " (%d)", i);
 458       END_TEST (0);
 459
 460       if (left_count > 0)
 461         {
 462           END_TEST (50);
 463           sprintf (buffer + strlen (buffer), _(" on left:"));
 464
 465           for (j = 1; j < nrules + 1; j++)
 466             {
 467               END_TEST (65);
 468               if (rules[j].lhs->number == i)
 469                 sprintf (buffer + strlen (buffer), " %d", j - 1);
 470             }
 471         }
 472
 473       if (right_count > 0)
 474         {
 475           if (left_count > 0)
 476             sprintf (buffer + strlen (buffer), ",");
 477           END_TEST (50);
 478           sprintf (buffer + strlen (buffer), _(" on right:"));
 479           for (j = 1; j < nrules + 1; j++)
 480             {
 481               for (rule = rules[j].rhs; *rule >= 0; rule++)
 482                 if (item_number_as_token_number (*rule) == i)
 483                   {
 484                     END_TEST (65);
 485                     sprintf (buffer + strlen (buffer), " %d", j - 1);
 486                     break;
 487                   }
 488             }
 489         }
 490       fprintf (out, "%s\n", buffer);
 491     }
 492   fputs ("\n\n", out);
 493 }
 494 \f
 495 void
 496 print_results (void)
 497 {
 498   size_t i;
 499
 500   /* We used to use just .out if SPEC_NAME_PREFIX (-p) was used, but
 501      that conflicts with Posix.  */
 502   FILE *out = xfopen (spec_verbose_file, "w");
 503
 504   size_t size = obstack_object_size (&output_obstack);
 505   fwrite (obstack_finish (&output_obstack), 1, size, out);
 506   obstack_free (&output_obstack, NULL);
 507
 508   if (size)
 509     fputs ("\n\n", out);
 510
 511   reduce_output (out);
 512   conflicts_output (out);
 513
 514   print_grammar (out);
 515
 516   /* New experimental feature: output all the items of a state, not
 517      only its kernel.  Requires to run closure, which need memory
 518      allocation/deallocation.  */
 519   if (trace_flag)
 520     new_closure (nritems);
 521   /* Storage for print_reductions.  */
 522   shiftset =  bitset_create (ntokens, BITSET_FIXED);
 523   lookaheadset = bitset_create (ntokens, BITSET_FIXED);
 524   for (i = 0; i < nstates; i++)
 525     print_state (out, states[i]);
 526   bitset_free (shiftset);
 527   bitset_free (lookaheadset);
 528   if (trace_flag)
 529     free_closure ();
 530
 531   xfclose (out);
 532 }