Precedence declarations applied to rules

[Hans Aberg]

I have looked a bit onto this precedence story. It convinced me that the
variation where one expresses precedence as a restriction one which rules
that can be expanded in the arguments is the correct one. The reason for
choosing such a system is that it is independent of the parsing algorithm.
Instead, the parsing algorithm should complain, if it cannot handle the
declarations, jazzed as in the case of grammars.

This system is then a somewhat more general formulation than what is given in
    http://www.cs.uu.nl/people/visser/ftp/BSVV02.pdf
It then turns out that it is not entirely easy to reformulate to the
formulation in the book by Dick Grune, "Modern Compiler Design" that I
quoted before, which is probably more like what Bison is using internally.
One probably into the LR algorithms to see exactly how these definitions
overlap.

But if one should implement a precedence system for rules into Bison,
instead of the old one using tokens, then it might look like this:
  %precedence {
  ...
  %left E: E_1 ... E_k
  ...
  }
This should mean that the precedence rules only apply to what is quoted
within each %precedence group. In terms of parse trees, it means that a
rule with higher precedence does not admit rules with lower precedence to
be expanded in its arguments. The declaration %left means that if it ends
with an argument, another rule cannot be expanded there. Then %right is the
same except applied to a rule beginning with an argument, and %non-assoc
combines the prohibitions of %left and %right.

Let's take an example, a modification of the Bison manual "Infix Notation
Calculator" with a dangling "else" thrown in. One can then notice that with
the new precedence declaration, all precedence declarations become neatly
localized, and further, the %prec declaration is unnecessary.

/* BISON Declarations */
%token NUM IF THEN ELSE
%nonassoc THEN
%nonassoc ELSE
%left '-' '+'
%left '*' '/'
%left NEG     /* negation--unary minus */
%right '^'    /* exponentiation        */

/* Grammar follows */
%%
...
exp:      NUM
        | IF exp THEN exp
        | IF exp THEN exp ELSE exp
        | exp '+' exp
        | exp '-' exp
        | exp '*' exp
        | exp '/' exp
        | '-' exp  %prec NEG
        | exp '^' exp
        | '(' exp ')'
;
%%

It will now look like:

/* BISON Declarations */
%token NUM

%precedence {
%nonassoc exp: IF exp THEN exp;
%nonassoc exp: IF exp THEN exp ELSE exp;
%left exp: exp '+' exp | exp '-' exp;
%left exp: exp '*' exp | exp '/' exp;
%left exp: '-' exp;     /* negation--unary minus */
%right exp: exp '^' exp;    /* exponentiation        */
}

/* Grammar follows */
%%
...
exp:      NUM
        | IF exp THEN exp
        | IF exp THEN exp ELSE exp
        | exp '+' exp
        | exp '-' exp
        | exp '*' exp
        | exp '/' exp
        | '-' exp
        | exp '^' exp
        | '(' exp ')'
;
%%

  Hans Aberg