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