Re: Eliminating conflicts of parenthesized subexpressions

[Hans Aberg]

At 18:12 +0200 2004/09/09, Vincent Zweije wrote:
>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.

I am inclined at following this line, to sort it out by action typing. This
makes the grammar simple. But it is not clear to me why it necessarily
should be viewed as semantic. One can think of grammars beyond the capacity
of Bison. The choice is merely dictated by practical concerns.

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

Actually, this is not a big problem, because I have currently a grammar
that admits the distinction between object_formula and metaformula by
limiting the use of "(" ... ")" when applying it to metaformulas. It is
when I generalize this grammar to become a more streamlined operator
grammar that I bump into this problem.

>You are actually overloading the "," and "|-" operators: you are
>using them for combining object formulas into object formulas,
>or metaformulas into metaformulas.

Yes, this is actually the case, and an interesting observation.

>Turning an object formula
>into a metaformula would require something akin to an implicit
>cast operator (the metaformula->object_formula rule).

Actually, I have a computing machinery that can interpret formulas as
metaformulas. Or, rather, originally, it could only work with
object_formula's, but it turned out important to let it handle metaformulas
as well.

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

I looked a bit in Aho, Sethi & Ullman, "Compilers..." (the Dragon book), p.
351 ff., and they do it in the actions.

>It is probably the overloading that is the real culprit here.

Right. Alternatively, I can take away the
    metaformula -> "(" metaformula ")"
rule. But that would cripple the language, I think. (There are in reality
two sets of logical operators built on top of each other: The operators
",", "|-" are in effect the metalogical operators "and", "=>" interpreted
in terms of provability.)

One can note, incidentally, that there is no similar problem with the use
of terms as a subpart of object_formula's as they end in the arguments of
predicates, thus the predicate names makes this. So if I require some such
explicit syntactical type conversion, the problem would disappear. But that
would not produce human readable formulas.

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

The advantage with doing it in the grammar is not having to implement a
type system. I think though that the only alternative is to sort it out in
the actions, because say (A |- B) => C is semantically incorrect, just as
(a == b) + c is in the arithmetical example. And I can't hand over
semantically incorrect closures to the computing core.

  Hans Aberg