On Mar 20, 2009, at 3:19 PM, Tim Goodwin wrote: > So my question still stands: can anybody show me a PEG that - for a > backtracking recursive descent parser - would be more complex than > O(n) to parse? Despite all the discussion of exponential complexity in > this post, that's not necessary: a mere O(n^2) would be great!
Try: S <- A* A <- a S b / a S c / a on a string consisting of all a's. A little contrived admittedly. :) Bryan _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
