Re: Eliminating conflicts of parenthesized subexpressions

[Vincent Zweije]

On Thu, Sep 09, 2004 at 03:02:33PM +0200, Hans Aberg wrote:

||  Here is a problem I have on how to resolve a shift/reduce
||  conflict in a Bison grammar:
||  
||  In the syntax I try to capture, an expression containing
||  ",", "|-", and atomic_metaformula, is called a metaformula;
||  a subexpressions that does not contain any of those is
||  called an object_formula. An object_formula can be
||  considered a metaformula (by assuming an implicit
||  provability "|-"), but a metaformula can never be viewed as
||  an object_formula.
||  
||  The grammar below (simplified, as to make a small,
||  compilable example) is ambiguous, because of the two
||  expansions
||    metaformula -> "(" metaformula ")" -> "(" formula ")
||    metaformula -> formula -> "(" formula ")
||  Bison chooses second one, preferring a shift over a
||  reduction:
||    metaformula -> formula .       -- reduce
||    formula -> "(" formula . ")    -- shift
||  The shift also gives the wanted result, so one can just
||  %expect the conflict away. But then there remains an
||  ambiguous grammar, which is unsatisfactory.
||  
||  So how do people generally resolve this problem? -- One
||  solution is to remove the rule
||    metaformula: "(" metaformula ")"
||  replace
||    object_formula: "(" object_formula ")"
||  with
||    object_formula: "(" metaformula ")"
||  and the resolve it semantically in the actions by checking
||  the type of the cover constructed. Is that what one would
||  generally do, or is there a way to do it via the grammar?

A not-too-organized reaction:

Think how the end user sees object formulas and meta formulas:
probably one as subset of the other, because you're unifying
(overloading) the operators for both formula types.  If you
don't want to present that view, don't overload the operators,
and you can easily make a syntactic distinction.

I would only have metaformulas in the grammar.  In my view, the
set of object formulas is a subset of the set of metaformulas,
distinguised by the fact that some of the operators are not
used.  This is a semantic distinction.

Trying to turn the semantic distinction into a syntactic
distinction causes all kinds of problems.  For instance, it
might lead to parsing errors that are less than clear to explain
to a user, such as "syntax error: unexpected token "|-" when
you're parsing an object formula because a higher level context
requires that.  A user is not going to understand easily why at
that point the "|-" is unexpected, and you'd have to special
rules to allow "|-" in object_formulas to be able to give a
sensible error message, and then you definitely lose the ability
to distinguish syntactically again.

You are actually overloading the "," and "|-" operators: you are
using them for combining object formulas into object formulas,
or metaformulas into metaformulas.  Turning an object formula
into a metaformula would require something akin to an implicit
cast operator (the metaformula->object_formula rule).  So a
simple form of type checking might also do the trick here;
however, type checking is better not done in the grammar, I
think.

It is probably the overloading that is the real culprit here.
It only really becomes a problem when at higher levels in the
grammar you want to be able to distinguish the two kinds of
formula.  If you just want to parse formulas, do that and
distinguish them in the calling program.