Re: SUMMARY: BNF definition (EBNF acceptance)

"Terence Parr" <parrt@s1.arc.umn.edu> 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
more interesting:


    1) Question Authority, and use empricism as one mode of answering
          those questions.


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

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