OLD | NEW |
(Empty) | |
| 1 /* Print information on generated parser, for bison, |
| 2 |
| 3 Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004, 2005, 2007 |
| 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 <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 |
| 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 |
| 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 |
| 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 } |
OLD | NEW |