Re: Eliminating conflicts of parenthesized subexpressions

[Laurence Finston]

Hans Aberg wrote on  Thu, 9 Sep 2004 15:02:33 +0200:

> 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.  It may be useful to you.
For each kind of `expression', there's a hierarchy, e.g.,

point_primary
point_secondary
point_tertiary
point_expression

For each type of expression (the word "expression" is unfortunately 
ambiguous), there is a set of rules that looks like this:

point_primary -> point_variable
point_primary -> ( point_expression )
point_secondary -> point_primary
point_tertiary -> point_secondary
point_expression -> point_tertiary

There are often, but not always, additional rules, e.g.,

point tertiary --> point_tertiary plus_or_minus point_secondary
point secondary --> point_secondary times_or_over numeric_primary

If you were to use similar hierarchies, you could exert finer 
control over the behavior of your parser by specifying the level of a given
symbol in its particular hierarchy in your rules.  
However, your example

metaformula -> "(" metaformula ")" -> "(" formula ")
metaformula -> formula -> "(" formula ")

is not suitable for demonstrating this technique, because parenthesizing
`expressions' always brings them up (or down, if you will) to the `primary'
level.

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.

Laurence