Re: O(n) Good Enough

J.Scheerder@cwi.nl (J. Scheerder)
17 Jan 1999 20:45:31 -0500

          From comp.compilers
Related articles
O(n) Good Enough qjackson@wave.home.com (Quinn Tyler Jackson) (1999-01-15)
Re: O(n) Good Enough J.Scheerder@cwi.nl (1999-01-17)
Re: O(n) Good Enough jejones@microware.com (James Jones) (1999-01-17)
Re: O(n) Good Enough gaustin@dallas.beasys.com (Glen Austin) (1999-01-17)
Re: O(n) Good Enough dmr@bell-labs.com (Dennis Ritchie) (1999-01-19)
Re: O(n) Good Enough dtribble@technologist.com (David R Tribble) (1999-01-22)
Re: O(n) Good Enough dmr@bell-labs.com (Dennis Ritchie) (1999-01-23)
| List of all articles for this month |
From: J.Scheerder@cwi.nl (J. Scheerder)
Newsgroups: comp.compilers
Date: 17 Jan 1999 20:45:31 -0500
Organization: NAKA
References: 99-01-052
Keywords: parse

"Quinn Tyler Jackson" <qjackson@wave.home.com>:
> Two simple questions:
> Is a O(n) parser good enough?


It depends. Good enough for what?


> Although there is plenty of literature discussing the efficiency
> of low level (read character based) pattern matching algorithms, I
> haven't found much O(x) [where x is anything from n log m to n^r] type
> literature on the efficiency of parsers. Any pointers to literature
> in this area?


Plenty. You might want to check
<http://www.cs.vu.nl/%7Edick/PTAPG.html>; you'll find a thorough
treatise on the subject of parsing, and it includes a very, very
extensive annotated bibliography (which is also available separately
in plaintext format (I recommend getting the full book, though) from
<ftp://ftp.cs.vu.nl/pub/dick/PTAPG/AnnotatedBibliography.txt>).




You'll find more, and better, information than I'll be able to provide
here.




-- J$

Post a followup to this message

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