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