Re: O(n) Good Enough (J. Scheerder)
17 Jan 1999 20:45:31 -0500

          From comp.compilers

Related articles
O(n) Good Enough (Quinn Tyler Jackson) (1999-01-15)
Re: O(n) Good Enough (1999-01-17)
Re: O(n) Good Enough (James Jones) (1999-01-17)
Re: O(n) Good Enough (Glen Austin) (1999-01-17)
Re: O(n) Good Enough (Dennis Ritchie) (1999-01-19)
Re: O(n) Good Enough (David R Tribble) (1999-01-22)
Re: O(n) Good Enough (Dennis Ritchie) (1999-01-23)
| List of all articles for this month |

From: (J. Scheerder)
Newsgroups: comp.compilers
Date: 17 Jan 1999 20:45:31 -0500
Organization: NAKA
References: 99-01-052
Keywords: parse

"Quinn Tyler Jackson" <>:
> 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
<>; 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

-- J$

Post a followup to this message

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