grammar: warn about unused precedence for symbols

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/symtab.c, src/symtab.h (prec_nodes, init_prec_nodes)
(symgraphlink_new, register_precedence_second_symbol)
(print_precedence_warnings): New.
Record relationships in a graph and warn about useless ones.
* src/main.c (main): Print precedence warnings.
* tests/conflicts.at: New.

diff --git a/NEWS b/NEWS
index 5b6ea0c5daa3344c97319b5d24c0f36b0eb035cf..62f834b6390960c110c4d0d3804a075c834a97fa 100644 (file)
--- a/NEWS
+++ b/NEWS
@@ -198,6 +198,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 %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 885bd78f2154f07a08e1ffad36ca68aee02170f2..5744ac366daa234495b0e36007143c5d48ceecb6 100644 (file)
--- 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 d0b696f73d6ccd32db02885ddc0b26c41ef957dd..22703d1dd67eefb441294ba3d2cfa89d8fb9857b 100644 (file)
--- 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 9014acf2a99ab18a35f113f44ddd3e36532625a3..3028df9fb5f84708a820b7e2f1f81a3818b9cfff 100644 (file)
--- 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,100 @@ symbols_pack (void)
               _("the start symbol %s is a token"),
               startsymbol->tag);
 }
+
+/*---------------------------------.
+| Initialize relation graph nodes. |
+`---------------------------------*/
+
+static void
+init_prec_nodes (void)
+{
+  int i;
+  prec_nodes = xcalloc (nsyms, sizeof *prec_nodes);
+  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;
+    }
+}
+
+/*----------------.
+| Create a link.  |
+`----------------*/
+
+static symgraphlink *
+symgraphlink_new (graphid id, symgraphlink *next)
+{
+  symgraphlink *l = xmalloc (sizeof *l);
+  l->id = id;
+  l->next = next;
+  return l;
+}
+
+
+/*------------------------------------------------------------------.
+| Register the second symbol of the precedence relation, and return |
+| whether this relation is new.  Use only in register_precedence.   |
+`------------------------------------------------------------------*/
+
+static bool
+register_precedence_second_symbol (symgraphlink **first, graphid sym)
+{
+  if (!*first || sym < (*first)->id)
+    *first = symgraphlink_new (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 = symgraphlink_new (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);
+}
+
+
+/*--------------------------------------------------.
+| 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 1a50bb95b793c4a1073bdc93f8d60f0e6dfe68b3..fee549999e3f0e34974b8a742bc5e5d05eff01f5 100644 (file)
--- 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 8633d8d42cce3c5cdbdd0cafb6f05791dc9f91a2..d2fb298d788529138fe86ca365df38537f120dcc 100644 (file)
--- a/tests/conflicts.at
+++ b/tests/conflicts.at
@@ -78,7 +78,15 @@ int main (void)
 }
 ]])
 
-AT_FULL_COMPILE([input])
+AT_BISON_CHECK([-o input.c input.y], [], [],
+[[input.y:24.13: warning: useless precedence for R [-Wother]
+input.y:24.15: warning: useless precedence for S [-Wother]
+input.y:24.17: warning: useless precedence for T [-Wother]
+input.y:24.19: warning: useless precedence for U [-Wother]
+input.y:25.13: warning: useless precedence for V [-Wother]
+input.y:25.15: warning: useless precedence for W [-Wother]
+]])
+AT_COMPILE([input])
 
 AT_PARSER_CHECK([./input])
 
@@ -87,6 +95,49 @@ AT_BISON_OPTION_POPDEFS
 AT_CLEANUP
 
 
+## ---------------------------- ##
+## 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.  ##
 ## ---------------- ##