Hi, I've only recently started working on PEG parsers (you can see the one I'm working on here: http://github.com/tolmasky/language/ ). I was wondering if there were any recommendations for good papers or other material relating to when it is safe to dump "memos" in a memoizing PEG parser. For example, in the following grammar:
start = A A A = something / something_else After successfully parsing through the first "A", it is safe to dump some entries from the memoization table since you know for sure that you will not be backtracking to them ever again. Unfortunately as far as I can tell this optimization can only be used when none of your ancestor rules are ordered choice rules (or I suppose any rule that may backtrack), so it can only be applied occasionally. I've read up a little and have a preliminary implementation for cut support ( http://www.ialab.cs.tsukuba.ac.jp/~mizusima/publications/paste513-mizushima.pdf ) but I am looking to see if there are any simpler heuristics like the one I showed above that don't require me to change the grammar. Any help is greatly appreciated. Thanks, Francisco _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
