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 static void
 169 print_reductions (FILE *out, state_t *state)
 170 {
 171   int i;
 172   shifts_t *shiftp = state->shifts;
 173   reductions_t *redp = state->reductions;
 174   errs_t *errp = state->errs;
 175   int nodefault = 0;
 176
 177   if (redp->nreds == 0)
 178     return;
 179
 180   if (state->consistent)
 181     {
 182       int rule = redp->rules[0];
 183       symbol_number_t symbol = rules[rule].lhs->number;
 184       fprintf (out, _("    $default\treduce using rule %d (%s)\n\n"),
 185                rule - 1, symbol_tag_get (symbols[symbol]));
 186       return;
 187     }
 188
 189   bitset_zero (shiftset);
 190
 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           nodefault = 1;
 198         bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i));
 199       }
 200
 201   for (i = 0; i < errp->nerrs; i++)
 202     if (errp->errs[i])
 203       bitset_set (shiftset, errp->errs[i]);
 204
 205   if (state->nlookaheads == 1 && !nodefault)
 206     {
 207       rule_t *default_rule = state->lookaheads_rule[0];
 208
 209       bitset_and (lookaheadset, state->lookaheads[0], shiftset);
 210
 211       BITSET_EXECUTE (lookaheadset, 0, i,
 212       {
 213         fprintf (out, _("    %-4s\t[reduce using rule %d (%s)]\n"),
 214                  symbol_tag_get (symbols[i]),
 215                  default_rule->number - 1,
 216                  symbol_tag_get_n (default_rule->lhs, 1));
 217       });
 218       fprintf (out, _("    $default\treduce using rule %d (%s)\n\n"),
 219                default_rule->number - 1,
 220                symbol_tag_get (default_rule->lhs));
 221     }
 222   else if (state->nlookaheads >= 1)
 223     {
 224       int cmax = 0;
 225       int default_LA = -1;
 226       rule_t *default_rule = NULL;
 227
 228       if (!nodefault)
 229         for (i = 0; i < state->nlookaheads; ++i)
 230           {
 231             int count = 0;
 232
 233             bitset_andn (lookaheadset, state->lookaheads[i], shiftset);
 234             count = bitset_count (lookaheadset);
 235
 236             if (count > cmax)
 237               {
 238                 cmax = count;
 239                 default_LA = i;
 240                 default_rule = state->lookaheads_rule[i];
 241               }
 242
 243             bitset_or (shiftset, shiftset, lookaheadset);
 244           }
 245
 246       bitset_zero (shiftset);
 247
 248       for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
 249         if (!SHIFT_IS_DISABLED (shiftp, i))
 250           bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i));
 251
 252       for (i = 0; i < ntokens; i++)
 253         {
 254           int j;
 255           int defaulted = 0;
 256           int count = bitset_test (shiftset, i);
 257
 258           for (j = 0; j < state->nlookaheads; ++j)
 259             if (bitset_test (state->lookaheads[j], i))
 260               {
 261                 if (count == 0)
 262                   {
 263                     if (j != default_LA)
 264                       fprintf (out,
 265                                _("    %-4s\treduce using rule %d (%s)\n"),
 266                                symbol_tag_get (symbols[i]),
 267                                state->lookaheads_rule[j]->number - 1,
 268                                symbol_tag_get_n (state->lookaheads_rule[j]->lhs, 1));
 269                     else
 270                       defaulted = 1;
 271
 272                     count++;
 273                   }
 274                 else
 275                   {
 276                     if (defaulted)
 277                       fprintf (out,
 278                                _("    %-4s\treduce using rule %d (%s)\n"),
 279                                symbol_tag_get (symbols[i]),
 280                                state->lookaheads_rule[default_LA]->number - 1,
 281                                symbol_tag_get_n (state->lookaheads_rule[default_LA]->lhs, 1));
 282                     defaulted = 0;
 283                     fprintf (out,
 284                              _("    %-4s\t[reduce using rule %d (%s)]\n"),
 285                              symbol_tag_get (symbols[i]),
 286                              state->lookaheads_rule[j]->number - 1,
 287                              symbol_tag_get_n (state->lookaheads_rule[j]->lhs, 1));
 288                   }
 289               }
 290         }
 291
 292       if (default_LA >= 0)
 293         fprintf (out, _("    $default\treduce using rule %d (%s)\n"),
 294                  default_rule->number - 1,
 295                  symbol_tag_get (default_rule->lhs));
 296     }
 297 }
 298
 299
 300 static void
 301 print_actions (FILE *out, state_t *state)
 302 {
 303   reductions_t *redp = state->reductions;
 304   shifts_t *shiftp = state->shifts;
 305
 306   if (shiftp->nshifts == 0 && redp->nreds == 0)
 307     {
 308       if (state->number == final_state->number)
 309        fprintf (out, _("    $default\taccept\n"));
 310       else
 311        fprintf (out, _("    NO ACTIONS\n"));
 312       return;
 313     }
 314
 315   print_shifts (out, state);
 316   print_errs (out, state);
 317   print_reductions (out, state);
 318   print_gotos (out, state);
 319 }
 320
 321 static void
 322 print_state (FILE *out, state_t *state)
 323 {
 324   fprintf (out, _("state %d"), state->number);
 325   fputs ("\n\n", out);
 326   print_core (out, state);
 327   print_actions (out, state);
 328   if ((report_flag & report_solved_conflicts)
 329       && state->solved_conflicts)
 330     fputs (state->solved_conflicts, out);
 331   fputs ("\n\n", out);
 332 }
 333 \f
 334 /*-----------------------------------------.
 335 | Print information on the whole grammar.  |
 336 `-----------------------------------------*/
 337
 338 #define END_TEST(End)                           \
 339 do {                                            \
 340   if (column + strlen(buffer) > (End))          \
 341     {                                           \
 342       fprintf (out, "%s\n   ", buffer);         \
 343       column = 3;                               \
 344       buffer[0] = 0;                            \
 345     }                                           \
 346 } while (0)
 347
 348
 349 static void
 350 print_grammar (FILE *out)
 351 {
 352   symbol_number_t i;
 353   char buffer[90];
 354   int column = 0;
 355
 356   grammar_rules_print (out);
 357
 358   /* TERMINAL (type #) : rule #s terminal is on RHS */
 359   fprintf (out, "%s\n\n", _("Terminals, with rules where they appear"));
 360   for (i = 0; i < max_user_token_number + 1; i++)
 361     if (token_translations[i] != undeftoken->number)
 362       {
 363         const char *tag = symbol_tag_get (symbols[token_translations[i]]);
 364         rule_number_t r;
 365         item_number_t *rhsp;
 366
 367         buffer[0] = 0;
 368         column = strlen (tag);
 369         fputs (tag, out);
 370         END_TEST (50);
 371         sprintf (buffer, " (%d)", i);
 372
 373         for (r = 1; r < nrules + 1; r++)
 374           for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
 375             if (item_number_as_symbol_number (*rhsp) == token_translations[i])
 376               {
 377                 END_TEST (65);
 378                 sprintf (buffer + strlen (buffer), " %d", r - 1);
 379                 break;
 380               }
 381         fprintf (out, "%s\n", buffer);
 382       }
 383   fputs ("\n\n", out);
 384
 385
 386   fprintf (out, "%s\n\n", _("Nonterminals, with rules where they appear"));
 387   for (i = ntokens; i < nsyms; i++)
 388     {
 389       int left_count = 0, right_count = 0;
 390       rule_number_t r;
 391       const char *tag = symbol_tag_get (symbols[i]);
 392
 393       for (r = 1; r < nrules + 1; r++)
 394         {
 395           item_number_t *rhsp;
 396           if (rules[r].lhs->number == i)
 397             left_count++;
 398           for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
 399             if (item_number_as_symbol_number (*rhsp) == i)
 400               {
 401                 right_count++;
 402                 break;
 403               }
 404         }
 405
 406       buffer[0] = 0;
 407       fputs (tag, out);
 408       column = strlen (tag);
 409       sprintf (buffer, " (%d)", i);
 410       END_TEST (0);
 411
 412       if (left_count > 0)
 413         {
 414           END_TEST (50);
 415           sprintf (buffer + strlen (buffer), _(" on left:"));
 416
 417           for (r = 1; r < nrules + 1; r++)
 418             {
 419               END_TEST (65);
 420               if (rules[r].lhs->number == i)
 421                 sprintf (buffer + strlen (buffer), " %d", r - 1);
 422             }
 423         }
 424
 425       if (right_count > 0)
 426         {
 427           if (left_count > 0)
 428             sprintf (buffer + strlen (buffer), ",");
 429           END_TEST (50);
 430           sprintf (buffer + strlen (buffer), _(" on right:"));
 431           for (r = 1; r < nrules + 1; r++)
 432             {
 433               item_number_t *rhsp;
 434               for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
 435                 if (item_number_as_symbol_number (*rhsp) == i)
 436                   {
 437                     END_TEST (65);
 438                     sprintf (buffer + strlen (buffer), " %d", r - 1);
 439                     break;
 440                   }
 441             }
 442         }
 443       fprintf (out, "%s\n", buffer);
 444     }
 445   fputs ("\n\n", out);
 446 }
 447 \f
 448 void
 449 print_results (void)
 450 {
 451   state_number_t i;
 452
 453   /* We used to use just .out if SPEC_NAME_PREFIX (-p) was used, but
 454      that conflicts with Posix.  */
 455   FILE *out = xfopen (spec_verbose_file, "w");
 456
 457   reduce_output (out);
 458   conflicts_output (out);
 459
 460   print_grammar (out);
 461
 462   /* If the whole state item sets, not only the kernels, are wanted,
 463      `closure' will be run, which needs memory allocation/deallocation.   */
 464   if (report_flag & report_itemsets)
 465     new_closure (nritems);
 466   /* Storage for print_reductions.  */
 467   shiftset =  bitset_create (ntokens, BITSET_FIXED);
 468   lookaheadset = bitset_create (ntokens, BITSET_FIXED);
 469   for (i = 0; i < nstates; i++)
 470     print_state (out, states[i]);
 471   bitset_free (shiftset);
 472   bitset_free (lookaheadset);
 473   if (report_flag & report_itemsets)
 474     free_closure ();
 475
 476   xfclose (out);
 477 }