src/print.c

   1 /* Print information on generated parser, for bison,
   2    Copyright 1984, 1986, 1989, 2000, 2001, 2002 Free Software Foundation, Inc.
   3
   4    This file is part of Bison, the GNU Compiler Compiler.
   5
   6    Bison is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    Bison is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with Bison; see the file COPYING.  If not, write to
  18    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19    Boston, MA 02111-1307, USA.  */
  20
  21
  22 #include "system.h"
  23 #include "quotearg.h"
  24 #include "files.h"
  25 #include "symtab.h"
  26 #include "gram.h"
  27 #include "LR0.h"
  28 #include "lalr.h"
  29 #include "conflicts.h"
  30 #include "getargs.h"
  31 #include "state.h"
  32 #include "reader.h"
  33 #include "print.h"
  34 #include "reduce.h"
  35 #include "closure.h"
  36 #include "bitset.h"
  37
  38 static bitset shiftset;
  39 static bitset lookaheadset;
  40
  41 #if 0
  42 static void
  43 print_token (int extnum, int token)
  44 {
  45   fprintf (out, _(" type %d is %s\n"), extnum, tags[token]);
  46 }
  47 #endif
  48
  49 static inline const char *
  50 escape (const char *s)
  51 {
  52   return quotearg_n_style (1, escape_quoting_style, s);
  53 }
  54
  55 /* Be cautious not to use twice the same slot in a single expression. */
  56 static inline const char *
  57 escape2 (const char *s)
  58 {
  59   return quotearg_n_style (2, escape_quoting_style, s);
  60 }
  61
  62 \f
  63 /*--------------------------------.
  64 | Report information on a state.  |
  65 `--------------------------------*/
  66
  67 static void
  68 print_core (FILE *out, state_t *state)
  69 {
  70   int i;
  71   short *sitems = state->items;
  72   int snitems   = state->nitems;
  73
  74   /* New experimental feature: if TRACE_FLAGS output all the items of
  75      a state, not only its kernel.  */
  76   if (trace_flag)
  77     {
  78       closure (sitems, snitems);
  79       sitems = itemset;
  80       snitems = nitemset;
  81     }
  82
  83   if (snitems)
  84     {
  85       for (i = 0; i < snitems; i++)
  86         {
  87           short *sp;
  88           short *sp1;
  89           int rule;
  90
  91           sp1 = sp = ritem + sitems[i];
  92
  93           while (*sp >= 0)
  94             sp++;
  95
  96           rule = -(*sp);
  97           fprintf (out, "    %s  ->  ", escape (symbols[rules[rule].lhs]->tag));
  98
  99           for (sp = ritem + rules[rule].rhs; sp < sp1; sp++)
 100             fprintf (out, "%s ", escape (symbols[*sp]->tag));
 101
 102           fputc ('.', out);
 103
 104           for (/* Nothing */; *sp >= 0; ++sp)
 105             fprintf (out, " %s", escape (symbols[*sp]->tag));
 106
 107           fprintf (out, _("   (rule %d)"), rule - 1);
 108           fputc ('\n', out);
 109         }
 110
 111       fputc ('\n', out);
 112     }
 113 }
 114
 115
 116 static void
 117 print_shifts (FILE *out, state_t *state)
 118 {
 119   int i;
 120   shifts *shiftp = state->shifts;
 121
 122   for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
 123     if (!SHIFT_IS_DISABLED (shiftp, i))
 124       {
 125         int state1 = shiftp->shifts[i];
 126         int symbol = states[state1]->accessing_symbol;
 127         fprintf (out,
 128                  _("    %-4s\tshift, and go to state %d\n"),
 129                  escape (symbols[symbol]->tag), state1);
 130       }
 131
 132   if (i > 0)
 133     fputc ('\n', out);
 134 }
 135
 136
 137 static void
 138 print_errs (FILE *out, state_t *state)
 139 {
 140   errs *errp = state->errs;
 141   int i;
 142
 143   for (i = 0; i < errp->nerrs; ++i)
 144     if (errp->errs[i])
 145       fprintf (out, _("    %-4s\terror (nonassociative)\n"),
 146                escape (symbols[errp->errs[i]]->tag));
 147
 148   if (i > 0)
 149     fputc ('\n', out);
 150 }
 151
 152
 153 static void
 154 print_gotos (FILE *out, state_t *state)
 155 {
 156   int i;
 157   shifts *shiftp = state->shifts;
 158
 159   for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
 160     /* Skip token shifts.  */;
 161
 162   if (i < shiftp->nshifts)
 163     {
 164       for (; i < shiftp->nshifts; i++)
 165         if (!SHIFT_IS_DISABLED (shiftp, i))
 166           {
 167             int state1 = shiftp->shifts[i];
 168             int symbol = states[state1]->accessing_symbol;
 169             fprintf (out, _("    %-4s\tgo to state %d\n"),
 170                      escape (symbols[symbol]->tag), state1);
 171           }
 172
 173       fputc ('\n', out);
 174     }
 175 }
 176
 177 static void
 178 print_reductions (FILE *out, state_t *state)
 179 {
 180   int i;
 181   shifts *shiftp = state->shifts;
 182   reductions *redp = state->reductions;
 183   errs *errp = state->errs;
 184   int nodefault = 0;
 185
 186   if (redp->nreds == 0)
 187     return;
 188
 189   if (state->consistent)
 190     {
 191       int rule = redp->rules[0];
 192       int symbol = rules[rule].lhs;
 193       fprintf (out, _("    $default\treduce using rule %d (%s)\n\n"),
 194                rule - 1, escape (symbols[symbol]->tag));
 195       return;
 196     }
 197
 198   bitset_zero (shiftset);
 199
 200   for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
 201     if (!SHIFT_IS_DISABLED (shiftp, i))
 202       {
 203         /* if this state has a shift for the error token, don't use a
 204            default rule.  */
 205         if (SHIFT_IS_ERROR (shiftp, i))
 206           nodefault = 1;
 207         bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i));
 208       }
 209
 210   for (i = 0; i < errp->nerrs; i++)
 211     if (errp->errs[i])
 212       bitset_set (shiftset, errp->errs[i]);
 213
 214   if (state->nlookaheads == 1 && !nodefault)
 215     {
 216       int default_rule = LAruleno[state->lookaheadsp];
 217
 218       for (i = 0; i < ntokens; ++i)
 219         if (BITISSET (LA (state->lookaheadsp), i)
 220             && bitset_test (shiftset, i))
 221           bitset_set (lookaheadset, i);
 222         else
 223           bitset_reset (lookaheadset, i);
 224
 225       for (i = 0; i < ntokens; i++)
 226         if (bitset_test (lookaheadset, i))
 227           fprintf (out, _("    %-4s\t[reduce using rule %d (%s)]\n"),
 228                    escape (symbols[i]->tag), default_rule - 1,
 229                    escape2 (symbols[rules[default_rule].lhs]->tag));
 230
 231       fprintf (out, _("    $default\treduce using rule %d (%s)\n\n"),
 232                default_rule - 1, escape (symbols[rules[default_rule].lhs]->tag));
 233     }
 234   else if (state->nlookaheads >= 1)
 235     {
 236       int cmax = 0;
 237       int default_LA = -1;
 238       int default_rule = 0;
 239
 240       if (!nodefault)
 241         for (i = 0; i < state->nlookaheads; ++i)
 242           {
 243             int count = 0;
 244             int j, k;
 245
 246             for (k = 0; k < ntokens; ++k)
 247               if (BITISSET (LA (state->lookaheadsp + i), k)
 248                   && ! bitset_test (shiftset, k))
 249                 bitset_set (lookaheadset, k);
 250               else
 251                 bitset_reset (lookaheadset, k);
 252
 253             for (j = 0; j < ntokens; j++)
 254               if (bitset_test (lookaheadset, j))
 255                 count++;
 256
 257             if (count > cmax)
 258               {
 259                 cmax = count;
 260                 default_LA = state->lookaheadsp + i;
 261                 default_rule = LAruleno[state->lookaheadsp + i];
 262               }
 263
 264             bitset_or (shiftset, shiftset, lookaheadset);
 265           }
 266
 267       bitset_zero (shiftset);
 268
 269       for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
 270         if (!SHIFT_IS_DISABLED (shiftp, i))
 271           bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i));
 272
 273       for (i = 0; i < ntokens; i++)
 274         {
 275           int j;
 276           int defaulted = 0;
 277           int count = bitset_test (shiftset, i);
 278
 279           for (j = 0; j < state->nlookaheads; ++j)
 280             {
 281               if (BITISSET (LA (state->lookaheadsp + j), i))
 282                 {
 283                   if (count == 0)
 284                     {
 285                       if (state->lookaheadsp + j != default_LA)
 286                         fprintf (out,
 287                                  _("    %-4s\treduce using rule %d (%s)\n"),
 288                                  escape (symbols[i]->tag),
 289                                  LAruleno[state->lookaheadsp + j] - 1,
 290                                  escape2 (symbols[rules[LAruleno[state->lookaheadsp + j]].lhs]->tag));
 291                       else
 292                         defaulted = 1;
 293
 294                       count++;
 295                     }
 296                   else
 297                     {
 298                       if (defaulted)
 299                         fprintf (out,
 300                                  _("    %-4s\treduce using rule %d (%s)\n"),
 301                                  escape (symbols[i]->tag),
 302                                  LAruleno[default_LA] - 1,
 303                                  escape2 (symbols[rules[LAruleno[default_LA]].lhs]->tag));
 304                       defaulted = 0;
 305                       fprintf (out,
 306                                _("    %-4s\t[reduce using rule %d (%s)]\n"),
 307                                escape (symbols[i]->tag),
 308                                LAruleno[state->lookaheadsp + j] - 1,
 309                                escape2 (symbols[rules[LAruleno[state->lookaheadsp + j]].lhs]->tag));
 310                     }
 311                 }
 312             }
 313         }
 314
 315       if (default_LA >= 0)
 316         fprintf (out, _("    $default\treduce using rule %d (%s)\n"),
 317                  default_rule - 1,
 318                  escape (symbols[rules[default_rule].lhs]->tag));
 319     }
 320 }
 321
 322
 323 static void
 324 print_actions (FILE *out, state_t *state)
 325 {
 326   reductions *redp = state->reductions;
 327   shifts *shiftp = state->shifts;
 328
 329   if (shiftp->nshifts == 0 && redp->nreds == 0)
 330     {
 331       if (final_state == state->number)
 332        fprintf (out, _("    $default\taccept\n"));
 333       else
 334        fprintf (out, _("    NO ACTIONS\n"));
 335       return;
 336     }
 337
 338   print_shifts (out, state);
 339   print_errs (out, state);
 340   print_reductions (out, state);
 341   print_gotos (out, state);
 342 }
 343
 344 static void
 345 print_state (FILE *out, state_t *state)
 346 {
 347   fprintf (out, _("state %d"), state->number);
 348   fputs ("\n\n", out);
 349   print_core (out, state);
 350   print_actions (out, state);
 351   fputs ("\n\n", out);
 352 }
 353 \f
 354 /*-----------------------------------------.
 355 | Print information on the whole grammar.  |
 356 `-----------------------------------------*/
 357
 358 #define END_TEST(End)                           \
 359 do {                                            \
 360   if (column + strlen(buffer) > (End))          \
 361     {                                           \
 362       fprintf (out, "%s\n   ", buffer);         \
 363       column = 3;                               \
 364       buffer[0] = 0;                            \
 365     }                                           \
 366 } while (0)
 367
 368
 369 static void
 370 print_grammar (FILE *out)
 371 {
 372   int i, j;
 373   short *rule;
 374   char buffer[90];
 375   int column = 0;
 376
 377   /* rule # : LHS -> RHS */
 378   fprintf (out, "%s\n\n", _("Grammar"));
 379   fprintf (out, "  %s\n", _("Number, Line, Rule"));
 380   for (i = 1; i <= nrules; i++)
 381     /* Don't print rules disabled in reduce_grammar_tables.  */
 382     if (rules[i].useful)
 383       {
 384         fprintf (out, _("  %3d %3d %s ->"),
 385                  i - 1, rules[i].line, escape (symbols[rules[i].lhs]->tag));
 386         rule = &ritem[rules[i].rhs];
 387         if (*rule >= 0)
 388           while (*rule >= 0)
 389             fprintf (out, " %s", escape (symbols[*rule++]->tag));
 390         else
 391           fprintf (out, " /* %s */", _("empty"));
 392         fputc ('\n', out);
 393       }
 394   fputs ("\n\n", out);
 395
 396
 397   /* TERMINAL (type #) : rule #s terminal is on RHS */
 398   fprintf (out, "%s\n\n", _("Terminals, with rules where they appear"));
 399   for (i = 0; i <= max_user_token_number; i++)
 400     if (token_translations[i] != 2)
 401       {
 402         buffer[0] = 0;
 403         column = strlen (escape (symbols[token_translations[i]]->tag));
 404         fputs (escape (symbols[token_translations[i]]->tag), out);
 405         END_TEST (50);
 406         sprintf (buffer, " (%d)", i);
 407
 408         for (j = 1; j <= nrules; j++)
 409           for (rule = &ritem[rules[j].rhs]; *rule >= 0; rule++)
 410             if (*rule == token_translations[i])
 411               {
 412                 END_TEST (65);
 413                 sprintf (buffer + strlen (buffer), " %d", j - 1);
 414                 break;
 415               }
 416         fprintf (out, "%s\n", buffer);
 417       }
 418   fputs ("\n\n", out);
 419
 420
 421   fprintf (out, "%s\n\n", _("Nonterminals, with rules where they appear"));
 422   for (i = ntokens; i <= nsyms - 1; i++)
 423     {
 424       int left_count = 0, right_count = 0;
 425
 426       for (j = 1; j <= nrules; j++)
 427         {
 428           if (rules[j].lhs == i)
 429             left_count++;
 430           for (rule = &ritem[rules[j].rhs]; *rule >= 0; rule++)
 431             if (*rule == i)
 432               {
 433                 right_count++;
 434                 break;
 435               }
 436         }
 437
 438       buffer[0] = 0;
 439       fputs (escape (symbols[i]->tag), out);
 440       column = strlen (escape (symbols[i]->tag));
 441       sprintf (buffer, " (%d)", i);
 442       END_TEST (0);
 443
 444       if (left_count > 0)
 445         {
 446           END_TEST (50);
 447           sprintf (buffer + strlen (buffer), _(" on left:"));
 448
 449           for (j = 1; j <= nrules; j++)
 450             {
 451               END_TEST (65);
 452               if (rules[j].lhs == i)
 453                 sprintf (buffer + strlen (buffer), " %d", j - 1);
 454             }
 455         }
 456
 457       if (right_count > 0)
 458         {
 459           if (left_count > 0)
 460             sprintf (buffer + strlen (buffer), ",");
 461           END_TEST (50);
 462           sprintf (buffer + strlen (buffer), _(" on right:"));
 463           for (j = 1; j <= nrules; j++)
 464             {
 465               for (rule = &ritem[rules[j].rhs]; *rule >= 0; rule++)
 466                 if (*rule == i)
 467                   {
 468                     END_TEST (65);
 469                     sprintf (buffer + strlen (buffer), " %d", j - 1);
 470                     break;
 471                   }
 472             }
 473         }
 474       fprintf (out, "%s\n", buffer);
 475     }
 476   fputs ("\n\n", out);
 477 }
 478 \f
 479 void
 480 print_results (void)
 481 {
 482   int i;
 483
 484   /* We used to use just .out if SPEC_NAME_PREFIX (-p) was used, but
 485      that conflicts with Posix.  */
 486   FILE *out = xfopen (spec_verbose_file, "w");
 487
 488   size_t size = obstack_object_size (&output_obstack);
 489   fwrite (obstack_finish (&output_obstack), 1, size, out);
 490   obstack_free (&output_obstack, NULL);
 491
 492   if (size)
 493     fputs ("\n\n", out);
 494
 495   reduce_output (out);
 496   conflicts_output (out);
 497
 498   print_grammar (out);
 499
 500   /* New experimental feature: output all the items of a state, not
 501      only its kernel.  Requires to run closure, which need memory
 502      allocation/deallocation.  */
 503   if (trace_flag)
 504     new_closure (nritems);
 505   /* Storage for print_reductions.  */
 506   shiftset =  bitset_create (ntokens, BITSET_FIXED);
 507   bitset_zero (shiftset);
 508   lookaheadset = bitset_create (ntokens, BITSET_FIXED);
 509   bitset_zero (lookaheadset);
 510   for (i = 0; i < nstates; i++)
 511     print_state (out, states[i]);
 512   bitset_free (shiftset);
 513   bitset_free (lookaheadset);
 514   if (trace_flag)
 515     free_closure ();
 516
 517   xfclose (out);
 518 }