From c8f002c7d3407d5c91a5882466916160a72aa8c4 Mon Sep 17 00:00:00 2001 From: Akim Demaille <akim@epita.fr> Date: Fri, 2 Aug 2002 08:05:01 +0000 Subject: [PATCH] * src/conflicts.c (conflicts_output): Don't output rules never reduced here, since anyway that computation doesn't work. * src/gram.h, src/gram.h (rule_filter_t, rule_useful_p) (rule_useless_p, rule_never_reduced_p): New. (grammar_rules_partial_print): Use a filter instead of a range. Display the title only if needed. (grammar_rules_print): Adjust. (grammar_rules_never_reduced_report): New. * src/tables.c (action_row): Move the computation of rules never reduced to... (token_actions): here. * src/main.c (main): Make the parser before making the report, so that rules never reduced are computed. Call grammar_rules_never_reduced_report. * src/print.c (print_results): Report rules never reduced. * tests/conflicts.at, tests/reduce.at: Adjust. --- ChangeLog | 19 +++++++++++ src/conflicts.c | 22 ------------- src/gram.c | 80 ++++++++++++++++++++++++++++++++++++++++------ src/gram.h | 54 +++++++++++++++++++++---------- src/main.c | 21 ++++++------ src/print.c | 2 ++ src/reduce.c | 18 +++-------- src/tables.c | 34 ++++++++------------ tests/conflicts.at | 7 +++- tests/reduce.at | 14 ++++---- 10 files changed, 172 insertions(+), 99 deletions(-) diff --git a/ChangeLog b/ChangeLog index b50e3503..d9e3482a 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,22 @@ +2002-08-02 Akim Demaille <akim@epita.fr> + + * src/conflicts.c (conflicts_output): Don't output rules never + reduced here, since anyway that computation doesn't work. + * src/gram.h, src/gram.h (rule_filter_t, rule_useful_p) + (rule_useless_p, rule_never_reduced_p): New. + (grammar_rules_partial_print): Use a filter instead of a range. + Display the title only if needed. + (grammar_rules_print): Adjust. + (grammar_rules_never_reduced_report): New. + * src/tables.c (action_row): Move the computation of rules never + reduced to... + (token_actions): here. + * src/main.c (main): Make the parser before making the report, so + that rules never reduced are computed. + Call grammar_rules_never_reduced_report. + * src/print.c (print_results): Report rules never reduced. + * tests/conflicts.at, tests/reduce.at: Adjust. + 2002-08-01 Akim Demaille <akim@epita.fr> Instead of attaching lookaheads and duplicating the rules being diff --git a/src/conflicts.c b/src/conflicts.c index 1c24d7e2..24f27cc8 100644 --- a/src/conflicts.c +++ b/src/conflicts.c @@ -451,15 +451,10 @@ void conflicts_output (FILE *out) { bool printed_sth = FALSE; - bool *used_rules = XCALLOC (bool, nrules); state_number_t i; for (i = 0; i < nstates; i++) { state_t *s = states[i]; - reductions_t *reds = s->reductions; - int j; - for (j = 0; j < reds->num; ++j) - used_rules[reds->rules[j]->number] = TRUE; if (conflicts[i]) { fprintf (out, _("State %d contains "), i); @@ -471,23 +466,6 @@ conflicts_output (FILE *out) } if (printed_sth) fputs ("\n\n", out); - - for (i = 0; i < nstates; i++) - { - state_t *s = states[i]; - reductions_t *r = s->reductions; - int j; - for (j = 0; j < r->num; ++j) - if (!used_rules[r->rules[j]->number]) - { - LOCATION_PRINT (stderr, r->rules[j]->location); - fprintf (stderr, ": %s: %s: ", - _("warning"), - _("rule never reduced because of conflicts")); - rule_print (r->rules[j], stderr); - } - } - free (used_rules); } /*--------------------------------------------------------. diff --git a/src/gram.c b/src/gram.c index c28f5b5e..263411a4 100644 --- a/src/gram.c +++ b/src/gram.c @@ -47,6 +47,40 @@ int glr_parser = 0; int pure_parser = 0; +/*--------------------------------------------------------------. +| Return true IFF the rule has a `number' smaller than NRULES. | +`--------------------------------------------------------------*/ + +bool +rule_useful_p (rule_t *r) +{ + return r->number < nrules; +} + + +/*-------------------------------------------------------------. +| Return true IFF the rule has a `number' higher than NRULES. | +`-------------------------------------------------------------*/ + +bool +rule_useless_p (rule_t *r) +{ + return r->number >= nrules; +} + + +/*--------------------------------------------------------------------. +| Return true IFF the rule is not flagged as useful *and* is useful. | +| In other words, it was discarded because of conflicts. | +`--------------------------------------------------------------------*/ + +bool +rule_never_reduced_p (rule_t *r) +{ + return !r->useful && r->number < nrules; +} + + /*----------------------------------------------------------------. | Print this RULE's number and lhs on OUT. If a PREVIOUS_LHS was | | already displayed (by a previous call for another rule), avoid | @@ -158,29 +192,34 @@ ritem_longest_rhs (void) } -/*----------------------------------------------------------------. -| Print the grammar's rules numbers from BEGIN (inclusive) to END | -| (exclusive) on OUT under TITLE. | -`----------------------------------------------------------------*/ +/*-----------------------------------------------------------------. +| Print the grammar's rules that match FILTER on OUT under TITLE. | +`-----------------------------------------------------------------*/ void grammar_rules_partial_print (FILE *out, const char *title, - rule_number_t begin, rule_number_t end) + rule_filter_t filter) { int r; + bool first = TRUE; symbol_t *previous_lhs = NULL; /* rule # : LHS -> RHS */ - fprintf (out, "%s\n\n", title); - for (r = begin; r < end; r++) + for (r = 0; r < nrules + nuseless_productions; r++) { - if (previous_lhs && previous_lhs != rules[r].lhs) + if (filter && !filter (&rules[r])) + continue; + if (first) + fprintf (out, "%s\n\n", title); + else if (previous_lhs && previous_lhs != rules[r].lhs) fputc ('\n', out); + first = FALSE; rule_lhs_print (&rules[r], previous_lhs, out); rule_rhs_print (&rules[r], out); previous_lhs = rules[r].lhs; } - fputs ("\n\n", out); + if (!first) + fputs ("\n\n", out); } @@ -191,7 +230,7 @@ grammar_rules_partial_print (FILE *out, const char *title, void grammar_rules_print (FILE *out) { - grammar_rules_partial_print (out, _("Grammar"), 0, nrules); + grammar_rules_partial_print (out, _("Grammar"), rule_useful_p); } @@ -262,6 +301,27 @@ grammar_dump (FILE *out, const char *title) } +/*------------------------------------------------------------------. +| Report on STDERR the rules that are not flagged USEFUL, using the | +| MESSAGE (which can be `useless rule' when invoked after grammar | +| reduction, or `never reduced' after conflicts were taken into | +| account). | +`------------------------------------------------------------------*/ + +void +grammar_rules_never_reduced_report (const char *message) +{ + rule_number_t r; + for (r = 0; r < nrules ; ++r) + if (!rules[r].useful) + { + LOCATION_PRINT (stderr, rules[r].location); + fprintf (stderr, ": %s: %s: ", + _("warning"), message); + rule_print (&rules[r], stderr); + } +} + void grammar_free (void) { diff --git a/src/gram.h b/src/gram.h index dd5a45f8..de782f7d 100644 --- a/src/gram.h +++ b/src/gram.h @@ -175,6 +175,36 @@ typedef struct rule_s extern struct rule_s *rules; +/* A function that selects a rule. */ +typedef bool (*rule_filter_t) PARAMS ((rule_t *r)); + +/* Return true IFF the rule has a `number' smaller than NRULES. */ +bool rule_useful_p PARAMS ((rule_t *r)); + +/* Return true IFF the rule has a `number' higher than NRULES. */ +bool rule_useless_p PARAMS ((rule_t *r)); + +/* Return true IFF the rule is not flagged as useful *and* is useful. + In other words, it was discarded because of conflicts. */ +bool rule_never_reduced_p PARAMS ((rule_t *r)); + +/* Print this RULE's number and lhs on OUT. If a PREVIOUS_LHS was + already displayed (by a previous call for another rule), avoid + useless repetitions. */ +void rule_lhs_print PARAMS ((rule_t *rule, symbol_t *previous_lhs, FILE *out)); + +/* Return the length of the RHS. */ +int rule_rhs_length PARAMS ((rule_t *rule)); + +/* Print this RULE's RHS on OUT. */ +void rule_rhs_print PARAMS ((rule_t *rule, FILE *out)); + +/* Print this RULE on OUT. */ +void rule_print PARAMS ((rule_t *rule, FILE *out)); + + + + /* Table of the symbols, indexed by the symbol number. */ extern symbol_t **symbols; @@ -185,6 +215,7 @@ extern symbol_number_t *token_translations; extern int max_user_token_number; + /* GLR_PARSER is nonzero if the input file says to use the GLR (Generalized LR) parser, and to output some additional information used by the GLR algorithm. */ @@ -196,20 +227,6 @@ extern int glr_parser; extern int pure_parser; -/* Print this RULE's number and lhs on OUT. If a PREVIOUS_LHS was - already displayed (by a previous call for another rule), avoid - useless repetitions. */ -void rule_lhs_print PARAMS ((rule_t *rule, symbol_t *previous_lhs, FILE *out)); - -/* Return the length of the RHS. */ -int rule_rhs_length PARAMS ((rule_t *rule)); - -/* Print this RULE's RHS on OUT. */ -void rule_rhs_print PARAMS ((rule_t *rule, FILE *out)); - -/* Print this RULE on OUT. */ -void rule_print PARAMS ((rule_t *rule, FILE *out)); - /* Dump RITEM for traces. */ void ritem_print PARAMS ((FILE *out)); @@ -219,8 +236,7 @@ size_t ritem_longest_rhs PARAMS ((void)); /* Print the grammar's rules numbers from BEGIN (inclusive) to END (exclusive) on OUT under TITLE. */ void grammar_rules_partial_print PARAMS ((FILE *out, const char *title, - rule_number_t begin, - rule_number_t end)); + rule_filter_t filter)); /* Print the grammar's rules on OUT. */ void grammar_rules_print PARAMS ((FILE *out)); @@ -228,6 +244,12 @@ void grammar_rules_print PARAMS ((FILE *out)); /* Dump the grammar. */ void grammar_dump PARAMS ((FILE *out, const char *title)); +/* Report on STDERR the rules that are not flagged USEFUL, using the + MESSAGE (which can be `useless rule' when invoked after grammar + reduction, or `never reduced' after conflicts were taken into + account). */ +void grammar_rules_never_reduced_report PARAMS ((const char *message)); + /* Free the packed grammar. */ void grammar_free PARAMS ((void)); diff --git a/src/main.c b/src/main.c index e634f310..602d4db6 100644 --- a/src/main.c +++ b/src/main.c @@ -108,6 +108,14 @@ main (int argc, char *argv[]) conflicts_print (); timevar_pop (TV_CONFLICTS); + /* Compute the parser tables. */ + timevar_push (TV_ACTIONS); + tables_generate (); + timevar_pop (TV_ACTIONS); + + grammar_rules_never_reduced_report + (_("rule never reduced because of conflicts")); + /* Output file names. */ compute_output_file_names (); @@ -119,11 +127,6 @@ main (int argc, char *argv[]) timevar_pop (TV_REPORT); } - /* Stop if there were errors, to avoid trashing previous output - files. */ - if (complain_message_count) - exit (1); - /* Output the VCG graph. */ if (graph_flag) { @@ -132,10 +135,10 @@ main (int argc, char *argv[]) timevar_pop (TV_GRAPH); } - /* Compute the parser tables. */ - timevar_push (TV_ACTIONS); - tables_generate (); - timevar_pop (TV_ACTIONS); + /* Stop if there were errors, to avoid trashing previous output + files. */ + if (complain_message_count) + exit (1); /* Lookaheads are no longer needed. */ timevar_push (TV_FREE); diff --git a/src/print.c b/src/print.c index 12466c90..6fbe2c9a 100644 --- a/src/print.c +++ b/src/print.c @@ -548,6 +548,8 @@ print_results (void) FILE *out = xfopen (spec_verbose_file, "w"); reduce_output (out); + grammar_rules_partial_print (out, + _("Rules never reduced"), rule_never_reduced_p); conflicts_output (out); print_grammar (out); diff --git a/src/reduce.c b/src/reduce.c index 986aecd0..7bbd8954 100644 --- a/src/reduce.c +++ b/src/reduce.c @@ -235,15 +235,8 @@ reduce_grammar_tables (void) { rule_number_t r; for (r = 0; r < nrules; r++) - { - rules[r].useful = bitset_test (P, r); - if (!rules[r].useful) - { - LOCATION_PRINT (stderr, rules[r].location); - fprintf (stderr, ": %s: %s: ", _("warning"), _("useless rule")); - rule_print (&rules[r], stderr); - } - } + rules[r].useful = bitset_test (P, r); + grammar_rules_never_reduced_report (_("useless rule")); } /* Map the nonterminals to their new index: useful first, useless @@ -353,7 +346,7 @@ reduce_output (FILE *out) if (nuseless_nonterminals > 0) { int i; - fprintf (out, "%s\n\n", _("Useless nonterminals:")); + fprintf (out, "%s\n\n", _("Useless nonterminals")); for (i = 0; i < nuseless_nonterminals; ++i) fprintf (out, " %s\n", symbols[nsyms + i]->tag); fputs ("\n\n", out); @@ -366,7 +359,7 @@ reduce_output (FILE *out) if (!bitset_test (V, i) && !bitset_test (V1, i)) { if (!b) - fprintf (out, "%s\n\n", _("Terminals which are not used:")); + fprintf (out, "%s\n\n", _("Terminals which are not used")); b = TRUE; fprintf (out, " %s\n", symbols[i]->tag); } @@ -376,8 +369,7 @@ reduce_output (FILE *out) if (nuseless_productions > 0) grammar_rules_partial_print (out, _("Useless rules"), - nrules, - nrules + nuseless_productions); + rule_useless_p); } diff --git a/src/tables.c b/src/tables.c index 75502759..47d9d6af 100644 --- a/src/tables.c +++ b/src/tables.c @@ -394,16 +394,6 @@ action_row (state_t *state) } } - /* Find the rules which are reduced. */ - if (!glr_parser) - { - for (i = 0; i < ntokens; i++) - if (actrow[i] < 0 && actrow[i] != ACTION_MIN) - rules[item_number_as_rule_number (actrow[i])].useful = TRUE; - if (default_rule) - default_rule->useful = TRUE; - } - /* If have no default rule, the default is an error. So replace any action which says "error" with "use default". */ @@ -477,7 +467,9 @@ static void token_actions (void) { state_number_t i; + symbol_number_t j; rule_number_t r; + int nconflict = conflicts_total_count (); yydefact = XCALLOC (rule_number_t, nstates); @@ -485,9 +477,7 @@ token_actions (void) actrow = XCALLOC (action_t, ntokens); conflrow = XCALLOC (unsigned int, ntokens); - /* Now that the parser was computed, we can find which rules are - really reduced, and which are not because of SR or RR conflicts. - */ + /* Find the rules which are reduced. */ if (!glr_parser) for (r = 0; r < nrules; ++r) rules[r].useful = FALSE; @@ -506,17 +496,19 @@ token_actions (void) rule_t *default_rule = action_row (states[i]); yydefact[i] = default_rule ? default_rule->number + 1 : 0; save_row (i); - } - if (!glr_parser) - for (r = 0; r < nrules ; ++r) - if (!rules[r].useful) + /* Now that the parser was computed, we can find which rules are + really reduced, and which are not because of SR or RR + conflicts. */ + if (!glr_parser) { - LOCATION_PRINT (stderr, rules[r].location); - fprintf (stderr, ": %s: %s: ", - _("warning"), _("rule never reduced because of conflicts")); - rule_print (&rules[r], stderr); + for (j = 0; j < ntokens; ++j) + if (actrow[j] < 0 && actrow[j] != ACTION_MIN) + rules[item_number_as_rule_number (actrow[j])].useful = TRUE; + if (yydefact[i]) + rules[yydefact[i] - 1].useful = TRUE; } + } free (actrow); free (conflrow); diff --git a/tests/conflicts.at b/tests/conflicts.at index 6a9ef9bd..6f0a971f 100644 --- a/tests/conflicts.at +++ b/tests/conflicts.at @@ -377,7 +377,12 @@ input.y:4.4-8: warning: rule never reduced because of conflicts: id: '0' # Check the contents of the report. AT_CHECK([cat input.output], [], -[[State 1 contains 1 reduce/reduce conflict. +[[Rules never reduced + + 4 id: '0' + + +State 1 contains 1 reduce/reduce conflict. Grammar diff --git a/tests/reduce.at b/tests/reduce.at index 4c8da723..e475cb04 100644 --- a/tests/reduce.at +++ b/tests/reduce.at @@ -47,7 +47,7 @@ exp: useful; AT_CHECK([[bison input.y]]) AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0, -[[Terminals which are not used: +[[Terminals which are not used useless1 useless2 useless3 @@ -102,7 +102,7 @@ input.y:12.8-15: warning: useless nonterminal: useless9 ]]) AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0, -[[Useless nonterminals: +[[Useless nonterminals useless1 useless2 useless3 @@ -166,7 +166,7 @@ input.y:14.9-13: warning: useless rule: useless9: '9' ]]) AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0, -[[Useless nonterminals: +[[Useless nonterminals useless1 useless2 useless3 @@ -176,7 +176,7 @@ AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0, useless7 useless8 useless9 -Terminals which are not used: +Terminals which are not used '1' '2' '3' @@ -248,10 +248,10 @@ not-reduced.y:17.15-18.63: warning: useless rule: non_productive: non_productive ]]) AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' not-reduced.output]], 0, -[[Useless nonterminals: +[[Useless nonterminals not_reachable non_productive -Terminals which are not used: +Terminals which are not used useless_token Useless rules 2 exp: non_productive @@ -322,7 +322,7 @@ input.y:7.12-24: warning: useless rule: indirection: underivable ]]) AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0, -[[Useless nonterminals: +[[Useless nonterminals underivable indirection Useless rules -- 2.45.2