src/print.c

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