1/* Print information on generated parser, for bison, 2 3 Copyright (C) 1984, 1986, 1989, 2000-2005, 2007, 2009-2012 Free 4 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 26#include "LR0.h" 27#include "closure.h" 28#include "conflicts.h" 29#include "files.h" 30#include "getargs.h" 31#include "gram.h" 32#include "lalr.h" 33#include "muscle-tab.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 41static bitset no_reduce_set; 42 43#if 0 44static void 45print_token (int extnum, int token) 46{ 47 fprintf (out, _(" type %d is %s\n"), extnum, tags[token]); 48} 49#endif 50 51 52 53/*---------------------------------------. 54| *WIDTH := max (*WIDTH, strlen (STR)). | 55`---------------------------------------*/ 56 57static void 58max_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 69static void 70print_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 127static void 128print_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 175static void 176print_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 214static void 215print_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 239static void 240print_reductions (FILE *out, state *s) 241{ 242 transitions *trans = s->transitions; 243 reductions *reds = s->reductions; 244 rule *default_reduction = NULL; 245 size_t width = 0; 246 int i, j; 247 bool default_reduction_only = true; 248 249 if (reds->num == 0) 250 return; 251 252 if (yydefact[s->number] != 0) 253 default_reduction = &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_reduction) 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_reduction) 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 if (count) 301 default_reduction_only = false; 302 303 for (j = 0; j < reds->num; ++j) 304 if (bitset_test (reds->lookahead_tokens[j], i)) 305 { 306 if (! count) 307 { 308 if (reds->rules[j] != default_reduction) 309 { 310 default_reduction_only = false; 311 print_reduction (out, width, 312 symbols[i]->tag, 313 reds->rules[j], true); 314 } 315 else 316 defaulted = true; 317 count = true; 318 } 319 else 320 { 321 default_reduction_only = false; 322 if (defaulted) 323 print_reduction (out, width, 324 symbols[i]->tag, 325 default_reduction, true); 326 defaulted = false; 327 print_reduction (out, width, 328 symbols[i]->tag, 329 reds->rules[j], false); 330 } 331 } 332 } 333 334 if (default_reduction) 335 { 336 char *default_reductions = 337 muscle_percent_define_get ("lr.default-reductions"); 338 print_reduction (out, width, _("$default"), default_reduction, true); 339 aver (0 == strcmp (default_reductions, "most") 340 || (0 == strcmp (default_reductions, "consistent") 341 && default_reduction_only) 342 || (reds->num == 1 && reds->rules[0]->number == 0)); 343 free (default_reductions); 344 } 345} 346 347 348/*--------------------------------------------------------------. 349| Report on OUT all the actions (shifts, gotos, reductions, and | 350| explicit erros from %nonassoc) of S. | 351`--------------------------------------------------------------*/ 352 353static void 354print_actions (FILE *out, state *s) 355{ 356 /* Print shifts. */ 357 print_transitions (s, out, true); 358 print_errs (out, s); 359 print_reductions (out, s); 360 /* Print gotos. */ 361 print_transitions (s, out, false); 362} 363 364 365/*----------------------------------. 366| Report all the data on S on OUT. | 367`----------------------------------*/ 368 369static void 370print_state (FILE *out, state *s) 371{ 372 fputs ("\n\n", out); 373 fprintf (out, _("State %d"), s->number); 374 fputc ('\n', out); 375 print_core (out, s); 376 print_actions (out, s); 377 if ((report_flag & report_solved_conflicts) && s->solved_conflicts) 378 { 379 fputc ('\n', out); 380 fputs (s->solved_conflicts, out); 381 } 382} 383 384/*-----------------------------------------. 385| Print information on the whole grammar. | 386`-----------------------------------------*/ 387 388#define END_TEST(End) \ 389do { \ 390 if (column + strlen(buffer) > (End)) \ 391 { \ 392 fprintf (out, "%s\n ", buffer); \ 393 column = 3; \ 394 buffer[0] = 0; \ 395 } \ 396} while (0) 397 398 399static void 400print_grammar (FILE *out) 401{ 402 symbol_number i; 403 char buffer[90]; 404 int column = 0; 405 406 grammar_rules_print (out); 407 408 /* TERMINAL (type #) : rule #s terminal is on RHS */ 409 fprintf (out, "%s\n\n", _("Terminals, with rules where they appear")); 410 for (i = 0; i < max_user_token_number + 1; i++) 411 if (token_translations[i] != undeftoken->number) 412 { 413 const char *tag = symbols[token_translations[i]]->tag; 414 rule_number r; 415 item_number *rhsp; 416 417 buffer[0] = 0; 418 column = strlen (tag); 419 fputs (tag, out); 420 END_TEST (65); 421 sprintf (buffer, " (%d)", i); 422 423 for (r = 0; r < nrules; r++) 424 for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++) 425 if (item_number_as_symbol_number (*rhsp) == token_translations[i]) 426 { 427 END_TEST (65); 428 sprintf (buffer + strlen (buffer), " %d", r); 429 break; 430 } 431 fprintf (out, "%s\n", buffer); 432 } 433 fputs ("\n\n", out); 434 435 436 fprintf (out, "%s\n\n", _("Nonterminals, with rules where they appear")); 437 for (i = ntokens; i < nsyms; i++) 438 { 439 int left_count = 0, right_count = 0; 440 rule_number r; 441 const char *tag = symbols[i]->tag; 442 443 for (r = 0; r < nrules; r++) 444 { 445 item_number *rhsp; 446 if (rules[r].lhs->number == i) 447 left_count++; 448 for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++) 449 if (item_number_as_symbol_number (*rhsp) == i) 450 { 451 right_count++; 452 break; 453 } 454 } 455 456 buffer[0] = 0; 457 fputs (tag, out); 458 column = strlen (tag); 459 sprintf (buffer, " (%d)", i); 460 END_TEST (0); 461 462 if (left_count > 0) 463 { 464 END_TEST (65); 465 sprintf (buffer + strlen (buffer), _(" on left:")); 466 467 for (r = 0; r < nrules; r++) 468 { 469 if (rules[r].lhs->number == i) 470 { 471 END_TEST (65); 472 sprintf (buffer + strlen (buffer), " %d", r); 473 } 474 } 475 } 476 477 if (right_count > 0) 478 { 479 if (left_count > 0) 480 sprintf (buffer + strlen (buffer), ","); 481 END_TEST (65); 482 sprintf (buffer + strlen (buffer), _(" on right:")); 483 for (r = 0; r < nrules; r++) 484 { 485 item_number *rhsp; 486 for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++) 487 if (item_number_as_symbol_number (*rhsp) == i) 488 { 489 END_TEST (65); 490 sprintf (buffer + strlen (buffer), " %d", r); 491 break; 492 } 493 } 494 } 495 fprintf (out, "%s\n", buffer); 496 } 497} 498 499void 500print_results (void) 501{ 502 state_number i; 503 504 /* We used to use just .out if SPEC_NAME_PREFIX (-p) was used, but 505 that conflicts with Posix. */ 506 FILE *out = xfopen (spec_verbose_file, "w"); 507 508 reduce_output (out); 509 grammar_rules_partial_print (out, 510 _("Rules useless in parser due to conflicts"), 511 rule_useless_in_parser_p); 512 conflicts_output (out); 513 514 print_grammar (out); 515 516 /* If the whole state item sets, not only the kernels, are wanted, 517 `closure' will be run, which needs memory allocation/deallocation. */ 518 if (report_flag & report_itemsets) 519 new_closure (nritems); 520 /* Storage for print_reductions. */ 521 no_reduce_set = bitset_create (ntokens, BITSET_FIXED); 522 for (i = 0; i < nstates; i++) 523 print_state (out, states[i]); 524 bitset_free (no_reduce_set); 525 if (report_flag & report_itemsets) 526 free_closure (); 527 528 xfclose (out); 529} 530