Re: Controlling the effects of precedence declarations

[Hans Aberg]

At 02:50 +0200 2003/05/13, Frank Heckenbach wrote:
>> 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.

Language should be structured so that this problem does not occur.
Typically, precedences occur within operator expressions and some other
localized situations.

>> 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).

This is an example; one should use %prec here.

You are slipping into the general discussion: "How can a language be
designed so that only sensible programs can be written". The Bison language
can only be designed so that it helps to catch some mistakes, but not all
of the language design.

>In my suggestion, I would have declared term, factor etc., and I'd
>see the conflict explicitly.

This is workable if you only have a few precedence levels, but becomes
cumbersome if you have many. In addition, using precedence, one gets fewer
grammar variables, so that the parser will make less computing.

> 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.

You might try to use %prec everywhere, then such errors would be caught.
The names declared in the precedence declaration are not tokens, but only
use in the rules via %prec statements.

>> 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

It should probably be like this: Each grammar variable B_i in
    A -> B_1 ... B_k
for which one wants to indicate precedence restrictions is replaced
by a unique new B_i' (different arguments get different new variables).
Then for each B_i', one lists the allowed expansions
    B_i' -> C_1 ... C_l
where one knows that B_i -> C_1 ... C_l is in the original grammar. This
then gives a way to translate a grammar with precedence declarations into
one without.

Take an example:
    left +
    E -> E + E
    E -> I
The restriction is that the second RHS only admits E -> I. Then one gets
    E -> E + T
    T -> I
    E -> I
It then becomes similar to that of the traditional
    E -> E + T
    E -> T
    T -> I

>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.

It is not only style, as fewer grammar variables means lesser parser
computations. Precedences helps simplifying the grammar, which should make
it easier to maintain.

>> 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.

That is the underlying most general theory I described. If one has standard
precedence declarations, then it is possible to translate into the picture
I gave.

>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.

Then the set of precedence restrictions is empty in the case you do not
need it.

>> 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.)

I think the most philosophical restriction against featuritis in this group
is to find somebody willing to implement it. :-)

I wrote down the theoretical precedence description so that anybody getting
curious about a generalized precedence system might implement it into Bison.

  Hans Aberg