|O(n) Good Enough email@example.com (Quinn Tyler Jackson) (1999-01-15)|
|Re: O(n) Good Enough J.Scheerder@cwi.nl (1999-01-17)|
|Re: O(n) Good Enough firstname.lastname@example.org (James Jones) (1999-01-17)|
|Re: O(n) Good Enough email@example.com (Glen Austin) (1999-01-17)|
|Re: O(n) Good Enough firstname.lastname@example.org (Dennis Ritchie) (1999-01-19)|
|Re: O(n) Good Enough email@example.com (David R Tribble) (1999-01-22)|
|Re: O(n) Good Enough firstname.lastname@example.org (Dennis Ritchie) (1999-01-23)|
|From:||J.Scheerder@cwi.nl (J. Scheerder)|
|Date:||17 Jan 1999 20:45:31 -0500|
"Quinn Tyler Jackson" <email@example.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
You'll find more, and better, information than I'll be able to provide
Return to the
Search the comp.compilers archives again.