Fast LR algorithms

haertel@euclid.uoregon.edu (Mike Haertel)
Tue, 15 Oct 91 09:24:19 PDT

          From comp.compilers

Related articles
Fast LR algorithms haertel@euclid.uoregon.edu (1991-10-15)
Re: Fast LR algorithms pardo@cs.washington.edu (1991-10-16)
Re: Fast LR algorithms -- yacc open code converter megatest!djones@decwrl.dec.com (1991-10-17)
| List of all articles for this month |

Newsgroups: comp.compilers
From: haertel@euclid.uoregon.edu (Mike Haertel)
Keywords: parse, performance
Organization: Compilers Central
Date: Tue, 15 Oct 91 09:24:19 PDT

I've lost count of the number of journal articles I've seen on finding
fast LR(1) algorithms. It seems to be one of the most popular subjects to
write about in the more theoretical reaches of CS.


But, realistically, aren't we losing sight of something here?


I think we should be far more concerned with the speed of the resulting
parsers, than with the speed with which we can produce parsers. Yet,
considering the amount of effort that appears to have been spent on the
two problems, it looks like producing parsers fast is considered far more
important than producing fast parsers!


Consider, for example, Ken Thompson's biggest complaint about his own C
compiler's performance: the yacc-generated parser is by far the slowest
part.
[Good point. I gather that an LL parser generated as open code, e.g. a
mechanically generated recursive descent parser, is a lot faster than
any of the LALR parsers. -John]
--


Post a followup to this message

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