Hello to the few in the millions, whats your take is a O(n) parser good enough? though there’s plenty of literature that involves efficiency of low-level (read character based) pattern matching algorithms, I havent found much O(x), where x is anythin from “n log m” to “n^r”, type of literature on the efficiency of such parsers…any pointers?
thanks,
Johnny.
Are you saying you haven’t found any asymptotic analysis of text-matching algorithms? If so, check Cormen et al. for some basic analysis and references to other sources.
I don’t think I understand the question. Clearly a O(n^r) parser is going to take longer than an O(n) for large enough n, so are you wondering about the constant factors involved? Or about what sorts of constructs a parser of some given complexity can handle?
It would depend on the grammar of the text to be parsed, wouldn’t it?
I’ll just say that I don’t think you’re going to get any better than O(n), since it would take that much time simply to read the input file in. (Assuming that n is the length of text to be parsed.)