Re: O(n) Good Enough

James Jones <jejones@microware.com>
17 Jan 1999 20:46:02 -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: James Jones <jejones@microware.com>
Newsgroups: comp.compilers
Date: 17 Jan 1999 20:46:02 -0500
Organization: Microware Systems Corporation
References: 99-01-052
Keywords: parse

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.


James


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?

Post a followup to this message

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