src/print.c

   1 /* Print information on generated parser, for bison,
   2
   3    Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004, 2005, 2007
   4    Free Software Foundation, Inc.
   5
   6    This file is part of Bison, the GNU Compiler Compiler.
   7
   8    Bison is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 2, or (at your option)
  11    any later version.
  12
  13    Bison is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with Bison; see the file COPYING.  If not, write to
  20    the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  21    Boston, MA 02110-1301, USA.  */
  22
  23 #include <config.h>
  24 #include "system.h"
  25
  26 #include <bitset.h>
  27 #include <quotearg.h>
  28
  29 #include "LR0.h"
  30 #include "closure.h"
  31 #include "conflicts.h"
  32 #include "files.h"
  33 #include "getargs.h"
  34 #include "gram.h"
  35 #include "lalr.h"
  36 #include "print.h"
  37 #include "reader.h"
  38 #include "reduce.h"
  39 #include "state.h"
  40 #include "symtab.h"
  41 #include "tables.h"
  42
  43 static bitset no_reduce_set;
  44
  45 #if 0
  46 static void
  47 print_token (int extnum, int token)
  48 {
  49   fprintf (out, _(" type %d is %s\n"), extnum, tags[token]);
  50 }
  51 #endif
  52
  53 \f
  54
  55 /*---------------------------------------.
  56 | *WIDTH := max (*WIDTH, strlen (STR)).  |
  57 `---------------------------------------*/
  58
  59 static void
  60 max_length (size_t *width, const char *str)
  61 {
  62   size_t len = strlen (str);
  63   if (len > *width)
  64     *width = len;
  65 }
  66
  67 /*--------------------------------.
  68 | Report information on a state.  |
  69 `--------------------------------*/
  70
  71 static void
  72 print_core (FILE *out, state *s)
  73 {
  74   size_t i;
  75   item_number *sitems = s->items;
  76   size_t snritems = s->nitems;
  77   symbol *previous_lhs = NULL;
  78
  79   /* Output all the items of a state, not only its kernel.  */
  80   if (report_flag & report_itemsets)
  81     {
  82       closure (sitems, snritems);
  83       sitems = itemset;
  84       snritems = nitemset;
  85     }
  86
  87   if (!snritems)
  88     return;
  89
  90   fputc ('\n', out);
  91
  92   for (i = 0; i < snritems; i++)
  93     {
  94       item_number *sp;
  95       item_number *sp1;
  96       rule_number r;
  97
  98       sp1 = sp = ritem + sitems[i];
  99
 100       while (*sp >= 0)
 101         sp++;
 102
 103       r = item_number_as_rule_number (*sp);
 104
 105       rule_lhs_print (&rules[r], previous_lhs, out);
 106       previous_lhs = rules[r].lhs;
 107
 108       for (sp = rules[r].rhs; sp < sp1; sp++)
 109         fprintf (out, " %s", symbols[*sp]->tag);
 110       fputs (" .", out);
 111       for (/* Nothing */; *sp >= 0; ++sp)
 112         fprintf (out, " %s", symbols[*sp]->tag);
 113
 114       /* Display the lookahead tokens?  */
 115       if (report_flag & report_lookahead_tokens)
 116         state_rule_lookahead_tokens_print (s, &rules[r], out);
 117
 118       fputc ('\n', out);
 119     }
 120 }
 121
 122
 123 /*------------------------------------------------------------.
 124 | Report the shifts iff DISPLAY_SHIFTS_P or the gotos of S on |
 125 | OUT.                                                        |
 126 `------------------------------------------------------------*/
 127
 128 static void
 129 print_transitions (state *s, FILE *out, bool display_transitions_p)
 130 {
 131   transitions *trans = s->transitions;
 132   size_t width = 0;
 133   int i;
 134
 135   /* Compute the width of the lookahead token column.  */
 136   for (i = 0; i < trans->num; i++)
 137     if (!TRANSITION_IS_DISABLED (trans, i)
 138         && TRANSITION_IS_SHIFT (trans, i) == display_transitions_p)
 139       {
 140         symbol *sym = symbols[TRANSITION_SYMBOL (trans, i)];
 141         max_length (&width, sym->tag);
 142       }
 143
 144   /* Nothing to report. */
 145   if (!width)
 146     return;
 147
 148   fputc ('\n', out);
 149   width += 2;
 150
 151   /* Report lookahead tokens and shifts.  */
 152   for (i = 0; i < trans->num; i++)
 153     if (!TRANSITION_IS_DISABLED (trans, i)
 154         && TRANSITION_IS_SHIFT (trans, i) == display_transitions_p)
 155       {
 156         symbol *sym = symbols[TRANSITION_SYMBOL (trans, i)];
 157         const char *tag = sym->tag;
 158         state *s1 = trans->states[i];
 159         int j;
 160
 161         fprintf (out, "    %s", tag);
 162         for (j = width - strlen (tag); j > 0; --j)
 163           fputc (' ', out);
 164         if (display_transitions_p)
 165           fprintf (out, _("shift, and go to state %d\n"), s1->number);
 166         else
 167           fprintf (out, _("go to state %d\n"), s1->number);
 168       }
 169 }
 170
 171
 172 /*--------------------------------------------------------.
 173 | Report the explicit errors of S raised from %nonassoc.  |
 174 `--------------------------------------------------------*/
 175
 176 static void
 177 print_errs (FILE *out, state *s)
 178 {
 179   errs *errp = s->errs;
 180   size_t width = 0;
 181   int i;
 182
 183   /* Compute the width of the lookahead token column.  */
 184   for (i = 0; i < errp->num; ++i)
 185     if (errp->symbols[i])
 186       max_length (&width, errp->symbols[i]->tag);
 187
 188   /* Nothing to report. */
 189   if (!width)
 190     return;
 191
 192   fputc ('\n', out);
 193   width += 2;
 194
 195   /* Report lookahead tokens and errors.  */
 196   for (i = 0; i < errp->num; ++i)
 197     if (errp->symbols[i])
 198       {
 199         const char *tag = errp->symbols[i]->tag;
 200         int j;
 201         fprintf (out, "    %s", tag);
 202         for (j = width - strlen (tag); j > 0; --j)
 203           fputc (' ', out);
 204         fputs (_("error (nonassociative)\n"), out);
 205       }
 206 }
 207
 208
 209 /*-------------------------------------------------------------------------.
 210 | Report a reduction of RULE on LOOKAHEAD_TOKEN (which can be `default').  |
 211 | If not ENABLED, the rule is masked by a shift or a reduce (S/R and       |
 212 | R/R conflicts).                                                          |
 213 `-------------------------------------------------------------------------*/
 214
 215 static void
 216 print_reduction (FILE *out, size_t width,
 217                  const char *lookahead_token,
 218                  rule *r, bool enabled)
 219 {
 220   int j;
 221   fprintf (out, "    %s", lookahead_token);
 222   for (j = width - strlen (lookahead_token); j > 0; --j)
 223     fputc (' ', out);
 224   if (!enabled)
 225     fputc ('[', out);
 226   if (r->number)
 227     fprintf (out, _("reduce using rule %d (%s)"), r->number, r->lhs->tag);
 228   else
 229     fprintf (out, _("accept"));
 230   if (!enabled)
 231     fputc (']', out);
 232   fputc ('\n', out);
 233 }
 234
 235
 236 /*-------------------------------------------.
 237 | Report on OUT the reduction actions of S.  |
 238 `-------------------------------------------*/
 239
 240 static void
 241 print_reductions (FILE *out, state *s)
 242 {
 243   transitions *trans = s->transitions;
 244   reductions *reds = s->reductions;
 245   rule *default_rule = NULL;
 246   size_t width = 0;
 247   int i, j;
 248
 249   if (reds->num == 0)
 250     return;
 251
 252   if (yydefact[s->number] != 0)
 253     default_rule = &rules[yydefact[s->number] - 1];
 254
 255   bitset_zero (no_reduce_set);
 256   FOR_EACH_SHIFT (trans, i)
 257     bitset_set (no_reduce_set, TRANSITION_SYMBOL (trans, i));
 258   for (i = 0; i < s->errs->num; ++i)
 259     if (s->errs->symbols[i])
 260       bitset_set (no_reduce_set, s->errs->symbols[i]->number);
 261
 262   /* Compute the width of the lookahead token column.  */
 263   if (default_rule)
 264     width = strlen (_("$default"));
 265
 266   if (reds->lookahead_tokens)
 267     for (i = 0; i < ntokens; i++)
 268       {
 269         bool count = bitset_test (no_reduce_set, i);
 270
 271         for (j = 0; j < reds->num; ++j)
 272           if (bitset_test (reds->lookahead_tokens[j], i))
 273             {
 274               if (! count)
 275                 {
 276                   if (reds->rules[j] != default_rule)
 277                     max_length (&width, symbols[i]->tag);
 278                   count = true;
 279                 }
 280               else
 281                 {
 282                   max_length (&width, symbols[i]->tag);
 283                 }
 284             }
 285       }
 286
 287   /* Nothing to report. */
 288   if (!width)
 289     return;
 290
 291   fputc ('\n', out);
 292   width += 2;
 293
 294   /* Report lookahead tokens (or $default) and reductions.  */
 295   if (reds->lookahead_tokens)
 296     for (i = 0; i < ntokens; i++)
 297       {
 298         bool defaulted = false;
 299         bool count = bitset_test (no_reduce_set, i);
 300
 301         for (j = 0; j < reds->num; ++j)
 302           if (bitset_test (reds->lookahead_tokens[j], i))
 303             {
 304               if (! count)
 305                 {
 306                   if (reds->rules[j] != default_rule)
 307                     print_reduction (out, width,
 308                                      symbols[i]->tag,
 309                                      reds->rules[j], true);
 310                   else
 311                     defaulted = true;
 312                   count = true;
 313                 }
 314               else
 315                 {
 316                   if (defaulted)
 317                     print_reduction (out, width,
 318                                      symbols[i]->tag,
 319                                      default_rule, true);
 320                   defaulted = false;
 321                   print_reduction (out, width,
 322                                    symbols[i]->tag,
 323                                    reds->rules[j], false);
 324                 }
 325             }
 326       }
 327
 328   if (default_rule)
 329     print_reduction (out, width,
 330                      _("$default"), default_rule, true);
 331 }
 332
 333
 334 /*--------------------------------------------------------------.
 335 | Report on OUT all the actions (shifts, gotos, reductions, and |
 336 | explicit erros from %nonassoc) of S.                          |
 337 `--------------------------------------------------------------*/
 338
 339 static void
 340 print_actions (FILE *out, state *s)
 341 {
 342   /* Print shifts.  */
 343   print_transitions (s, out, true);
 344   print_errs (out, s);
 345   print_reductions (out, s);
 346   /* Print gotos.  */
 347   print_transitions (s, out, false);
 348 }
 349
 350
 351 /*----------------------------------.
 352 | Report all the data on S on OUT.  |
 353 `----------------------------------*/
 354
 355 static void
 356 print_state (FILE *out, state *s)
 357 {
 358   fputs ("\n\n", out);
 359   fprintf (out, _("state %d"), s->number);
 360   fputc ('\n', out);
 361   print_core (out, s);
 362   print_actions (out, s);
 363   if ((report_flag & report_solved_conflicts) && s->solved_conflicts)
 364     {
 365       fputc ('\n', out);
 366       fputs (s->solved_conflicts, out);
 367     }
 368 }
 369 \f
 370 /*-----------------------------------------.
 371 | Print information on the whole grammar.  |
 372 `-----------------------------------------*/
 373
 374 #define END_TEST(End)                           \
 375 do {                                            \
 376   if (column + strlen(buffer) > (End))          \
 377     {                                           \
 378       fprintf (out, "%s\n   ", buffer);         \
 379       column = 3;                               \
 380       buffer[0] = 0;                            \
 381     }                                           \
 382 } while (0)
 383
 384
 385 static void
 386 print_grammar (FILE *out)
 387 {
 388   symbol_number i;
 389   char buffer[90];
 390   int column = 0;
 391
 392   grammar_rules_print (out);
 393
 394   /* TERMINAL (type #) : rule #s terminal is on RHS */
 395   fprintf (out, "%s\n\n", _("Terminals, with rules where they appear"));
 396   for (i = 0; i < max_user_token_number + 1; i++)
 397     if (token_translations[i] != undeftoken->number)
 398       {
 399         const char *tag = symbols[token_translations[i]]->tag;
 400         rule_number r;
 401         item_number *rhsp;
 402
 403         buffer[0] = 0;
 404         column = strlen (tag);
 405         fputs (tag, out);
 406         END_TEST (50);
 407         sprintf (buffer, " (%d)", i);
 408
 409         for (r = 0; r < nrules; r++)
 410           for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
 411             if (item_number_as_symbol_number (*rhsp) == token_translations[i])
 412               {
 413                 END_TEST (65);
 414                 sprintf (buffer + strlen (buffer), " %d", r);
 415                 break;
 416               }
 417         fprintf (out, "%s\n", buffer);
 418       }
 419   fputs ("\n\n", out);
 420
 421
 422   fprintf (out, "%s\n\n", _("Nonterminals, with rules where they appear"));
 423   for (i = ntokens; i < nsyms; i++)
 424     {
 425       int left_count = 0, right_count = 0;
 426       rule_number r;
 427       const char *tag = symbols[i]->tag;
 428
 429       for (r = 0; r < nrules; r++)
 430         {
 431           item_number *rhsp;
 432           if (rules[r].lhs->number == i)
 433             left_count++;
 434           for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
 435             if (item_number_as_symbol_number (*rhsp) == i)
 436               {
 437                 right_count++;
 438                 break;
 439               }
 440         }
 441
 442       buffer[0] = 0;
 443       fputs (tag, out);
 444       column = strlen (tag);
 445       sprintf (buffer, " (%d)", i);
 446       END_TEST (0);
 447
 448       if (left_count > 0)
 449         {
 450           END_TEST (50);
 451           sprintf (buffer + strlen (buffer), _(" on left:"));
 452
 453           for (r = 0; r < nrules; r++)
 454             {
 455               END_TEST (65);
 456               if (rules[r].lhs->number == i)
 457                 sprintf (buffer + strlen (buffer), " %d", r);
 458             }
 459         }
 460
 461       if (right_count > 0)
 462         {
 463           if (left_count > 0)
 464             sprintf (buffer + strlen (buffer), ",");
 465           END_TEST (50);
 466           sprintf (buffer + strlen (buffer), _(" on right:"));
 467           for (r = 0; r < nrules; r++)
 468             {
 469               item_number *rhsp;
 470               for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
 471                 if (item_number_as_symbol_number (*rhsp) == i)
 472                   {
 473                     END_TEST (65);
 474                     sprintf (buffer + strlen (buffer), " %d", r);
 475                     break;
 476                   }
 477             }
 478         }
 479       fprintf (out, "%s\n", buffer);
 480     }
 481 }
 482 \f
 483 void
 484 print_results (void)
 485 {
 486   state_number i;
 487
 488   /* We used to use just .out if SPEC_NAME_PREFIX (-p) was used, but
 489      that conflicts with Posix.  */
 490   FILE *out = xfopen (spec_verbose_file, "w");
 491
 492   reduce_output (out);
 493   grammar_rules_partial_print (out,
 494                                _("Rules never reduced"), rule_never_reduced_p);
 495   conflicts_output (out);
 496
 497   print_grammar (out);
 498
 499   /* If the whole state item sets, not only the kernels, are wanted,
 500      `closure' will be run, which needs memory allocation/deallocation.   */
 501   if (report_flag & report_itemsets)
 502     new_closure (nritems);
 503   /* Storage for print_reductions.  */
 504   no_reduce_set =  bitset_create (ntokens, BITSET_FIXED);
 505   for (i = 0; i < nstates; i++)
 506     print_state (out, states[i]);
 507   bitset_free (no_reduce_set);
 508   if (report_flag & report_itemsets)
 509     free_closure ();
 510
 511   xfclose (out);
 512 }