mckeeman@wivax.UUCP (05/16/84)
I had an interesting experience in comparing recursive
descent and LL(1) recently. The language in question was
simpler than Pascal, and the performance criterion was
compile speed. It was done both ways, via a recursive
program in PL/I and hand-built LL(1) tables. (I was an
observor, not a contributor)
Both turned out to be about the same size, and both turned
out to be the same speed (within 1%!). The parsing took
about 8% of the total run time of the compiler.
The LL(1) technique was quite a bit harder to get going,
primarily because the programmer had to hand-build the
tables and wasn't able to get around hard problems by
"cheating" (making parsing decision on other than a
strictly syntactic basis, as one often does in recursive
descent).
On the other hand the semantics and syntax were cleanly
separated, as must be the case in table-driven schemes.
Error recovery had to be built into the tables too, which
is just another form of "cheating".
The LL(1) version won, primarily because the implementing
programmer liked it, but also because no casual hacker was
going to come along later and change his compiler without a
lot of study. It was a peculiar way to insure stability in
the product. This sounds manipulative, but my experience
with commercially produced recursive descent compilers is
that they increase in size over the years until they reach
critical mass and cease to function. Examination of the
corpse often shows the signature of many maintainers in the
right margin, each contributing a straw to the load.
/s/ Bill McKeeman.Wang-Inst at CSNet-Relay
...decvax!wivax!mckeeman
Wang Institute of Graduate Studies, Tyngsboro, MA 01879