Re: User friendly compiler-compiler tools

Fergus Henderson <>
Thu, 9 Nov 1995 18:16:00 GMT

          From comp.compilers

Related articles
User friendly compiler-compiler tools (1995-09-18)
Re: User friendly compiler-compiler tools (1995-10-02)
User friendly compiler-compiler tools (1995-10-14)
Re: User friendly compiler-compiler tools [comp.compilers #7671] (1995-10-23)
Re: User friendly compiler-compiler tools (Fergus Henderson) (1995-11-09)
| List of all articles for this month |

Newsgroups: comp.compilers
From: Fergus Henderson <>
Keywords: parse, theory
Organization: Compilers Central
References: 95-10-083 95-10-127
Date: Thu, 9 Nov 1995 18:16:00 GMT (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: PGP: finger fjh@

Post a followup to this message

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