>From c76aa0001ecce041fad69f6c72879a13af05b831 Mon Sep 17 00:00:00 2001 From: Valentin Tolmer Date: Mon, 28 Jan 2013 10:57:18 +0100 Subject: [PATCH] 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/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