[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
cex: always show ε/%empty in counterexamples
|
From: |
Akim Demaille |
|
Subject: |
cex: always show ε/%empty in counterexamples |
|
Date: |
Wed, 2 Sep 2020 07:34:19 +0200 |
This is for master, not maint.
commit 325ec7d32414d3b732d22387bb54da6918ec2ffc
Author: Akim Demaille <akim.demaille@gmail.com>
Date: Mon Aug 31 07:22:17 2020 +0200
cex: always show ε/%empty in counterexamples
On a case such as
%%
exp
: empty "a"
| "a" empty
empty
: %empty
we used to display
warning: shift/reduce conflict on token "a" [-Wcounterexamples]
Example: • "a"
Shift derivation
exp
↳ 2: • "a" empty
↳ 2: ε
Example: • "a"
Reduce derivation
exp
↳ 1: empty "a"
↳ 3: •
where the shift derivation shows an item "2: empty → ε", with an
explicit "ε", but the reduce derivation shows "3: empty → •", without
"ε".
For consistency, let's always show ε/%empty in rules with an empty
rhs:
Reduce derivation
exp
↳ 1: empty "a"
↳ 3: ε •
* src/derivation.c (derivation_width, derivation_print_tree_impl):
Always show ε/%empty in counterexamples.
* tests/diagnostics.at: Check that case.
* tests/conflicts.at, tests/counterexample.at: Adjust.
diff --git a/NEWS b/NEWS
index c14d17f2..5f869f12 100644
--- a/NEWS
+++ b/NEWS
@@ -19,17 +19,18 @@ GNU Bison NEWS
*** Counterexamples
- Counterexamples now show the rule numbers:
+ Counterexamples now show the rule numbers, and always show ε for rules
+ with an empty right-hand side. For instance
exp
- ↳ 1: "if" exp "then" exp
- ↳ 2: "if" exp "then" exp • "else" exp
+ ↳ 1: e1 e2 "a"
+ ↳ 3: ε • ↳ 1: ε
instead of
exp
- ↳ "if" exp "then" exp
- ↳ "if" exp "then" exp • "else" exp
+ ↳ e1 e2 "a"
+ ↳ • ↳ ε
* Noteworthy changes in release 3.7.1 (2020-08-02) [stable]
diff --git a/doc/bison.texi b/doc/bison.texi
index e36f8a38..f9aaf343 100644
--- a/doc/bison.texi
+++ b/doc/bison.texi
@@ -10605,8 +10605,8 @@ This shows two separate derivations in the grammar for
the same @code{exp}:
given example. Here, the first derivation completes a reduction when seeing
@samp{/}, causing @samp{e1 + e2} to be grouped as an @code{exp}. The second
derivation shifts on @samp{/}, resulting in @samp{e2 / e3} being grouped as
-an @code{exp}. Therefore, it is easy to see that adding @code{%precedence}
-directives would fix this conflict.
+an @code{exp}. Therefore, it is easy to see that adding
+precedence/associativity directives would fix this conflict.
The remaining states are similar:
diff --git a/src/derivation.c b/src/derivation.c
index 382dc458..433f504e 100644
--- a/src/derivation.c
+++ b/src/derivation.c
@@ -245,6 +245,13 @@ derivation_width (const derivation *deriv)
children_width += empty_width;
else
{
+ if (gl_list_size (deriv->children) == 1
+ && gl_list_get_first (deriv->children) == &d_dot)
+ {
+ children_width += empty_width;
+ children_width += derivation_separator_width;
+ }
+
derivation *child;
for (gl_list_iterator_t it = gl_list_iterator (deriv->children);
derivation_list_next (&it, &child);
@@ -310,6 +317,13 @@ derivation_print_tree_impl (const derivation *deriv, FILE
*out,
res += fputs_if (depth == 1, out, padding, empty);
else
{
+ if (gl_list_size (deriv->children) == 1
+ && gl_list_get_first (deriv->children) == &d_dot)
+ {
+ res += fputs_if (depth == 1, out, padding, empty);
+ res += fputs_if (depth == 1, out, padding,
derivation_separator);
+ }
+
bool first = true;
derivation *child;
for (gl_list_iterator_t it = gl_list_iterator (deriv->children);
diff --git a/tests/conflicts.at b/tests/conflicts.at
index d68f03aa..de0a993e 100644
--- a/tests/conflicts.at
+++ b/tests/conflicts.at
@@ -1776,7 +1776,7 @@ State 4
Reduce derivation
start
`-> 1: resolved_conflict reported_conflicts 'a'
- `-> 10: .
+ `-> 10: %empty .
shift/reduce conflict on token 'a':
10 reported_conflicts: . %empty
@@ -1790,7 +1790,7 @@ State 4
Reduce derivation
start
`-> 1: resolved_conflict reported_conflicts 'a'
- `-> 10: .
+ `-> 10: %empty .
@@ -1999,12 +1999,12 @@ AT_CHECK([[cat input.output | sed -n '/^State
0$/,/^State 1$/p']], 0,
Example: . 'c'
First reduce derivation
start
- `-> 7: empty_c2 'c'
- `-> 12: .
+ `-> 7: empty_c2 'c'
+ `-> 12: %empty .
Second reduce derivation
start
- `-> 8: empty_c3 'c'
- `-> 13: .
+ `-> 8: empty_c3 'c'
+ `-> 13: %empty .
diff --git a/tests/counterexample.at b/tests/counterexample.at
index bd9c1e96..fcc239bb 100644
--- a/tests/counterexample.at
+++ b/tests/counterexample.at
@@ -164,9 +164,9 @@ input.y: warning: shift/reduce conflict on token B
[-Wcounterexamples]
`-> 9: . B
Reduce derivation
s
- `-> 1: ax by
- `-> 3: A x `-> 6: B y
- `-> 4: . `-> 6: %empty
+ `-> 1: ax by
+ `-> 3: A x `-> 6: B y
+ `-> 4: %empty . `-> 6: %empty
input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
First example: A X . B Y $end
Shift derivation
@@ -178,11 +178,11 @@ input.y: warning: shift/reduce conflict on token B
[-Wcounterexamples]
Second example: A X . B y $end
Reduce derivation
$accept
- `-> 0: s $end
- `-> 1: ax by
- `-> 3: A x `-> 6: B y
+ `-> 0: s $end
+ `-> 1: ax by
+ `-> 3: A x `-> 6: B y
`-> 5: X x
- `-> 4: .
+ `-> 4: %empty .
input.y:5.4-9: warning: rule useless in parser due to conflicts [-Wother]
]],
[[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
@@ -571,10 +571,10 @@ input.y: warning: reduce/reduce conflict on tokens b, c
[-Wcounterexamples]
Second reduce derivation
S
`-> 1: B C
- `-> 7: A c A
- `-> 3: B `-> 7: %empty
- `-> 6: A b A
- `-> 5: . `-> 6: %empty
+ `-> 7: A c A
+ `-> 3: B `-> 7:
%empty
+ `-> 6: A b A
+ `-> 5: %empty . `-> 6: %empty
input.y: warning: reduce/reduce conflict on tokens b, c [-Wcounterexamples]
Example: C . c b
First reduce derivation
@@ -585,10 +585,10 @@ input.y: warning: reduce/reduce conflict on tokens b, c
[-Wcounterexamples]
Second reduce derivation
S
`-> 2: C B
- `-> 6: A b A
- `-> 4: C `-> 6: %empty
- `-> 7: A c A
- `-> 5: . `-> 7: %empty
+ `-> 6: A b A
+ `-> 4: C `-> 6:
%empty
+ `-> 7: A c A
+ `-> 5: %empty . `-> 7: %empty
]],
[[input.y: warning: 4 reduce/reduce conflicts [-Wconflicts-rr]
input.y: warning: reduce/reduce conflict on tokens b, c [-Wcounterexamples]
@@ -625,49 +625,49 @@ input.y: warning: reduce/reduce conflict on token A
[-Wcounterexamples]
First example: . c A A $end
First reduce derivation
$accept
- `-> 0: a $end
- `-> 1: b d
- `-> 3: . `-> 6: c A A
+ `-> 0: a $end
+ `-> 1: b d
+ `-> 3: %empty . `-> 6: c A A
Second example: . c A A $end
Second reduce derivation
$accept
- `-> 0: a $end
- `-> 2: c d
- `-> 4: . `-> 6: c A A
+ `-> 0: a $end
+ `-> 2: c d
+ `-> 4: %empty . `-> 6: c A A
input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples]
time limit exceeded: XXX
First example: b . c A A $end
First reduce derivation
$accept
- `-> 0: a $end
+ `-> 0: a $end
`-> 1: b d
`-> 5: a
- `-> 1: b d
- `-> 3: . `-> 6: c A A
+ `-> 1: b d
+ `-> 3: %empty . `-> 6: c A A
Second example: b . A $end
Second reduce derivation
$accept
- `-> 0: a $end
+ `-> 0: a $end
`-> 1: b d
- `-> 6: c A
- `-> 4: .
+ `-> 6: c A
+ `-> 4: %empty .
input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples]
time limit exceeded: XXX
First example: c . c A A $end
First reduce derivation
$accept
- `-> 0: a $end
+ `-> 0: a $end
`-> 2: c d
`-> 5: a
- `-> 1: b d
- `-> 3: . `-> 6: c A A
+ `-> 1: b d
+ `-> 3: %empty . `-> 6: c A A
Second example: c . A $end
Second reduce derivation
$accept
- `-> 0: a $end
+ `-> 0: a $end
`-> 2: c d
- `-> 6: c A
- `-> 4: .
+ `-> 6: c A
+ `-> 4: %empty .
input.y: warning: shift/reduce conflict on token A [-Wcounterexamples]
time limit exceeded: XXX
First example: b c . A
@@ -678,33 +678,33 @@ time limit exceeded: XXX
Second example: b c . c A A $end
Reduce derivation
$accept
- `-> 0: a $end
+ `-> 0: a
$end
`-> 1: b d
`-> 5: a
`-> 2: c d
`-> 5: a
- `-> 1: b d
- `-> 3: . `-> 6: c A A
+ `-> 1: b d
+ `-> 3: %empty . `-> 6: c A A
input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples]
First example: b c . c A A $end
First reduce derivation
$accept
- `-> 0: a $end
+ `-> 0: a
$end
`-> 1: b d
`-> 5: a
`-> 2: c d
`-> 5: a
- `-> 1: b d
- `-> 3: . `-> 6: c A A
+ `-> 1: b d
+ `-> 3: %empty . `-> 6: c A A
Second example: b c . A $end
Second reduce derivation
$accept
- `-> 0: a $end
+ `-> 0: a $end
`-> 1: b d
`-> 5: a
`-> 2: c d
- `-> 6: c A
- `-> 4: .
+ `-> 6: c A
+ `-> 4: %empty .
input.y: warning: shift/reduce conflict on token A [-Wcounterexamples]
First example: b c . A
Shift derivation
@@ -714,12 +714,12 @@ input.y: warning: shift/reduce conflict on token A
[-Wcounterexamples]
Second example: b c . A $end
Reduce derivation
$accept
- `-> 0: a $end
+ `-> 0: a $end
`-> 1: b d
`-> 5: a
`-> 2: c d
- `-> 6: c A
- `-> 4: .
+ `-> 6: c A
+ `-> 4: %empty .
input.y: warning: reduce/reduce conflict on token $end [-Wcounterexamples]
Example: b d .
First reduce derivation
@@ -861,10 +861,10 @@ input.y: warning: shift/reduce conflict on token D
[-Wcounterexamples]
`-> 6: . D
Reduce derivation
s
- `-> 2: A a a d
- `-> 3: b `-> 6: D
+ `-> 2: A a a d
+ `-> 3: b `-> 6: D
`-> 4: c
- `-> 5: .
+ `-> 5: %empty .
]],
[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
input.y: warning: shift/reduce conflict on token D [-Wcounterexamples]
@@ -905,11 +905,11 @@ input.y: warning: shift/reduce conflict on token D
[-Wcounterexamples]
Second example: A a . D E $end
Reduce derivation
$accept
- `-> 0: s $end
- `-> 2: A a a d E
- `-> 3: b `-> 6: D
+ `-> 0: s $end
+ `-> 2: A a a d E
+ `-> 3: b `-> 6: D
`-> 4: c
- `-> 5: .
+ `-> 5: %empty .
]],
[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
input.y: warning: shift/reduce conflict on token D [-Wcounterexamples]
diff --git a/tests/diagnostics.at b/tests/diagnostics.at
index faf4c9a7..42b6d3a8 100644
--- a/tests/diagnostics.at
+++ b/tests/diagnostics.at
@@ -532,9 +532,58 @@ exp
| "if" exp "then" exp "else" exp
| exp "+" exp
| "num"
+| empty "a"
+| "a" empty
+
+empty
+: %empty
]],
[1],
-[[input.y: <error>error:</error> shift/reduce conflicts: 4 found, 0 expected
+[[input.y: <error>error:</error> shift/reduce conflicts: 9 found, 0 expected
+input.y: <warning>warning:</warning> shift/reduce conflict on token "a"
[<warning>-Wcounterexamples</warning>]
+ Example: <cex-0><cex-dot>•</cex-dot>
<cex-leaf>"a"</cex-leaf><cex-1></cex-1></cex-0>
+ Shift derivation
+ <cex-0><cex-step>exp</cex-step></cex-0>
+ <cex-0><cex-step>↳ 6: <cex-dot>•</cex-dot><cex-leaf>
"a"</cex-leaf><cex-1><cex-step> empty</cex-step></cex-1></cex-step></cex-0>
+ <cex-1><cex-step> ↳ 6: ε</cex-step></cex-1>
+ Example: <cex-0><cex-1><cex-dot>•</cex-dot></cex-1>
<cex-leaf>"a"</cex-leaf></cex-0>
+ Reduce derivation
+ <cex-0><cex-step>exp</cex-step></cex-0>
+ <cex-0><cex-step>↳ 5: <cex-1><cex-step>empty</cex-step></cex-1><cex-leaf>
"a"</cex-leaf></cex-step></cex-0>
+ <cex-1><cex-step> ↳ 7: ε<cex-dot> •</cex-dot></cex-step></cex-1>
+input.y: <warning>warning:</warning> shift/reduce conflict on token "a"
[<warning>-Wcounterexamples</warning>]
+ Example: <cex-0><cex-dot>•</cex-dot>
<cex-leaf>"a"</cex-leaf><cex-1></cex-1></cex-0>
+ Shift derivation
+ <cex-0><cex-step>exp</cex-step></cex-0>
+ <cex-0><cex-step>↳ 6: <cex-dot>•</cex-dot><cex-leaf>
"a"</cex-leaf><cex-1><cex-step> empty</cex-step></cex-1></cex-step></cex-0>
+ <cex-1><cex-step> ↳ 6: ε</cex-step></cex-1>
+ Example: <cex-0><cex-1><cex-dot>•</cex-dot></cex-1>
<cex-leaf>"a"</cex-leaf></cex-0>
+ Reduce derivation
+ <cex-0><cex-step>exp</cex-step></cex-0>
+ <cex-0><cex-step>↳ 5: <cex-1><cex-step>empty</cex-step></cex-1><cex-leaf>
"a"</cex-leaf></cex-step></cex-0>
+ <cex-1><cex-step> ↳ 7: ε<cex-dot> •</cex-dot></cex-step></cex-1>
+input.y: <warning>warning:</warning> shift/reduce conflict on token "a"
[<warning>-Wcounterexamples</warning>]
+ Example: <cex-0><cex-dot>•</cex-dot>
<cex-leaf>"a"</cex-leaf><cex-1></cex-1></cex-0>
+ Shift derivation
+ <cex-0><cex-step>exp</cex-step></cex-0>
+ <cex-0><cex-step>↳ 6: <cex-dot>•</cex-dot><cex-leaf>
"a"</cex-leaf><cex-1><cex-step> empty</cex-step></cex-1></cex-step></cex-0>
+ <cex-1><cex-step> ↳ 6: ε</cex-step></cex-1>
+ Example: <cex-0><cex-1><cex-dot>•</cex-dot></cex-1>
<cex-leaf>"a"</cex-leaf></cex-0>
+ Reduce derivation
+ <cex-0><cex-step>exp</cex-step></cex-0>
+ <cex-0><cex-step>↳ 5: <cex-1><cex-step>empty</cex-step></cex-1><cex-leaf>
"a"</cex-leaf></cex-step></cex-0>
+ <cex-1><cex-step> ↳ 7: ε<cex-dot> •</cex-dot></cex-step></cex-1>
+input.y: <warning>warning:</warning> shift/reduce conflict on token "a"
[<warning>-Wcounterexamples</warning>]
+ Example: <cex-0><cex-dot>•</cex-dot>
<cex-leaf>"a"</cex-leaf><cex-1></cex-1></cex-0>
+ Shift derivation
+ <cex-0><cex-step>exp</cex-step></cex-0>
+ <cex-0><cex-step>↳ 6: <cex-dot>•</cex-dot><cex-leaf>
"a"</cex-leaf><cex-1><cex-step> empty</cex-step></cex-1></cex-step></cex-0>
+ <cex-1><cex-step> ↳ 6: ε</cex-step></cex-1>
+ Example: <cex-0><cex-1><cex-dot>•</cex-dot></cex-1>
<cex-leaf>"a"</cex-leaf></cex-0>
+ Reduce derivation
+ <cex-0><cex-step>exp</cex-step></cex-0>
+ <cex-0><cex-step>↳ 5: <cex-1><cex-step>empty</cex-step></cex-1><cex-leaf>
"a"</cex-leaf></cex-step></cex-0>
+ <cex-1><cex-step> ↳ 7: ε<cex-dot> •</cex-dot></cex-step></cex-1>
input.y: <warning>warning:</warning> shift/reduce conflict on token "+"
[<warning>-Wcounterexamples</warning>]
Example: <cex-0><cex-leaf>exp</cex-leaf> <cex-leaf>"+"</cex-leaf><cex-1>
<cex-leaf>exp</cex-leaf> <cex-dot>•</cex-dot> <cex-leaf>"+"</cex-leaf>
<cex-leaf>exp</cex-leaf></cex-1></cex-0>
Shift derivation
@@ -568,6 +617,17 @@ input.y: <warning>warning:</warning> shift/reduce conflict
on token "+" [<warnin
<cex-0><cex-step>exp</cex-step></cex-0>
<cex-0><cex-step>↳ 3: <cex-1><cex-step>exp</cex-step></cex-1><cex-leaf>
"+"</cex-leaf><cex-leaf> exp</cex-leaf></cex-step></cex-0>
<cex-1><cex-step> ↳ 1: <cex-leaf>"if"</cex-leaf><cex-leaf>
exp</cex-leaf><cex-leaf> "then"</cex-leaf><cex-leaf> exp</cex-leaf><cex-dot>
•</cex-dot></cex-step></cex-1>
+input.y: <warning>warning:</warning> shift/reduce conflict on token "a"
[<warning>-Wcounterexamples</warning>]
+ Example: <cex-0><cex-dot>•</cex-dot>
<cex-leaf>"a"</cex-leaf><cex-1></cex-1></cex-0>
+ Shift derivation
+ <cex-0><cex-step>exp</cex-step></cex-0>
+ <cex-0><cex-step>↳ 6: <cex-dot>•</cex-dot><cex-leaf>
"a"</cex-leaf><cex-1><cex-step> empty</cex-step></cex-1></cex-step></cex-0>
+ <cex-1><cex-step> ↳ 6: ε</cex-step></cex-1>
+ Example: <cex-0><cex-1><cex-dot>•</cex-dot></cex-1>
<cex-leaf>"a"</cex-leaf></cex-0>
+ Reduce derivation
+ <cex-0><cex-step>exp</cex-step></cex-0>
+ <cex-0><cex-step>↳ 5: <cex-1><cex-step>empty</cex-step></cex-1><cex-leaf>
"a"</cex-leaf></cex-step></cex-0>
+ <cex-1><cex-step> ↳ 7: ε<cex-dot> •</cex-dot></cex-step></cex-1>
input.y: <warning>warning:</warning> shift/reduce conflict on token "+"
[<warning>-Wcounterexamples</warning>]
Example: <cex-0><cex-leaf>"if"</cex-leaf> <cex-leaf>exp</cex-leaf>
<cex-leaf>"then"</cex-leaf> <cex-leaf>exp</cex-leaf>
<cex-leaf>"else"</cex-leaf><cex-1> <cex-leaf>exp</cex-leaf>
<cex-dot>•</cex-dot> <cex-leaf>"+"</cex-leaf>
<cex-leaf>exp</cex-leaf></cex-1></cex-0>
Shift derivation
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- cex: always show ε/%empty in counterexamples,
Akim Demaille <=