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             state_rule_lookaheads_print (state, &rules[rule], out);
  97
  98           fprintf (out, _("   (rule %d)"), rule - 1);
  99           fputc ('\n', out);
 100         }
 101
 102       fputc ('\n', out);
 103     }
 104 }
 105
 106
 107 static void
 108 print_shifts (FILE *out, state_t *state)
 109 {
 110   int i;
 111   shifts_t *shiftp = state->shifts;
 112
 113   for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
 114     if (!SHIFT_IS_DISABLED (shiftp, i))
 115       {
 116         state_number_t state1 = shiftp->shifts[i];
 117         symbol_number_t symbol = states[state1]->accessing_symbol;
 118         fprintf (out,
 119                  _("    %-4s\tshift, and go to state %d\n"),
 120                  symbol_tag_get (symbols[symbol]), state1);
 121       }
 122
 123   if (i > 0)
 124     fputc ('\n', out);
 125 }
 126
 127
 128 static void
 129 print_errs (FILE *out, state_t *state)
 130 {
 131   errs_t *errp = state->errs;
 132   int i;
 133
 134   for (i = 0; i < errp->nerrs; ++i)
 135     if (errp->errs[i])
 136       fprintf (out, _("    %-4s\terror (nonassociative)\n"),
 137                symbol_tag_get (symbols[errp->errs[i]]));
 138
 139   if (i > 0)
 140     fputc ('\n', out);
 141 }
 142
 143
 144 static void
 145 print_gotos (FILE *out, state_t *state)
 146 {
 147   int i;
 148   shifts_t *shiftp = state->shifts;
 149
 150   for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
 151     /* Skip token shifts.  */;
 152
 153   if (i < shiftp->nshifts)
 154     {
 155       for (; i < shiftp->nshifts; i++)
 156         if (!SHIFT_IS_DISABLED (shiftp, i))
 157           {
 158             state_number_t state1 = shiftp->shifts[i];
 159             symbol_number_t symbol = states[state1]->accessing_symbol;
 160             fprintf (out, _("    %-4s\tgo to state %d\n"),
 161                      symbol_tag_get (symbols[symbol]), state1);
 162           }
 163
 164       fputc ('\n', out);
 165     }
 166 }
 167
 168
 169 /*----------------------------------------------------------.
 170 | Return the default rule of this STATE if it has one, NULL |
 171 | otherwise.                                                |
 172 `----------------------------------------------------------*/
 173
 174 static rule_t *
 175 state_default_rule_compute (state_t *state)
 176 {
 177   reductions_t *redp = state->reductions;
 178   rule_t *default_rule = NULL;
 179   int cmax = 0;
 180   int i;
 181
 182   /* No need for a lookahead.  */
 183   if (state->consistent)
 184     return &rules[redp->rules[0]];
 185
 186   /* 1. Each reduction is possibly masked by the lookaheads on which
 187      we shift (S/R conflicts)...  */
 188   bitset_zero (shiftset);
 189   {
 190     shifts_t *shiftp = state->shifts;
 191     for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
 192       if (!SHIFT_IS_DISABLED (shiftp, i))
 193         {
 194           /* If this state has a shift for the error token, don't use a
 195              default rule.  */
 196           if (SHIFT_IS_ERROR (shiftp, i))
 197             return NULL;
 198           bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i));
 199         }
 200   }
 201
 202   /* 2. Each reduction is possibly masked by the lookaheads on which
 203      we raise an error (due to %nonassoc).  */
 204   {
 205     errs_t *errp = state->errs;
 206     for (i = 0; i < errp->nerrs; i++)
 207       if (errp->errs[i])
 208         bitset_set (shiftset, errp->errs[i]);
 209   }
 210
 211   for (i = 0; i < state->nlookaheads; ++i)
 212     {
 213       int count = 0;
 214
 215       /* How many non-masked lookaheads are there for this reduction?
 216          */
 217       bitset_andn (lookaheadset, state->lookaheads[i], shiftset);
 218       count = bitset_count (lookaheadset);
 219
 220       if (count > cmax)
 221         {
 222           cmax = count;
 223           default_rule = state->lookaheads_rule[i];
 224         }
 225
 226       /* 3. And finally, each reduction is possibly masked by previous
 227          reductions (in R/R conflicts, we keep the first reductions).
 228          */
 229       bitset_or (shiftset, shiftset, state->lookaheads[i]);
 230     }
 231
 232   return default_rule;
 233 }
 234
 235
 236 /*----------------------------------------------------.
 237 | Report on OUT the reduction actions of this STATE.  |
 238 `----------------------------------------------------*/
 239
 240 static void
 241 print_reductions (FILE *out, state_t *state)
 242 {
 243   int i;
 244   shifts_t *shiftp = state->shifts;
 245   reductions_t *redp = state->reductions;
 246   rule_t *default_rule = NULL;
 247
 248   if (redp->nreds == 0)
 249     return;
 250
 251   default_rule = state_default_rule_compute (state);
 252
 253   bitset_zero (shiftset);
 254   for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
 255     if (!SHIFT_IS_DISABLED (shiftp, i))
 256       bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i));
 257
 258   for (i = 0; i < ntokens; i++)
 259     {
 260       int j;
 261       int defaulted = 0;
 262       int count = bitset_test (shiftset, i);
 263
 264       for (j = 0; j < state->nlookaheads; ++j)
 265         if (bitset_test (state->lookaheads[j], i))
 266           {
 267             if (count == 0)
 268               {
 269                 if (state->lookaheads_rule[j] != default_rule)
 270                   fprintf (out,
 271                            _("    %-4s\treduce using rule %d (%s)\n"),
 272                            symbol_tag_get (symbols[i]),
 273                            state->lookaheads_rule[j]->number - 1,
 274                            symbol_tag_get_n (state->lookaheads_rule[j]->lhs, 1));
 275                 else
 276                   defaulted = 1;
 277                 count++;
 278               }
 279             else
 280               {
 281                 if (defaulted)
 282                   fprintf (out,
 283                            _("    %-4s\treduce using rule %d (%s)\n"),
 284                            symbol_tag_get (symbols[i]),
 285                            default_rule->number - 1,
 286                            symbol_tag_get_n (default_rule->lhs, 1));
 287                 defaulted = 0;
 288                 fprintf (out,
 289                          _("    %-4s\t[reduce using rule %d (%s)]\n"),
 290                          symbol_tag_get (symbols[i]),
 291                          state->lookaheads_rule[j]->number - 1,
 292                          symbol_tag_get_n (state->lookaheads_rule[j]->lhs, 1));
 293               }
 294           }
 295     }
 296
 297   if (default_rule)
 298     fprintf (out, _("    $default\treduce using rule %d (%s)\n"),
 299              default_rule->number - 1,
 300              symbol_tag_get (default_rule->lhs));
 301   fputc ('\n', out);
 302 }
 303
 304
 305 /*--------------------------------------------------------------.
 306 | Report on OUT all the actions (shifts, gotos, reductions, and |
 307 | explicit erros from %nonassoc) of STATE.                      |
 308 `--------------------------------------------------------------*/
 309
 310 static void
 311 print_actions (FILE *out, state_t *state)
 312 {
 313   reductions_t *redp = state->reductions;
 314   shifts_t *shiftp = state->shifts;
 315
 316   if (shiftp->nshifts == 0 && redp->nreds == 0)
 317     {
 318       if (state->number == final_state->number)
 319         fprintf (out, _("    $default\taccept\n"));
 320       else
 321         fprintf (out, _("    NO ACTIONS\n"));
 322       return;
 323     }
 324
 325   print_shifts (out, state);
 326   print_errs (out, state);
 327   print_reductions (out, state);
 328   print_gotos (out, state);
 329 }
 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   if ((report_flag & report_solved_conflicts)
 340       && state->solved_conflicts)
 341     fputs (state->solved_conflicts, out);
 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   symbol_number_t i;
 364   char buffer[90];
 365   int column = 0;
 366
 367   grammar_rules_print (out);
 368
 369   /* TERMINAL (type #) : rule #s terminal is on RHS */
 370   fprintf (out, "%s\n\n", _("Terminals, with rules where they appear"));
 371   for (i = 0; i < max_user_token_number + 1; i++)
 372     if (token_translations[i] != undeftoken->number)
 373       {
 374         const char *tag = symbol_tag_get (symbols[token_translations[i]]);
 375         rule_number_t r;
 376         item_number_t *rhsp;
 377
 378         buffer[0] = 0;
 379         column = strlen (tag);
 380         fputs (tag, out);
 381         END_TEST (50);
 382         sprintf (buffer, " (%d)", i);
 383
 384         for (r = 1; r < nrules + 1; r++)
 385           for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
 386             if (item_number_as_symbol_number (*rhsp) == token_translations[i])
 387               {
 388                 END_TEST (65);
 389                 sprintf (buffer + strlen (buffer), " %d", r - 1);
 390                 break;
 391               }
 392         fprintf (out, "%s\n", buffer);
 393       }
 394   fputs ("\n\n", out);
 395
 396
 397   fprintf (out, "%s\n\n", _("Nonterminals, with rules where they appear"));
 398   for (i = ntokens; i < nsyms; i++)
 399     {
 400       int left_count = 0, right_count = 0;
 401       rule_number_t r;
 402       const char *tag = symbol_tag_get (symbols[i]);
 403
 404       for (r = 1; r < nrules + 1; r++)
 405         {
 406           item_number_t *rhsp;
 407           if (rules[r].lhs->number == i)
 408             left_count++;
 409           for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
 410             if (item_number_as_symbol_number (*rhsp) == i)
 411               {
 412                 right_count++;
 413                 break;
 414               }
 415         }
 416
 417       buffer[0] = 0;
 418       fputs (tag, out);
 419       column = strlen (tag);
 420       sprintf (buffer, " (%d)", i);
 421       END_TEST (0);
 422
 423       if (left_count > 0)
 424         {
 425           END_TEST (50);
 426           sprintf (buffer + strlen (buffer), _(" on left:"));
 427
 428           for (r = 1; r < nrules + 1; r++)
 429             {
 430               END_TEST (65);
 431               if (rules[r].lhs->number == i)
 432                 sprintf (buffer + strlen (buffer), " %d", r - 1);
 433             }
 434         }
 435
 436       if (right_count > 0)
 437         {
 438           if (left_count > 0)
 439             sprintf (buffer + strlen (buffer), ",");
 440           END_TEST (50);
 441           sprintf (buffer + strlen (buffer), _(" on right:"));
 442           for (r = 1; r < nrules + 1; r++)
 443             {
 444               item_number_t *rhsp;
 445               for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
 446                 if (item_number_as_symbol_number (*rhsp) == i)
 447                   {
 448                     END_TEST (65);
 449                     sprintf (buffer + strlen (buffer), " %d", r - 1);
 450                     break;
 451                   }
 452             }
 453         }
 454       fprintf (out, "%s\n", buffer);
 455     }
 456   fputs ("\n\n", out);
 457 }
 458 \f
 459 void
 460 print_results (void)
 461 {
 462   state_number_t i;
 463
 464   /* We used to use just .out if SPEC_NAME_PREFIX (-p) was used, but
 465      that conflicts with Posix.  */
 466   FILE *out = xfopen (spec_verbose_file, "w");
 467
 468   reduce_output (out);
 469   conflicts_output (out);
 470
 471   print_grammar (out);
 472
 473   /* If the whole state item sets, not only the kernels, are wanted,
 474      `closure' will be run, which needs memory allocation/deallocation.   */
 475   if (report_flag & report_itemsets)
 476     new_closure (nritems);
 477   /* Storage for print_reductions.  */
 478   shiftset =  bitset_create (ntokens, BITSET_FIXED);
 479   lookaheadset = bitset_create (ntokens, BITSET_FIXED);
 480   for (i = 0; i < nstates; i++)
 481     print_state (out, states[i]);
 482   bitset_free (shiftset);
 483   bitset_free (lookaheadset);
 484   if (report_flag & report_itemsets)
 485     free_closure ();
 486
 487   xfclose (out);
 488 }