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