src/print.c

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