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 = 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       bitset_and (lookaheadset, LA[state->lookaheadsp], shiftset);
 219
 220       for (i = 0; i < ntokens; i++)
 221         if (bitset_test (lookaheadset, i))
 222           fprintf (out, _("    %-4s\t[reduce using rule %d (%s)]\n"),
 223                    escape (symbols[i]->tag), default_rule - 1,
 224                    escape2 (symbols[rules[default_rule].lhs]->tag));
 225
 226       fprintf (out, _("    $default\treduce using rule %d (%s)\n\n"),
 227                default_rule - 1, escape (symbols[rules[default_rule].lhs]->tag));
 228     }
 229   else if (state->nlookaheads >= 1)
 230     {
 231       int cmax = 0;
 232       int default_LA = -1;
 233       int default_rule = 0;
 234
 235       if (!nodefault)
 236         for (i = 0; i < state->nlookaheads; ++i)
 237           {
 238             int count = 0;
 239             int j;
 240
 241             bitset_andn (lookaheadset, LA[state->lookaheadsp + i], shiftset);
 242
 243             for (j = 0; j < ntokens; j++)
 244               if (bitset_test (lookaheadset, j))
 245                 count++;
 246
 247             if (count > cmax)
 248               {
 249                 cmax = count;
 250                 default_LA = state->lookaheadsp + i;
 251                 default_rule = LAruleno[state->lookaheadsp + i];
 252               }
 253
 254             bitset_or (shiftset, shiftset, lookaheadset);
 255           }
 256
 257       bitset_zero (shiftset);
 258
 259       for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
 260         if (!SHIFT_IS_DISABLED (shiftp, i))
 261           bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i));
 262
 263       for (i = 0; i < ntokens; i++)
 264         {
 265           int j;
 266           int defaulted = 0;
 267           int count = bitset_test (shiftset, i);
 268
 269           for (j = 0; j < state->nlookaheads; ++j)
 270             if (bitset_test (LA[state->lookaheadsp + j], i))
 271               {
 272                 if (count == 0)
 273                   {
 274                     if (state->lookaheadsp + j != default_LA)
 275                       fprintf (out,
 276                                _("    %-4s\treduce using rule %d (%s)\n"),
 277                                escape (symbols[i]->tag),
 278                                LAruleno[state->lookaheadsp + j] - 1,
 279                                escape2 (symbols[rules[LAruleno[state->lookaheadsp + j]].lhs]->tag));
 280                     else
 281                       defaulted = 1;
 282
 283                     count++;
 284                   }
 285                 else
 286                   {
 287                     if (defaulted)
 288                       fprintf (out,
 289                                _("    %-4s\treduce using rule %d (%s)\n"),
 290                                escape (symbols[i]->tag),
 291                                LAruleno[default_LA] - 1,
 292                                escape2 (symbols[rules[LAruleno[default_LA]].lhs]->tag));
 293                     defaulted = 0;
 294                     fprintf (out,
 295                              _("    %-4s\t[reduce using rule %d (%s)]\n"),
 296                              escape (symbols[i]->tag),
 297                              LAruleno[state->lookaheadsp + j] - 1,
 298                              escape2 (symbols[rules[LAruleno[state->lookaheadsp + j]].lhs]->tag));
 299                   }
 300               }
 301         }
 302
 303       if (default_LA >= 0)
 304         fprintf (out, _("    $default\treduce using rule %d (%s)\n"),
 305                  default_rule - 1,
 306                  escape (symbols[rules[default_rule].lhs]->tag));
 307     }
 308 }
 309
 310
 311 static void
 312 print_actions (FILE *out, state_t *state)
 313 {
 314   reductions *redp = state->reductions;
 315   shifts *shiftp = state->shifts;
 316
 317   if (shiftp->nshifts == 0 && redp->nreds == 0)
 318     {
 319       if (final_state == state->number)
 320        fprintf (out, _("    $default\taccept\n"));
 321       else
 322        fprintf (out, _("    NO ACTIONS\n"));
 323       return;
 324     }
 325
 326   print_shifts (out, state);
 327   print_errs (out, state);
 328   print_reductions (out, state);
 329   print_gotos (out, state);
 330 }
 331
 332 static void
 333 print_state (FILE *out, state_t *state)
 334 {
 335   fprintf (out, _("state %d"), state->number);
 336   fputs ("\n\n", out);
 337   print_core (out, state);
 338   print_actions (out, state);
 339   fputs ("\n\n", out);
 340 }
 341 \f
 342 /*-----------------------------------------.
 343 | Print information on the whole grammar.  |
 344 `-----------------------------------------*/
 345
 346 #define END_TEST(End)                           \
 347 do {                                            \
 348   if (column + strlen(buffer) > (End))          \
 349     {                                           \
 350       fprintf (out, "%s\n   ", buffer);         \
 351       column = 3;                               \
 352       buffer[0] = 0;                            \
 353     }                                           \
 354 } while (0)
 355
 356
 357 static void
 358 print_grammar (FILE *out)
 359 {
 360   int i, j;
 361   short *rule;
 362   char buffer[90];
 363   int column = 0;
 364
 365   /* rule # : LHS -> RHS */
 366   fprintf (out, "%s\n\n", _("Grammar"));
 367   fprintf (out, "  %s\n", _("Number, Line, Rule"));
 368   for (i = 1; i < nrules + 1; i++)
 369     /* Don't print rules disabled in reduce_grammar_tables.  */
 370     if (rules[i].useful)
 371       {
 372         fprintf (out, _("  %3d %3d %s ->"),
 373                  i - 1, rules[i].line, escape (symbols[rules[i].lhs]->tag));
 374         rule = rules[i].rhs;
 375         if (*rule >= 0)
 376           while (*rule >= 0)
 377             fprintf (out, " %s", escape (symbols[*rule++]->tag));
 378         else
 379           fprintf (out, " /* %s */", _("empty"));
 380         fputc ('\n', out);
 381       }
 382   fputs ("\n\n", out);
 383
 384
 385   /* TERMINAL (type #) : rule #s terminal is on RHS */
 386   fprintf (out, "%s\n\n", _("Terminals, with rules where they appear"));
 387   for (i = 0; i < max_user_token_number + 1; i++)
 388     if (token_translations[i] != 2)
 389       {
 390         buffer[0] = 0;
 391         column = strlen (escape (symbols[token_translations[i]]->tag));
 392         fputs (escape (symbols[token_translations[i]]->tag), out);
 393         END_TEST (50);
 394         sprintf (buffer, " (%d)", i);
 395
 396         for (j = 1; j < nrules + 1; j++)
 397           for (rule = rules[j].rhs; *rule >= 0; rule++)
 398             if (*rule == token_translations[i])
 399               {
 400                 END_TEST (65);
 401                 sprintf (buffer + strlen (buffer), " %d", j - 1);
 402                 break;
 403               }
 404         fprintf (out, "%s\n", buffer);
 405       }
 406   fputs ("\n\n", out);
 407
 408
 409   fprintf (out, "%s\n\n", _("Nonterminals, with rules where they appear"));
 410   for (i = ntokens; i < nsyms; i++)
 411     {
 412       int left_count = 0, right_count = 0;
 413
 414       for (j = 1; j < nrules + 1; j++)
 415         {
 416           if (rules[j].lhs == i)
 417             left_count++;
 418           for (rule = rules[j].rhs; *rule >= 0; rule++)
 419             if (*rule == i)
 420               {
 421                 right_count++;
 422                 break;
 423               }
 424         }
 425
 426       buffer[0] = 0;
 427       fputs (escape (symbols[i]->tag), out);
 428       column = strlen (escape (symbols[i]->tag));
 429       sprintf (buffer, " (%d)", i);
 430       END_TEST (0);
 431
 432       if (left_count > 0)
 433         {
 434           END_TEST (50);
 435           sprintf (buffer + strlen (buffer), _(" on left:"));
 436
 437           for (j = 1; j < nrules + 1; j++)
 438             {
 439               END_TEST (65);
 440               if (rules[j].lhs == i)
 441                 sprintf (buffer + strlen (buffer), " %d", j - 1);
 442             }
 443         }
 444
 445       if (right_count > 0)
 446         {
 447           if (left_count > 0)
 448             sprintf (buffer + strlen (buffer), ",");
 449           END_TEST (50);
 450           sprintf (buffer + strlen (buffer), _(" on right:"));
 451           for (j = 1; j < nrules + 1; j++)
 452             {
 453               for (rule = rules[j].rhs; *rule >= 0; rule++)
 454                 if (*rule == i)
 455                   {
 456                     END_TEST (65);
 457                     sprintf (buffer + strlen (buffer), " %d", j - 1);
 458                     break;
 459                   }
 460             }
 461         }
 462       fprintf (out, "%s\n", buffer);
 463     }
 464   fputs ("\n\n", out);
 465 }
 466 \f
 467 void
 468 print_results (void)
 469 {
 470   size_t i;
 471
 472   /* We used to use just .out if SPEC_NAME_PREFIX (-p) was used, but
 473      that conflicts with Posix.  */
 474   FILE *out = xfopen (spec_verbose_file, "w");
 475
 476   size_t size = obstack_object_size (&output_obstack);
 477   fwrite (obstack_finish (&output_obstack), 1, size, out);
 478   obstack_free (&output_obstack, NULL);
 479
 480   if (size)
 481     fputs ("\n\n", out);
 482
 483   reduce_output (out);
 484   conflicts_output (out);
 485
 486   print_grammar (out);
 487
 488   /* New experimental feature: output all the items of a state, not
 489      only its kernel.  Requires to run closure, which need memory
 490      allocation/deallocation.  */
 491   if (trace_flag)
 492     new_closure (nritems);
 493   /* Storage for print_reductions.  */
 494   shiftset =  bitset_create (ntokens, BITSET_FIXED);
 495   lookaheadset = bitset_create (ntokens, BITSET_FIXED);
 496   for (i = 0; i < nstates; i++)
 497     print_state (out, states[i]);
 498   bitset_free (shiftset);
 499   bitset_free (lookaheadset);
 500   if (trace_flag)
 501     free_closure ();
 502
 503   xfclose (out);
 504 }