[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
cex: display all the S/R conflicts, not just one per (state, rule)
From: |
Akim Demaille |
Subject: |
cex: display all the S/R conflicts, not just one per (state, rule) |
Date: |
Tue, 23 Jun 2020 07:04:19 +0200 |
commit b65bd16e45d5ce1a9404cd46ea3b32256e2e477d
Author: Akim Demaille <akim.demaille@gmail.com>
Date: Tue Jun 16 08:37:28 2020 +0200
cex: display all the S/R conflicts, not just one per (state, rule)
Before this commit, on
%%
exp
: "if" exp "then" exp
| "if" exp "then" exp "else" exp
| exp "+" exp
| "num"
we used to not display the third counterexample below:
Shift/reduce conflict on token "+":
Example exp "+" exp . "+" exp
First derivation exp ::=[ exp ::=[ exp "+" exp . ] "+" exp ]
Second derivation exp ::=[ exp "+" exp ::=[ exp . "+" exp ] ]
Shift/reduce conflict on token "else":
Example "if" exp "then" "if" exp "then" exp . "else" exp
First derivation exp ::=[ "if" exp "then" exp ::=[ "if" exp
"then" exp . ] "else" exp ]
Second derivation exp ::=[ "if" exp "then" exp ::=[ "if" exp
"then" exp . "else" exp ] ]
Shift/reduce conflict on token "+":
Example "if" exp "then" exp . "+" exp
First derivation exp ::=[ exp ::=[ "if" exp "then" exp . ] "+"
exp ]
Second derivation exp ::=[ "if" exp "then" exp ::=[ exp . "+" exp
] ]
Shift/reduce conflict on token "+":
Example "if" exp "then" exp "else" exp . "+" exp
First derivation exp ::=[ exp ::=[ "if" exp "then" exp "else" exp
. ] "+" exp ]
Second derivation exp ::=[ "if" exp "then" exp "else" exp ::=[ exp
. "+" exp ] ]
* src/counterexample.c (counterexample_report_state): Don't stop of
the first conflicts.
* tests/conflicts.at, tests/counterexample.at, tests/diagnostics.at,
* tests/report.at: Adjust.
diff --git a/TODO b/TODO
index 2fa508aa..3f21d72d 100644
--- a/TODO
+++ b/TODO
@@ -37,10 +37,6 @@ Unless we play it dumb (little structure).
Use "•" instead of ".".
-*** Conflict coverage
-Not all the conflicts have counterexamples generated. See the "break"s in
-counterexample_report_state.
-
*** point, dot
We have too many names. In XML we use "point", in C "dot". A traditional
more accurate name of "item" is "pointed rule", so we should probably prefer
diff --git a/src/counterexample.c b/src/counterexample.c
index e5b3a0af..a60456b5 100644
--- a/src/counterexample.c
+++ b/src/counterexample.c
@@ -1279,20 +1279,16 @@ counterexample_report_state (const state *s, FILE *out,
const char *prefix)
const reductions *reds = s->reductions;
for (int i = 0; i < reds->num; ++i)
{
- rule *r1 = reds->rules[i];
+ const rule *r1 = reds->rules[i];
const state_item_number c1 = find_state_item_number (r1, sn);
for (int j = state_item_map[sn]; j < state_item_map[sn + 1]; ++j)
+ if (!SI_DISABLED (j))
{
- if (SI_DISABLED (j))
- continue;
state_item *si = state_items + j;
item_number conf = *si->item;
if (item_number_is_symbol_number (conf)
&& bitset_test (reds->lookahead_tokens[i], conf))
- {
counterexample_report_shift_reduce (c1, j, conf, out, prefix);
- break;
- }
}
for (int j = i+1; j < reds->num; ++j)
{
@@ -1302,12 +1298,10 @@ counterexample_report_state (const state *s, FILE *out,
const char *prefix)
reds->lookahead_tokens[j]);
if (!bitset_empty_p (conf))
{
- rule *r2 = reds->rules[j];
- for (int k = state_item_map[sn];
- k < state_item_map[sn + 1]; ++k)
+ const rule *r2 = reds->rules[j];
+ for (int k = state_item_map[sn]; k < state_item_map[sn + 1]; ++k)
+ if (!SI_DISABLED (k))
{
- if (SI_DISABLED (k))
- continue;
state_item *si = state_items + k;
const rule *r = item_rule (si->item);
if (r == r2)
diff --git a/tests/conflicts.at b/tests/conflicts.at
index 95ab79df..7a1cafee 100644
--- a/tests/conflicts.at
+++ b/tests/conflicts.at
@@ -1758,6 +1758,14 @@ State 4
Second example resolved_conflict . 'a' 'a'
Second derivation start ::=[ resolved_conflict reported_conflicts
::=[ . 'a' ] 'a' ]
+ Shift/reduce conflict on token 'a':
+ 10 reported_conflicts: . %empty
+ 9 reported_conflicts: . 'a'
+ First example resolved_conflict . 'a'
+ First derivation start ::=[ resolved_conflict reported_conflicts
::=[ . ] 'a' ]
+ Second example resolved_conflict . 'a' 'a'
+ Second derivation start ::=[ resolved_conflict reported_conflicts
::=[ . 'a' ] 'a' ]
+
State 5
diff --git a/tests/counterexample.at b/tests/counterexample.at
index 48d5acf3..92ce5109 100644
--- a/tests/counterexample.at
+++ b/tests/counterexample.at
@@ -79,6 +79,11 @@ Shift/reduce conflict on token B:
First derivation s ::=[ a ::=[ A . ] bc ::=[ B C ] ]
Second derivation s ::=[ ac ::=[ A ac ::=[ b ::=[ . 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 ] ]
+
input.y:6.4: warning: rule useless in parser due to conflicts [-Wother]
]])
@@ -328,6 +333,11 @@ Shift/reduce conflict on token B:
First derivation s ::=[ n ::=[ N a ::=[ A . ] B ] C ]
Second derivation s ::=[ n ::=[ N b ::=[ 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 ] ]
+
input.y:5.4: warning: rule useless in parser due to conflicts [-Wother]
]])
diff --git a/tests/diagnostics.at b/tests/diagnostics.at
index 6d3ead97..17a2ebc5 100644
--- a/tests/diagnostics.at
+++ b/tests/diagnostics.at
@@ -545,6 +545,12 @@ Shift/reduce conflict on token "else":
Example <cex-0><cex-leaf>"if"</cex-leaf>
<cex-leaf>exp</cex-leaf> <cex-leaf>"then"</cex-leaf><cex-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-leaf>"else"</cex-leaf>
<cex-leaf>exp</cex-leaf></cex-1></cex-0>
Second derivation <cex-0><cex-step>exp ::=[
</cex-step><cex-leaf>"if"</cex-leaf> <cex-leaf>exp</cex-leaf>
<cex-leaf>"then"</cex-leaf><cex-1> <cex-step>exp ::=[
</cex-step><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-leaf>"else"</cex-leaf> <cex-leaf>exp</cex-leaf><cex-step>
]</cex-step></cex-1><cex-step> ]</cex-step></cex-0>
+Shift/reduce conflict on token "+":
+ Example <cex-0><cex-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-1> <cex-leaf>"+"</cex-leaf>
<cex-leaf>exp</cex-leaf></cex-0>
+ First derivation <cex-0><cex-step>exp ::=[
</cex-step><cex-1><cex-step>exp ::=[ </cex-step><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-step></cex-1> <cex-leaf>"+"</cex-leaf>
<cex-leaf>exp</cex-leaf><cex-step> ]</cex-step></cex-0>
+ Example <cex-0><cex-leaf>"if"</cex-leaf>
<cex-leaf>exp</cex-leaf> <cex-leaf>"then"</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>
+ Second derivation <cex-0><cex-step>exp ::=[
</cex-step><cex-leaf>"if"</cex-leaf> <cex-leaf>exp</cex-leaf>
<cex-leaf>"then"</cex-leaf><cex-1> <cex-step>exp ::=[
</cex-step><cex-leaf>exp</cex-leaf> <cex-dot>•</cex-dot>
<cex-leaf>"+"</cex-leaf> <cex-leaf>exp</cex-leaf><cex-step>
]</cex-step></cex-1><cex-step> ]</cex-step></cex-0>
+
Shift/reduce conflict on token "+":
Example <cex-0><cex-1><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-leaf>exp</cex-leaf>
<cex-dot>•</cex-dot></cex-1> <cex-leaf>"+"</cex-leaf>
<cex-leaf>exp</cex-leaf></cex-0>
First derivation <cex-0><cex-step>exp ::=[
</cex-step><cex-1><cex-step>exp ::=[ </cex-step><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-leaf>exp</cex-leaf>
<cex-dot>•</cex-dot><cex-step> ]</cex-step></cex-1> <cex-leaf>"+"</cex-leaf>
<cex-leaf>exp</cex-leaf><cex-step> ]</cex-step></cex-0>
diff --git a/tests/report.at b/tests/report.at
index 1d93f9a5..3801c919 100644
--- a/tests/report.at
+++ b/tests/report.at
@@ -1190,6 +1190,16 @@ Shift/reduce conflict on token "⊕":
First derivation exp ::=[ exp ::=[ exp "⊕" exp • ] "⊕" exp ]
Second 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/reduce conflict on token "+":
+ Example exp "⊕" exp • "+" exp
+ First derivation exp ::=[ exp ::=[ exp "⊕" exp • ] "+" exp ]
+ Second derivation exp ::=[ exp "⊕" exp ::=[ exp • "+" exp ] ]
+
input.y:6.3-13: warning: rule useless in parser due to conflicts [-Wother]
]])
@@ -1377,6 +1387,20 @@ State 8
First derivation exp ::=[ exp ::=[ exp "⊕" exp • ] "⊕" exp ]
Second 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/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 ] ]
+
]])
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- cex: display all the S/R conflicts, not just one per (state, rule),
Akim Demaille <=