Re: Eliminating conflicts of parenthesized subexpressions

[Hans Aberg]

At 00:29 +0200 2004/09/16, Laurence Finston wrote:
>> Here is a problem I have on how to resolve a shift/reduce conflict in a
>> Bison grammar [...]
>
>There's a technique Knuth uses in the grammar for Metafont, and which
>I've borrowed for GNU 3DLDF. ...
...
>I'm also pretty certain that using this technique makes it unnecessary to
>explicitly declare the precedence and associativity of operators using Bison's
>facilities.  That is, `%token' declarations for operators need not be ordered
>and `%right', `%left', and `%nonassoc' need not be used.
>However, I do use them, and I haven't tested what happens if I change them all
>to `%token' and mix them up.

The paper I wrote (called "Constrained Grammars") handles not only the type
of precedence systems we discovered so far, but admits one to prohibit an
arbitrary choice of rule expansions of the grammar rule RHS variables. Then
one can either implement it directly into a LR(k) parser, or rewrite it to
a new CFG. The results differs in some cases from token-based precedence:
for example, the dangle "else" case. But one then just writes a different
specification. The advantage of this method is that it is grammar specific.
Token-based precedence is parsing-algorithm specific, so it is not clear
that it does not depend on the parsing algorithm chosen.

I used it to resolving my problem, and I posted a hands-on version in this
thread last week. It turns out to be easy to use by hand. It is similar in
idea to what you are describing, but more specific and systematic.

  Hans Aberg