Re: User friendly compiler-compiler tools

anton@complang.tuwien.ac.at (Anton Ertl) writes:


>|> [re building expression grammars]
>|> > If you think it's necessary, add a few rules for implicit
>|> > parenthesizing; when in doubt, require explicit parenthesizing.
>|>
>|> Current operator-precedence parser generator tools such as yacc make
>|> this unnecessarily difficult, because they require a total ordering of
>|> operator precedences. Future such tools should allow a partial ordering.
>
>If I remember my math education, partial ordering implies
>transitivity.


Yes, that's right.


>I.e., by stating explicit precedences like
>
>'+' < '='
>'=' < '&&'
>
>you would get an implicit precedence
>
>'+' < '&&'
>
>which I did not learn in school and is not intuitive to everyone; in
>other word, this precedence is probably not a good idea.


I tend to disagree. If


x = y + 1 && p is equivalent to (x = (y + 1)) && p


then I think it makes sense for


q + 1 && r to be equivalent to (q + 1) && r


I would hope that your school taught more than just rote learning -
schools should also teach students to make inferences from the
knowledge they hold. If you learnt the precedences orderings `+' < `='
and `=' < `&&' in school, I would hope that you could infer `+' < `&&'
without too much difficulty.


Mind you, the above example is probably a somewhat pathological one -
if you are using a strongly-typed language, adding an integer to a
boolean would be a type error anyway.


>As soon as the cases interact, things become more complex: The
>classical hierarchical scheme with implied transitive precedences has
>to be avoided. There also is the problem of LALR (or LL) conflicts.


Transitivity dramatically simplifies both the specification and
implementation of grammars. With transitivity, the specification
of a grammer with N operators will requires roughly O(N) rules,
but without transitivity, it will require O(N^2). For a user
of the language, it is better to have a simple specification.


So I think that the major problem is the use of total rather than
partial orderings, not the use of transitivity. Use of a partial
ordering can eliminate most or even all of the undesireable
combinations, without significantly complicating the specification or
implementation.


--
Fergus Henderson WWW: http://www.cs.mu.oz.au/~fjh
fjh@cs.mu.oz.au PGP: finger fjh@128.250.37.3
--

Return to the comp.compilers page.
Search the comp.compilers archives again.