On Oct 20, 2010, at 12:05 AM, Mathias wrote: > Concerning this issue with packrat parsing (rather than backtracking): > parboiled does not do packrat parsing but rather concentrates on providing a > really efficient backtracking engine, since I have yet to see a real-word > example where packratting does actually increase parsing performance over an > efficient parser without the overhead of creating and managing the rule match > cache. > If anyone has such an example I would be very interested...
Hi Mathias, I have a number of large examples that won't terminate in my lifetime (though I'm getting old!) w/o the memoize=true option in ANTLR in grammars that backtrack a lot. Turning on/off means finishing quickly or not terminating. Efficient parsers are a constant in O(...) whereas the memoize reduces an exponential to a linear problem, with a bigger constant. In my experience, memoization can be a necessity depending on the grammar. I think it was a PEG C grammar I converted to ANTLR a few days ago that needed memoizing. 'course one can always work on the grammar to reduce backtracking needs. ANTLR's approach to PEG parsing is to optimize away the speculation as much as possible to attenuate this issue with actions. Ter _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
