Re: [PATCH] {master} Useless precedence warning

[Valentin Tolmer]

Patch correction.

Symbols with precedence but no associativity, and whose precedence is never
used can be declared with %token instead. The used precedence relationships
are recorded and a warning about useless ones is issued.

* src/conflicts.c (resolve_sr_conflict): Record precedence relation.
* src/main.c (main): Print precedence warnings.
* src/symtab.c src/symtab.h : Record relationships in a graph and warn about
  useless ones.
* tests/conflicts.at : New.
---
 NEWS               |    7 ++++
 src/conflicts.c    |    2 +
 src/main.c         |    2 +
 src/symtab.c       |  115 
++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/symtab.h       |   46 +++++++++++++++++++++
 tests/conflicts.at |   42 +++++++++++++++++++
 6 files changed, 214 insertions(+)

diff --git a/NEWS b/NEWS
index a44e1be..3e34149 100644
--- a/NEWS
+++ b/NEWS
@@ -156,6 +156,13 @@ GNU Bison NEWS
     bar.y: error: shift/reduce conflicts: 1 found, 0 expected
     bar.y: error: reduce/reduce conflicts: 2 found, 0 expected

+*** Useless precedence
+
+  Bison now warns about symbols with a declared precedence but no declared
+  associativity (i.e. declared with %precedence), and whose precedence is
+  never used.  In that case, the symbol can be safely declared with a 
%token
+  instead, without modifying the parsing tables.
+
 ** Additional yylex/yyparse arguments

   The new directive %param declares additional arguments to both yylex and
diff --git a/src/conflicts.c b/src/conflicts.c
index 2ea6de1..696d0a0 100644
--- a/src/conflicts.c
+++ b/src/conflicts.c
@@ -276,11 +276,13 @@ resolve_sr_conflict (state *s, int ruleno, symbol 
**errors, int *nerrs)
            The precedence of shifting is that of token i.  */
         if (symbols[i]->prec < redprec)
           {
+            register_precedence (redrule->prec->number, i);
             log_resolution (redrule, i, reduce_resolution);
             flush_shift (s, i);
           }
         else if (symbols[i]->prec > redprec)
           {
+            register_precedence (i, redrule->prec->number);
             log_resolution (redrule, i, shift_resolution);
             flush_reduce (lookahead_tokens, i);
           }
