[PATCH 4/7] syntax: introducing %precr to add specific precedence relations

[Valentin Tolmer]

It is now possible to add specific precedence relations between two symbols,
or a symbol and a group, with the %precr keyword:

%gprec arith {
  %left '+' '-'
  %left '*' '/'
}
%gprec boolean {
  %left OR
  %left AND
}
%right '^'

%precr '^' > arith
%precr OR AND > '^'

Here, the symbol ^ is of higher priority than the the ones in arith, but of
lower priority than both OR and AND. OR and '+', for example, cannot be
compared.

* src/parse-gram.y, src/scan-gram.l: Lexer and grammar implementation of
%precr.
* src/symtab.c, src/symtab.h: implementation of the addition of single link
precedence relationships.
---
 src/parse-gram.y |   51 ++++++++++++++++++++++++++++++++++++++++++-
 src/scan-gram.l  |    2 ++
 src/symtab.c     |   64 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/symtab.h     |   15 +++++++++++++
 4 files changed, 131 insertions(+), 1 deletion(-)

diff --git a/src/parse-gram.y b/src/parse-gram.y
index 89af756..0bd0d3a 100644
--- a/src/parse-gram.y
+++ b/src/parse-gram.y
@@ -131,6 +131,7 @@
 %token PERCENT_PREC          "%prec"
 %token PERCENT_DPREC         "%dprec"
 %token PERCENT_GPREC         "%gprec"
+%token PERCENT_PRECR         "%precr"
 %token PERCENT_MERGE         "%merge"
 
 /*----------------------.
@@ -176,6 +177,7 @@
 %token PIPE            "|"
 %token PROLOGUE        "%{...%}"
 %token SEMICOLON       ";"
+%token GT              ">"
 %token TAG             "<tag>"
 %token TAG_ANY         "<*>"
 %token TAG_NONE        "<>"
@@ -217,7 +219,13 @@
 %union {named_ref *named_ref;}
 %type <named_ref> named_ref.opt
 
-%type <uniqstr> prec_group_name.opt
+%type <uniqstr> prec_group_name.opt string_or_id
+
+%union {prec_rel_comparator prec_rel_comparator;}
+%type <prec_rel_comparator> prec_rel_comparator
+
+%type <list> precedence_relation_symbols precedence_symbol
+
 /*---------.
 | %param.  |
 `---------*/
@@ -370,6 +378,7 @@ params:
 grammar_declaration:
   precedence_declaration
 | precedence_group_declaration
