From e8832397ea06de8049828011aff948b5302ffe66 Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Tue, 30 Jul 2002 11:06:50 +0000 Subject: [PATCH] Report rules which are never reduced by the parser: those hidden by conflicts. * src/LR0.c (save_reductions): Don't make the final state too different: save its reduction (accept) instead of having a state without any action (no shift or goto, no reduce). Note: the final state is now a ``regular'' state, i.e., the parsers now contain `reduce 0' as default reduction. Nevertheless, since they decide to `accept' when yystate = final_state, they still will not reduce rule 0. * src/print.c (print_actions, print_reduction): Adjust. * src/output.c (action_row): Track reduced rules. (token_actions): Report rules never reduced. * tests/conflicts.at, tests/regression.at: Adjust. --- ChangeLog | 17 +++++++++++++++++ NEWS | 6 +++++- src/LR0.c | 5 ----- src/output.c | 29 +++++++++++++++++++++++++++++ src/print.c | 20 +++++--------------- tests/conflicts.at | 15 +++++++++------ tests/regression.at | 6 +++--- 7 files changed, 68 insertions(+), 30 deletions(-) diff --git a/ChangeLog b/ChangeLog index 3c4a350f..ccb65060 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,20 @@ +2002-07-30 Akim Demaille + + Report rules which are never reduced by the parser: those hidden + by conflicts. + + * src/LR0.c (save_reductions): Don't make the final state too + different: save its reduction (accept) instead of having a state + without any action (no shift or goto, no reduce). + Note: the final state is now a ``regular'' state, i.e., the + parsers now contain `reduce 0' as default reduction. + Nevertheless, since they decide to `accept' when yystate = + final_state, they still will not reduce rule 0. + * src/print.c (print_actions, print_reduction): Adjust. + * src/output.c (action_row): Track reduced rules. + (token_actions): Report rules never reduced. + * tests/conflicts.at, tests/regression.at: Adjust. + 2002-07-30 Akim Demaille `stage' was accidently included in a previous patch. diff --git a/NEWS b/NEWS index 144d865d..6123e57a 100644 --- a/NEWS +++ b/NEWS @@ -8,7 +8,7 @@ Changes in version 1.49b: %glr-parser causes Bison to produce a Generalized LR (GLR) parser, capable of handling almost any context-free grammar, ambiguous or not. The new declarations - %dprec and %merge on grammar rules allow parse-time resolution of + %dprec and %merge on grammar rules allow parse-time resolution of ambiguities. Contributed by Paul Hilfinger. * Output Directory @@ -58,6 +58,10 @@ Changes in version 1.49b: * Useless rules, useless nonterminals They are now reported, as a warning, with their locations. +* Rules never reduced + Rules that can never be reduced because of conflicts are now + reported. + * Incorrect `Token not used' On a grammar such as diff --git a/src/LR0.c b/src/LR0.c index 00ff736c..184a25f4 100644 --- a/src/LR0.c +++ b/src/LR0.c @@ -282,11 +282,6 @@ save_reductions (state_t *state) int count = 0; int i; - /* If this is the final state, we want it to have no reductions at - all, although it has one for `START_SYMBOL $end .'. */ - if (final_state && state->number == final_state->number) - return; - /* Find and count the active items that represent ends of rules. */ for (i = 0; i < nritemset; ++i) { diff --git a/src/output.c b/src/output.c index 1ec4d6b0..5f0fa05f 100644 --- a/src/output.c +++ b/src/output.c @@ -598,6 +598,16 @@ 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". */ @@ -671,6 +681,7 @@ static void token_actions (void) { state_number_t i; + rule_number_t r; int nconflict = conflicts_total_count (); rule_number_t *yydefact = XCALLOC (rule_number_t, nstates); @@ -678,6 +689,13 @@ 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. + */ + if (!glr_parser) + for (r = 0; r < nrules; ++r) + rules[r].useful = FALSE; + if (glr_parser) { conflict_list = XCALLOC (unsigned int, 1 + 2 * nconflict); @@ -696,6 +714,17 @@ token_actions (void) muscle_insert_rule_number_table ("defact", yydefact, yydefact[0], 1, nstates); + + if (!glr_parser) + for (r = 0; r < nrules ; ++r) + if (!rules[r].useful) + { + LOCATION_PRINT (stderr, rules[r].location); + fprintf (stderr, ": %s: %s: ", + _("warning"), _("rule never reduced because of conflicts")); + rule_print (&rules[r], stderr); + } + XFREE (actrow); XFREE (conflrow); XFREE (yydefact); diff --git a/src/print.c b/src/print.c index 1227765b..2a07affa 100644 --- a/src/print.c +++ b/src/print.c @@ -286,8 +286,11 @@ print_reduction (FILE *out, size_t width, fputc (' ', out); if (!enabled) fputc ('[', out); - fprintf (out, _("reduce using rule %d (%s)"), - rule->number, rule->lhs->tag); + if (rule->number) + fprintf (out, _("reduce using rule %d (%s)"), + rule->number, rule->lhs->tag); + else + fprintf (out, _("accept")); if (!enabled) fputc (']', out); fputc ('\n', out); @@ -393,19 +396,6 @@ print_reductions (FILE *out, state_t *state) static void print_actions (FILE *out, state_t *state) { - reductions_t *redp = state->reductions; - transitions_t *transitions = state->transitions; - - if (transitions->num == 0 && redp->num == 0) - { - fputc ('\n', out); - if (state->number == final_state->number) - fprintf (out, _(" $default\taccept\n")); - else - fprintf (out, _(" NO ACTIONS\n")); - return; - } - /* Print shifts. */ print_transitions (state, out, TRUE); print_errs (out, state); diff --git a/tests/conflicts.at b/tests/conflicts.at index 84b4fcda..d0da937b 100644 --- a/tests/conflicts.at +++ b/tests/conflicts.at @@ -37,7 +37,9 @@ exp: e 'e'; e: 'e' | /* Nothing. */; ]]) -AT_CHECK([bison input.y -o input.c]) +AT_CHECK([bison input.y -o input.c], 0, [], +[[input.y:4.8: warning: rule never reduced because of conflicts: e: /* empty */ +]]) AT_CLEANUP @@ -203,7 +205,7 @@ state 3 0 $accept: exp $end . - $default accept + $default accept state 4 @@ -306,7 +308,7 @@ state 3 0 $accept: exp $end . - $default accept + $default accept state 4 @@ -369,8 +371,9 @@ id : '0'; ]]) AT_CHECK([bison input.y -o input.c --report=all], 0, [], -[input.y contains 1 reduce/reduce conflict. -]) +[[input.y contains 1 reduce/reduce conflict. +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], [], @@ -458,7 +461,7 @@ state 5 0 $accept: exp $end . - $default accept + $default accept ]]) AT_CLEANUP diff --git a/tests/regression.at b/tests/regression.at index ca5c2f97..f8768f76 100644 --- a/tests/regression.at +++ b/tests/regression.at @@ -228,7 +228,7 @@ state 5 0 $accept: expr $end . - $default accept + $default accept state 6 @@ -456,7 +456,7 @@ state 5 0 $accept: CONST_DEC_PART $end . - $default accept + $default accept state 6 @@ -601,7 +601,7 @@ static const unsigned char yyr2[] = }; static const unsigned char yydefact[] = { - 3, 0, 0, 2, 0, 0, 0, 3, 4, 3, + 3, 0, 0, 2, 0, 0, 1, 3, 4, 3, 6, 5 }; static const signed char yydefgoto[] = -- 2.45.2