|SUMMARY: BNF definition email@example.com (Ronny De Winter) (1994-05-18)|
|Re: SUMMARY: BNF definition (EBNF acceptance) firstname.lastname@example.org (Nathan K. Inada) (1994-05-18)|
|Re: SUMMARY: BNF definition (EBNF acceptance) email@example.com (Terence Parr) (1994-05-20)|
|Re: SUMMARY: BNF definition (EBNF acceptance) firstname.lastname@example.org (1994-05-22)|
|Re: SUMMARY: BNF definition (EBNF acceptance) max@Kolmogorov.gac.edu (1994-05-23)|
|From:||max@Kolmogorov.gac.edu (Max Hailperin)|
|Organization:||Gustavus Adolphus College, St. Peter, MN|
|Date:||Mon, 23 May 1994 14:16:35 GMT|
"Terence Parr" <email@example.com> writes:
... Anyhoo, EBNF makes a difference for recursive-descent as the following
illustrates: ... [a recursive production] generates [tail recursive proc]
which uses evil tail-recursion. The equivalent EBNF construct is easier
to read/debug and can be used to generate better code ...[i.e., while]
I'm not going to argue against the superiority of EBNF for ease of
reasoning or debugging. However, the party line about tail-recursion
being evil and while loops being better is something we compiler folks
should pay closer attention to.
This same party line crops up in the first couple days of my
undergraduate compilers course, since we use the red dragon book as
the primary text and Aho, Sethi, and Ullman go to great lengths in
their introductory example to turn the tail-recursive
recursive-descent procedures into looping ones.
However, I take this as an opportunity for some religous conversion.
I bring in to class the code that gcc (which is the C compiler we use)
generates from each of Aho, Sethi, and Ullman's versions, and some
empirical timing data on them. We look at this, and lo and behold,
gcc generates the same assembly code from each version, mod a few
uninteresting differences, and the timing is indistinguishable.
>From this I point out two lessons, the second of which is perhaps the
1) Question Authority, and use empricism as one mode of answering
2) Programmers write the kind of code that existing compilers do
a good job of compiling. Compiler writers, on the other hand,
invest effort in optimizing those kinds of code that existing
programs use. This results in a viscious cycle where arbitrary
historical artifacts can be self-perpetuated. In the case of
tail-recusion and C, this cycle was broken when someone from a
different "culture" (namely, RMS from Lisp Hackerdom) came in and
Return to the
Search the comp.compilers archives again.