I'm exploring certain aspects of PEG parsing, and have a reached a point where my imagination fails me! Perhaps someone on this list can help?
Packrat parsers, of course, run in linear time - O(n) where n is the size of the input. Presumably a recursive descent (but not packrat) parser for PEGs may be less efficient? It's trivial to think of a PEG that for a recursive descent parser will be O(n*r), where r is the number of rules / alternatives in the grammar. For example, S <- Ab / Ac; A <- a* will cause a recursive descent parser to back up the entire input. But I'm having trouble thinking of a more complex PEG. Can anybody help me? I'd really like to see a PEG which would be O(n^2), or worse, for a recursive descent parser. (Over in the world of CFGs, things are very different. I have a bootleg copy of Earley's paper - isn't it outrageous that the ACM wants money for a paper they published nearly 40 years ago? - which discusses "grammar UBDA": A -> x | AA; this is O(n^3) for Earley's algorithm. But I don't think the language x ^ n is expressible in a PEG. Incidentally, Wikipedia says that "parsers that use recursive descent with backup may require exponential time." Can this really be true?) Thanks in advance for any pointers! #t _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
