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 shift_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 (shift_set);
 256   FOR_EACH_SHIFT (trans, i)
 257     bitset_set (shift_set, TRANSITION_SYMBOL (trans, i));
 258
 259   /* Compute the width of the lookahead token column.  */
 260   if (default_rule)
 261     width = strlen (_("$default"));
 262
 263   if (reds->lookahead_tokens)
 264     for (i = 0; i < ntokens; i++)
 265       {
 266         bool count = bitset_test (shift_set, i);
 267
 268         for (j = 0; j < reds->num; ++j)
 269           if (bitset_test (reds->lookahead_tokens[j], i))
 270             {
 271               if (! count)
 272                 {
 273                   if (reds->rules[j] != default_rule)
 274                     max_length (&width, symbols[i]->tag);
 275                   count = true;
 276                 }
 277               else
 278                 {
 279                   max_length (&width, symbols[i]->tag);
 280                 }
 281             }
 282       }
 283
 284   /* Nothing to report. */
 285   if (!width)
 286     return;
 287
 288   fputc ('\n', out);
 289   width += 2;
 290
 291   /* Report lookahead tokens (or $default) and reductions.  */
 292   if (reds->lookahead_tokens)
 293     for (i = 0; i < ntokens; i++)
 294       {
 295         bool defaulted = false;
 296         bool count = bitset_test (shift_set, i);
 297
 298         for (j = 0; j < reds->num; ++j)
 299           if (bitset_test (reds->lookahead_tokens[j], i))
 300             {
 301               if (! count)
 302                 {
 303                   if (reds->rules[j] != default_rule)
 304                     print_reduction (out, width,
 305                                      symbols[i]->tag,
 306                                      reds->rules[j], true);
 307                   else
 308                     defaulted = true;
 309                   count = true;
 310                 }
 311               else
 312                 {
 313                   if (defaulted)
 314                     print_reduction (out, width,
 315                                      symbols[i]->tag,
 316                                      default_rule, true);
 317                   defaulted = false;
 318                   print_reduction (out, width,
 319                                    symbols[i]->tag,
 320                                    reds->rules[j], false);
 321                 }
 322             }
 323       }
 324
 325   if (default_rule)
 326     print_reduction (out, width,
 327                      _("$default"), default_rule, true);
 328 }
 329
 330
 331 /*--------------------------------------------------------------.
 332 | Report on OUT all the actions (shifts, gotos, reductions, and |
 333 | explicit erros from %nonassoc) of S.                          |
 334 `--------------------------------------------------------------*/
 335
 336 static void
 337 print_actions (FILE *out, state *s)
 338 {
 339   /* Print shifts.  */
 340   print_transitions (s, out, true);
 341   print_errs (out, s);
 342   print_reductions (out, s);
 343   /* Print gotos.  */
 344   print_transitions (s, out, false);
 345 }
 346
 347
 348 /*----------------------------------.
 349 | Report all the data on S on OUT.  |
 350 `----------------------------------*/
 351
 352 static void
 353 print_state (FILE *out, state *s)
 354 {
 355   fputs ("\n\n", out);
 356   fprintf (out, _("state %d"), s->number);
 357   fputc ('\n', out);
 358   print_core (out, s);
 359   print_actions (out, s);
 360   if ((report_flag & report_solved_conflicts) && s->solved_conflicts)
 361     {
 362       fputc ('\n', out);
 363       fputs (s->solved_conflicts, out);
 364     }
 365 }
 366 \f
 367 /*-----------------------------------------.
 368 | Print information on the whole grammar.  |
 369 `-----------------------------------------*/
 370
 371 #define END_TEST(End)                           \
 372 do {                                            \
 373   if (column + strlen(buffer) > (End))          \
 374     {                                           \
 375       fprintf (out, "%s\n   ", buffer);         \
 376       column = 3;                               \
 377       buffer[0] = 0;                            \
 378     }                                           \
 379 } while (0)
 380
 381
 382 static void
 383 print_grammar (FILE *out)
 384 {
 385   symbol_number i;
 386   char buffer[90];
 387   int column = 0;
 388
 389   grammar_rules_print (out);
 390
 391   /* TERMINAL (type #) : rule #s terminal is on RHS */
 392   fprintf (out, "%s\n\n", _("Terminals, with rules where they appear"));
 393   for (i = 0; i < max_user_token_number + 1; i++)
 394     if (token_translations[i] != undeftoken->number)
 395       {
 396         const char *tag = symbols[token_translations[i]]->tag;
 397         rule_number r;
 398         item_number *rhsp;
 399
 400         buffer[0] = 0;
 401         column = strlen (tag);
 402         fputs (tag, out);
 403         END_TEST (50);
 404         sprintf (buffer, " (%d)", i);
 405
 406         for (r = 0; r < nrules; r++)
 407           for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
 408             if (item_number_as_symbol_number (*rhsp) == token_translations[i])
 409               {
 410                 END_TEST (65);
 411                 sprintf (buffer + strlen (buffer), " %d", r);
 412                 break;
 413               }
 414         fprintf (out, "%s\n", buffer);
 415       }
 416   fputs ("\n\n", out);
 417
 418
 419   fprintf (out, "%s\n\n", _("Nonterminals, with rules where they appear"));
 420   for (i = ntokens; i < nsyms; i++)
 421     {
 422       int left_count = 0, right_count = 0;
 423       rule_number r;
 424       const char *tag = symbols[i]->tag;
 425
 426       for (r = 0; r < nrules; r++)
 427         {
 428           item_number *rhsp;
 429           if (rules[r].lhs->number == i)
 430             left_count++;
 431           for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
 432             if (item_number_as_symbol_number (*rhsp) == i)
 433               {
 434                 right_count++;
 435                 break;
 436               }
 437         }
 438
 439       buffer[0] = 0;
 440       fputs (tag, out);
 441       column = strlen (tag);
 442       sprintf (buffer, " (%d)", i);
 443       END_TEST (0);
 444
 445       if (left_count > 0)
 446         {
 447           END_TEST (50);
 448           sprintf (buffer + strlen (buffer), _(" on left:"));
 449
 450           for (r = 0; r < nrules; r++)
 451             {
 452               END_TEST (65);
 453               if (rules[r].lhs->number == i)
 454                 sprintf (buffer + strlen (buffer), " %d", r);
 455             }
 456         }
 457
 458       if (right_count > 0)
 459         {
 460           if (left_count > 0)
 461             sprintf (buffer + strlen (buffer), ",");
 462           END_TEST (50);
 463           sprintf (buffer + strlen (buffer), _(" on right:"));
 464           for (r = 0; r < nrules; r++)
 465             {
 466               item_number *rhsp;
 467               for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
 468                 if (item_number_as_symbol_number (*rhsp) == i)
 469                   {
 470                     END_TEST (65);
 471                     sprintf (buffer + strlen (buffer), " %d", r);
 472                     break;
 473                   }
 474             }
 475         }
 476       fprintf (out, "%s\n", buffer);
 477     }
 478 }
 479 \f
 480 void
 481 print_results (void)
 482 {
 483   state_number i;
 484
 485   /* We used to use just .out if SPEC_NAME_PREFIX (-p) was used, but
 486      that conflicts with Posix.  */
 487   FILE *out = xfopen (spec_verbose_file, "w");
 488
 489   reduce_output (out);
 490   grammar_rules_partial_print (out,
 491                                _("Rules never reduced"), rule_never_reduced_p);
 492   conflicts_output (out);
 493
 494   print_grammar (out);
 495
 496   /* If the whole state item sets, not only the kernels, are wanted,
 497      `closure' will be run, which needs memory allocation/deallocation.   */
 498   if (report_flag & report_itemsets)
 499     new_closure (nritems);
 500   /* Storage for print_reductions.  */
 501   shift_set =  bitset_create (ntokens, BITSET_FIXED);
 502   for (i = 0; i < nstates; i++)
 503     print_state (out, states[i]);
 504   bitset_free (shift_set);
 505   if (report_flag & report_itemsets)
 506     free_closure ();
 507
 508   xfclose (out);
 509 }