Re: GNU-NYU Ada project

[noc.near.net!inmet!spock!stt@uunet.uu.net (Tucker Taft)]

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