diff --git a/src/main.c b/src/main.c
index 5386aa7..2ab87fb 100644
--- a/src/main.c
+++ b/src/main.c
@@ -144,6 +144,8 @@ main (int argc, char *argv[])

   grammar_rules_useless_report (_("rule useless in parser due to 
conflicts"));

+  print_precedence_warnings ();
+
   /* Output file names. */
   compute_output_file_names ();

diff --git a/src/symtab.c b/src/symtab.c
index cc81c5f..6e360a4 100644
--- a/src/symtab.c
+++ b/src/symtab.c
@@ -46,6 +46,11 @@ symbol *accept = NULL;
 symbol *startsymbol = NULL;
 location startsymbol_location;

+/*---------------------------.
+| Precedence relation graph. |
+`---------------------------*/
+
+static symgraph **prec_nodes;

 /*---------------------------------.
 | Create a new symbol, named TAG.  |
@@ -971,3 +976,113 @@ symbols_pack (void)
               _("the start symbol %s is a token"),
               startsymbol->tag);
 }
+
+/*---------------------------------.
+| Initialize relation graph nodes. |
+`---------------------------------*/
+
+static void
+init_prec_nodes (void)
+{
+  prec_nodes = xcalloc (nsyms, sizeof (* prec_nodes));
+  int i;
+  for (i = 0; i < nsyms; ++i)
+    {
+      prec_nodes[i] = xmalloc (sizeof (*prec_nodes[i]));
+      symgraph *s = prec_nodes[i];
+      s->id = i;
+      s->succ = 0;
+      s->pred = 0;
+    }
+}
+
+/*--------------------------.
+| Routine to create a link. |
+`--------------------------*/
+
+static symgraphlink *
+create_symgraphlink (graphid id, symgraphlink *next)
+{
+  symgraphlink *l = xmalloc (sizeof (*l));
+  l->id = id;
+  l->next = next;
+  return l;
+}
+
+/*-----------------------------------------------------------------------.
+| Registers the second symbol of the precedence relation. Should only be |
+| used in add_precedence_relation.                                       |
+`-----------------------------------------------------------------------*/
+
+static bool
+register_precedence_second_symbol (symgraphlink **first, graphid sym)
+{
+  if (!*first || sym < (*first)->id)
+      *first = create_symgraphlink (sym, *first);
+  else
+    {
+      symgraphlink *slist = *first;
+
+      while (slist->next && slist->next->id <= sym)
+        slist = slist->next;
+
+      if (slist->id == sym)
+      /* Relation already present. */
+        return false;
+
+      slist->next = create_symgraphlink (sym, slist->next);
+    }
+  return true;
+}
+
+/*------------------------------------------------------------------.
+| Register a new relation between symbols as used. The first symbol |
+| has a greater precedence than the second one. |
+`------------------------------------------------------------------*/
+
+void
+register_precedence (graphid first, graphid snd)
+{
+  if (!prec_nodes)
+    init_prec_nodes ();
+  register_precedence_second_symbol (&(prec_nodes[first]->succ), snd);
+  register_precedence_second_symbol (&(prec_nodes[snd]->pred), first);
+}
+
+/*-----------------------------.
+| Free a simple symgraph list. |
+`-----------------------------*/
+
+static void
+free_symgraphlink (symgraphlink *s)
+{
+  if (s)
+    {
+      free_symgraphlink (s->next);
+      free (s);
+    }
+}
+
+
+/*--------------------------------------------------.
+| Print a warning for unused precedence relations. |
+`--------------------------------------------------*/
+
+void
+print_precedence_warnings (void)
+{
+  int i;
+  if (!prec_nodes)
+    init_prec_nodes ();
+  for (i = 0; i < nsyms; ++i)
+    {
+      symbol *s = symbols[i];
+      if (s
+          && s->prec != 0
+          && !prec_nodes[i]->pred
+          && !prec_nodes[i]->succ
+          && s->assoc == precedence_assoc)
+        complain (&s->location, Wother,
+                  _("useless precedence for %s"), s->tag);
+    }
+}
diff --git a/src/symtab.h b/src/symtab.h
index a01db24..c1edac5 100644
--- a/src/symtab.h
+++ b/src/symtab.h
@@ -224,6 +224,52 @@ extern symbol *startsymbol;
 extern location startsymbol_location;


+
+/*-------------------.
+| Symbol Relations.  |
+`-------------------*/
+
+/* The symbol relations are represented by a directed graph. */
+
+/* The id of a node */
+typedef int graphid;
+
+typedef struct symgraphlink symgraphlink;
+
+struct symgraphlink
+{
+  /** The second \c symbol or group of a precedence relation.
+   * See \c symgraph. */
+  graphid id;
+
+  symgraphlink *next;
+};
+
+/* Symbol precedence graph, to store the used precedence relations between
+ * symbols. */
+
+typedef struct symgraph symgraph;
+
+struct symgraph
+{
+  /** Identifier for the node: equal to the number of the symbol. */
+  graphid id;
+
+  /** The list of related symbols that have a smaller precedence. */
+  symgraphlink *succ;
+
+  /** The list of related symbols that have a greater precedence. */
+  symgraphlink *pred;
+};
+
+/** Register a new precedence relation as used. */
+
+void register_precedence (graphid first, graphid snd);
+
+/** Print a warning for each symbol whose precedence is useless. */
+
+void print_precedence_warnings (void);
+
 /*-----------------.
 | Semantic types.  |
 `-----------------*/
diff --git a/tests/conflicts.at b/tests/conflicts.at
index c7ed2fe..7ba4553 100644
--- a/tests/conflicts.at
+++ b/tests/conflicts.at
@@ -18,6 +18,48 @@
 AT_BANNER([[Conflicts.]])


+## ---------------------------- ##
+## Useless precedence warning.  ##
+## ---------------------------- ##
+
+AT_SETUP([Useless precedence warning])
+
+AT_DATA([[input.y]],
+[[%token A B
+%precedence Z
+%left X
+%precedence Y
+%left W
+%right V
+%nonassoc U
+%%
+a: b
+ | a U b
+ | f
+;
+b: c
+ | b V c
+;
+c: d
+ | c W d
+;
+d: A
+ | d X d
+ | d Y A
+;
+f: B
+ | f Z B
+;
+]])
+
+AT_BISON_CHECK([-fcaret -o input.c input.y], 0, [],
+[[input.y:2.13: warning: useless precedence for Z [-Wother]
+ %precedence Z
+             ^
+]])
+
+AT_CLEANUP
+
 ## ---------------- ##
 ## S/R in initial.  ##
 ## ---------------- ##
--
1.7.9.5