From bc933ef16d171af4f27616649c7a99c77e9b75fe Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Sun, 30 Jun 2002 17:32:47 +0000 Subject: [PATCH] * src/print.c (state_default_rule_compute): New, extracted from... (print_reductions): here. Pessimize, but clarify the code. * tests/conflicts.at (Defaulted Conflicted Reduction): New. --- ChangeLog | 7 ++ TODO | 24 +++-- src/print.c | 227 ++++++++++++++++++++++++--------------------- tests/conflicts.at | 167 ++++++++++++++++++++++++++++++--- 4 files changed, 300 insertions(+), 125 deletions(-) diff --git a/ChangeLog b/ChangeLog index 637a57fc..42008b99 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,10 @@ +2002-06-30 Akim Demaille + + * src/print.c (state_default_rule_compute): New, extracted from... + (print_reductions): here. + Pessimize, but clarify the code. + * tests/conflicts.at (Defaulted Conflicted Reduction): New. + 2002-06-30 Akim Demaille * src/output.c (action_row): Let default_rule be always a rule diff --git a/TODO b/TODO index 51d8d460..97505830 100644 --- a/TODO +++ b/TODO @@ -3,6 +3,16 @@ * URGENT: Documenting C++ output Write a first documentation for C++ output. +* Report and GLR +How would Paul like to display the conflicted actions? In particular, +what when two reductions are possible on a given lookahead, but one is +part of $default. Should we make the two reductions explicit, or just +keep $default? See the following point. + +* Report and Disabled Reductions +See `tests/conflicts.at (Defaulted Conflicted Reduction)', and decide +what we want to do. + * value_components_used Was defined but not used: where was it coming from? It can't be to check if %union is used, since the user is free to $n on her @@ -16,7 +26,9 @@ to #define yyerror and yyprint to steal internal variables... * documentation Explain $axiom (and maybe change its name: BTYacc names it `goal', byacc `$accept' probably based on AT&T Yacc, Meta `Start'...). -Complete the glossary (item, axiom, ?). +Complete the glossary (item, axiom, ?). Should we also rename `$'? +BYacc uses `$end'. `$eof' is attracting, but after all we may be +parsing a string, a stream etc. * Error messages Some are really funky. For instance @@ -26,11 +38,11 @@ Some are really funky. For instance is really weird. Revisit them all. * Report documentation -Extend with error. The hard part will probably be finding the right -rule so that a single state does not exhibit to many yet undocumented -``features''. Maybe an empty action ought to be presented too. Shall -we try to make a single grammar with all these features, or should we -have several very small grammars? +Extend with error productions. The hard part will probably be finding +the right rule so that a single state does not exhibit too many yet +undocumented ``features''. Maybe an empty action ought to be +presented too. Shall we try to make a single grammar with all these +features, or should we have several very small grammars? * Documentation Some history of Bison and some bibliography would be most welcome. diff --git a/src/print.c b/src/print.c index 021cb483..9ed6919e 100644 --- a/src/print.c +++ b/src/print.c @@ -165,138 +165,148 @@ print_gotos (FILE *out, state_t *state) } } + +/*----------------------------------------------------------. +| Return the default rule of this STATE if it has one, NULL | +| otherwise. | +`----------------------------------------------------------*/ + +static rule_t * +state_default_rule_compute (state_t *state) +{ + reductions_t *redp = state->reductions; + rule_t *default_rule = NULL; + int cmax = 0; + int i; + + /* No need for a lookahead. */ + if (state->consistent) + return &rules[redp->rules[0]]; + + /* 1. Each reduction is possibly masked by the lookaheads on which + we shift (S/R conflicts)... */ + bitset_zero (shiftset); + { + shifts_t *shiftp = state->shifts; + 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)) + return NULL; + bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i)); + } + } + + /* 2. Each reduction is possibly masked by the lookaheads on which + we raise an error (due to %nonassoc). */ + { + errs_t *errp = state->errs; + for (i = 0; i < errp->nerrs; i++) + if (errp->errs[i]) + bitset_set (shiftset, errp->errs[i]); + } + + for (i = 0; i < state->nlookaheads; ++i) + { + int count = 0; + + /* How many non-masked lookaheads are there for this reduction? + */ + bitset_andn (lookaheadset, state->lookaheads[i], shiftset); + count = bitset_count (lookaheadset); + + if (count > cmax) + { + cmax = count; + default_rule = state->lookaheads_rule[i]; + } + + /* 3. And finally, each reduction is possibly masked by previous + reductions (in R/R conflicts, we keep the first reductions). + */ + bitset_or (shiftset, shiftset, state->lookaheads[i]); + } + + return default_rule; +} + + +/*----------------------------------------------------. +| Report on OUT the reduction actions of this STATE. | +`----------------------------------------------------*/ + static void print_reductions (FILE *out, state_t *state) { int i; shifts_t *shiftp = state->shifts; reductions_t *redp = state->reductions; - errs_t *errp = state->errs; - int nodefault = 0; + rule_t *default_rule = NULL; if (redp->nreds == 0) return; - if (state->consistent) - { - int rule = redp->rules[0]; - symbol_number_t symbol = rules[rule].lhs->number; - fprintf (out, _(" $default\treduce using rule %d (%s)\n\n"), - rule - 1, symbol_tag_get (symbols[symbol])); - return; - } + default_rule = state_default_rule_compute (state); bitset_zero (shiftset); - 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; - bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i)); - } - - for (i = 0; i < errp->nerrs; i++) - if (errp->errs[i]) - bitset_set (shiftset, errp->errs[i]); - - if (state->nlookaheads == 1 && !nodefault) - { - rule_t *default_rule = state->lookaheads_rule[0]; - - bitset_and (lookaheadset, state->lookaheads[0], shiftset); + bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i)); - BITSET_EXECUTE (lookaheadset, 0, i, - { - fprintf (out, _(" %-4s\t[reduce using rule %d (%s)]\n"), - symbol_tag_get (symbols[i]), - default_rule->number - 1, - symbol_tag_get_n (default_rule->lhs, 1)); - }); - fprintf (out, _(" $default\treduce using rule %d (%s)\n\n"), - default_rule->number - 1, - symbol_tag_get (default_rule->lhs)); - } - else if (state->nlookaheads >= 1) + for (i = 0; i < ntokens; i++) { - int cmax = 0; - int default_LA = -1; - rule_t *default_rule = NULL; + int j; + int defaulted = 0; + int count = bitset_test (shiftset, i); - if (!nodefault) - for (i = 0; i < state->nlookaheads; ++i) + for (j = 0; j < state->nlookaheads; ++j) + if (bitset_test (state->lookaheads[j], i)) { - int count = 0; - - bitset_andn (lookaheadset, state->lookaheads[i], shiftset); - count = bitset_count (lookaheadset); - - if (count > cmax) + if (count == 0) { - cmax = count; - default_LA = i; - default_rule = state->lookaheads_rule[i]; + if (state->lookaheads_rule[j] != default_rule) + fprintf (out, + _(" %-4s\treduce using rule %d (%s)\n"), + symbol_tag_get (symbols[i]), + state->lookaheads_rule[j]->number - 1, + symbol_tag_get_n (state->lookaheads_rule[j]->lhs, 1)); + else + defaulted = 1; + count++; } - - bitset_or (shiftset, shiftset, lookaheadset); - } - - bitset_zero (shiftset); - - for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++) - if (!SHIFT_IS_DISABLED (shiftp, i)) - bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i)); - - for (i = 0; i < ntokens; i++) - { - int j; - int defaulted = 0; - int count = bitset_test (shiftset, i); - - for (j = 0; j < state->nlookaheads; ++j) - if (bitset_test (state->lookaheads[j], i)) + else { - if (count == 0) - { - if (j != default_LA) - fprintf (out, - _(" %-4s\treduce using rule %d (%s)\n"), - symbol_tag_get (symbols[i]), - state->lookaheads_rule[j]->number - 1, - symbol_tag_get_n (state->lookaheads_rule[j]->lhs, 1)); - else - defaulted = 1; - - count++; - } - else - { - if (defaulted) - fprintf (out, - _(" %-4s\treduce using rule %d (%s)\n"), - symbol_tag_get (symbols[i]), - state->lookaheads_rule[default_LA]->number - 1, - symbol_tag_get_n (state->lookaheads_rule[default_LA]->lhs, 1)); - defaulted = 0; - fprintf (out, - _(" %-4s\t[reduce using rule %d (%s)]\n"), - symbol_tag_get (symbols[i]), - state->lookaheads_rule[j]->number - 1, - symbol_tag_get_n (state->lookaheads_rule[j]->lhs, 1)); - } + if (defaulted) + fprintf (out, + _(" %-4s\treduce using rule %d (%s)\n"), + symbol_tag_get (symbols[i]), + default_rule->number - 1, + symbol_tag_get_n (default_rule->lhs, 1)); + defaulted = 0; + fprintf (out, + _(" %-4s\t[reduce using rule %d (%s)]\n"), + symbol_tag_get (symbols[i]), + state->lookaheads_rule[j]->number - 1, + symbol_tag_get_n (state->lookaheads_rule[j]->lhs, 1)); } - } - - if (default_LA >= 0) - fprintf (out, _(" $default\treduce using rule %d (%s)\n"), - default_rule->number - 1, - symbol_tag_get (default_rule->lhs)); + } } + + if (default_rule) + fprintf (out, _(" $default\treduce using rule %d (%s)\n"), + default_rule->number - 1, + symbol_tag_get (default_rule->lhs)); + fputc ('\n', out); } +/*--------------------------------------------------------------. +| Report on OUT all the actions (shifts, gotos, reductions, and | +| explicit erros from %nonassoc) of STATE. | +`--------------------------------------------------------------*/ + static void print_actions (FILE *out, state_t *state) { @@ -306,9 +316,9 @@ print_actions (FILE *out, state_t *state) if (shiftp->nshifts == 0 && redp->nreds == 0) { if (state->number == final_state->number) - fprintf (out, _(" $default\taccept\n")); + fprintf (out, _(" $default\taccept\n")); else - fprintf (out, _(" NO ACTIONS\n")); + fprintf (out, _(" NO ACTIONS\n")); return; } @@ -318,6 +328,7 @@ print_actions (FILE *out, state_t *state) print_gotos (out, state); } + static void print_state (FILE *out, state_t *state) { diff --git a/tests/conflicts.at b/tests/conflicts.at index 3aceda1c..38f8f0e9 100644 --- a/tests/conflicts.at +++ b/tests/conflicts.at @@ -41,6 +41,7 @@ AT_CHECK([bison input.y -o input.c]) AT_CLEANUP + ## ------------------- ## ## %nonassoc and eof. ## ## ------------------- ## @@ -237,26 +238,30 @@ state 5 AT_CLEANUP -## --------------------- ## -## Solved SR Conflicts. ## -## --------------------- ## +## ------------------------- ## +## Unresolved SR Conflicts. ## +## ------------------------- ## -AT_SETUP([Solved SR Conflicts]) +AT_SETUP([Unresolved SR Conflicts]) AT_KEYWORDS([report]) AT_DATA([input.y], [[%token NUM OP -%right OP %% exp: exp OP exp | NUM; ]]) -AT_CHECK([bison input.y -o input.c --report=all], 0, [], []) +AT_CHECK([bison input.y -o input.c --report=all], 0, [], +[input.y contains 1 shift/reduce conflict. +]) # Check the contents of the report. AT_CHECK([cat input.output], [], -[[Grammar +[[State 5 contains 1 shift/reduce conflict. + + +Grammar 0 $axiom: exp $ @@ -331,14 +336,154 @@ state 4 state 5 - exp -> exp . OP exp [$] (rule 1) - exp -> exp OP exp . [$] (rule 1) + exp -> exp . OP exp [$, OP] (rule 1) + exp -> exp OP exp . [$, OP] (rule 1) OP shift, and go to state 4 + OP [reduce using rule 1 (exp)] + $default reduce using rule 1 (exp) + + + +]]) + +AT_CLEANUP + + + +## -------------------------------- ## +## Defaulted Conflicted Reduction. ## +## -------------------------------- ## + +# When there are RR conflicts, some rules are disabled. Usually it is +# simply displayed as: +# +# $ reduce using rule 3 (num) +# $ [reduce using rule 4 (id)] +# +# But when `reduce 3' is the default action, we'd produce: +# +# $ [reduce using rule 4 (id)] +# $default reduce using rule 3 (num) +# +# In this precise case (a reduction is masked by the default +# reduction), we make the `reduce 3' explicit: +# +# $ reduce using rule 3 (num) +# $ [reduce using rule 4 (id)] +# $default reduce using rule 3 (num) +# +# Maybe that's not the best display, but then, please propose something +# else. + +AT_SETUP([Defaulted Conflicted Reduction]) +AT_KEYWORDS([report]) + +AT_DATA([input.y], +[[%% +exp: num | id; +num: '0'; +id : '0'; +%% +]]) + +AT_CHECK([bison input.y -o input.c --report=all], 1, [], +[input.y contains 1 reduce/reduce conflict. +]) + +# Check the contents of the report. +AT_CHECK([cat input.output], [], +[[State 1 contains 1 reduce/reduce conflict. + + +Grammar + + 0 $axiom: exp $ + + 1 exp: num + 2 | id + + 3 num: '0' + + 4 id: '0' + + +Terminals, with rules where they appear + +$ (0) 0 +'0' (48) 3 4 +error (256) + + +Nonterminals, with rules where they appear + +$axiom (4) + on left: 0 +exp (5) + on left: 1 2, on right: 0 +num (6) + on left: 3, on right: 1 +id (7) + on left: 4, on right: 2 + + +state 0 + + $axiom -> . exp $ (rule 0) + exp -> . num (rule 1) + exp -> . id (rule 2) + num -> . '0' (rule 3) + id -> . '0' (rule 4) + + '0' shift, and go to state 1 + + exp go to state 2 + num go to state 3 + id go to state 4 + + + +state 1 + + num -> '0' . [$] (rule 3) + id -> '0' . [$] (rule 4) + + $ reduce using rule 3 (num) + $ [reduce using rule 4 (id)] + $default reduce using rule 3 (num) + + + +state 2 + + $axiom -> exp . $ (rule 0) + + $ shift, and go to state 5 + + + +state 3 + + exp -> num . (rule 1) + $default reduce using rule 1 (exp) - Conflict between rule 2 and token OP resolved as reduce (%right OP). + + +state 4 + + exp -> id . (rule 2) + + $default reduce using rule 2 (exp) + + + +state 5 + + $axiom -> exp $ . (rule 0) + + $default accept ]]) @@ -381,7 +526,7 @@ AT_DATA([input.y], exp: exp OP exp | NUM; ]]) -AT_CHECK([bison input.y -o input.c], 0) +AT_CHECK([bison input.y -o input.c]) AT_CLEANUP -- 2.45.2