X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/5092aba5a75e23dc8bca281a5ea240a7e155eff3..8cdabf02eaeb9a225c82013b37057398e07f1912:/src/print.c diff --git a/src/print.c b/src/print.c index e1f53a1e..ddd76a60 100644 --- a/src/print.c +++ b/src/print.c @@ -1,39 +1,44 @@ /* Print information on generated parser, for bison, - Copyright 1984, 1986, 1989, 2000, 2001 Free Software Foundation, Inc. + + Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004, 2005, 2007 + Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. - Bison is free software; you can redistribute it and/or modify + This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2, or (at your option) - any later version. + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. - Bison is distributed in the hope that it will be useful, + This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License - along with Bison; see the file COPYING. If not, write to - the Free Software Foundation, Inc., 59 Temple Place - Suite 330, - Boston, MA 02111-1307, USA. */ - + along with this program. If not, see . */ +#include #include "system.h" -#include "files.h" -#include "gram.h" + +#include +#include + #include "LR0.h" -#include "lalr.h" +#include "closure.h" #include "conflicts.h" +#include "files.h" #include "getargs.h" -#include "state.h" -#include "reader.h" +#include "gram.h" +#include "lalr.h" #include "print.h" +#include "reader.h" #include "reduce.h" -#include "closure.h" +#include "state.h" +#include "symtab.h" +#include "tables.h" -static unsigned *shiftset = NULL; -static unsigned *lookaheadset = NULL; +static bitset no_reduce_set; #if 0 static void @@ -44,292 +49,321 @@ print_token (int extnum, int token) #endif + +/*---------------------------------------. +| *WIDTH := max (*WIDTH, strlen (STR)). | +`---------------------------------------*/ + +static void +max_length (size_t *width, const char *str) +{ + size_t len = strlen (str); + if (len > *width) + *width = len; +} + /*--------------------------------. | Report information on a state. | `--------------------------------*/ static void -print_core (FILE *out, state_t *state) +print_core (FILE *out, state *s) { - int i; - short *sitems = state->items; - int snitems = state->nitems; + size_t i; + item_number *sitems = s->items; + size_t snritems = s->nitems; + symbol *previous_lhs = NULL; - /* New experimental feature: if TRACE_FLAGS output all the items of - a state, not only its kernel. */ - if (trace_flag) + /* Output all the items of a state, not only its kernel. */ + if (report_flag & report_itemsets) { - closure (sitems, snitems); + closure (sitems, snritems); sitems = itemset; - snitems = nitemset; + snritems = nitemset; } - if (snitems) - { - for (i = 0; i < snitems; i++) - { - short *sp; - short *sp1; - int rule; + if (!snritems) + return; - sp1 = sp = ritem + sitems[i]; + fputc ('\n', out); - while (*sp > 0) - sp++; + for (i = 0; i < snritems; i++) + { + item_number *sp; + item_number *sp1; + rule_number r; - rule = -(*sp); - fprintf (out, " %s -> ", tags[rule_table[rule].lhs]); + sp1 = sp = ritem + sitems[i]; - for (sp = ritem + rule_table[rule].rhs; sp < sp1; sp++) - fprintf (out, "%s ", tags[*sp]); + while (*sp >= 0) + sp++; - fputc ('.', out); + r = item_number_as_rule_number (*sp); - for (/* Nothing */; *sp > 0; ++sp) - fprintf (out, " %s", tags[*sp]); + rule_lhs_print (&rules[r], previous_lhs, out); + previous_lhs = rules[r].lhs; - fprintf (out, _(" (rule %d)"), rule); - fputc ('\n', out); - } + for (sp = rules[r].rhs; sp < sp1; sp++) + fprintf (out, " %s", symbols[*sp]->tag); + fputs (" .", out); + for (/* Nothing */; *sp >= 0; ++sp) + fprintf (out, " %s", symbols[*sp]->tag); + + /* Display the lookahead tokens? */ + if (report_flag & report_lookahead_tokens + && item_number_is_rule_number (*sp1)) + state_rule_lookahead_tokens_print (s, &rules[r], out); fputc ('\n', out); } } +/*------------------------------------------------------------. +| Report the shifts iff DISPLAY_SHIFTS_P or the gotos of S on | +| OUT. | +`------------------------------------------------------------*/ + static void -print_shifts (FILE *out, state_t *state) +print_transitions (state *s, FILE *out, bool display_transitions_p) { + transitions *trans = s->transitions; + size_t width = 0; int i; - shifts *shiftp = state->shifts; - for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++) - if (!SHIFT_IS_DISABLED (shiftp, i)) + /* Compute the width of the lookahead token column. */ + for (i = 0; i < trans->num; i++) + if (!TRANSITION_IS_DISABLED (trans, i) + && TRANSITION_IS_SHIFT (trans, i) == display_transitions_p) { - int state1 = shiftp->shifts[i]; - int symbol = state_table[state1]->accessing_symbol; - fprintf (out, - _(" %-4s\tshift, and go to state %d\n"), - tags[symbol], state1); + symbol *sym = symbols[TRANSITION_SYMBOL (trans, i)]; + max_length (&width, sym->tag); } - if (i > 0) - fputc ('\n', out); + /* Nothing to report. */ + if (!width) + return; + + fputc ('\n', out); + width += 2; + + /* Report lookahead tokens and shifts. */ + for (i = 0; i < trans->num; i++) + if (!TRANSITION_IS_DISABLED (trans, i) + && TRANSITION_IS_SHIFT (trans, i) == display_transitions_p) + { + symbol *sym = symbols[TRANSITION_SYMBOL (trans, i)]; + const char *tag = sym->tag; + state *s1 = trans->states[i]; + int j; + + fprintf (out, " %s", tag); + for (j = width - strlen (tag); j > 0; --j) + fputc (' ', out); + if (display_transitions_p) + fprintf (out, _("shift, and go to state %d\n"), s1->number); + else + fprintf (out, _("go to state %d\n"), s1->number); + } } +/*--------------------------------------------------------. +| Report the explicit errors of S raised from %nonassoc. | +`--------------------------------------------------------*/ + static void -print_errs (FILE *out, state_t *state) +print_errs (FILE *out, state *s) { - errs *errp = state->errs; + errs *errp = s->errs; + size_t width = 0; int i; - if (!errp) + /* Compute the width of the lookahead token column. */ + for (i = 0; i < errp->num; ++i) + if (errp->symbols[i]) + max_length (&width, errp->symbols[i]->tag); + + /* Nothing to report. */ + if (!width) return; - for (i = 0; i < errp->nerrs; ++i) - if (errp->errs[i]) - fprintf (out, _(" %-4s\terror (nonassociative)\n"), - tags[errp->errs[i]]); + fputc ('\n', out); + width += 2; - if (i > 0) - fputc ('\n', out); + /* Report lookahead tokens and errors. */ + for (i = 0; i < errp->num; ++i) + if (errp->symbols[i]) + { + const char *tag = errp->symbols[i]->tag; + int j; + fprintf (out, " %s", tag); + for (j = width - strlen (tag); j > 0; --j) + fputc (' ', out); + fputs (_("error (nonassociative)\n"), out); + } } +/*-------------------------------------------------------------------------. +| Report a reduction of RULE on LOOKAHEAD_TOKEN (which can be `default'). | +| If not ENABLED, the rule is masked by a shift or a reduce (S/R and | +| R/R conflicts). | +`-------------------------------------------------------------------------*/ + static void -print_gotos (FILE *out, state_t *state) +print_reduction (FILE *out, size_t width, + const char *lookahead_token, + rule *r, bool enabled) { - int i; - shifts *shiftp = state->shifts; + int j; + fprintf (out, " %s", lookahead_token); + for (j = width - strlen (lookahead_token); j > 0; --j) + fputc (' ', out); + if (!enabled) + fputc ('[', out); + if (r->number) + fprintf (out, _("reduce using rule %d (%s)"), r->number, r->lhs->tag); + else + fprintf (out, _("accept")); + if (!enabled) + fputc (']', out); + fputc ('\n', out); +} - for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++) - /* Skip token shifts. */; - if (i < shiftp->nshifts) - { - for (; i < shiftp->nshifts; i++) - if (!SHIFT_IS_DISABLED (shiftp, i)) - { - int state1 = shiftp->shifts[i]; - int symbol = state_table[state1]->accessing_symbol; - fprintf (out, _(" %-4s\tgo to state %d\n"), - tags[symbol], state1); - } - - fputc ('\n', out); - } -} +/*-------------------------------------------. +| Report on OUT the reduction actions of S. | +`-------------------------------------------*/ static void -print_reductions (FILE *out, state_t *state) +print_reductions (FILE *out, state *s) { - int i; - shifts *shiftp = state->shifts; - reductions *redp = state->reductions; - errs *errp = state->errs; - int nodefault = 0; - - if (state->consistent) - { - int rule = redp->rules[0]; - int symbol = rule_table[rule].lhs; - fprintf (out, _(" $default\treduce using rule %d (%s)\n\n"), - rule, tags[symbol]); - return; - } - - for (i = 0; i < tokensetsize; i++) - shiftset[i] = 0; - - for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++) - if (!SHIFT_IS_DISABLED (shiftp, i)) - { - /* if this state has a shift for the error token, don't use a - default rule. */ - if (SHIFT_IS_ERROR (shiftp, i)) - nodefault = 1; - SETBIT (shiftset, SHIFT_SYMBOL (shiftp, i)); - } - - if (errp) - for (i = 0; i < errp->nerrs; i++) - if (errp->errs[i]) - SETBIT (shiftset, errp->errs[i]); - - if (state->nlookaheads == 1 && !nodefault) - { - int k; - int default_rule = LAruleno[state->lookaheadsp]; - - for (k = 0; k < tokensetsize; ++k) - lookaheadset[k] = LA (state->lookaheadsp)[k] & shiftset[k]; - - for (i = 0; i < ntokens; i++) - if (BITISSET (lookaheadset, i)) - fprintf (out, _(" %-4s\t[reduce using rule %d (%s)]\n"), - tags[i], default_rule, - tags[rule_table[default_rule].lhs]); + transitions *trans = s->transitions; + reductions *reds = s->reductions; + rule *default_rule = NULL; + size_t width = 0; + int i, j; - fprintf (out, _(" $default\treduce using rule %d (%s)\n\n"), - default_rule, tags[rule_table[default_rule].lhs]); - } - else if (state->nlookaheads >= 1) - { - int cmax = 0; - int default_LA = -1; - int default_rule = 0; + if (reds->num == 0) + return; - if (!nodefault) - for (i = 0; i < state->nlookaheads; ++i) - { - int count = 0; - int j, k; + if (yydefact[s->number] != 0) + default_rule = &rules[yydefact[s->number] - 1]; - for (k = 0; k < tokensetsize; ++k) - lookaheadset[k] = LA (state->lookaheadsp + i)[k] & ~shiftset[k]; + bitset_zero (no_reduce_set); + FOR_EACH_SHIFT (trans, i) + bitset_set (no_reduce_set, TRANSITION_SYMBOL (trans, i)); + for (i = 0; i < s->errs->num; ++i) + if (s->errs->symbols[i]) + bitset_set (no_reduce_set, s->errs->symbols[i]->number); - for (j = 0; j < ntokens; j++) - if (BITISSET (lookaheadset, j)) - count++; + /* Compute the width of the lookahead token column. */ + if (default_rule) + width = strlen (_("$default")); - if (count > cmax) - { - cmax = count; - default_LA = state->lookaheadsp + i; - default_rule = LAruleno[state->lookaheadsp + i]; - } + if (reds->lookahead_tokens) + for (i = 0; i < ntokens; i++) + { + bool count = bitset_test (no_reduce_set, i); - for (k = 0; k < tokensetsize; ++k) - shiftset[k] |= lookaheadset[k]; - } + for (j = 0; j < reds->num; ++j) + if (bitset_test (reds->lookahead_tokens[j], i)) + { + if (! count) + { + if (reds->rules[j] != default_rule) + max_length (&width, symbols[i]->tag); + count = true; + } + else + { + max_length (&width, symbols[i]->tag); + } + } + } - for (i = 0; i < tokensetsize; i++) - shiftset[i] = 0; + /* Nothing to report. */ + if (!width) + return; - for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++) - if (!SHIFT_IS_DISABLED (shiftp, i)) - SETBIT (shiftset, SHIFT_SYMBOL (shiftp, i)); + fputc ('\n', out); + width += 2; - for (i = 0; i < ntokens; i++) - { - int j; - int defaulted = 0; - int count = BITISSET (shiftset, i); + /* Report lookahead tokens (or $default) and reductions. */ + if (reds->lookahead_tokens) + for (i = 0; i < ntokens; i++) + { + bool defaulted = false; + bool count = bitset_test (no_reduce_set, i); - for (j = 0; j < state->nlookaheads; ++j) + for (j = 0; j < reds->num; ++j) + if (bitset_test (reds->lookahead_tokens[j], i)) { - if (BITISSET (LA (state->lookaheadsp + j), i)) + if (! count) { - if (count == 0) - { - if (state->lookaheadsp + j != default_LA) - fprintf (out, - _(" %-4s\treduce using rule %d (%s)\n"), - tags[i], - LAruleno[state->lookaheadsp + j], - tags[rule_table[LAruleno[state->lookaheadsp + j]].lhs]); - else - defaulted = 1; - - count++; - } + if (reds->rules[j] != default_rule) + print_reduction (out, width, + symbols[i]->tag, + reds->rules[j], true); else - { - if (defaulted) - fprintf (out, - _(" %-4s\treduce using rule %d (%s)\n"), - tags[i], - LAruleno[default_LA], - tags[rule_table[LAruleno[default_LA]].lhs]); - defaulted = 0; - fprintf (out, - _(" %-4s\t[reduce using rule %d (%s)]\n"), - tags[i], - LAruleno[state->lookaheadsp + j], - tags[rule_table[LAruleno[state->lookaheadsp + j]].lhs]); - } + defaulted = true; + count = true; + } + else + { + if (defaulted) + print_reduction (out, width, + symbols[i]->tag, + default_rule, true); + defaulted = false; + print_reduction (out, width, + symbols[i]->tag, + reds->rules[j], false); } } - } + } - if (default_LA >= 0) - fprintf (out, _(" $default\treduce using rule %d (%s)\n"), - default_rule, tags[rule_table[default_rule].lhs]); - } + if (default_rule) + print_reduction (out, width, + _("$default"), default_rule, true); } +/*--------------------------------------------------------------. +| Report on OUT all the actions (shifts, gotos, reductions, and | +| explicit erros from %nonassoc) of S. | +`--------------------------------------------------------------*/ + static void -print_actions (FILE *out, state_t *state) +print_actions (FILE *out, state *s) { - reductions *redp = state->reductions; - shifts *shiftp = state->shifts; + /* Print shifts. */ + print_transitions (s, out, true); + print_errs (out, s); + print_reductions (out, s); + /* Print gotos. */ + print_transitions (s, out, false); +} - if (!shiftp->nshifts && !redp) - { - if (final_state == state->number) - fprintf (out, _(" $default\taccept\n")); - else - fprintf (out, _(" NO ACTIONS\n")); - return; - } - print_shifts (out, state); - print_errs (out, state); - if (redp) - print_reductions (out, state); - print_gotos (out, state); -} +/*----------------------------------. +| Report all the data on S on OUT. | +`----------------------------------*/ static void -print_state (FILE *out, state_t *state) +print_state (FILE *out, state *s) { - fprintf (out, _("state %d"), state->number); - fputs ("\n\n", out); - print_core (out, state); - print_actions (out, state); fputs ("\n\n", out); + fprintf (out, _("state %d"), s->number); + fputc ('\n', out); + print_core (out, s); + print_actions (out, s); + if ((report_flag & report_solved_conflicts) && s->solved_conflicts) + { + fputc ('\n', out); + fputs (s->solved_conflicts, out); + } } /*-----------------------------------------. @@ -350,50 +384,33 @@ do { \ static void print_grammar (FILE *out) { - int i, j; - short *rule; + symbol_number i; char buffer[90]; int column = 0; - /* rule # : LHS -> RHS */ - fprintf (out, "%s\n\n", _("Grammar")); - fprintf (out, " %s\n", _("Number, Line, Rule")); - for (i = 1; i <= nrules; i++) - /* Don't print rules disabled in reduce_grammar_tables. */ - if (rule_table[i].useful) - { - fprintf (out, _(" %3d %3d %s ->"), - i, rule_table[i].line, tags[rule_table[i].lhs]); - rule = &ritem[rule_table[i].rhs]; - if (*rule > 0) - while (*rule > 0) - fprintf (out, " %s", tags[*rule++]); - else - fprintf (out, " /* %s */", _("empty")); - fputc ('\n', out); - } - fputs ("\n\n", out); - + grammar_rules_print (out); /* TERMINAL (type #) : rule #s terminal is on RHS */ fprintf (out, "%s\n\n", _("Terminals, with rules where they appear")); - fprintf (out, "%s (-1)\n", tags[0]); - - for (i = 0; i <= max_user_token_number; i++) - if (token_translations[i] != 2) + for (i = 0; i < max_user_token_number + 1; i++) + if (token_translations[i] != undeftoken->number) { + const char *tag = symbols[token_translations[i]]->tag; + rule_number r; + item_number *rhsp; + buffer[0] = 0; - column = strlen (tags[token_translations[i]]); - fputs (tags[token_translations[i]], out); - END_TEST (50); + column = strlen (tag); + fputs (tag, out); + END_TEST (65); sprintf (buffer, " (%d)", i); - for (j = 1; j <= nrules; j++) - for (rule = &ritem[rule_table[j].rhs]; *rule > 0; rule++) - if (*rule == token_translations[i]) + for (r = 0; r < nrules; r++) + for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++) + if (item_number_as_symbol_number (*rhsp) == token_translations[i]) { END_TEST (65); - sprintf (buffer + strlen (buffer), " %d", j); + sprintf (buffer + strlen (buffer), " %d", r); break; } fprintf (out, "%s\n", buffer); @@ -402,16 +419,19 @@ print_grammar (FILE *out) fprintf (out, "%s\n\n", _("Nonterminals, with rules where they appear")); - for (i = ntokens; i <= nsyms - 1; i++) + for (i = ntokens; i < nsyms; i++) { int left_count = 0, right_count = 0; + rule_number r; + const char *tag = symbols[i]->tag; - for (j = 1; j <= nrules; j++) + for (r = 0; r < nrules; r++) { - if (rule_table[j].lhs == i) + item_number *rhsp; + if (rules[r].lhs->number == i) left_count++; - for (rule = &ritem[rule_table[j].rhs]; *rule > 0; rule++) - if (*rule == i) + for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++) + if (item_number_as_symbol_number (*rhsp) == i) { right_count++; break; @@ -419,21 +439,23 @@ print_grammar (FILE *out) } buffer[0] = 0; - fputs (tags[i], out); - column = strlen (tags[i]); + fputs (tag, out); + column = strlen (tag); sprintf (buffer, " (%d)", i); END_TEST (0); if (left_count > 0) { - END_TEST (50); + END_TEST (65); sprintf (buffer + strlen (buffer), _(" on left:")); - for (j = 1; j <= nrules; j++) + for (r = 0; r < nrules; r++) { - END_TEST (65); - if (rule_table[j].lhs == i) - sprintf (buffer + strlen (buffer), " %d", j); + if (rules[r].lhs->number == i) + { + END_TEST (65); + sprintf (buffer + strlen (buffer), " %d", r); + } } } @@ -441,58 +463,51 @@ print_grammar (FILE *out) { if (left_count > 0) sprintf (buffer + strlen (buffer), ","); - END_TEST (50); + END_TEST (65); sprintf (buffer + strlen (buffer), _(" on right:")); - for (j = 1; j <= nrules; j++) + for (r = 0; r < nrules; r++) { - for (rule = &ritem[rule_table[j].rhs]; *rule > 0; rule++) - if (*rule == i) + item_number *rhsp; + for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++) + if (item_number_as_symbol_number (*rhsp) == i) { END_TEST (65); - sprintf (buffer + strlen (buffer), " %d", j); + sprintf (buffer + strlen (buffer), " %d", r); break; } } } fprintf (out, "%s\n", buffer); } - fputs ("\n\n", out); } void print_results (void) { - int i; + state_number i; /* We used to use just .out if SPEC_NAME_PREFIX (-p) was used, but that conflicts with Posix. */ FILE *out = xfopen (spec_verbose_file, "w"); - size_t size = obstack_object_size (&output_obstack); - fwrite (obstack_finish (&output_obstack), 1, size, out); - obstack_free (&output_obstack, NULL); - - if (size) - fputs ("\n\n", out); - reduce_output (out); + grammar_rules_partial_print (out, + _("Rules useless in parser due to conflicts"), + rule_useless_in_parser_p); conflicts_output (out); print_grammar (out); - /* New experimental feature: output all the items of a state, not - only its kernel. Requires to run closure, which need memory - allocation/deallocation. */ - if (trace_flag) - new_closure (nitems); + /* If the whole state item sets, not only the kernels, are wanted, + `closure' will be run, which needs memory allocation/deallocation. */ + if (report_flag & report_itemsets) + new_closure (nritems); /* Storage for print_reductions. */ - shiftset = XCALLOC (unsigned, tokensetsize); - lookaheadset = XCALLOC (unsigned, tokensetsize); + no_reduce_set = bitset_create (ntokens, BITSET_FIXED); for (i = 0; i < nstates; i++) - print_state (out, state_table[i]); - free (shiftset); - free (lookaheadset); - if (trace_flag) + print_state (out, states[i]); + bitset_free (no_reduce_set); + if (report_flag & report_itemsets) free_closure (); xfclose (out);