From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.5-pre1 (2020-06-20) on ip-172-31-74-118.ec2.internal X-Spam-Level: X-Spam-Status: No, score=-0.9 required=3.0 tests=BAYES_00,TO_NO_BRKTS_PCNT autolearn=no autolearn_force=no version=3.4.5-pre1 Date: 20 Nov 92 21:02:32 GMT From: noc.near.net!inmet!spock!stt@uunet.uu.net (Tucker Taft) Subject: Re: GNU-NYU Ada project Message-ID: <1992Nov20.210232.27477@inmet.camb.inmet.com> List-Id: In article <1992Nov19.184504.22639@coe.montana.edu> dpoole@hydrogen.oscs.montana.edu (David Poole) writes: > One of the professors at my university posted this to our local newsgroup. >I haven't seen anything here on this, so I thought I'd post it and see if >anyone can confirm/deny this report. > > A few things in this report seem a mite confusing. It mentions the parser >running around 1,000,000 lines a minute on a 16 MHz 386. Is this realistic? Yes. That implies 60 micro-seconds per line, or roughly 500 386 instructions, which is sufficient to parse the average line of source code in a well-written parser. And this one is. >Also, the parser uses recursive descent. Why? I thought LALR was the best >possible. LALR is easier to construct, given a tool like YACC. However, for raw speed, a well-written recursive descent parser can be about 50% faster than YACC (or even BISON). In general, anything table-driven has to pay some overhead relative to hand-coding. The procedure call overhead of recursive descent is not very great if the compiler passes parameters in registers. Of course when the parser gets this fast, it becomes a miniscule part of the time spent in the compiler, so speeding it up by 50% might not be worth the extra hassle. However, one additional nice thing about recursive descent is that it is easy to pass data up and down during the parse, and to keep local variables. To do this in YACC or BISON requires explicit stacks and/or parse-trees, which can be more work and more error-prone. >-----------------------------------cut here-------------------------------- > > GNAT Project > GNU-NYU Ada Translator. > > GNAT Report 0001-921101 > > November 1, 1992 [etc...] S. Tucker Taft stt@inmet.com Intermetrics, Inc. Cambridge, MA 02138