On Mar 20, 2009, at 7:19 AM, 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!
Hi. super busy but the idea is to make a backtracking decision that jumps to another backtracking decision. The fanout can create a very large nonlinear call graph. All nonlinear parsing requires that we parse the same input with the same rule multiple times; that's the trick to memoization's linearization: it cashes partial results preventing re-computation. Before v3 ANTLR (w/memoization), backtracking often caused nonlinearity landmines that would prevent parsing completely. Ter _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