+| precedence_relation_declaration
 | symbol_declaration
 | "%start" symbol
     {
@@ -513,6 +522,46 @@ tag.opt:
 | TAG    { current_type = $1; tag_seen = true; }
 ;
 
+/* Declaration of a precedence relation between two (lists of) tokens */
+precedence_relation_declaration:
+  "%precr" precedence_relation_symbols
+    { prec_braces = default_braces_state; }
+    prec_rel_comparator
+    precedence_relation_symbols
+    { declare_precedence_relation ($2, $5, $4, @4); }
+;
+
+precedence_relation_symbols:
+  precedence_symbol { $$ = $1; }
+| precedence_relation_symbols precedence_symbol
+    { $$ = symbol_list_append ($1, $2); }
+;
+
+precedence_symbol:
+  string_or_id
+  {
+    if (is_prec_group ($1))
+      $$ = expand_symbol_group (symgroup_from_uniqstr($1, &@1), @1);
+    else
+      $$ = symbol_list_sym_new (symbol_from_uniqstr ($1, @1), @1);
+  }
+| CHAR
+  {
+    $$ = symbol_list_sym_new (symbol_from_uniqstr (uniqstr_new (char_name 
($1)), @1), @1);
+  }
+;
+
+string_or_id:
+  STRING { $$ = uniqstr_new (quotearg_style (c_quoting_style, $1)); }
+| ID { $$ = $1; }
+;
+
+prec_rel_comparator:
+  ">"     { $$ = prec_superior; }
+| "="     { $$ = prec_equal; }
+| ">" ">" { $$ = prec_superior_strict; }
+;
+
 /* Just like symbols.1 but accept INT for the sake of POSIX.  */
 symbols.prec:
   symbol.prec
diff --git a/src/scan-gram.l b/src/scan-gram.l
index f5157c9..737646c 100644
--- a/src/scan-gram.l
+++ b/src/scan-gram.l
@@ -243,6 +243,7 @@ eqopt    ([[:space:]]*=)?
   "%parse-param"                    RETURN_PERCENT_PARAM(parse);
   "%prec"                           return PERCENT_PREC;
   "%precedence"                     return PERCENT_PRECEDENCE;
+  "%precr"                          return PERCENT_PRECR;
   "%printer"                        return PERCENT_PRINTER;
   "%pure-parser"                    RETURN_PERCENT_FLAG("api.pure");
   "%require"                        return PERCENT_REQUIRE;
@@ -278,6 +279,7 @@ eqopt    ([[:space:]]*=)?
   "|"                     return PIPE;
   ";"                     return SEMICOLON;
   "}"                     return RBRACE;
+  ">"                     return GT;
 
   {id} {
     val->uniqstr = uniqstr_new (yytext);
diff --git a/src/symtab.c b/src/symtab.c
index aa7c5e8..dcc3513 100644
--- a/src/symtab.c
+++ b/src/symtab.c
@@ -240,6 +240,55 @@ add_prec_equal_link (prec_node *s1, prec_node *s2, bool 
transitive,
 }
 
 
+/* The function to use to register \a c type relations.  */
+typedef void (*add_link_t) (prec_node *, prec_node *, bool, location);
+static add_link_t
+add_link_function (prec_rel_comparator c)
+{
+  switch (c)
+    {
+    case prec_superior_strict:
+    case prec_superior:
+      return &add_prec_link;
+    case prec_equal:
+      return &add_prec_equal_link;
+    }
+  abort ();
+}
+
+
+/*---------------------------------------------------------------------.
+| Handle the precedence declaration between the elements of S1 and S2. |
+`---------------------------------------------------------------------*/
+
+void
+declare_precedence_relation (symbol_list *s1, symbol_list *s2,
+                             prec_rel_comparator c, location loc)
+{
+  void (*functionPtr) (prec_node *, prec_node *, bool, location)
+    = add_link_function (c);
+  bool transitive = c != prec_superior_strict;
+  for (symbol_list *l1 = s1; l1; l1 = l1->next)
+    for (symbol_list *l2 = s2; l2; l2 = l2->next)
+      (*functionPtr)(l1->content.sym->content->prec_node,
+                     l2->content.sym->content->prec_node, transitive, loc);
+  symbol_list_free (s1);
+  symbol_list_free (s2);
+}
+
+/*----------------------------------------------.
+| Get the list of symbols contained in a group. |
+`----------------------------------------------*/
+
+symbol_list *
+expand_symbol_group (symgroup *group, location loc)
+{
+  symbol_list *l = NULL;
+  for (sym_content *s = group->symbol_list; s; s = s->group_next)
+    l = symbol_list_append (l, symbol_list_sym_new (s->symbol, loc));
+  return l;
+}
+
 /*------------------------------------------------------------------------.
 | Add a symbol to the current declaration group, and declare the implicit |
 | precedence links. SAME_LINE is true if the symbol was declared in the   |
@@ -358,6 +407,7 @@ symbol_new (uniqstr tag, location loc)
 
   res->tag = tag;
   res->location = loc;
+
   res->alias = NULL;
   res->content = sym_content_new (res);
   res->is_alias = false;
@@ -1503,6 +1553,20 @@ symgroup_new (const uniqstr tag, location loc)
   return group;
 }
 
+/*----------------------------------------.
+| Check if there is a group by that name. |
+`----------------------------------------*/
+
+bool
+is_prec_group (const uniqstr key)
+{
+  symgroup probe;
+  symgroup *entry;
+  probe.tag = key;
+  entry = hash_lookup (group_table, &probe);
+  return entry != NULL;
+}
+
 /*--------------------------------------------------------------------------.
 | Get the symbol precedence group by that name. If not present, a new group |
 | is created and inserted in the table, with the location information       |
diff --git a/src/symtab.h b/src/symtab.h
index 5c042b0..12904d9 100644
--- a/src/symtab.h
+++ b/src/symtab.h
@@ -330,6 +330,11 @@ void set_current_group (const uniqstr name, location *loc);
 symgroup *
 symgroup_from_uniqstr (const uniqstr key, location *loc);
 
+/** Check if there is a symbol precedence group by that name. */
+bool
+is_prec_group (const uniqstr key);
+
+
 /*----------------------------------.
 | Graph of precedence relationships |
 `----------------------------------*/
@@ -361,6 +366,16 @@ enum prec_rel_comparator
     prec_superior,
     prec_superior_strict,
 };
+
+/** Declare a precedence relationship between the symbols of the two lists,
+ *  as defined by the operator. */
+void
+declare_precedence_relation (symbol_list *l1, symbol_list *l2,
+                             prec_rel_comparator c, location loc);
+/** Return the list of symbols contained in the group. */
+symbol_list *
+expand_symbol_group (symgroup * group, location loc);
+
 /** Check if s1 and s2 have the same precedence level. */
 bool is_prec_equal (prec_node * s1, prec_node * s2);
 
-- 
1.7.9.5