Re: Controlling the effects of precedence declarations

[Frank Heckenbach]

> At 05:22 +0200 2003/05/12, Frank Heckenbach wrote:
> >I generally prefer to avoid precedence declarations in favour of
> >explicit rules (e.g., multi-level arithmetic nonterminals such as
> >expression, term, factor etc. instead of a single `expression' with
> >precedence for `+', `*' etc.).
> 
> There is no reason to avoid it: Precedence declaration can in fact be
> expressed as a statement about restrictions of the parse tree generated
> from the grammar alone.

And this can cause conflicting (or even ambiguous) grammars to be
accepted by bison without complaint. I don't like this. If some
future change in my grammar causes a conflict, I want to see this
conflict and decide myself what to do with it, rather than having it
resolved automatically.

> Quite on the contrary, precedences help compacting the grammar. So use them
> whenever prudent.
> 
> >But there are a few places where this explicit coding would be too
> >costly, e.g., a dangling else problem in a C-like language which,
> >AFAIK, would typically require duplication of all rules involved
> >with `if' and all structured statements that can appear within an
> >`if' statement. So I do use precedence in a few such places.
> >
> >Now I'd like to avoid unwanted effects of the precedence
> >declarations. There will probably be more changes to the grammar in
> >the future, and it might be that one of them will cause an actual
> >S/R conflict. With some bad luck, this might involve tokens with a
> >declared precedence and therefore be resolved automatically by
> >bison, possibly not in the way intended, and I wouldn't directly
> >notice this when running bison.
> 
> If you can give an exmple, that would help.

To use a canonical example, suppose you have a typical grammar for
arithmetic expressions using precedence (see attachment). Later you
decide to add the unary minus, so you add a rule:

  expr: '-' expr { $$ = -$2; };

Bison just accepts this and assigns the rule the same precedence as
the binary minus. This may or may not be what you intended. In some
languages, unary minus has in fact this precedence (like in
mathematics), in other languages (e.g., C) it has a higher
precedence. But bison does not even tell you that there is a
conflict which is resolved this way (unless you check the verbose
logs).

In my suggestion, I would have declared term, factor etc., and I'd
see the conflict explicitly. And even if I needed a precedence
elsewhere which might happen to involve the `-' token, this would
not affect the new rule because it has no explicit `%prec'
declaration.

Of course, we all have seen the unary minus issue dozens of times
and we're aware of this particular problem. But similar things might
happen in unexpected places in complex grammars. Or they might be
the effect of some mistake made when writing the grammar. I'd just
like to see such conflicts and not have them resolved automatically.

> >I know I can declare precedence of rules using `%prec', and for this
> >I can use tokens not otherwise used, so they at least won't have
> >unwanted effects. But for the other side, I have to declare the
> >precedence of the respective look-ahead token which is, of course, a
> >regular token.
> >
> >As an example, say I have a conflict between a rule `foo' and a
> >look-ahead token `bar' and another one between a rule `baz' and a
> >token `qux'. So I can declare the following precedences (depending
> >on how I want to resolve the conflicts, e.g.):
> 
> In the generalized precedence scheme that I devised is as follows: For
> every production
>     A -> B_1 ... B_k
> if B_i is a variable, one is admitted to impose restrtiction which othe
> productions of the form
>     B_i -> ...
> that can be used in a derviation (i.e., when constructing the parse tree).

So effectively, you split B_i into two symbols:

  B_i_1 -> ...  /* those rules that are allowed in the A rule */

  B_i -> B_i_1 | ...  /* other rules */

And then:

  A -> B_i_1 ... B_k

So your suggestion seems to help reduce the number of nonterminals.
You might prefer this. I prefer to have a grammar with as few
conflicts as possible (even if resolved by precedence). I think it's
a matter of style, and bison should not be restricted to one
particular style.

> So it is possible to implement the kind of things you are asking for, in
> fact in much greater generality: For each production and each of its RHS
> grammar variables, one can be allowed to declare a set of parse tree
> derivation restrictions.

That's not really what I asked for. You suggest to declare such a
set for every production (in whichever way), to impose additional
restrictions.

What I like is do to without such restrictions as far as possible
and only use precedence when I really think I need it, i.e. to let
bison do as *little* as possible in the area of precedence.

> But nobody is working with it for now.

I think the second of my suggestions (no default precedence for
rules) is probably rather easy to implement. If I do so, will it be
accepted, or are there "philosophical" reservations against it? (I'm
asking because my time is quite limited, and if it would be rejected
anyway, I don't need to waste my time with it.)

Frank

-- 
Frank Heckenbach, address@hidden
http://fjf.gnu.de/
GnuPG and PGP keys: http://fjf.gnu.de/plan (7977168E)

arith.y
Description: Binary data