1 /* Print information on generated parser, for bison, 2 3 Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004, 2005 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 42 static bitset shift_set; 43 static bitset look_ahead_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 54 56 /*---------------------------------------. 57 | *WIDTH := max (*WIDTH, strlen (STR)). | 58 `---------------------------------------*/ 59 60 static void 61 max_length (size_t *width, const char *str) 62 { 63 size_t len = strlen (str); 64 if (len > *width) 65 *width = len; 66 } 67 68 /*--------------------------------. 69 | Report information on a state. | 70 `--------------------------------*/ 71 72 static void 73 print_core (FILE *out, state *s) 74 { 75 size_t i; 76 item_number *sitems = s->items; 77 size_t snritems = s->nitems; 78 symbol *previous_lhs = NULL; 79 80 /* Output all the items of a state, not only its kernel. */ 81 if (report_flag & report_itemsets) 82 { 83 closure (sitems, snritems); 84 sitems = itemset; 85 snritems = nritemset; 86 } 87 88 if (!snritems) 89 return; 90 91 fputc ('\n', out); 92 93 for (i = 0; i < snritems; i++) 94 { 95 item_number *sp; 96 item_number *sp1; 97 rule_number r; 98 99 sp1 = sp = ritem + sitems[i]; 100 101 while (*sp >= 0) 102 sp++; 103 104 r = item_number_as_rule_number (*sp); 105 106 rule_lhs_print (&rules[r], previous_lhs, out); 107 previous_lhs = rules[r].lhs; 108 109 for (sp = rules[r].rhs; sp < sp1; sp++) 110 fprintf (out, " %s", symbols[*sp]->tag); 111 fputs (" .", out); 112 for (/* Nothing */; *sp >= 0; ++sp) 113 fprintf (out, " %s", symbols[*sp]->tag); 114 115 /* Display the look-ahead tokens? */ 116 if (report_flag & report_look_ahead_tokens) 117 state_rule_look_ahead_tokens_print (s, &rules[r], out); 118 119 fputc ('\n', out); 120 } 121 } 122 123 124 /*------------------------------------------------------------. 125 | Report the shifts iff DISPLAY_SHIFTS_P or the gotos of S on | 126 | OUT. | 127 `------------------------------------------------------------*/ 128 129 static void 130 print_transitions (state *s, FILE *out, bool display_transitions_p) 131 { 132 transitions *trans = s->transitions; 133 size_t width = 0; 134 int i; 135 136 /* Compute the width of the look-ahead token column. */ 137 for (i = 0; i < trans->num; i++) 138 if (!TRANSITION_IS_DISABLED (trans, i) 139 && TRANSITION_IS_SHIFT (trans, i) == display_transitions_p) 140 { 141 symbol *sym = symbols[TRANSITION_SYMBOL (trans, i)]; 142 max_length (&width, sym->tag); 143 } 144 145 /* Nothing to report. */ 146 if (!width) 147 return; 148 149 fputc ('\n', out); 150 width += 2; 151 152 /* Report look-ahead tokens and shifts. */ 153 for (i = 0; i < trans->num; i++) 154 if (!TRANSITION_IS_DISABLED (trans, i) 155 && TRANSITION_IS_SHIFT (trans, i) == display_transitions_p) 156 { 157 symbol *sym = symbols[TRANSITION_SYMBOL (trans, i)]; 158 const char *tag = sym->tag; 159 state *s1 = trans->states[i]; 160 int j; 161 162 fprintf (out, " %s", tag); 163 for (j = width - strlen (tag); j > 0; --j) 164 fputc (' ', out); 165 if (display_transitions_p) 166 fprintf (out, _("shift, and go to state %d\n"), s1->number); 167 else 168 fprintf (out, _("go to state %d\n"), s1->number); 169 } 170 } 171 172 173 /*--------------------------------------------------------. 174 | Report the explicit errors of S raised from %nonassoc. | 175 `--------------------------------------------------------*/ 176 177 static void 178 print_errs (FILE *out, state *s) 179 { 180 errs *errp = s->errs; 181 size_t width = 0; 182 int i; 183 184 /* Compute the width of the look-ahead token column. */ 185 for (i = 0; i < errp->num; ++i) 186 if (errp->symbols[i]) 187 max_length (&width, errp->symbols[i]->tag); 188 189 /* Nothing to report. */ 190 if (!width) 191 return; 192 193 fputc ('\n', out); 194 width += 2; 195 196 /* Report look-ahead tokens and errors. */ 197 for (i = 0; i < errp->num; ++i) 198 if (errp->symbols[i]) 199 { 200 const char *tag = errp->symbols[i]->tag; 201 int j; 202 fprintf (out, " %s", tag); 203 for (j = width - strlen (tag); j > 0; --j) 204 fputc (' ', out); 205 fputs (_("error (nonassociative)\n"), out); 206 } 207 } 208 209 210 /*-------------------------------------------------------------. 211 | Return the default rule of S if it has one, NULL otherwise. | 212 `-------------------------------------------------------------*/ 213 214 static rule * 215 state_default_rule (state *s) 216 { 217 reductions *reds = s->reductions; 218 rule *default_rule = NULL; 219 int cmax = 0; 220 int i; 221 222 /* No need for a look-ahead. */ 223 if (s->consistent) 224 return reds->rules[0]; 225 226 /* 1. Each reduction is possibly masked by the look-ahead tokens on which 227 we shift (S/R conflicts)... */ 228 bitset_zero (shift_set); 229 { 230 transitions *trans = s->transitions; 231 FOR_EACH_SHIFT (trans, i) 232 { 233 /* If this state has a shift for the error token, don't use a 234 default rule. */ 235 if (TRANSITION_IS_ERROR (trans, i)) 236 return NULL; 237 bitset_set (shift_set, TRANSITION_SYMBOL (trans, i)); 238 } 239 } 240 241 /* 2. Each reduction is possibly masked by the look-ahead tokens on which 242 we raise an error (due to %nonassoc). */ 243 { 244 errs *errp = s->errs; 245 for (i = 0; i < errp->num; i++) 246 if (errp->symbols[i]) 247 bitset_set (shift_set, errp->symbols[i]->number); 248 } 249 250 for (i = 0; i < reds->num; ++i) 251 { 252 int count = 0; 253 254 /* How many non-masked look-ahead tokens are there for this 255 reduction? */ 256 bitset_andn (look_ahead_set, reds->look_ahead_tokens[i], shift_set); 257 count = bitset_count (look_ahead_set); 258 259 if (count > cmax) 260 { 261 cmax = count; 262 default_rule = reds->rules[i]; 263 } 264 265 /* 3. And finally, each reduction is possibly masked by previous 266 reductions (in R/R conflicts, we keep the first reductions). 267 */ 268 bitset_or (shift_set, shift_set, reds->look_ahead_tokens[i]); 269 } 270 271 return default_rule; 272 } 273 274 275 /*--------------------------------------------------------------------------. 276 | Report a reduction of RULE on LOOK_AHEAD_TOKEN (which can be `default'). | 277 | If not ENABLED, the rule is masked by a shift or a reduce (S/R and | 278 | R/R conflicts). | 279 `--------------------------------------------------------------------------*/ 280 281 static void 282 print_reduction (FILE *out, size_t width, 283 const char *look_ahead_token, 284 rule *r, bool enabled) 285 { 286 int j; 287 fprintf (out, " %s", look_ahead_token); 288 for (j = width - strlen (look_ahead_token); j > 0; --j) 289 fputc (' ', out); 290 if (!enabled) 291 fputc ('[', out); 292 if (r->number) 293 fprintf (out, _("reduce using rule %d (%s)"), r->number, r->lhs->tag); 294 else 295 fprintf (out, _("accept")); 296 if (!enabled) 297 fputc (']', out); 298 fputc ('\n', out); 299 } 300 301 302 /*-------------------------------------------. 303 | Report on OUT the reduction actions of S. | 304 `-------------------------------------------*/ 305 306 static void 307 print_reductions (FILE *out, state *s) 308 { 309 transitions *trans = s->transitions; 310 reductions *reds = s->reductions; 311 rule *default_rule = NULL; 312 size_t width = 0; 313 int i, j; 314 315 if (reds->num == 0) 316 return; 317 318 default_rule = state_default_rule (s); 319 320 bitset_zero (shift_set); 321 FOR_EACH_SHIFT (trans, i) 322 bitset_set (shift_set, TRANSITION_SYMBOL (trans, i)); 323 324 /* Compute the width of the look-ahead token column. */ 325 if (default_rule) 326 width = strlen (_("$default")); 327 328 if (reds->look_ahead_tokens) 329 for (i = 0; i < ntokens; i++) 330 { 331 bool count = bitset_test (shift_set, i); 332 333 for (j = 0; j < reds->num; ++j) 334 if (bitset_test (reds->look_ahead_tokens[j], i)) 335 { 336 if (! count) 337 { 338 if (reds->rules[j] != default_rule) 339 max_length (&width, symbols[i]->tag); 340 count = true; 341 } 342 else 343 { 344 max_length (&width, symbols[i]->tag); 345 } 346 } 347 } 348 349 /* Nothing to report. */ 350 if (!width) 351 return; 352 353 fputc ('\n', out); 354 width += 2; 355 356 /* Report look-ahead tokens (or $default) and reductions. */ 357 if (reds->look_ahead_tokens) 358 for (i = 0; i < ntokens; i++) 359 { 360 bool defaulted = false; 361 bool count = bitset_test (shift_set, i); 362 363 for (j = 0; j < reds->num; ++j) 364 if (bitset_test (reds->look_ahead_tokens[j], i)) 365 { 366 if (! count) 367 { 368 if (reds->rules[j] != default_rule) 369 print_reduction (out, width, 370 symbols[i]->tag, 371 reds->rules[j], true); 372 else 373 defaulted = true; 374 count = true; 375 } 376 else 377 { 378 if (defaulted) 379 print_reduction (out, width, 380 symbols[i]->tag, 381 default_rule, true); 382 defaulted = false; 383 print_reduction (out, width, 384 symbols[i]->tag, 385 reds->rules[j], false); 386 } 387 } 388 } 389 390 if (default_rule) 391 print_reduction (out, width, 392 _("$default"), default_rule, true); 393 } 394 395 396 /*--------------------------------------------------------------. 397 | Report on OUT all the actions (shifts, gotos, reductions, and | 398 | explicit erros from %nonassoc) of S. | 399 `--------------------------------------------------------------*/ 400 401 static void 402 print_actions (FILE *out, state *s) 403 { 404 /* Print shifts. */ 405 print_transitions (s, out, true); 406 print_errs (out, s); 407 print_reductions (out, s); 408 /* Print gotos. */ 409 print_transitions (s, out, false); 410 } 411 412 413 /*----------------------------------. 414 | Report all the data on S on OUT. | 415 `----------------------------------*/ 416 417 static void 418 print_state (FILE *out, state *s) 419 { 420 fputs ("\n\n", out); 421 fprintf (out, _("state %d"), s->number); 422 fputc ('\n', out); 423 print_core (out, s); 424 print_actions (out, s); 425 if ((report_flag & report_solved_conflicts) && s->solved_conflicts) 426 { 427 fputc ('\n', out); 428 fputs (s->solved_conflicts, out); 429 } 430 } 431 432 /*-----------------------------------------. 434 | Print information on the whole grammar. | 435 `-----------------------------------------*/ 436 437 #define END_TEST(End) \ 438 do { \ 439 if (column + strlen(buffer) > (End)) \ 440 { \ 441 fprintf (out, "%s\n ", buffer); \ 442 column = 3; \ 443 buffer[0] = 0; \ 444 } \ 445 } while (0) 446 447 448 static void 449 print_grammar (FILE *out) 450 { 451 symbol_number i; 452 char buffer[90]; 453 int column = 0; 454 455 grammar_rules_print (out); 456 457 /* TERMINAL (type #) : rule #s terminal is on RHS */ 458 fprintf (out, "%s\n\n", _("Terminals, with rules where they appear")); 459 for (i = 0; i < max_user_token_number + 1; i++) 460 if (token_translations[i] != undeftoken->number) 461 { 462 const char *tag = symbols[token_translations[i]]->tag; 463 rule_number r; 464 item_number *rhsp; 465 466 buffer[0] = 0; 467 column = strlen (tag); 468 fputs (tag, out); 469 END_TEST (50); 470 sprintf (buffer, " (%d)", i); 471 472 for (r = 0; r < nrules; r++) 473 for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++) 474 if (item_number_as_symbol_number (*rhsp) == token_translations[i]) 475 { 476 END_TEST (65); 477 sprintf (buffer + strlen (buffer), " %d", r); 478 break; 479 } 480 fprintf (out, "%s\n", buffer); 481 } 482 fputs ("\n\n", out); 483 484 485 fprintf (out, "%s\n\n", _("Nonterminals, with rules where they appear")); 486 for (i = ntokens; i < nsyms; i++) 487 { 488 int left_count = 0, right_count = 0; 489 rule_number r; 490 const char *tag = symbols[i]->tag; 491 492 for (r = 0; r < nrules; r++) 493 { 494 item_number *rhsp; 495 if (rules[r].lhs->number == i) 496 left_count++; 497 for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++) 498 if (item_number_as_symbol_number (*rhsp) == i) 499 { 500 right_count++; 501 break; 502 } 503 } 504 505 buffer[0] = 0; 506 fputs (tag, out); 507 column = strlen (tag); 508 sprintf (buffer, " (%d)", i); 509 END_TEST (0); 510 511 if (left_count > 0) 512 { 513 END_TEST (50); 514 sprintf (buffer + strlen (buffer), _(" on left:")); 515 516 for (r = 0; r < nrules; r++) 517 { 518 END_TEST (65); 519 if (rules[r].lhs->number == i) 520 sprintf (buffer + strlen (buffer), " %d", r); 521 } 522 } 523 524 if (right_count > 0) 525 { 526 if (left_count > 0) 527 sprintf (buffer + strlen (buffer), ","); 528 END_TEST (50); 529 sprintf (buffer + strlen (buffer), _(" on right:")); 530 for (r = 0; r < nrules; r++) 531 { 532 item_number *rhsp; 533 for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++) 534 if (item_number_as_symbol_number (*rhsp) == i) 535 { 536 END_TEST (65); 537 sprintf (buffer + strlen (buffer), " %d", r); 538 break; 539 } 540 } 541 } 542 fprintf (out, "%s\n", buffer); 543 } 544 } 545 546 void 548 print_results (void) 549 { 550 state_number i; 551 552 /* We used to use just .out if SPEC_NAME_PREFIX (-p) was used, but 553 that conflicts with Posix. */ 554 FILE *out = xfopen (spec_verbose_file, "w"); 555 556 reduce_output (out); 557 grammar_rules_partial_print (out, 558 _("Rules never reduced"), rule_never_reduced_p); 559 conflicts_output (out); 560 561 print_grammar (out); 562 563 /* If the whole state item sets, not only the kernels, are wanted, 564 `closure' will be run, which needs memory allocation/deallocation. */ 565 if (report_flag & report_itemsets) 566 new_closure (nritems); 567 /* Storage for print_reductions. */ 568 shift_set = bitset_create (ntokens, BITSET_FIXED); 569 look_ahead_set = bitset_create (ntokens, BITSET_FIXED); 570 for (i = 0; i < nstates; i++) 571 print_state (out, states[i]); 572 bitset_free (shift_set); 573 bitset_free (look_ahead_set); 574 if (report_flag & report_itemsets) 575 free_closure (); 576 577 xfclose (out); 578 } 579
