|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:||James Jones <email@example.com>|
|Date:||17 Jan 1999 20:46:02 -0500|
|Organization:||Microware Systems Corporation|
I can't speak for the second question, but something less than O(n)
wouldn't be looking at all the input, and it's hard to imagine being
able to always do that in a parser.
Quinn Tyler Jackson wrote:
> Two simple questions:
> Is a O(n) parser good enough?
> 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?
Return to the
Search the comp.compilers archives again.