[PATCH] grammar: warn about unused precedence for symbols

[Valentin Tolmer]

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       |  122 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/symtab.h       |   47 ++++++++++++++++++++
 tests/conflicts.at |   42 ++++++++++++++++++
 6 files changed, 222 insertions(+)

diff --git a/NEWS b/NEWS
index a44e1be..70263e9 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
 
+*** Unused 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..e031558 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)
           {
+            add_precedence_relation (redrule->prec->number, i);
             log_resolution (redrule, i, reduce_resolution);
             flush_shift (s, i);
           }
         else if (symbols[i]->prec > redprec)
           {
+            add_precedence_relation (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..a7cba29 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,120 @@ symbols_pack (void)
               _("the start symbol %s is a token"),
               startsymbol->tag);
 }
+
+/*------------------------.
+| Initialize 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;
+    }
+}
+
+/*--------------------------------------------------------------------.
+| Registers the second symbol of the relation. Should only be used in |
+| add_precedence_relation.                                                     
  |
+`--------------------------------------------------------------------*/
+
+static bool
+add_relation_second_symbol (symgraphlink **first, graphid sym)
+{
+  if (!*first || sym < (*first)->id)
+    {
+      symgraphlink *newlist = xmalloc (sizeof (*newlist));
+      newlist->id = sym;
+      newlist->next = *first;
+      *first = newlist;
+    }
+  else
+    {
+      symgraphlink *slist = *first;
+
+      while (slist->next && slist->next->id <= sym)
+        slist = slist->next;
+
+      if (slist->id == sym)
+        return false;  /* Relation already present. */
+
+      symgraphlink *newlist =  xmalloc (sizeof (*newlist));
+      newlist->id = sym;
+      newlist->next = slist->next;
+      slist->next = newlist;
+    }
+  return true;
+}
+
+/*------------------------------------------------------------------.
+| Register a new relation between symbols as used. The first symbol |
+| has a greater precedence than the second one.                     |
+`------------------------------------------------------------------*/
+
+void
+add_precedence_relation (graphid first, graphid snd)
+{
+  if (!prec_nodes)
+    init_prec_nodes ();
+  add_relation_second_symbol (&(prec_nodes[first]->succ), snd);
+  add_relation_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 ();
+  symgraphlink *unused = xmalloc (sizeof (*unused));
+  unused->next = 0;
+  symgraphlink *cur = unused;
+  for (i = 0; i < nsyms; ++i)
+    {
+      if (symbols[i] && symbols[i]->prec != 0
+          && !(prec_nodes[i]->pred || prec_nodes[i]->succ))
+        {
+          symgraphlink *new = xmalloc (sizeof (*new));
+          new->id = i;
+          new->next = 0;
+          cur->next = new;
+          cur = new;
+        }
+    }
+  /* Skipping the first element is intended. */
+  for (cur = unused; cur = cur->next; )
+    {
+      symbol *s = symbols[cur->id];
+      if (s->assoc == precedence_assoc)
+        complain (&s->location, Wother,
+                  _("useless precedence for %s"), s->tag);
+    }
+  free_symgraphlink (unused);
+}
diff --git a/src/symtab.h b/src/symtab.h
index a01db24..044ecae 100644
--- a/src/symtab.h
+++ b/src/symtab.h
@@ -224,6 +224,53 @@ extern symbol *startsymbol;
 extern location startsymbol_location;
 
 
+
+/*-------------------.
+| Symbol Relations.  |
+`-------------------*/
+
+/* The symbols 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 relation. See \c symgraph. */
+  graphid id;
+
+  symgraphlink *next;
+};
+
+/* Symbols graph, to store the used relations between symbols */
+
+typedef struct symgraph symgraph;
+
+struct symgraph
+{
+  /** Identifier for the node: either equals to the number of the symbol
+   * or to a negative id number for a group of symbols.
+   * As for the rules, the number here is the opposite of the index in the
+   * group table, shifted by one. */
+  graphid id;
+
+  /** The list of symbols it is in relation with. */
+  symgraphlink *succ;
+
+  /** The list of symbols that are in relation with it. */
+  symgraphlink *pred;
+};
+
+/** Register a new relation as used. */
+
+void add_precedence_relation (graphid first, graphid snd);
+
+/** Print a warning for each symbol whose precedence is unused. */
+
+void print_precedence_warnings (void);
+
 /*-----------------.
 | Semantic types.  |
 `-----------------*/
diff --git a/tests/conflicts.at b/tests/conflicts.at
index c7ed2fe..88eb284 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