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