On Thu, Mar 28, 2013 at 03:55:28PM -0430, Juancarlo Añez wrote: > Hello Kota, > I'm reading your paper more carefully now (Packrat Parsers can Handle > Practical Grammars in Mostly Constant Space). > If I understand correctly, if a cut is seen at position P in the input, > then all memoization for positions prior to P can be discarded? > Thanks in advance! > Cheers, > --
Not exactly, I found that paper poorly writen, main idea is: Create counter c. In c maintain number of pending ordered choice branches in current derivation. When c==0 then you can obviously discard entries before current position. This idea is hidden in paper and mentioned only implicitly. This is interwined with transformation that allow us say that some branches are not possible. How they write paper it forces you to use certain representation to carry transformations. This is problem as your representation is almost certainly incompatible. It is better to use generic optimizations (predication gives most) and get better space utilization for free See my thesis for other improvements, chapter 2.6 most of ideas apply http://kam.mff.cuni.cz/~ondra/thesis.pdf Ondra > Juancarlo Añez _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
