[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Controlling the effects of precedence declarations

From: Hans Aberg
Subject: Re: Controlling the effects of precedence declarations
Date: Mon, 12 May 2003 11:02:27 +0200

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. One reference is
<http://www.cs.uu.nl/people/visser/ftp/BSVV02.pdf>, and as I could could
parse that one, I made another version myself.

This means that if one changes parsing algorithms, the same language will
be parsed. One ref

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.

>Of course, I could run bison with `-v' and regularly check the
>verbose output to see which conflicts were actually resolved by
>precedence, but I wonder if there's a more automatic way. (I could
>use `%expect', but it only checks how many conflicts there are, and
>I can't control how to resolve them since they're always resolved as

I do not think there is any other way with Bison for now.

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

For example,
  %left "+"
  E: E "+" E
says that the RHS first E can be expanded with the production E -> E "+" E,
but not the second hand E.

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.

But nobody is working with it for now.

  Hans Aberg

reply via email to

[Prev in Thread] Current Thread [Next in Thread]