[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH 9/9] cex: display shifts before reductions
From: |
Akim Demaille |
Subject: |
[PATCH 9/9] cex: display shifts before reductions |
Date: |
Sun, 12 Jul 2020 19:23:18 +0200 |
When reporting counterexamples for s/r conflicts, put the shift first.
This is more natural, and displays the default resolution first, which
is also what happens for r/r conflicts where the smallest rule number
is displayed first, and "wins".
* src/counterexample.c (counterexample): Add a shift_reduce member.
(new_counterexample): Adjust.
Swap the derivations when this is a s/r conflict.
(print_counterexample): For s/r conflicts, prefer "Shift derivation"
and "Reduce derivation" rather than "First/Second derivation".
* tests/conflicts.at, tests/counterexample.at, tests/report.at: Adjust.
* NEWS, doc/bison.texi: Ditto.
---
NEWS | 14 +++---
doc/bison.texi | 42 ++++++++---------
src/counterexample.c | 34 ++++++++++----
tests/conflicts.at | 4 +-
tests/counterexample.at | 100 ++++++++++++++++++++--------------------
tests/report.at | 40 ++++++++--------
6 files changed, 126 insertions(+), 108 deletions(-)
diff --git a/NEWS b/NEWS
index b4b61f40..c7efefa1 100644
--- a/NEWS
+++ b/NEWS
@@ -2,6 +2,8 @@ GNU Bison NEWS
* Noteworthy changes in release ?.? (????-??-??) [?]
+Changes in the display of counterexamples.
+
** Documentation
*** Examples
@@ -45,8 +47,8 @@ GNU Bison NEWS
conflict. For example:
Example exp '+' exp • '/' exp
- First derivation exp → [ exp → [ exp '+' exp • ] '/' exp ]
- Second derivation exp → [ exp '+' exp → [ exp • '/' exp ] ]
+ Shift derivation exp → [ exp '+' exp → [ exp • '/' exp ] ]
+ Reduce derivation exp → [ exp → [ exp '+' exp • ] '/' exp ]
When Bison is installed with text styling enabled, the example is actually
shown twice, with colors highlighting the ambiguity.
@@ -56,10 +58,10 @@ GNU Bison NEWS
bison cannot find an example that can be derived in two ways, it instead
generates two examples that are the same up until the dot:
- First example expr • ID $end
- First derivation $accept → [ s → [ a → [ expr • ] ID ] $end ]
- Second example expr • ID ',' ID $end
- Second derivation $accept → [ s → [ a → [ expr → [ expr • ID ',' ] ] ID
] $end ]
+ First example expr • ID ',' ID $end
+ Shift derivation $accept → [ s → [ a → [ expr → [ expr • ID ',' ] ] ID
] $end ]
+ Second example expr • ID $end
+ Reduce derivation $accept → [ s → [ a → [ expr • ] ID ] $end ]
In these cases, the parser usually doesn't have enough lookahead to
differentiate the two given examples.
diff --git a/doc/bison.texi b/doc/bison.texi
index 90adab69..d467497a 100644
--- a/doc/bison.texi
+++ b/doc/bison.texi
@@ -9936,10 +9936,10 @@ output is actually in color)}:
@example
Shift/reduce conflict on token "else":
@group
- Example @yellow{"if" expr "then"} @blue{"if" expr "then" stmt}
@red{•} @yellow{"else" stmt}
- First derivation @yellow{if_stmt @arrow{} [ "if" expr "then"} @green{stmt
@arrow{} [} @blue{if_stmt @arrow{} [ "if" expr "then" stmt} @red{•} @blue{]}
@green{]} @yellow{"else" stmt ]}
Example @yellow{"if" expr "then"} @blue{"if" expr "then" stmt}
@red{•} @blue{"else" stmt}
- Second derivation @yellow{if_stmt @arrow{} [ "if" expr "then"} @green{stmt
@arrow{} [} @blue{if_stmt @arrow{} [ "if" expr "then" stmt} @red{•}
@blue{"else" stmt ]} @green{]} @yellow{]}
+ Shift derivation @yellow{if_stmt @arrow{} [ "if" expr "then"} @green{stmt
@arrow{} [} @blue{if_stmt @arrow{} [ "if" expr "then" stmt} @red{•}
@blue{"else" stmt ]} @green{]} @yellow{]}
+ Example @yellow{"if" expr "then"} @blue{"if" expr "then" stmt}
@red{•} @yellow{"else" stmt}
+ Reduce derivation @yellow{if_stmt @arrow{} [ "if" expr "then"} @green{stmt
@arrow{} [} @blue{if_stmt @arrow{} [ "if" expr "then" stmt} @red{•} @blue{]}
@green{]} @yellow{"else" stmt ]}
@end group
@end example
@end ifhtml
@@ -9947,14 +9947,14 @@ Shift/reduce conflict on token "else":
@smallexample
Shift/reduce conflict on token "else":
@group
- Example
- @yellow{"if" expr "then"} @blue{"if" expr "then" stmt} @red{•}
@yellow{"else" stmt}
- First derivation
- @yellow{if_stmt @arrow{} [ "if" expr "then"} @green{stmt @arrow{} [}
@blue{if_stmt @arrow{} [ "if" expr "then" stmt} @red{•} @blue{]} @green{]}
@yellow{"else" stmt ]}
Example
@yellow{"if" expr "then"} @blue{"if" expr "then" stmt} @red{•}
@blue{"else" stmt}
- Second derivation
+ Shift derivation
@yellow{if_stmt @arrow{} [ "if" expr "then"} @green{stmt @arrow{} [}
@blue{if_stmt @arrow{} [ "if" expr "then" stmt} @red{•} @blue{"else" stmt ]}
@green{]} @yellow{]}
+ Example
+ @yellow{"if" expr "then"} @blue{"if" expr "then" stmt} @red{•}
@yellow{"else" stmt}
+ Reduce derivation
+ @yellow{if_stmt @arrow{} [ "if" expr "then"} @green{stmt @arrow{} [}
@blue{if_stmt @arrow{} [ "if" expr "then" stmt} @red{•} @blue{]} @green{]}
@yellow{"else" stmt ]}
@end group
@end smallexample
@end ifnothtml
@@ -9987,10 +9987,10 @@ $ @kbd{bison -Wcex sequence.y}
sequence.y: @dwarning{warning}: 1 shift/reduce conflict
[@dwarning{-Wconflicts-sr}]
sequence.y: @dwarning{warning}: 2 reduce/reduce conflicts
[@dwarning{-Wconflicts-rr}]
Shift/reduce conflict on token "word":
- Example @red{•} @yellow{"word"}
- First derivation @yellow{sequence @arrow{} [} @green{sequence @arrow{}
[} @red{•} @green{]} @yellow{"word" ]}
Example @red{•} @green{"word"}
- Second derivation @yellow{sequence @arrow{} [} @green{maybeword @arrow{}
[} @red{•} @green{"word" ]} @yellow{]}
+ Shift derivation @yellow{sequence @arrow{} [} @green{maybeword @arrow{}
[} @red{•} @green{"word" ]} @yellow{]}
+ Example @red{•} @yellow{"word"}
+ Reduce derivation @yellow{sequence @arrow{} [} @green{sequence @arrow{}
[} @red{•} @green{]} @yellow{"word" ]}
Reduce/reduce conflict on tokens $end, "word":
Example @red{•}
@@ -9999,10 +9999,10 @@ Reduce/reduce conflict on tokens $end, "word":
Second derivation @yellow{sequence @arrow{} [} @green{maybeword @arrow{}
[} @red{•} @green{]} @yellow{]}
Shift/reduce conflict on token "word":
- Example @red{•} @yellow{"word"}
- First derivation @yellow{sequence @arrow{} [} @green{sequence @arrow{}
[} @blue{maybeword @arrow{} [} @red{•} @blue{]} @green{]} @yellow{"word" ]}
Example @red{•} @green{"word"}
- Second derivation @yellow{sequence @arrow{} [} @green{maybeword @arrow{}
[} @red{•} @green{"word" ]} @yellow{]}
+ Shift derivation @yellow{sequence @arrow{} [} @green{maybeword @arrow{}
[} @red{•} @green{"word" ]} @yellow{]}
+ Example @red{•} @yellow{"word"}
+ Reduce derivation @yellow{sequence @arrow{} [} @green{sequence @arrow{}
[} @blue{maybeword @arrow{} [} @red{•} @blue{]} @green{]} @yellow{"word" ]}
sequence.y:8.3-45: @dwarning{warning}: rule useless in parser due to conflicts
[@dwarning{-Wother}]
8 | @dwarning{%empty @{ printf ("empty maybeword\n"); @}}
@@ -10033,10 +10033,10 @@ expr: %empty | expr ID ','
@smallexample
Shift/reduce conflict on token ID:
- First example @blue{expr} @red{•} @green{ID} @yellow{$end}
- First derivation @yellow{$accept @arrow{} [} @green{s @arrow{} [}
@blue{a @arrow{} [ expr} @red{•} @blue{]} @green{ID ]} @yellow{$end ]}
- Second example @purple{expr} @red{•} @purple{ID ','} @green{ID}
@yellow{$end}
- Second derivation @yellow{$accept @arrow{} [} @green{s @arrow{} [}
@blue{a @arrow{} [} @purple{expr @arrow{} [ expr} @red{•} @purple{ID ',' ]}
@blue{]} @green{ID ]} @yellow{$end ]}
+ First example @purple{expr} @red{•} @purple{ID ','} @green{ID}
@yellow{$end}
+ Shift derivation @yellow{$accept @arrow{} [} @green{s @arrow{} [}
@blue{a @arrow{} [} @purple{expr @arrow{} [ expr} @red{•} @purple{ID ',' ]}
@blue{]} @green{ID ]} @yellow{$end ]}
+ Second example @blue{expr} @red{•} @green{ID} @yellow{$end}
+ Reduce derivation @yellow{$accept @arrow{} [} @green{s @arrow{} [}
@blue{a @arrow{} [ expr} @red{•} @blue{]} @green{ID ]} @yellow{$end ]}
@end smallexample
This conflict is caused by the parser not having enough information to know
@@ -10432,10 +10432,10 @@ counterexamples within the report, augmented with the
corresponding items
Shift/reduce conflict on token '/':
1 exp: exp '+' exp •
4 exp: exp • '/' exp
- Example @green{exp '+' exp} @red{•} @yellow{'/' exp}
- First derivation @yellow{exp @arrow{} [} @green{exp @arrow{} [ exp '+'
exp} @red{•} @green{]} @yellow{'/' exp ]}
Example @yellow{exp '+'} @green{exp} @red{•} @green{'/' exp}
- Second derivation @yellow{exp @arrow{} [ exp '+'} @green{exp @arrow{} [
exp} @red{•} @green{'/' exp ]} @yellow{]}
+ Shift derivation @yellow{exp @arrow{} [ exp '+'} @green{exp @arrow{} [
exp} @red{•} @green{'/' exp ]} @yellow{]}
+ Example @green{exp '+' exp} @red{•} @yellow{'/' exp}
+ Reduce derivation @yellow{exp @arrow{} [} @green{exp @arrow{} [ exp '+'
exp} @red{•} @green{]} @yellow{'/' exp ]}
@end example
This shows two separate derivations in the grammar for the same @code{exp}:
diff --git a/src/counterexample.c b/src/counterexample.c
index 6735cd45..b7a4a57f 100644
--- a/src/counterexample.c
+++ b/src/counterexample.c
@@ -76,17 +76,29 @@ typedef struct
{
derivation *d1;
derivation *d2;
+ bool shift_reduce;
bool unifying;
bool timeout;
} counterexample;
static counterexample *
new_counterexample (derivation *d1, derivation *d2,
+ bool shift_reduce,
bool u, bool t)
{
counterexample *res = xmalloc (sizeof *res);
- res->d1 = d1;
- res->d2 = d2;
+ res->shift_reduce = shift_reduce;
+ if (shift_reduce)
+ {
+ // Display the shift first.
+ res->d1 = d2;
+ res->d2 = d1;
+ }
+ else
+ {
+ res->d1 = d1;
+ res->d2 = d2;
+ }
res->unifying = u;
res->timeout = t;
return res;
@@ -107,7 +119,7 @@ print_counterexample (counterexample *cex, FILE *out, const
char *prefix)
prefix, cex->unifying ? _("Example") : _("First example"));
derivation_print_leaves (cex->d1, out, prefix);
fprintf (out, " %s%-20s ",
- prefix, _("First derivation"));
+ prefix, cex->shift_reduce ? _("Shift derivation") : _("First
derivation"));
derivation_print (cex->d1, out, prefix);
// If we output to the terminal (via stderr) and we have color
@@ -120,7 +132,7 @@ print_counterexample (counterexample *cex, FILE *out, const
char *prefix)
derivation_print_leaves (cex->d2, out, prefix);
}
fprintf (out, " %s%-20s ",
- prefix, _("Second derivation"));
+ prefix, cex->shift_reduce ? _("Reduce derivation") : _("Second
derivation"));
derivation_print (cex->d2, out, prefix);
fputc ('\n', out);
@@ -506,7 +518,7 @@ example_from_path (bool shift_reduce,
: shortest_path_from_start (itm2, next_sym);
derivation *deriv2 = complete_diverging_example (next_sym, path_2, NULL);
gl_list_free (path_2);
- return new_counterexample (deriv1, deriv2, false, true);
+ return new_counterexample (deriv1, deriv2, shift_reduce, false, true);
}
/*
@@ -619,7 +631,8 @@ ss_set_parse_state (search_state *ss, int idx, parse_state
*ps)
*/
static counterexample *
complete_diverging_examples (search_state *ss,
- symbol_number next_sym)
+ symbol_number next_sym,
+ bool shift_reduce)
{
derivation *new_derivs[2];
for (int i = 0; i < 2; ++i)
@@ -630,7 +643,8 @@ complete_diverging_examples (search_state *ss,
new_derivs[i] = complete_diverging_example (next_sym, sitems, derivs);
gl_list_free (sitems);
}
- return new_counterexample (new_derivs[0], new_derivs[1], false, true);
+ return new_counterexample (new_derivs[0], new_derivs[1],
+ shift_reduce, false, true);
}
/*
@@ -1111,7 +1125,7 @@ unifying_example (state_item_number itm1,
{
// Once we have two derivations for the same symbol,
// we've found a unifying counterexample.
- cex = new_counterexample (d1, d2, true, false);
+ cex = new_counterexample (d1, d2, shift_reduce, true,
false);
derivation_retain (d1);
derivation_retain (d2);
goto cex_search_end;
@@ -1149,7 +1163,7 @@ cex_search_end:;
// If a search state from Stage 3 is available, use it
// to construct a more compact nonunifying counterexample.
if (stage3result)
- cex = complete_diverging_examples (stage3result, next_sym);
+ cex = complete_diverging_examples (stage3result, next_sym,
shift_reduce);
// Otherwise, construct a nonunifying counterexample that
// begins from the start state using the shortest
// lookahead-sensitive path to the reduce item.
@@ -1226,6 +1240,8 @@ counterexample_report (state_item_number itm1,
state_item_number itm2,
free_counterexample (cex);
}
+
+// ITM1 denotes a shift, ITM2 a reduce.
static void
counterexample_report_shift_reduce (state_item_number itm1, state_item_number
itm2,
symbol_number next_sym,
diff --git a/tests/conflicts.at b/tests/conflicts.at
index 22456f30..46daf78b 100644
--- a/tests/conflicts.at
+++ b/tests/conflicts.at
@@ -865,8 +865,8 @@ State 5
1 exp: exp OP exp .
1 exp: exp . OP exp
Example exp OP exp . OP exp
- First derivation exp -> [ exp -> [ exp OP exp . ] OP exp ]
- Second derivation exp -> [ exp OP exp -> [ exp . OP exp ] ]
+ Shift derivation exp -> [ exp OP exp -> [ exp . OP exp ] ]
+ Reduce derivation exp -> [ exp -> [ exp OP exp . ] OP exp ]
]])
diff --git a/tests/counterexample.at b/tests/counterexample.at
index 17123106..a37d46b4 100644
--- a/tests/counterexample.at
+++ b/tests/counterexample.at
@@ -47,8 +47,8 @@ AT_BISON_CHECK_CEX([input.y], [], [],
[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
Shift/reduce conflict on token B:
Example A . B C
- First derivation s -> [ a -> [ A . ] x -> [ B C ] ]
- Second derivation s -> [ y -> [ A . B ] c -> [ C ] ]
+ Shift derivation s -> [ y -> [ A . B ] c -> [ C ] ]
+ Reduce derivation s -> [ a -> [ A . ] x -> [ B C ] ]
input.y:4.4: warning: rule useless in parser due to conflicts [-Wother]
]])
@@ -76,13 +76,13 @@ AT_BISON_CHECK_CEX([input.y], [], [],
[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
Shift/reduce conflict on token B:
Example A . B C
- First derivation s -> [ a -> [ A . ] bc -> [ B C ] ]
- Second derivation s -> [ ac -> [ A ac -> [ b -> [ . B ] ] C ] ]
+ Shift derivation s -> [ ac -> [ A ac -> [ b -> [ . B ] ] C ] ]
+ Reduce derivation s -> [ a -> [ A . ] bc -> [ B C ] ]
Shift/reduce conflict on token B:
Example A A . B B C C
- First derivation s -> [ a -> [ A a -> [ A . ] ] bc -> [ B bc -> [ B C ]
C ] ]
- Second derivation s -> [ ac -> [ A ac -> [ A ac -> [ b -> [ . b -> [ B B
] ] ] C ] C ] ]
+ Shift derivation s -> [ ac -> [ A ac -> [ A ac -> [ b -> [ . b -> [ B B
] ] ] C ] C ] ]
+ Reduce derivation s -> [ a -> [ A a -> [ A . ] ] bc -> [ B bc -> [ B C ]
C ] ]
input.y:6.4: warning: rule useless in parser due to conflicts [-Wother]
]])
@@ -111,14 +111,14 @@ AT_BISON_CHECK_CEX([input.y], [], [],
[[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
Shift/reduce conflict on token B:
Example A . B
- First derivation s -> [ ax -> [ A x -> [ . ] ] by -> [ B y -> [ ] ] ]
- Second derivation s -> [ A xby -> [ . B ] ]
+ Shift derivation s -> [ A xby -> [ . B ] ]
+ Reduce derivation s -> [ ax -> [ A x -> [ . ] ] by -> [ B y -> [ ] ] ]
Shift/reduce conflict on token B:
- First example A X . B y $end
- First derivation $accept -> [ s -> [ ax -> [ A x -> [ X x -> [ . ] ] ]
by -> [ B y ] ] $end ]
- Second example A X . B Y $end
- Second derivation $accept -> [ s -> [ A xby -> [ X xby -> [ . B ] Y ] ]
$end ]
+ First example A X . B Y $end
+ Shift derivation $accept -> [ s -> [ A xby -> [ X xby -> [ . B ] Y ] ]
$end ]
+ Second example A X . B y $end
+ Reduce derivation $accept -> [ s -> [ ax -> [ A x -> [ X x -> [ . ] ] ]
by -> [ B y ] ] $end ]
input.y:5.4-9: warning: rule useless in parser due to conflicts [-Wother]
]])
@@ -146,10 +146,10 @@ bc: B C;
AT_BISON_CHECK_CEX([input.y], [], [],
[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
Shift/reduce conflict on token C:
- First example B . C D $end
- First derivation $accept -> [ g -> [ x -> [ b -> [ B . ] cd -> [ C D ] ]
] $end ]
- Second example B . C $end
- Second derivation $accept -> [ g -> [ x -> [ bc -> [ B . C ] ] ] $end ]
+ First example B . C $end
+ Shift derivation $accept -> [ g -> [ x -> [ bc -> [ B . C ] ] ] $end ]
+ Second example B . C D $end
+ Reduce derivation $accept -> [ g -> [ x -> [ b -> [ B . ] cd -> [ C D ] ]
] $end ]
input.y:6.4: warning: rule useless in parser due to conflicts [-Wother]
]])
@@ -175,10 +175,10 @@ y: A A B;
AT_BISON_CHECK_CEX([input.y], [], [],
[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
Shift/reduce conflict on token A:
- First example A . A $end
- First derivation $accept -> [ s -> [ s -> [ t -> [ x -> [ A . ] ] ] t ->
[ x -> [ A ] ] ] $end ]
- Second example A . A B $end
- Second derivation $accept -> [ s -> [ t -> [ y -> [ A . A B ] ] ] $end ]
+ First example A . A B $end
+ Shift derivation $accept -> [ s -> [ t -> [ y -> [ A . A B ] ] ] $end ]
+ Second example A . A $end
+ Reduce derivation $accept -> [ s -> [ s -> [ t -> [ x -> [ A . ] ] ] t ->
[ x -> [ A ] ] ] $end ]
]])
@@ -209,14 +209,14 @@ AT_BISON_CHECK_CEX([input.y], [], [],
[[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
Shift/reduce conflict on token A:
Example b . A X X Y
- First derivation a -> [ r -> [ b . ] t -> [ A x -> [ X ] xy -> [ X Y ] ]
]
- Second derivation a -> [ s -> [ b . xx -> [ A X X ] y -> [ Y ] ] ]
+ Shift derivation a -> [ s -> [ b . xx -> [ A X X ] y -> [ Y ] ] ]
+ Reduce derivation a -> [ r -> [ b . ] t -> [ A x -> [ X ] xy -> [ X Y ] ]
]
Shift/reduce conflict on token X:
- First example X . X xy
- First derivation a -> [ x -> [ X . ] t -> [ X xy ] ]
- Second example A X . X
- Second derivation a -> [ t -> [ A xx -> [ X . X ] ] ]
+ First example A X . X
+ Shift derivation a -> [ t -> [ A xx -> [ X . X ] ] ]
+ Second example X . X xy
+ Reduce derivation a -> [ x -> [ X . ] t -> [ X xy ] ]
input.y:4.4: warning: rule useless in parser due to conflicts [-Wother]
input.y:8.4: warning: rule useless in parser due to conflicts [-Wother]
@@ -297,10 +297,10 @@ AT_BISON_CHECK_CEX([input.y], [], [],
[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
Shift/reduce conflict on token J:
time limit exceeded: XXX
- First example H i . J $end
- First derivation $accept -> [ s -> [ a -> [ H i . ] J ] $end ]
- Second example H i . J K $end
- Second derivation $accept -> [ a -> [ H i -> [ i . J K ] ] $end ]
+ First example H i . J K $end
+ Shift derivation $accept -> [ a -> [ H i -> [ i . J K ] ] $end ]
+ Second example H i . J $end
+ Reduce derivation $accept -> [ s -> [ a -> [ H i . ] J ] $end ]
input.y:4.4-6: warning: rule useless in parser due to conflicts [-Wother]
]])
@@ -330,13 +330,13 @@ AT_BISON_CHECK_CEX([input.y], [], [],
[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
Shift/reduce conflict on token B:
Example N A . B C
- First derivation s -> [ n -> [ N a -> [ A . ] B ] C ]
- Second derivation s -> [ n -> [ N b -> [ A . B C ] ] ]
+ Shift derivation s -> [ n -> [ N b -> [ A . B C ] ] ]
+ Reduce derivation s -> [ n -> [ N a -> [ A . ] B ] C ]
Shift/reduce conflict on token B:
Example N N A . B D C
- First derivation s -> [ n -> [ N n -> [ N a -> [ A . ] B ] D ] C ]
- Second derivation s -> [ n -> [ N n -> [ N b -> [ A . B D ] ] C ] ]
+ Shift derivation s -> [ n -> [ N n -> [ N b -> [ A . B D ] ] C ] ]
+ Reduce derivation s -> [ n -> [ N n -> [ N a -> [ A . ] B ] D ] C ]
input.y:5.4: warning: rule useless in parser due to conflicts [-Wother]
]])
@@ -420,10 +420,10 @@ time limit exceeded: XXX
Shift/reduce conflict on token A:
time limit exceeded: XXX
- First example b c . c A A $end
- First derivation $accept -> [ a -> [ b d -> [ a -> [ c d -> [ a -> [ b
-> [ . ] d -> [ c A A ] ] ] ] ] ] $end ]
- Second example b c . A
- Second derivation a -> [ b d -> [ c . A ] ]
+ First example b c . A
+ Shift derivation a -> [ b d -> [ c . A ] ]
+ Second example b c . c A A $end
+ Reduce derivation $accept -> [ a -> [ b d -> [ a -> [ c d -> [ a -> [ b
-> [ . ] d -> [ c A A ] ] ] ] ] ] $end ]
Reduce/reduce conflict on token A:
First example b c . c A A $end
@@ -432,10 +432,10 @@ Reduce/reduce conflict on token A:
Second derivation $accept -> [ a -> [ b d -> [ a -> [ c d -> [ c -> [ . ]
A ] ] ] ] $end ]
Shift/reduce conflict on token A:
- First example b c . A $end
- First derivation $accept -> [ a -> [ b d -> [ a -> [ c d -> [ c -> [ . ]
A ] ] ] ] $end ]
- Second example b c . A
- Second derivation a -> [ b d -> [ c . A ] ]
+ First example b c . A
+ Shift derivation a -> [ b d -> [ c . A ] ]
+ Second example b c . A $end
+ Reduce derivation $accept -> [ a -> [ b d -> [ a -> [ c d -> [ c -> [ . ]
A ] ] ] ] $end ]
Reduce/reduce conflict on token $end:
Example b d .
@@ -475,8 +475,8 @@ AT_BISON_CHECK_CEX([input.y], [], [],
[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
Shift/reduce conflict on token J:
Example H i J . J J
- First derivation s -> [ a -> [ H i -> [ i J . ] J J ] ]
- Second derivation s -> [ a -> [ H i J . J ] J ]
+ Shift derivation s -> [ a -> [ H i J . J ] J ]
+ Reduce derivation s -> [ a -> [ H i -> [ i J . ] J J ] ]
input.y:5.13-15: warning: rule useless in parser due to conflicts [-Wother]
]])
@@ -507,8 +507,8 @@ AT_BISON_CHECK_CEX([input.y], [], [],
[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
Shift/reduce conflict on token D:
Example A a . D
- First derivation s -> [ A a a -> [ b -> [ c -> [ . ] ] ] d -> [ D ] ]
- Second derivation s -> [ A a d -> [ . D ] ]
+ Shift derivation s -> [ A a d -> [ . D ] ]
+ Reduce derivation s -> [ A a a -> [ b -> [ c -> [ . ] ] ] d -> [ D ] ]
]])
@@ -536,10 +536,10 @@ d: D;
AT_BISON_CHECK_CEX([input.y], [], [],
[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
Shift/reduce conflict on token D:
- First example A a . D E $end
- First derivation $accept -> [ s -> [ A a a -> [ b -> [ c -> [ . ] ] ] d
-> [ D ] E ] $end ]
- Second example A a . D $end
- Second derivation $accept -> [ s -> [ A a d -> [ . D ] ] $end ]
+ First example A a . D $end
+ Shift derivation $accept -> [ s -> [ A a d -> [ . D ] ] $end ]
+ Second example A a . D E $end
+ Reduce derivation $accept -> [ s -> [ A a a -> [ b -> [ c -> [ . ] ] ] d
-> [ D ] E ] $end ]
]])
diff --git a/tests/report.at b/tests/report.at
index e9695cf3..e3497037 100644
--- a/tests/report.at
+++ b/tests/report.at
@@ -1539,8 +1539,8 @@ AT_CHECK([LC_ALL="$locale" bison -fno-caret -o input.cc
-rall -Wcex --graph=inpu
input.y: warning: 3 reduce/reduce conflicts [-Wconflicts-rr]
Shift/reduce conflict on token "⊕":
Example exp "+" exp • "⊕" exp
- First derivation exp → [ exp → [ exp "+" exp • ] "⊕" exp ]
- Second derivation exp → [ exp "+" exp → [ exp • "⊕" exp ] ]
+ Shift derivation exp → [ exp "+" exp → [ exp • "⊕" exp ] ]
+ Reduce derivation exp → [ exp → [ exp "+" exp • ] "⊕" exp ]
Reduce/reduce conflict on tokens $end, "+", "⊕":
Example exp "+" exp •
@@ -1549,23 +1549,23 @@ Reduce/reduce conflict on tokens $end, "+", "⊕":
Shift/reduce conflict on token "⊕":
Example exp "+" exp • "⊕" exp
- First derivation exp → [ exp → [ exp "+" exp • ] "⊕" exp ]
- Second derivation exp → [ exp "+" exp → [ exp • "⊕" exp ] ]
+ Shift derivation exp → [ exp "+" exp → [ exp • "⊕" exp ] ]
+ Reduce derivation exp → [ exp → [ exp "+" exp • ] "⊕" exp ]
Shift/reduce conflict on token "⊕":
Example exp "⊕" exp • "⊕" exp
- First derivation exp → [ exp → [ exp "⊕" exp • ] "⊕" exp ]
- Second derivation exp → [ exp "⊕" exp → [ exp • "⊕" exp ] ]
+ Shift derivation exp → [ exp "⊕" exp → [ exp • "⊕" exp ] ]
+ Reduce derivation exp → [ exp → [ exp "⊕" exp • ] "⊕" exp ]
Shift/reduce conflict on token "+":
Example exp "⊕" exp • "+" exp
- First derivation exp → [ exp → [ exp "⊕" exp • ] "+" exp ]
- Second derivation exp → [ exp "⊕" exp → [ exp • "+" exp ] ]
+ Shift derivation exp → [ exp "⊕" exp → [ exp • "+" exp ] ]
+ Reduce derivation exp → [ exp → [ exp "⊕" exp • ] "+" exp ]
Shift/reduce conflict on token "+":
Example exp "⊕" exp • "+" exp
- First derivation exp → [ exp → [ exp "⊕" exp • ] "+" exp ]
- Second derivation exp → [ exp "⊕" exp → [ exp • "+" exp ] ]
+ Shift derivation exp → [ exp "⊕" exp → [ exp • "+" exp ] ]
+ Reduce derivation exp → [ exp → [ exp "⊕" exp • ] "+" exp ]
input.y:6.3-13: warning: rule useless in parser due to conflicts [-Wother]
]])
@@ -1714,8 +1714,8 @@ State 7
2 exp: exp "+" exp •
1 exp: exp • "⊕" exp
Example exp "+" exp • "⊕" exp
- First derivation exp → [ exp → [ exp "+" exp • ] "⊕" exp ]
- Second derivation exp → [ exp "+" exp → [ exp • "⊕" exp ] ]
+ Shift derivation exp → [ exp "+" exp → [ exp • "⊕" exp ] ]
+ Reduce derivation exp → [ exp → [ exp "+" exp • ] "⊕" exp ]
Reduce/reduce conflict on tokens $end, "+", "⊕":
2 exp: exp "+" exp •
@@ -1728,8 +1728,8 @@ State 7
3 exp: exp "+" exp •
1 exp: exp • "⊕" exp
Example exp "+" exp • "⊕" exp
- First derivation exp → [ exp → [ exp "+" exp • ] "⊕" exp ]
- Second derivation exp → [ exp "+" exp → [ exp • "⊕" exp ] ]
+ Shift derivation exp → [ exp "+" exp → [ exp • "⊕" exp ] ]
+ Reduce derivation exp → [ exp → [ exp "+" exp • ] "⊕" exp ]
@@ -1751,22 +1751,22 @@ State 8
1 exp: exp "⊕" exp •
1 exp: exp • "⊕" exp
Example exp "⊕" exp • "⊕" exp
- First derivation exp → [ exp → [ exp "⊕" exp • ] "⊕" exp ]
- Second derivation exp → [ exp "⊕" exp → [ exp • "⊕" exp ] ]
+ Shift derivation exp → [ exp "⊕" exp → [ exp • "⊕" exp ] ]
+ Reduce derivation exp → [ exp → [ exp "⊕" exp • ] "⊕" exp ]
Shift/reduce conflict on token "+":
1 exp: exp "⊕" exp •
2 exp: exp • "+" exp
Example exp "⊕" exp • "+" exp
- First derivation exp → [ exp → [ exp "⊕" exp • ] "+" exp ]
- Second derivation exp → [ exp "⊕" exp → [ exp • "+" exp ] ]
+ Shift derivation exp → [ exp "⊕" exp → [ exp • "+" exp ] ]
+ Reduce derivation exp → [ exp → [ exp "⊕" exp • ] "+" exp ]
Shift/reduce conflict on token "+":
1 exp: exp "⊕" exp •
3 exp: exp • "+" exp
Example exp "⊕" exp • "+" exp
- First derivation exp → [ exp → [ exp "⊕" exp • ] "+" exp ]
- Second derivation exp → [ exp "⊕" exp → [ exp • "+" exp ] ]
+ Shift derivation exp → [ exp "⊕" exp → [ exp • "+" exp ] ]
+ Reduce derivation exp → [ exp → [ exp "⊕" exp • ] "+" exp ]
]])
--
2.27.0
- [PATCH 0/9] cex: shift derivation vs reduce derivation, Akim Demaille, 2020/07/12
- [PATCH 1/9] tests: beware of version numbers from git describe, Akim Demaille, 2020/07/12
- [PATCH 2/9] cex: minor style changes, Akim Demaille, 2020/07/12
- [PATCH 3/9] cex: use better type names, Akim Demaille, 2020/07/12
- [PATCH 4/9] cex: minor renaming, Akim Demaille, 2020/07/12
- [PATCH 5/9] cex: more consistent memory allocation/copy, Akim Demaille, 2020/07/12
- [PATCH 6/9] cex: use state_item_number consistently, Akim Demaille, 2020/07/12
- [PATCH 7/9] cex: factor memory allocation, Akim Demaille, 2020/07/12
- [PATCH 8/9] style: s/lookahead_tokens/lookaheads/g, Akim Demaille, 2020/07/12
- [PATCH 9/9] cex: display shifts before reductions,
Akim Demaille <=