|User friendly compiler-compiler tools firstname.lastname@example.org (1995-09-18)|
|Re: User friendly compiler-compiler tools email@example.com (1995-10-02)|
|User friendly compiler-compiler tools firstname.lastname@example.org.OZ.AU (1995-10-14)|
|Re: User friendly compiler-compiler tools [comp.compilers #7671] email@example.com (1995-10-23)|
|Re: User friendly compiler-compiler tools firstname.lastname@example.org.OZ.AU (Fergus Henderson) (1995-11-09)|
|From:||Fergus Henderson <email@example.com.OZ.AU>|
|Date:||Thu, 9 Nov 1995 18:16:00 GMT|
firstname.lastname@example.org (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
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
Fergus Henderson WWW: http://www.cs.mu.oz.au/~fjh
email@example.com PGP: finger firstname.lastname@example.org
Return to the
Search the comp.compilers archives again.