[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH 6/6] cex: display derivations as trees
|
From: |
Akim Demaille |
|
Subject: |
[PATCH 6/6] cex: display derivations as trees |
|
Date: |
Sat, 18 Jul 2020 07:59:06 +0200 |
Sometimes, understanding the derivations is difficult, because they
are serialized to fit in one line. For instance, the example taken
from the NEWS file:
%token ID
%%
s: a ID
a: expr
expr: expr ID ',' | "expr"
gave
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 ]
Printing as trees, it gives:
First example expr • ID ',' ID $end
Shift derivation
$accept
↳ s $end
↳ a ID
↳ expr
↳ expr • ID ','
Second example expr • ID $end
Reduce derivation
$accept
↳ s $end
↳ a ID
↳ expr •
* src/glyphs.h, src/glyphs.c (down_arrow, empty, derivation_separator):
New.
* src/derivation.c (derivation_print, derivation_print_impl): Rename
as...
(derivation_print_flat, derivation_print_flat_impl): These.
(fputs_if, derivation_depth, derivation_width, derivation_print_tree)
(derivation_print_tree_impl, derivation_print): New.
* src/counterexample.c (print_counterexample): Adjust.
* tests/conflicts.at, tests/counterexample.at, tests/diagnostics.at,
* tests/report.at: Adjust.
---
NEWS | 27 ++-
src/counterexample.c | 5 +-
src/derivation.c | 256 +++++++++++++++++++++--
src/glyphs.c | 21 +-
src/glyphs.h | 12 ++
tests/conflicts.at | 64 ++++--
tests/counterexample.at | 452 +++++++++++++++++++++++++++++++++++++++-
tests/diagnostics.at | 100 ++++++++-
tests/report.at | 119 ++++++++---
9 files changed, 985 insertions(+), 71 deletions(-)
diff --git a/NEWS b/NEWS
index c7efefa1..e7bf5c4f 100644
--- a/NEWS
+++ b/NEWS
@@ -46,9 +46,17 @@ Changes in the display of counterexamples.
strings in the grammar which can be parsed in two ways due to the
conflict. For example:
- Example 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
+ Shift derivation
+ exp
+ ↳ exp "+" exp
+ ↳ exp • "/" exp
+ Example 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.
@@ -59,9 +67,18 @@ Changes in the display of counterexamples.
generates two examples that are the same up until the dot:
First example expr • ID ',' ID $end
- Shift derivation $accept → [ s → [ a → [ expr → [ expr • ID ',' ] ] ID
] $end ]
+ Shift derivation
+ $accept
+ ↳ s $end
+ ↳ a ID
+ ↳ expr
+ ↳ expr • ID ','
Second example expr • ID $end
- Reduce derivation $accept → [ s → [ a → [ expr • ] ID ] $end ]
+ Reduce derivation
+ $accept
+ ↳ s $end
+ ↳ a ID
+ ↳ expr •
In these cases, the parser usually doesn't have enough lookahead to
differentiate the two given examples.
diff --git a/src/counterexample.c b/src/counterexample.c
index 4aa0009b..1f690d3a 100644
--- a/src/counterexample.c
+++ b/src/counterexample.c
@@ -115,10 +115,11 @@ free_counterexample (counterexample *cex)
static void
print_counterexample (const counterexample *cex, FILE *out, const char *prefix)
{
+ const bool flat = getenv ("YYFLAT");
fprintf (out, " %s%-20s ",
prefix, cex->unifying ? _("Example") : _("First example"));
derivation_print_leaves (cex->d1, out, prefix);
- fprintf (out, " %s%-20s ",
+ fprintf (out, flat ? " %s%-20s " : " %s%s",
prefix, cex->shift_reduce ? _("Shift derivation") : _("First
derivation"));
derivation_print (cex->d1, out, prefix);
@@ -131,7 +132,7 @@ print_counterexample (const counterexample *cex, FILE *out,
const char *prefix)
prefix, cex->unifying ? _("Example") : _("Second example"));
derivation_print_leaves (cex->d2, out, prefix);
}
- fprintf (out, " %s%-20s ",
+ fprintf (out, flat ? " %s%-20s " : " %s%s",
prefix, cex->shift_reduce ? _("Reduce derivation") : _("Second
derivation"));
derivation_print (cex->d2, out, prefix);
diff --git a/src/derivation.c b/src/derivation.c
index 235333cc..5ad5a1c8 100644
--- a/src/derivation.c
+++ b/src/derivation.c
@@ -22,7 +22,9 @@
#include "derivation.h"
#include "glyphs.h"
+#include <c-ctype.h>
#include <gl_linked_list.h>
+#include <mbswidth.h>
#include "system.h"
#include "complain.h"
@@ -32,9 +34,13 @@ struct derivation
symbol_number sym;
derivation_list children;
int reference_count;
+ // Color assigned for styling. Guarantees that the derivation is
+ // always displayed with the same color, independently of the order
+ // in which the derivations are traversed.
+ int color;
};
-static derivation d_dot = { -1, NULL, -1 };
+static derivation d_dot = { -1, NULL, -1, -1 };
derivation *
derivation_dot (void)
@@ -74,6 +80,7 @@ derivation_new (symbol_number sym, derivation_list children)
deriv->sym = sym;
deriv->children = children;
deriv->reference_count = 0;
+ deriv->color = -1;
return deriv;
}
@@ -127,19 +134,235 @@ derivation_size (const derivation *deriv)
return size;
}
+
+static int
+max (int a, int b)
+{
+ return a < b ? b : a;
+}
+
+// Longest distance from root to leaf.
+static int
+derivation_depth (const derivation *deriv)
+{
+ if (deriv->children)
+ {
+ // Children's depth cannot be 0, even if there are no children
+ // (the case of a derivation with an empty RHS).
+ int res = 1;
+ derivation *child;
+ for (gl_list_iterator_t it = gl_list_iterator (deriv->children);
+ derivation_list_next (&it, &child);
+ )
+ res = max (res, derivation_depth (child));
+ return res + 1;
+ }
+ else
+ return 1;
+}
+
+static bool
+all_spaces (const char *s)
+{
+ while (c_isspace (*s))
+ s++;
+ return *s == '\0';
+}
+
+// Printing the derivation as trees without trailing spaces is
+// painful: we cannot simply pad one "column" before moving to the
+// next:
+//
+// exp
+// ↳ x1 e1 foo1 x1
+// ↳ x2 ↳ ε ↳ foo2 ↳ x2
+// ↳ x3 ↳ foo3 ↳ x3
+// ↳ "X" • ↳ x1 foo4 ↳ "X"
+// ↳ x2 ↳ "quuux"
+// ↳ x3
+// ↳ "X"
+//
+// It's hard for a column to know that it's "last" to decide whether
+// to output the right-padding or not. So when we need to pad on the
+// right to complete a column, we don't output the spaces, we
+// accumulate the width of padding in *PADDING.
+//
+// Each time we actually print something (non space), we flush that
+// padding. When we _don't_ print something, its width is added to
+// the current padding.
+//
+// This function implements this.
+//
+// When COND is true, put S on OUT, preceeded by *PADDING white
+// spaces. Otherwise add the width to *PADDING. Return the width of
+// S.
+static int
+fputs_if (bool cond, FILE *out, int *padding, const char *s)
+{
+ int res = mbswidth (s, 0);
+ if (cond && !all_spaces (s))
+ {
+ fprintf (out, "%*s%s", *padding, "", s);
+ *padding = 0;
+ }
+ else
+ {
+ *padding += res;
+ }
+ return res;
+}
+
+// The width taken to report this derivation recursively down to its
+// leaves.
+static int
+derivation_width (const derivation *deriv)
+{
+ if (deriv->children)
+ {
+ const symbol *sym = symbols[deriv->sym];
+ int self_width = mbswidth (sym->tag, 0);
+
+ // Arrow and space.
+ int children_width = down_arrow_width;
+ if (gl_list_size (deriv->children) == 0)
+ // Empty rhs.
+ children_width += empty_width;
+ else
+ {
+ derivation *child;
+ for (gl_list_iterator_t it = gl_list_iterator (deriv->children);
+ derivation_list_next (&it, &child);
+ )
+ children_width
+ += derivation_separator_width + derivation_width (child);
+ // No separator at the beginning.
+ children_width -= derivation_separator_width;
+ }
+ return max (self_width, children_width);
+ }
+ else if (deriv == &d_dot)
+ {
+ return dot_width;
+ }
+ else // leaf.
+ {
+ const symbol *sym = symbols[deriv->sym];
+ return mbswidth (sym->tag, 0);
+ }
+}
+
+
+// Print DERIV for DEPTH.
+//
+// The tree is printed from top to bottom with DEPTH ranging from 0 to
+// the total depth of the tree. DERIV should only printed when we
+// reach its depth, i.e., then DEPTH is 0.
+//
+// When DEPTH is 1 and we're on a subderivation, then we print the RHS
+// of the derivation (in DEPTH 0 we printed its LHS).
+//
+// Return the "logical printed" width. We might have not have reached
+// that width, in which case the missing spaces are in *PADDING.
+static int
+derivation_print_tree_impl (const derivation *deriv, FILE *out,
+ int depth, int *padding)
+{
+ const int width = derivation_width (deriv);
+
+ int res = 0;
+ if (deriv->children)
+ {
+ const symbol *sym = symbols[deriv->sym];
+ char style[20];
+ snprintf (style, 20, "cex-%d", deriv->color);
+
+ if (depth == 0 || depth == 1)
+ {
+ begin_use_class (style, out);
+ begin_use_class ("cex-step", out);
+ }
+ if (depth == 0)
+ {
+ res += fputs_if (true, out, padding, sym->tag);
+ }
+ else
+ {
+ res += fputs_if (depth == 1, out, padding, down_arrow);
+ if (gl_list_size (deriv->children) == 0)
+ // Empty rhs.
+ res += fputs_if (depth == 1, out, padding, empty);
+ else
+ {
+ bool first = true;
+ derivation *child;
+ for (gl_list_iterator_t it = gl_list_iterator (deriv->children);
+ derivation_list_next (&it, &child);
+ )
+ {
+ if (!first)
+ res += fputs_if (depth == 1, out, padding,
derivation_separator);
+ res += derivation_print_tree_impl (child, out, depth - 1,
padding);
+ first = false;
+ }
+ }
+ }
+ if (depth == 0 || depth == 1)
+ {
+ end_use_class ("cex-step", out);
+ end_use_class (style, out);
+ }
+ *padding += width - res;
+ res = width;
+ }
+ else if (deriv == &d_dot)
+ {
+ if (depth == 0)
+ begin_use_class ("cex-dot", out);
+ res += fputs_if (depth == 0, out, padding, dot);
+ if (depth == 0)
+ end_use_class ("cex-dot", out);
+ }
+ else // leaf.
+ {
+ const symbol *sym = symbols[deriv->sym];
+ if (depth == 0)
+ begin_use_class ("cex-leaf", out);
+ res += fputs_if (depth == 0, out, padding, sym->tag);
+ if (depth == 0)
+ end_use_class ("cex-leaf", out);
+ }
+ return res;
+}
+
+static void
+derivation_print_tree (const derivation *deriv, FILE *out, const char *prefix)
+{
+ fputc ('\n', out);
+ for (int depth = 0, max_depth = derivation_depth (deriv);
+ depth < max_depth; ++depth)
+ {
+ int padding = 0;
+ fprintf (out, " %s", prefix);
+ derivation_print_tree_impl (deriv, out, depth, &padding);
+ fputc ('\n', out);
+ }
+}
+
+
/* Print DERIV, colored according to COUNTER.
Return false if nothing is printed. */
static bool
-derivation_print_impl (const derivation *deriv, FILE *out,
- bool leaves_only,
- int *counter, const char *prefix)
+derivation_print_flat_impl (derivation *deriv, FILE *out,
+ bool leaves_only,
+ int *counter, const char *prefix)
{
if (deriv->children)
{
const symbol *sym = symbols[deriv->sym];
- char style[20];
- snprintf (style, 20, "cex-%d", *counter);
+ deriv->color = *counter;
++*counter;
+ char style[20];
+ snprintf (style, 20, "cex-%d", deriv->color);
begin_use_class (style, out);
if (!leaves_only)
@@ -156,7 +379,8 @@ derivation_print_impl (const derivation *deriv, FILE *out,
derivation_list_next (&it, &child);
)
{
- if (derivation_print_impl (child, out, leaves_only, counter, prefix))
+ if (derivation_print_flat_impl (child, out,
+ leaves_only, counter, prefix))
{
prefix = " ";
res = true;
@@ -194,21 +418,29 @@ derivation_print_impl (const derivation *deriv, FILE *out,
return true;
}
-void
-derivation_print (const derivation *deriv, FILE *out, const char *prefix)
+static void
+derivation_print_flat (const derivation *deriv, FILE *out, const char *prefix)
{
int counter = 0;
fputs (prefix, out);
- derivation_print_impl (deriv, out, false, &counter, "");
+ derivation_print_flat_impl ((derivation *)deriv, out, false, &counter, "");
fputc ('\n', out);
}
-
void
derivation_print_leaves (const derivation *deriv, FILE *out, const char
*prefix)
{
int counter = 0;
fputs (prefix, out);
- derivation_print_impl (deriv, out, true, &counter, "");
+ derivation_print_flat_impl ((derivation *)deriv, out, true, &counter, "");
fputc ('\n', out);
}
+
+void
+derivation_print (const derivation *deriv, FILE *out, const char *prefix)
+{
+ if (getenv ("YYFLAT"))
+ derivation_print_flat (deriv, out, prefix);
+ else
+ derivation_print_tree (deriv, out, prefix);
+}
diff --git a/src/glyphs.c b/src/glyphs.c
index 65f32536..0c0e9fc2 100644
--- a/src/glyphs.c
+++ b/src/glyphs.c
@@ -36,10 +36,21 @@ static glyph_buffer_t arrow_buf;
const char *arrow;
int arrow_width;
+static glyph_buffer_t down_arrow_buf;
+const char *down_arrow;
+int down_arrow_width;
+
static glyph_buffer_t dot_buf;
const char *dot;
int dot_width;
+static glyph_buffer_t empty_buf;
+const char *empty;
+int empty_width;
+
+const char *derivation_separator = " ";
+int derivation_separator_width = 1;
+
typedef struct
{
const char **glyph;
@@ -54,7 +65,6 @@ on_success (const char *buf, size_t buflen, void
*callback_arg)
callback_arg_t *arg = (callback_arg_t *) callback_arg;
assert (buflen < sizeof arg->buf);
strncpy (arg->buf, buf, buflen);
- *arg->glyph = arg->buf;
return 1;
}
@@ -63,7 +73,8 @@ on_failure (unsigned code MAYBE_UNUSED, const char *msg
MAYBE_UNUSED,
void *callback_arg)
{
callback_arg_t *arg = (callback_arg_t *) callback_arg;
- *arg->glyph = arg->fallback;
+ assert (strlen (arg->fallback) < sizeof arg->buf);
+ strcpy (arg->buf, arg->fallback);
return 0;
}
@@ -74,6 +85,7 @@ glyph_set (const char **glyph,
{
callback_arg_t arg = { glyph, buf, fallback };
int res = unicode_to_mb (code, on_success, on_failure, &arg);
+ *glyph = buf;
*width = mbswidth (*glyph, 0);
return res;
}
@@ -83,4 +95,9 @@ glyphs_init (void)
{
glyph_set (&arrow, arrow_buf, &arrow_width, 0x2192, "->");
glyph_set (&dot, dot_buf, &dot_width, 0x2022, ".");
+ glyph_set (&down_arrow, down_arrow_buf, &down_arrow_width, 0x21b3, "`->");
+ glyph_set (&empty, empty_buf, &empty_width, 0x03b5, "%empty");
+
+ strncat (down_arrow_buf, " ", sizeof down_arrow_buf - strlen
(down_arrow_buf) - 1);
+ down_arrow_width += 1;
}
diff --git a/src/glyphs.h b/src/glyphs.h
index 1faeb5aa..43f0a155 100644
--- a/src/glyphs.h
+++ b/src/glyphs.h
@@ -31,4 +31,16 @@ extern int arrow_width;
extern const char *dot;
extern int dot_width;
+/* "↳ ", below an lhs to announce the rhs. */
+extern const char *down_arrow;
+extern int down_arrow_width;
+
+/* "ε", an empty rhs. */
+extern const char *empty;
+extern int empty_width;
+
+/* " ", separate symbols in the rhs of a derivation. */
+extern const char *derivation_separator;
+extern int derivation_separator_width;
+
#endif /* GLYPHS_H */
diff --git a/tests/conflicts.at b/tests/conflicts.at
index 32b2858c..794c7795 100644
--- a/tests/conflicts.at
+++ b/tests/conflicts.at
@@ -865,8 +865,14 @@ State 5
1 exp: exp OP exp .
1 exp: exp . OP exp
Example exp OP exp . OP exp
- Shift derivation exp -> [ exp OP exp -> [ exp . OP exp ] ]
- Reduce derivation exp -> [ exp -> [ exp OP exp . ] OP exp ]
+ Shift derivation
+ exp
+ `-> exp OP exp
+ `-> exp . OP exp
+ Reduce derivation
+ exp
+ `-> exp OP exp
+ `-> exp OP exp .
]])
@@ -1119,7 +1125,7 @@ m4_popdef([AT_TEST])
# else.
AT_SETUP([Defaulted Conflicted Reduction])
-AT_KEYWORDS([report])
+AT_KEYWORDS([cex report])
AT_DATA([input.y],
[[%%
@@ -1207,8 +1213,14 @@ State 1
3 num: '0' .
4 id: '0' .
Example '0' .
- First derivation exp -> [ num -> [ '0' . ] ]
- Second derivation exp -> [ id -> [ '0' . ] ]
+ First derivation
+ exp
+ `-> num
+ `-> '0' .
+ Second derivation
+ exp
+ `-> id
+ `-> '0' .
@@ -1579,6 +1591,8 @@ AT_CLEANUP
AT_SETUP([[Unreachable States After Conflict Resolution]])
+AT_KEYWORDS([cex report])
+
# If conflict resolution makes states unreachable, remove those states, report
# rules that are then unused, and don't report conflicts in those states. Test
# what happens when a nonterminal becomes useless as a result of state removal
@@ -1754,17 +1768,29 @@ State 4
10 reported_conflicts: . %empty
8 reported_conflicts: . 'a'
First example resolved_conflict . 'a' 'a'
- Shift derivation start -> [ resolved_conflict reported_conflicts
-> [ . 'a' ] 'a' ]
+ Shift derivation
+ start
+ `-> resolved_conflict reported_conflicts 'a'
+ `-> . 'a'
Second example resolved_conflict . 'a'
- Reduce derivation start -> [ resolved_conflict reported_conflicts
-> [ . ] 'a' ]
+ Reduce derivation
+ start
+ `-> resolved_conflict reported_conflicts 'a'
+ `-> .
Shift/reduce conflict on token 'a':
10 reported_conflicts: . %empty
9 reported_conflicts: . 'a'
First example resolved_conflict . 'a' 'a'
- Shift derivation start -> [ resolved_conflict reported_conflicts
-> [ . 'a' ] 'a' ]
+ Shift derivation
+ start
+ `-> resolved_conflict reported_conflicts 'a'
+ `-> . 'a'
Second example resolved_conflict . 'a'
- Reduce derivation start -> [ resolved_conflict reported_conflicts
-> [ . ] 'a' ]
+ Reduce derivation
+ start
+ `-> resolved_conflict reported_conflicts 'a'
+ `-> .
@@ -1781,8 +1807,12 @@ State 5
8 reported_conflicts: 'a' .
9 reported_conflicts: 'a' .
Example 'a' .
- First derivation reported_conflicts -> [ 'a' . ]
- Second derivation reported_conflicts -> [ 'a' . ]
+ First derivation
+ reported_conflicts
+ `-> 'a' .
+ Second derivation
+ reported_conflicts
+ `-> 'a' .
@@ -1904,6 +1934,8 @@ AT_CLEANUP
AT_SETUP([[%nonassoc error actions for multiple reductions in a state]])
+AT_KEYWORDS([cex report])
+
AT_DATA([[input.y]],
[[%nonassoc 'a' 'b' 'c'
%%
@@ -1965,8 +1997,14 @@ AT_CHECK([[cat input.output | sed -n '/^State
0$/,/^State 1$/p']], 0,
12 empty_c2: . %empty
13 empty_c3: . %empty
Example . 'c'
- First derivation start -> [ empty_c2 -> [ . ] 'c' ]
- Second derivation start -> [ empty_c3 -> [ . ] 'c' ]
+ First derivation
+ start
+ `-> empty_c2 'c'
+ `-> .
+ Second derivation
+ start
+ `-> empty_c3 'c'
+ `-> .
diff --git a/tests/counterexample.at b/tests/counterexample.at
index 17006c31..2b85d061 100644
--- a/tests/counterexample.at
+++ b/tests/counterexample.at
@@ -17,14 +17,23 @@
AT_BANNER([[Counterexamples.]])
-# AT_BISON_CHECK_CEX(EXPERR)
-# --------------------------
+# AT_BISON_CHECK_CEX(TREE, FLAT)
+# ------------------------------
m4_define([AT_BISON_CHECK_CEX],
[AT_KEYWORDS([cex])
-AT_DATA([expout], [$1])
+
+AT_BISON_CHECK([-Wcounterexamples input.y], [0], [], [stderr])
+# FIXME: Avoid trailing white spaces.
+AT_CHECK([[sed -e 's/time limit exceeded: [0-9][.0-9]*/time limit exceeded:
XXX/g;s/ *$//;' stderr]],
+ [], [$1])
+
+m4_pushdef([AT_SET_ENV_IF],
+ [[YYFLAT=1; export YYFLAT;]]m4_defn([AT_SET_ENV_IF]))
AT_BISON_CHECK([-Wcounterexamples input.y], [0], [], [stderr])
AT_CHECK([[sed -e 's/time limit exceeded: [0-9][.0-9]*/time limit exceeded:
XXX/g' stderr]],
- [], [expout])
+ [], [$2])
+m4_popdef([AT_SET_ENV_IF])
+
])
## --------------------- ##
@@ -45,6 +54,20 @@ y: A | A B;
AT_BISON_CHECK_CEX(
[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
+Shift/reduce conflict on token B:
+ Example A . B C
+ Shift derivation
+ s
+ `-> y c
+ `-> A . B `-> C
+ Reduce derivation
+ s
+ `-> a x
+ `-> A . `-> B C
+
+input.y:4.4: warning: rule useless in parser due to conflicts [-Wother]
+]],
+[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
Shift/reduce conflict on token B:
Example A . B C
Shift derivation s -> [ y -> [ A . B ] c -> [ C ] ]
@@ -73,6 +96,38 @@ bc: B bc C | B C;
AT_BISON_CHECK_CEX(
[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
+Shift/reduce conflict on token B:
+ Example A . B C
+ Shift derivation
+ s
+ `-> ac
+ `-> A ac C
+ `-> b
+ `-> . B
+ Reduce derivation
+ s
+ `-> a bc
+ `-> A . `-> B C
+
+Shift/reduce conflict on token B:
+ Example A A . B B C C
+ Shift derivation
+ s
+ `-> ac
+ `-> A ac C
+ `-> A ac C
+ `-> b
+ `-> . b
+ `-> B B
+ Reduce derivation
+ s
+ `-> a bc
+ `-> A a `-> B bc C
+ `-> A . `-> B C
+
+input.y:6.4: warning: rule useless in parser due to conflicts [-Wother]
+]],
+[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
Shift/reduce conflict on token B:
Example A . B C
Shift derivation s -> [ ac -> [ A ac -> [ b -> [ . B ] ] C ] ]
@@ -107,6 +162,38 @@ xby: B | X xby Y;
AT_BISON_CHECK_CEX(
[[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
+Shift/reduce conflict on token B:
+ Example A . B
+ Shift derivation
+ s
+ `-> A xby
+ `-> . B
+ Reduce derivation
+ s
+ `-> ax by
+ `-> A x `-> B y
+ `-> . `-> %empty
+
+Shift/reduce conflict on token B:
+ First example A X . B Y $end
+ Shift derivation
+ $accept
+ `-> s $end
+ `-> A xby
+ `-> X xby Y
+ `-> . B
+ Second example A X . B y $end
+ Reduce derivation
+ $accept
+ `-> s $end
+ `-> ax by
+ `-> A x `-> B y
+ `-> X x
+ `-> .
+
+input.y:5.4-9: warning: rule useless in parser due to conflicts [-Wother]
+]],
+[[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
Shift/reduce conflict on token B:
Example A . B
Shift derivation s -> [ A xby -> [ . B ] ]
@@ -142,6 +229,25 @@ bc: B C;
AT_BISON_CHECK_CEX(
[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
+Shift/reduce conflict on token C:
+ First example B . C $end
+ Shift derivation
+ $accept
+ `-> g $end
+ `-> x
+ `-> bc
+ `-> B . C
+ Second example B . C D $end
+ Reduce derivation
+ $accept
+ `-> g $end
+ `-> x
+ `-> b cd
+ `-> B . `-> C D
+
+input.y:6.4: warning: rule useless in parser due to conflicts [-Wother]
+]],
+[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
Shift/reduce conflict on token C:
First example B . C $end
Shift derivation $accept -> [ g -> [ x -> [ bc -> [ B . C ] ] ] $end ]
@@ -170,6 +276,25 @@ y: A A B;
AT_BISON_CHECK_CEX(
[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
+Shift/reduce conflict on token A:
+ First example A . A B $end
+ Shift derivation
+ $accept
+ `-> s $end
+ `-> t
+ `-> y
+ `-> A . A B
+ Second example A . A $end
+ Reduce derivation
+ $accept
+ `-> s $end
+ `-> s t
+ `-> t `-> x
+ `-> x `-> A
+ `-> A .
+
+]],
+[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
Shift/reduce conflict on token A:
First example A . A B $end
Shift derivation $accept -> [ s -> [ t -> [ y -> [ A . A B ] ] ] $end ]
@@ -202,6 +327,36 @@ y: Y;
AT_BISON_CHECK_CEX(
[[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
+Shift/reduce conflict on token A:
+ Example b . A X X Y
+ Shift derivation
+ a
+ `-> s
+ `-> b . xx y
+ `-> A X X `-> Y
+ Reduce derivation
+ a
+ `-> r t
+ `-> b . `-> A x xy
+ `-> X `-> X Y
+
+Shift/reduce conflict on token X:
+ First example A X . X
+ Shift derivation
+ a
+ `-> t
+ `-> A xx
+ `-> X . X
+ Second example X . X xy
+ Reduce derivation
+ a
+ `-> x t
+ `-> X . `-> 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]
+]],
+[[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
Shift/reduce conflict on token A:
Example b . A X X Y
Shift derivation a -> [ s -> [ b . xx -> [ A X X ] y -> [ Y ] ] ]
@@ -234,6 +389,19 @@ b : A | b;
AT_BISON_CHECK_CEX(
[[input.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]
+Reduce/reduce conflict on token $end:
+ Example A b .
+ First derivation
+ a
+ `-> A b .
+ Second derivation
+ a
+ `-> A b
+ `-> b .
+
+input.y:4.9: warning: rule useless in parser due to conflicts [-Wother]
+]],
+[[input.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]
Reduce/reduce conflict on token $end:
Example A b .
First derivation a -> [ A b . ]
@@ -260,6 +428,23 @@ b: D;
AT_BISON_CHECK_CEX(
[[input.y: warning: 2 reduce/reduce conflicts [-Wconflicts-rr]
+Reduce/reduce conflict on tokens A, C:
+ First example D . A $end
+ First derivation
+ $accept
+ `-> s $end
+ `-> a A
+ `-> D .
+ Second example B D . A $end
+ Second derivation
+ $accept
+ `-> s $end
+ `-> B b A
+ `-> D .
+
+input.y:5.4: warning: rule useless in parser due to conflicts [-Wother]
+]],
+[[input.y: warning: 2 reduce/reduce conflicts [-Wconflicts-rr]
Reduce/reduce conflict on tokens A, C:
First example D . A $end
First derivation $accept -> [ s -> [ a -> [ D . ] A ] $end ]
@@ -288,6 +473,24 @@ i: X | i J K;
AT_BISON_CHECK_CEX(
[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
Shift/reduce conflict on token J:
+time limit exceeded: XXX
+ First example H i . J K $end
+ Shift derivation
+ $accept
+ `-> a $end
+ `-> H i
+ `-> i . J K
+ Second example H i . J $end
+ Reduce derivation
+ $accept
+ `-> s $end
+ `-> a J
+ `-> H i .
+
+input.y:4.4-6: warning: rule useless in parser due to conflicts [-Wother]
+]],
+[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
+Shift/reduce conflict on token J:
time limit exceeded: XXX
First example H i . J K $end
Shift derivation $accept -> [ a -> [ H i -> [ i . J K ] ] $end ]
@@ -319,6 +522,37 @@ b: A B C | A B D;
AT_BISON_CHECK_CEX(
[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
+Shift/reduce conflict on token B:
+ Example N A . B C
+ Shift derivation
+ s
+ `-> n
+ `-> N b
+ `-> A . B C
+ Reduce derivation
+ s
+ `-> n C
+ `-> N a B
+ `-> A .
+
+Shift/reduce conflict on token B:
+ Example N N A . B D C
+ Shift derivation
+ s
+ `-> n
+ `-> N n C
+ `-> N b
+ `-> A . B D
+ Reduce derivation
+ s
+ `-> n C
+ `-> N n D
+ `-> N a B
+ `-> A .
+
+input.y:5.4: warning: rule useless in parser due to conflicts [-Wother]
+]],
+[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
Shift/reduce conflict on token B:
Example N A . B C
Shift derivation s -> [ n -> [ N b -> [ A . B C ] ] ]
@@ -355,6 +589,38 @@ C : A c A;
AT_BISON_CHECK_CEX(
[[input.y: warning: 4 reduce/reduce conflicts [-Wconflicts-rr]
+Reduce/reduce conflict on tokens b, c:
+ Example B . b c
+ First derivation
+ S
+ `-> B C
+ `-> A b A `-> A c A
+ `-> B . `-> %empty `-> %empty `-> %empty
+ Second derivation
+ S
+ `-> B C
+ `-> A c A
+ `-> B `-> %empty
+ `-> A b A
+ `-> . `-> %empty
+
+Reduce/reduce conflict on tokens b, c:
+ Example C . c b
+ First derivation
+ S
+ `-> C B
+ `-> A c A `-> A b A
+ `-> C . `-> %empty `-> %empty `-> %empty
+ Second derivation
+ S
+ `-> C B
+ `-> A b A
+ `-> C `-> %empty
+ `-> A c A
+ `-> . `-> %empty
+
+]],
+[[input.y: warning: 4 reduce/reduce conflicts [-Wconflicts-rr]
Reduce/reduce conflict on tokens b, c:
Example B . b c
First derivation S -> [ B -> [ A -> [ B . ] b A -> [ ] ] C -> [ A -> [ ]
c A -> [ ] ] ]
@@ -387,6 +653,136 @@ d : a | c A | d;
AT_BISON_CHECK_CEX(
[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
input.y: warning: 6 reduce/reduce conflicts [-Wconflicts-rr]
+Reduce/reduce conflict on token A:
+ First example . c A A $end
+ First derivation
+ $accept
+ `-> a $end
+ `-> b d
+ `-> . `-> c A A
+ Second example . c A A $end
+ Second derivation
+ $accept
+ `-> a $end
+ `-> c d
+ `-> . `-> c A A
+
+Reduce/reduce conflict on token A:
+time limit exceeded: XXX
+ First example b . c A A $end
+ First derivation
+ $accept
+ `-> a $end
+ `-> b d
+ `-> a
+ `-> b d
+ `-> . `-> c A A
+ Second example b . A $end
+ Second derivation
+ $accept
+ `-> a $end
+ `-> b d
+ `-> c A
+ `-> .
+
+Reduce/reduce conflict on token A:
+time limit exceeded: XXX
+ First example c . c A A $end
+ First derivation
+ $accept
+ `-> a $end
+ `-> c d
+ `-> a
+ `-> b d
+ `-> . `-> c A A
+ Second example c . A $end
+ Second derivation
+ $accept
+ `-> a $end
+ `-> c d
+ `-> c A
+ `-> .
+
+Shift/reduce conflict on token A:
+time limit exceeded: XXX
+ First example b c . A
+ Shift derivation
+ a
+ `-> b d
+ `-> c . A
+ Second example b c . c A A $end
+ Reduce derivation
+ $accept
+ `-> a $end
+ `-> b d
+ `-> a
+ `-> c d
+ `-> a
+ `-> b d
+ `-> . `-> c A A
+
+Reduce/reduce conflict on token A:
+ First example b c . c A A $end
+ First derivation
+ $accept
+ `-> a $end
+ `-> b d
+ `-> a
+ `-> c d
+ `-> a
+ `-> b d
+ `-> . `-> c A A
+ Second example b c . A $end
+ Second derivation
+ $accept
+ `-> a $end
+ `-> b d
+ `-> a
+ `-> c d
+ `-> c A
+ `-> .
+
+Shift/reduce conflict on token A:
+ First example b c . A
+ Shift derivation
+ a
+ `-> b d
+ `-> c . A
+ Second example b c . A $end
+ Reduce derivation
+ $accept
+ `-> a $end
+ `-> b d
+ `-> a
+ `-> c d
+ `-> c A
+ `-> .
+
+Reduce/reduce conflict on token $end:
+ Example b d .
+ First derivation
+ a
+ `-> b d .
+ Second derivation
+ a
+ `-> b d
+ `-> d .
+
+Reduce/reduce conflict on token $end:
+ Example c d .
+ First derivation
+ a
+ `-> c d .
+ Second derivation
+ a
+ `-> c d
+ `-> d .
+
+input.y:5.4: warning: rule useless in parser due to conflicts [-Wother]
+input.y:6.15: warning: rule useless in parser due to conflicts [-Wother]
+]],
+[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
+input.y: warning: 6 reduce/reduce conflicts [-Wconflicts-rr]
Reduce/reduce conflict on token A:
First example . c A A $end
First derivation $accept -> [ a -> [ b -> [ . ] d -> [ c A A ] ] $end ]
@@ -461,6 +857,21 @@ i: %empty | i J;
AT_BISON_CHECK_CEX(
[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
+Shift/reduce conflict on token J:
+ Example H i J . J J
+ Shift derivation
+ s
+ `-> a J
+ `-> H i J . J
+ Reduce derivation
+ s
+ `-> a
+ `-> H i J J
+ `-> i J .
+
+input.y:5.13-15: warning: rule useless in parser due to conflicts [-Wother]
+]],
+[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
Shift/reduce conflict on token J:
Example H i J . J J
Shift derivation s -> [ a -> [ H i J . J ] J ]
@@ -492,6 +903,21 @@ d: D;
AT_BISON_CHECK_CEX(
[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
+Shift/reduce conflict on token D:
+ Example A a . D
+ Shift derivation
+ s
+ `-> A a d
+ `-> . D
+ Reduce derivation
+ s
+ `-> A a a d
+ `-> b `-> D
+ `-> c
+ `-> .
+
+]],
+[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
Shift/reduce conflict on token D:
Example A a . D
Shift derivation s -> [ A a d -> [ . D ] ]
@@ -521,6 +947,24 @@ d: D;
AT_BISON_CHECK_CEX(
[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
+Shift/reduce conflict on token D:
+ First example A a . D $end
+ Shift derivation
+ $accept
+ `-> s $end
+ `-> A a d
+ `-> . D
+ Second example A a . D E $end
+ Reduce derivation
+ $accept
+ `-> s $end
+ `-> A a a d E
+ `-> b `-> D
+ `-> c
+ `-> .
+
+]],
+[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
Shift/reduce conflict on token D:
First example A a . D $end
Shift derivation $accept -> [ s -> [ A a d -> [ . D ] ] $end ]
diff --git a/tests/diagnostics.at b/tests/diagnostics.at
index 1fd600d9..75202e10 100644
--- a/tests/diagnostics.at
+++ b/tests/diagnostics.at
@@ -28,6 +28,8 @@ m4_pushdef([AT_TEST],
AT_SETUP([$1])
AT_KEYWORDS([diagnostics])
+m4_if(m4_index([$1], [Counterexample]), [-1], [], [AT_KEYWORDS([cex])])
+
# We need UTF-8 support for correct screen-width computation of UTF-8
# characters. Skip the test if not available.
locale=`locale -a | $EGREP '^en_US\.(UTF-8|utf8)$' | sed 1q`
@@ -535,32 +537,114 @@ exp
[[input.y: <error>error:</error> shift/reduce conflicts: 4 found, 0 expected
Shift/reduce conflict on token "+":
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 <cex-0><cex-step>exp → [
</cex-step><cex-leaf>exp</cex-leaf> <cex-leaf>"+"</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 derivation
+ <cex-0><cex-step>exp</cex-step></cex-0>
+ <cex-0><cex-step>↳ <cex-leaf>exp</cex-leaf><cex-leaf>
"+"</cex-leaf><cex-1><cex-step> exp</cex-step></cex-1></cex-step></cex-0>
+ <cex-1><cex-step> ↳ <cex-leaf>exp</cex-leaf><cex-dot>
•</cex-dot><cex-leaf> "+"</cex-leaf><cex-leaf> exp</cex-leaf></cex-step></cex-1>
Example <cex-0><cex-1><cex-leaf>exp</cex-leaf>
<cex-leaf>"+"</cex-leaf> <cex-leaf>exp</cex-leaf> <cex-dot>•</cex-dot></cex-1>
<cex-leaf>"+"</cex-leaf> <cex-leaf>exp</cex-leaf></cex-0>
- Reduce derivation <cex-0><cex-step>exp → [
</cex-step><cex-1><cex-step>exp → [ </cex-step><cex-leaf>exp</cex-leaf>
<cex-leaf>"+"</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>
+ Reduce derivation
+ <cex-0><cex-step>exp</cex-step></cex-0>
+ <cex-0><cex-step>↳ <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> ↳ <cex-leaf>exp</cex-leaf><cex-leaf>
"+"</cex-leaf><cex-leaf> exp</cex-leaf><cex-dot> •</cex-dot></cex-step></cex-1>
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>
- Shift 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 derivation
+ <cex-0><cex-step>exp</cex-step></cex-0>
+ <cex-0><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-1></cex-step></cex-0>
+ <cex-1><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-1>
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-1>
<cex-leaf>"else"</cex-leaf> <cex-leaf>exp</cex-leaf></cex-0>
- Reduce 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-step> ]</cex-step></cex-1> <cex-leaf>"else"</cex-leaf>
<cex-leaf>exp</cex-leaf><cex-step> ]</cex-step></cex-0>
+ Reduce derivation
+ <cex-0><cex-step>exp</cex-step></cex-0>
+ <cex-0><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-1><cex-leaf>
"else"</cex-leaf><cex-leaf> exp</cex-leaf></cex-step></cex-0>
+ <cex-1><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-1>
Shift/reduce conflict on token "+":
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>
- Shift 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 derivation
+ <cex-0><cex-step>exp</cex-step></cex-0>
+ <cex-0><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-1></cex-step></cex-0>
+ <cex-1><cex-step> ↳ <cex-leaf>exp</cex-leaf><cex-dot>
•</cex-dot><cex-leaf> "+"</cex-leaf><cex-leaf> exp</cex-leaf></cex-step></cex-1>
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>
- Reduce 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>
+ Reduce derivation
+ <cex-0><cex-step>exp</cex-step></cex-0>
+ <cex-0><cex-step>↳ <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> ↳ <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>
Shift/reduce conflict on token "+":
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 <cex-0><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-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 derivation
+ <cex-0><cex-step>exp</cex-step></cex-0>
+ <cex-0><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-1><cex-step> exp</cex-step></cex-1></cex-step></cex-0>
+ <cex-1><cex-step> ↳
<cex-leaf>exp</cex-leaf><cex-dot> •</cex-dot><cex-leaf>
"+"</cex-leaf><cex-leaf> exp</cex-leaf></cex-step></cex-1>
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>
- Reduce 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>
+ Reduce derivation
+ <cex-0><cex-step>exp</cex-step></cex-0>
+ <cex-0><cex-step>↳ <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> ↳ <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-1>
]])
+AT_TEST([[Deep Counterexamples]],
+[[%expect 0
+%%
+exp: x1 e1 foo1 x1 | y1 e2 bar1 y1
+foo1: foo2
+foo2: foo3
+foo3: x1 foo4
+foo4: "quuux"
+
+bar1: bar2
+bar2: bar3
+bar3: y1 bar4
+bar4: "quuux"
+
+x1: x2
+x2: x3
+x3: "X"
+
+y1: y2
+y2: y3
+y3: "X"
+
+e1:
+e2:
+]],
+[1],
+[[input.y:30.4: <warning>warning:</warning> empty rule without %empty
[<warning>-Wempty-rule</warning>]
+ 30 | e1:
+ | <warning>^</warning>
+ | <fixit-insert>%empty</fixit-insert>
+input.y:31.4: <warning>warning:</warning> empty rule without %empty
[<warning>-Wempty-rule</warning>]
+ 31 | e2:
+ | <warning>^</warning>
+ | <fixit-insert>%empty</fixit-insert>
+input.y: <error>error:</error> reduce/reduce conflicts: 1 found, 0 expected
+Reduce/reduce conflict on token "X":
+ Example <cex-0><cex-1><cex-2><cex-3><cex-leaf>"X"</cex-leaf>
<cex-dot>•</cex-dot></cex-3></cex-2></cex-1><cex-4></cex-4><cex-5><cex-6><cex-7><cex-8><cex-9><cex-10>
<cex-leaf>"X"</cex-leaf></cex-10></cex-9></cex-8><cex-11>
<cex-leaf>"quuux"</cex-leaf></cex-11></cex-7></cex-6></cex-5><cex-12><cex-13><cex-14>
<cex-leaf>"X"</cex-leaf></cex-14></cex-13></cex-12></cex-0>
+ First derivation
+ <cex-0><cex-step>exp</cex-step></cex-0>
+ <cex-0><cex-step>↳ <cex-1><cex-step>x1</cex-step></cex-1><cex-4><cex-step>
e1</cex-step></cex-4><cex-5><cex-step>
foo1</cex-step></cex-5><cex-12><cex-step>
x1</cex-step></cex-12></cex-step></cex-0>
+ <cex-1><cex-step> ↳
<cex-2><cex-step>x2</cex-step></cex-2></cex-step></cex-1><cex-4><cex-step>
↳ ε</cex-step></cex-4><cex-5><cex-step> ↳
<cex-6><cex-step>foo2</cex-step></cex-6></cex-step></cex-5><cex-12><cex-step>
↳ <cex-13><cex-step>x2</cex-step></cex-13></cex-step></cex-12>
+ <cex-2><cex-step> ↳
<cex-3><cex-step>x3</cex-step></cex-3></cex-step></cex-2><cex-6><cex-step>
↳
<cex-7><cex-step>foo3</cex-step></cex-7></cex-step></cex-6><cex-13><cex-step>
↳ <cex-14><cex-step>x3</cex-step></cex-14></cex-step></cex-13>
+ <cex-3><cex-step> ↳ <cex-leaf>"X"</cex-leaf><cex-dot>
•</cex-dot></cex-step></cex-3><cex-7><cex-step> ↳
<cex-8><cex-step>x1</cex-step></cex-8><cex-11><cex-step>
foo4</cex-step></cex-11></cex-step></cex-7><cex-14><cex-step> ↳
<cex-leaf>"X"</cex-leaf></cex-step></cex-14>
+ <cex-8><cex-step> ↳
<cex-9><cex-step>x2</cex-step></cex-9></cex-step></cex-8><cex-11><cex-step>
↳ <cex-leaf>"quuux"</cex-leaf></cex-step></cex-11>
+ <cex-9><cex-step> ↳
<cex-10><cex-step>x3</cex-step></cex-10></cex-step></cex-9>
+ <cex-10><cex-step> ↳
<cex-leaf>"X"</cex-leaf></cex-step></cex-10>
+ Example <cex-0><cex-1><cex-2><cex-3><cex-leaf>"X"</cex-leaf>
<cex-dot>•</cex-dot></cex-3></cex-2></cex-1><cex-4></cex-4><cex-5><cex-6><cex-7><cex-8><cex-9><cex-10>
<cex-leaf>"X"</cex-leaf></cex-10></cex-9></cex-8><cex-11>
<cex-leaf>"quuux"</cex-leaf></cex-11></cex-7></cex-6></cex-5><cex-12><cex-13><cex-14>
<cex-leaf>"X"</cex-leaf></cex-14></cex-13></cex-12></cex-0>
+ Second derivation
+ <cex-0><cex-step>exp</cex-step></cex-0>
+ <cex-0><cex-step>↳ <cex-1><cex-step>y1</cex-step></cex-1><cex-4><cex-step>
e2</cex-step></cex-4><cex-5><cex-step>
bar1</cex-step></cex-5><cex-12><cex-step>
y1</cex-step></cex-12></cex-step></cex-0>
+ <cex-1><cex-step> ↳
<cex-2><cex-step>y2</cex-step></cex-2></cex-step></cex-1><cex-4><cex-step>
↳ ε</cex-step></cex-4><cex-5><cex-step> ↳
<cex-6><cex-step>bar2</cex-step></cex-6></cex-step></cex-5><cex-12><cex-step>
↳ <cex-13><cex-step>y2</cex-step></cex-13></cex-step></cex-12>
+ <cex-2><cex-step> ↳
<cex-3><cex-step>y3</cex-step></cex-3></cex-step></cex-2><cex-6><cex-step>
↳
<cex-7><cex-step>bar3</cex-step></cex-7></cex-step></cex-6><cex-13><cex-step>
↳ <cex-14><cex-step>y3</cex-step></cex-14></cex-step></cex-13>
+ <cex-3><cex-step> ↳ <cex-leaf>"X"</cex-leaf><cex-dot>
•</cex-dot></cex-step></cex-3><cex-7><cex-step> ↳
<cex-8><cex-step>y1</cex-step></cex-8><cex-11><cex-step>
bar4</cex-step></cex-11></cex-step></cex-7><cex-14><cex-step> ↳
<cex-leaf>"X"</cex-leaf></cex-step></cex-14>
+ <cex-8><cex-step> ↳
<cex-9><cex-step>y2</cex-step></cex-9></cex-step></cex-8><cex-11><cex-step>
↳ <cex-leaf>"quuux"</cex-leaf></cex-step></cex-11>
+ <cex-9><cex-step> ↳
<cex-10><cex-step>y3</cex-step></cex-10></cex-step></cex-9>
+ <cex-10><cex-step> ↳
<cex-leaf>"X"</cex-leaf></cex-step></cex-10>
+input.y: <warning>warning:</warning> fix-its can be applied. Rerun with
option '--update'. [<warning>-Wother</warning>]
+]])
m4_popdef([AT_TEST])
diff --git a/tests/report.at b/tests/report.at
index e3497037..9aa1c7be 100644
--- a/tests/report.at
+++ b/tests/report.at
@@ -1539,39 +1539,74 @@ 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
- Shift derivation exp → [ exp "+" exp → [ exp • "⊕" exp ] ]
- Reduce 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 •
- First derivation exp → [ exp "+" exp • ]
- Second derivation exp → [ exp "+" exp • ]
+ First derivation
+ exp
+ ↳ exp "+" exp •
+ Second derivation
+ exp
+ ↳ exp "+" exp •
Shift/reduce conflict on token "⊕":
Example exp "+" exp • "⊕" exp
- Shift derivation exp → [ exp "+" exp → [ exp • "⊕" exp ] ]
- Reduce 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
- Shift derivation exp → [ exp "⊕" exp → [ exp • "⊕" exp ] ]
- Reduce 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
- Shift derivation exp → [ exp "⊕" exp → [ exp • "+" exp ] ]
- Reduce 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
- Shift derivation exp → [ exp "⊕" exp → [ exp • "+" exp ] ]
- Reduce 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]
]])
# Check the contents of the report.
-AT_CHECK([cat input.output], [],
+# FIXME: Avoid trailing white spaces.
+AT_CHECK([sed -e 's/ *$//' input.output], [],
[[Rules useless in parser due to conflicts
3 exp: exp "+" exp
@@ -1714,22 +1749,38 @@ State 7
2 exp: exp "+" exp •
1 exp: exp • "⊕" exp
Example exp "+" exp • "⊕" exp
- Shift derivation exp → [ exp "+" exp → [ exp • "⊕" exp ] ]
- Reduce 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 •
3 exp: exp "+" exp •
Example exp "+" exp •
- First derivation exp → [ exp "+" exp • ]
- Second derivation exp → [ exp "+" exp • ]
+ First derivation
+ exp
+ ↳ exp "+" exp •
+ Second derivation
+ exp
+ ↳ exp "+" exp •
Shift/reduce conflict on token "⊕":
3 exp: exp "+" exp •
1 exp: exp • "⊕" exp
Example exp "+" exp • "⊕" exp
- Shift derivation exp → [ exp "+" exp → [ exp • "⊕" exp ] ]
- Reduce derivation exp → [ exp → [ exp "+" exp • ] "⊕" exp ]
+ Shift derivation
+ exp
+ ↳ exp "+" exp
+ ↳ exp • "⊕" exp
+ Reduce derivation
+ exp
+ ↳ exp "⊕" exp
+ ↳ exp "+" exp •
@@ -1751,22 +1802,40 @@ State 8
1 exp: exp "⊕" exp •
1 exp: exp • "⊕" exp
Example exp "⊕" exp • "⊕" exp
- Shift derivation exp → [ exp "⊕" exp → [ exp • "⊕" exp ] ]
- Reduce 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
- Shift derivation exp → [ exp "⊕" exp → [ exp • "+" exp ] ]
- Reduce 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
- Shift derivation exp → [ exp "⊕" exp → [ exp • "+" exp ] ]
- Reduce 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/6] Print derivations as trees, Akim Demaille, 2020/07/18
- [PATCH 1/6] cex: more colors, Akim Demaille, 2020/07/18
- [PATCH 2/6] cex: simplify tests, Akim Demaille, 2020/07/18
- [PATCH 3/6] cex: style changes, Akim Demaille, 2020/07/18
- [PATCH 4/6] cex: factor the handling of graphical symbols, Akim Demaille, 2020/07/18
- [PATCH 5/6] cex: use the glyphs, Akim Demaille, 2020/07/18
- [PATCH 6/6] cex: display derivations as trees,
Akim Demaille <=