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