Ondra, On the contrary, I found the paper quite well written. Al the background and the references are there, and the explanation of the new work is quite approachable.
As I see it, the paper has two parts: 1. How the availability of *cut* han reduce memory by a Packrat parser from O(n) to O(c). 2. How it could be possible to automatically insert *cut* statements in a grammar by using a PEG definition of FIRST. As two the first part, I read it again, and it clearly says that after a * cut*, all memos for positions less than the position of the cut can be discarded. It's a concept simple enough that I went ahead and implemented a simple and conservative version of it in Grako. The results were a reduction of 38% in memory use and of 4% in runtime. The 38% is significant and would require further analysis, because my tests were with model construction and code generation (COBOL to C#) turned on. Grako already calculates FIRST, but I have no incentive to implement automatic *cut* insertion because a) They found that hand-inserted *cuts*are superior, b) My grammars already have hand-inserted *cuts, *c) I'd rather remain in control of that part of the behavior produced by my grammars, d) My context is such I really don't care about memory use; I care about performance, and happen to know that better memory use will help me with that. I already merged the pruning of memos into the main branch of Grako. The changes are visible here: http://goo.gl/YDEkw This morning I dreamed of a simple optimization for the pruning, which I'll try now. Cheers, On Thu, Mar 28, 2013 at 6:04 PM, Ondřej Bílka <nel...@seznam.cz> wrote: > 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 > > > -- Juancarlo *Añez*
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
