src/print.c

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